Paper: Uniform Recognition For Acyclic Context-Sensitive Grammars Is NP-Complete

ACL ID C92-4183
Title Uniform Recognition For Acyclic Context-Sensitive Grammars Is NP-Complete
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1992
Authors
  • Erik Aarts (Utrecht University, Utrecht The Netherlands)

Context-sensitive grammars in which each rule is of the forln aZfl - -~ (-*Tfl are acyclic if the associ- ated context-free grammar with the rules Z ~ 3' is acyclic. The problem whether an intmt string is in the language generated by an acyclic context- sensitive grammar is NP-conlplete.