Growing context-sensitive grammar
You can help expand this article with text translated from the corresponding article in Deutsch. Click [show] for important translation instructions.
|
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.[1][2] 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.[1]
These grammars were introduced by Dahlhaus and Warmuth.[3] They were later shown to be equivalent to the acyclic context-sensitive grammars.[3] Membership in any growing context-sensitive language is polynomial time computable;[4][5] however, the uniform problem of deciding whether a given string belongs to the language generated by a given growing[6] or acyclic[7] context-sensitive grammar is NP-complete.
See also
[edit | edit source]References
[edit | edit source]- ^ a b Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value). Here: p.316-317
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ a b Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).. Here: p.197-198
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value). Here: p.85-86
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ G. Buntrock and K. Lorys. On growing context-sensitive languages. In Proc. 19th ICALP, Lecture Notes in Computer Science (W. Kuich, ed, pages 77–88. Springer-Verlag, 1992.
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
External links
[edit | edit source]- G. Buntrock: Growing context-sensitive languages
