Constraint Grammar Parsing with Left and Right Sequential Finite Transducers
Mans Hulden · Finite-State Methods and Natural Language Processing · 2011
We propose an approach to parsing Constraint Grammars using finite-state transducers and report on a compiler that converts Constraint Grammar rules into transducer representations. The resulting transducers are further optimized by conversion to left and right sequential transducers. Using the method, we show that we can improve on the worst-case asymptotic bound of Constraint Grammar parsing from cubic to quadratic in the length of input sentences.