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

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence