Growing context-sensitive grammar

In formal language theory, a growing context-sensitive grammar is a context-sensitive grammar in which the productions increase the length of the sentences being generated.{{cite journal | author=Gerhard Buntrock and Friedrich Otto | title=Growing Context-Sensitive Languages and Church-Rosser Languages | journal=Information and Computation | volume=141 | pages=1–36 | year=1998 | doi=10.1006/inco.1997.2681| doi-access=free }} These grammars are thus noncontracting and context-sensitive. A growing context-sensitive language is a context-sensitive language generated by these grammars.

In these grammars the "start symbol" S does not appear on the right hand side of any production rule and the length of the right hand side of each production exceeds the length of the left side, unless the left side is S.{{cite book | author=G. Buntrock and F. Otto | contribution=Growing Context-Sensitive Languages and Church-Rosser Languages | editor=Ernst W. Mayr and Claude Puech | title=Proc. 12th STACS | publisher=Springer | series=LNCS | volume=900 | pages=313–324 | isbn=978-3540590422 | year=1995 }} Here: p.316-317

These grammars were introduced by Dahlhaus and Warmuth.{{cite book | author=Gundula Niemann and Jens R. Woinowski | contribution=The Growing Context-Sensitive Languages Are the Acyclic Context-Sensitive Languages | editor=Werner Kuich and Grzegorz Rozenberg and Arto Salomaa | title=Proc. 5th Int. Conf on Developments in Language Theory (DLT) | publisher=Springer | series=Lecture Notes in Computer Science | volume=2295 | pages=197–205 | isbn=978-3540434535 | year=2002 }}. Here: p.197-198 They were later shown to be equivalent to the acyclic context-sensitive grammars. Membership in any growing context-sensitive language is polynomial time computable;{{cite book | author=E. Dahlhaus und M.K. Warmuth | contribution=Membership for growing context-sensitive grammars is polynomial | editor=Paul Franchi-Zannettacci | title=Proc. 11th Colloquium on Trees in Algebra and Programming (CAAP) | publisher=Springer | series=LNCS | volume=214 | pages=85–99 | year=1986 |url=https://users.soe.ucsc.edu/~manfred/pubs/J8.pdf}} Here: p.85-86{{cite journal | author=E. Dahlhaus und M.K. Warmuth | title=Membership for growing context-sensitive grammars is polynomial | journal=Journal of Computer and System Sciences | volume=33 | issue=3 | pages=456–472 | year=1986 | doi=10.1016/0022-0000(86)90062-0| doi-access=free }} however, the uniform problem of deciding whether a given string belongs to the language generated by a given growingG. Buntrock and K. Lorys. [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.2654 On growing context-sensitive languages.] In Proc. 19th ICALP, Lecture

Notes in Computer Science (W. Kuich, ed, pages 77–88. Springer-Verlag, 1992. or acyclic{{cite book | author=Erik Aarts | contribution=Uniform recognition for context-sensitive grammars is NP-complete | title=Proc. 14th Int. Conf. on Computational Linguistics (COLING, Nantes, Aug. 23-28) | pages=1157–1161 | contribution-url=http://aclweb.org/anthology-new/C/C92/C92-4183.pdf | year=1992 }} context-sensitive grammar is NP-complete.