DFKI-LT - On the Complexity of some Extensions of RCG Parsing

Eberhard Bertsch, Mark-Jan Nederhof
On the Complexity of some Extensions of RCG Parsing
1 Proceedings of the 7th International Workshop on Parsing Technologies (IWPT'01), October 17-19, Pages 66-77, Beijing, China, o.A., 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.
 
Files: BibTeX, Bertsch:2001:CSE.pdf