Skip to main content Skip to main navigation


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.


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.

Weitere Links