Schematic Finite-State Intersection Parsing
Anssi Yli-Jyrä · 2005
The framework of Finite-State Intersection Grammars employs a parsing technique according to which several finite-state automata are intersected to determine the output automaton. Implementation of the intersection parser has turned out to be a difficult task. Several problems in efficiency arise when disambiguation choices are based on long contexts with many don't cares. We are concerned with the long-distance effects of the grammatical constraints. We outline a compacting method that rearranges the search space of the intersection process and makes it shallower. This method is based on the specialization of grammar rules relative to each input sentence. 1 Introduction The present work is relevant to the framework of Finite-State Intersection Grammars (FSIG) proposed by Koskenniemi [Kos90]. The FSIG parsing process is currently based on the idea that several finite-state automata (FSA) are intersected to determine the output automaton. The input automata are considered as p...