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. 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. 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).
- ^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:ab 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.