An embedded pushdown automaton or EPDA is a computational model that parse languages in the tree-adjoining grammar (TAG). It is similar to the context-free grammar-parsing pushdown automaton, except that instead of using a plain stack to store symbols, it has a stack of iterated stacks that store symbols, giving TAGs a complexity between context-free grammars and context-sensitive grammars, or a subset of the mildly context-sensitive grammars.
EP...
more
An embedded pushdown automaton or EPDA is a computational model that parse languages in the tree-adjoining grammar (TAG). It is similar to the context-free grammar-parsing pushdown automaton, except that instead of using a plain stack to store symbols, it has a stack of iterated stacks that store symbols, giving TAGs a complexity between context-free grammars and context-sensitive grammars, or a subset of the mildly context-sensitive grammars.
EPDAs were first described by K. Vijay-Shanker in his 1988 doctoral thesis. They have since been applied to more complete descriptions of the class of mildly context-sensitive grammars and have had important roles in extending and refining the Chomsky hierarchy to this class. Various subgrammars, such as the linear indexed grammar, can thus be defined. They 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...
less
