Paper: Recognition Of Linear Context-Free Rewriting Systems

ACL ID P92-1012
Title Recognition Of Linear Context-Free Rewriting Systems
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1992
Authors

The class of linear context-free rewriting sys- tems has been introduced as a generalization of a class of grammar formalisms known as mildly context-sensitive. The recognition problem for lin- ear context-free rewriting languages is studied at length here, presenting evidence that, even in some restricted cases, it cannot be solved efficiently. This entails the existence of a gap between, for exam- ple, tree adjoining languages and the subclass of lin- ear context-free rewriting languages that generalizes the former class; such a gap is attributed to "cross- ing configurations". A few other interesting conse- quences of the main result are discussed, that con- cern the recognition problem for linear context-free rewriting languages.