DFKI-LT - Tabulation of Automata for Tree-Adjoining Languages

Miguel Alonso Pardo, Mark-Jan Nederhof, Eric Villemonte de la Clergerie
Tabulation of Automata for Tree-Adjoining Languages
1 Grammars volume 3, Pages 89-110, 2000
 
We propose a modular design of tabular parsing algorithms for tree-adjoining languages. The modularity is made possible by a separation of the parsing strategy from the mechanism of tabulation. The parsing strategy is expressed in terms of the construction of a nondeterministic automaton from a grammar; three distinct types of automaton will be discussed. The mechanism of tabulation leads to the simulation of these nondeterministic automata in polynomial time, independent of the parsing strategy. The proposed application of this work is the design of efficient parsing algorithms for tree-adjoining grammars and related formalisms.
 
Files: BibTeX, Pardo:2000:TAT.pdf