Skip to main content Skip to main navigation


Tabulation of Automata for Tree-Adjoining Languages

Miguel Alonso Pardo; Mark-Jan Nederhof; Eric Villemonte de la Clergerie
In: Grammars, Vol. 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.

Weitere Links