automate à piles empilé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 « tree-adjoining grammar » 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 (en). 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.