DFKI-LT - On the Complexity of some Extensions of RCG Parsing
On the Complexity of some Extensions of RCG Parsing
1 Proceedings of the 7th International Workshop on Parsing Technologies (IWPT'01), October 17-19,
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