Publikation
On the Complexity of some Extensions of RCG Parsing
Eberhard Bertsch; Mark-Jan Nederhof
In: Proceedings of the 7th International Workshop on Parsing Technologies (IWPT'01), October 17-19. International Conference on Parsing Technologies (IWPT), Beijing, China, Pages 66-77, 2001.
Zusammenfassung
We consider the parsing problem for range concatenation grammars (RCGs). Two new applications of RCG parsing are studied. The first is the parsing of finite automata, the second is string-to-string transduction, with an extension of RCGs. We show that these problems are undecidable in general, but become tractable for subclasses of the formalism.