automate à piles imbriquées

En théorie des automates, un automate à piles emboîtées est un automate fini qui utilise comme mémoire auxiliaire une pile dont les éléments peuvent eux-mêmes être des piles. Mais contrairement à un automate à pile usuel, un automate à piles emboîtées peut se déplacer en avant et en arrière sur la « pile », qui est donc plutôt structurée en liste ; de plus, l'automate peut insérer une nouvelle pile, opérer sur elle, la détruire, et continuer à travailler sur l'ancienne pile. Ce mode opératoire peut être emboîté récursivement à une profondeur arbitraire ; toutefois, l'automate manipule toujours la pile la plus interne. Un automate à piles emboîtées est capable de reconnaître un langage indexé, et de fait les langages indexés sont exactement les langages reconnus par les automates à piles emboîtées non déterministes. Les automates à piles emboîtées diffèrent des automates à piles embarquées qui sont moins puissants puisque pour ces derniers, la mémoire auxiliaire, toujours organisée récursivement, n'est accessible que par le haut de pile. Les automates à pile embarquée reconnaissent exactement les langages engendrés par les grammaires d'arbres adjoints.