Embedded pushdown automaton

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

  1. ^Vijay-Shanker, K. (January 1988). “A Study of Tree-Adjoining Grammars”. Ph.D. Thesis. University of Pennsylvania.
  2. ^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.
  3. ^ 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.
  4. ^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.
  5. ^Nabil Anton Khabbaz (1972). Generalized context-free languages (Ph.D.). University of Iowa.
  6. ^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.

Ofer Abarbanel – Executive Profile

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library