Linear indexed automata and tabulation of TAG parsing
Mark-Jan Nederhof · University of Groningen research database (University of Groningen / Centre for Information Technology) · 1998
We present a new kind of recognizer for tree-adjoining languages, the linear indexed automata. Such recognizers allow straightforward realization by means of logical programming languages. We show that the computations by such automata, which are in general nondeterministic, can be tabulated by means of an extension of a technique originally devised for context-free languages. The proposed application of this work is the design of efficient parsing algorithms for tree-adjoining grammars.