In
formal language theory
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of sy ...
, 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 rules may be surrounded by a context of terminal and nonterminal symbols. Context-sensitive grammars are more general than ...
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 one of the four types of grammars in the Chomsky hierarc ...
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 grammar
Acyclic may refer to:
* In chemistry, a compound which is an open-chain compound, e.g. alkanes and acyclic aliphatic compounds
* In mathematics:
** A graph without a cycle
Cycle, cycles, or cyclic may refer to:
Anthropology and social sciences
...
s.
Membership in any growing context-sensitive language is
polynomial time
In 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 performed by ...
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, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
.
See also
*
Noncontracting grammar In formal language theory, a grammar is noncontracting (or monotonic) if all of its production rules are of the form
α → β where α and β are strings of nonterminal and terminal symbols, and
the length of α is less than or equal t ...
References
External links
* G. Buntrock
Growing context-sensitive languages
{{Formal languages and grammars, state=collapsed
Formal languages