In
formal language theory
In logic, mathematics, computer science, and linguistics, a formal language is a set of string (computer science), strings whose symbols are taken from a set called "#Definition, alphabet".
The alphabet of a formal language consists of symbol ...
, a growing context-sensitive grammar is a
context-sensitive grammar
A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any Production (computer science), production rules may be surrounded by a context of terminal symbol, terminal and nonterminal symbols. Cont ...
in which the productions increase the length of the sentences being generated.
These grammars are thus
noncontracting and context-sensitive. A growing context-sensitive language is a
context-sensitive language
In formal language theory, a context-sensitive language is a language that can be defined by a context-sensitive grammar (and equivalently by a noncontracting grammar). Context-sensitive is known as type-1 in the Chomsky hierarchy of formal langu ...
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.
[ Here: p.316-317]
These grammars were introduced by Dahlhaus and Warmuth.
[. 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
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
computable; however, the
''uniform'' problem of deciding whether a given string belongs to the language generated by a given growing or acyclic
context-sensitive grammar is
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
.
See also
*
Noncontracting grammar
References
External links
* G. Buntrock
Growing context-sensitive languages
{{Formal languages and grammars, state=collapsed
Formal languages