Automate à piles intégrées

En linguistique et en théorie des automates, un automate à piles intégrées en anglais « embedded pushdown automaton » ou EPDA est une automate pour la reconnaissance d'un langages engendré par une grammaire d'arbres adjoints (en anglais ou TAG). Un tel automate ressemble à un automate à pile utilisé pour l’analyse des langages algébriques, mais à la place d'une pile simple contenant des symboles, il possède une pile composée de piles. Ainsi, la pile d'un EPDA est une constituée d'une suite de piles (ordinaires) juxtaposées. Ceci donne aux grammaires correspondantes une capacité générative plus importante et les situe entre les grammaires algébriques et les grammaires contextuelles ; ces grammaires forment un sous-ensemble des grammaires regroupées sous le terme de . Les automates à piles intégrées ne doivent pas être confondues avec les automates à piles emboîtées dont la puissance de reconnaissance est encore plus importante puisque ces derniers reconnaissent les langages indexés. Les automates à piles intégrées (EPDA) ont été introduits par K. Vijay-Shanker en 1987 dans sa thèse de doctorat. Les automates à piles intégrées reconnaissent la classe de langages d'arbres adjoints ; ils constituent une extension naturelle des automates à pile qui eux reconnaissent les langages algébriques. La caractéristique principales des EPDA est de remplacer la pile unique utilisée dans un automate à pile par une pile constituée elle-même de piles non vides. Ceci permet de réaliser des réécritures emboîtées sur l'élément de tête de la pile : en plus de la traiter comme une pile simple, on peut l'entourer de nouvelles piles. Cet aspect est fondamental dans la comparaison de la puissance de reconnaissance entre automates à pile et automates à piles intégrées. Alors que la pile simple d'une automate à pile usuel ne peut traiter que les emboîtements d'un langage algébrique, la pile de piles d'un EPDA peut gérer les dépendances croisées comme on les rencontre dans les langages d'arbres adjoints.