An **embedded pushdown automaton** or **EPDA** is a computational model for parsing languages generated by tree-adjoining grammars (TAGs). It is similar to the context-free grammar-parsing pushdown automaton, but instead of using a plain stack to store symbols, it has a stack of iterated stacks that store symbols, giving TAGs a generative capacity between context-free and context-sensitive grammars, or a subset of mildly context-sensitive grammars. Embedded pushdown automata should not be confused with nested stack automata which have more computational power.

History and applications

EPDAs were first described by K. Vijay-Shanker in his 1988 doctoral thesis.^{[1]} They have since been applied to more complete descriptions of classes of mildly context-sensitive grammars and have had important roles in refining the Chomsky hierarchy. Various subgrammars, such as the linear indexed grammar, can thus be defined.^{[2]} EPDAs are also beginning to play an important role in natural language processing.

While natural languages have traditionally been analyzed using context-free grammars (see transformational-generative grammar and computational linguistics), this model does not work well for languages with crossed dependencies, such as Dutch, situations for which an EPDA is well suited. A detailed linguistic analysis is available in Joshi, Schabes (1997).^{[3]}

References

**^***Vijay-Shanker, K. (January 1988). “A Study of Tree-Adjoining Grammars”. Ph.D. Thesis. University of Pennsylvania.***^***Weir, David J. (1994). “Linear Iterated Pushdowns”**(PDF)**. Computational Intelligence.***10**(4): 431–439. doi:10.1111/j.1467-8640.1994.tb00007.x. Retrieved 2012-10-20.- ^ Jump up to:
^{a}^{b}*Joshi, Aravind K.; Yves Schabes (1997). “Tree-Adjoining Grammars”**(PDF)**. Handbook of Formal Languages. Springer.***3**: 69–124. doi:10.1007/978-3-642-59126-6_2. ISBN 978-3-642-63859-6. Retrieved 2014-02-07. **^***Weir, D. J. (1992), “A geometric hierarchy beyond context-free languages”, Theoretical Computer Science,***104**(2): 235–261, doi:10.1016/0304-3975(92)90124-X.**^***Nabil Anton Khabbaz (1972). Generalized context-free languages (Ph.D.). University of Iowa.***^***Nabil Anton Khabbaz (1974). “A geometric hierarchy of languages”. J. Comput. Syst. Sci.***8**(2): 142–157. doi:10.1016/s0022-0000(74)80052-8.