Carroll, J., N. Nicolov, M. Smets, O. Shaumyan and D. Weir (1998) `Grammar compaction and computation sharing in automata-based parsing'. In Proceedings of the 1st Workshop on Tabulation in Parsing and Deduction, Paris, France. 16-25.
Wide-coverage grammars in Lexicalised Tree-Adjoining Grammar (LTAG) and related formalisms are structurally complex, containing many hundreds of elementary trees. In the context of the development of a full-scale LTAG-like grammar and parsing system, we have investigated the claim that because many of these trees have a great deal of structure in common, a parser that manipulates trees individually performs a considerable amount of redundant computation. This claim has been used to motivate a parsing technique that encodes trees as finite state automata and captures overlapping computation through automata minimization. Our preliminary results show that this technique leads to considerable computation sharing.
Download postscript version.