Increasingly context-sensitive language

Growing context-sensitive languages ( English Growing Context Sensitive Languages , abbreviated GCSL ) is a term from the theory of formal languages , a branch of theoretical computer science . An increasingly context-sensitive language is defined with formal grammars , the rules of which have the following property: The right side is always longer than the left. The language class was defined in 1986.

This language class has in theory the following meaning: It represents a true extension of the class of context-free languages is, but remains a subclass of P . Robert McNaughton once recognized this class as the missing language class in the Chomsky hierarchy

In 2002, Gundula Niemann and Jens Woinowski showed that GCSL corresponds to the class of acyclic context-sensitive languages.

Analogous to the deterministically context-free languages , the deterministically growing context-sensitive languages are also defined: The deterministic variant of the characterizing automaton is chosen here as the definition. It is known here that this class corresponds to the Church-Rosser languages .

Definitions

1. A grammar is called a strictly monotonous grammar if the following applies: ${\displaystyle G=(\Sigma ,T,S,P)}$
   • All rules from have the following form: ${\displaystyle P}$
     • The nonterminal appears only on the left side of rules on ${\displaystyle S}$ ${\displaystyle P}$
     • If is (i.e. a rule of ) and , then: ${\displaystyle (\alpha \rightarrow \beta )\in P}$ ${\displaystyle G}$ ${\displaystyle \alpha \not =S}$ ${\displaystyle |\alpha |<|\beta |}$
2. Strictly monotonous grammars are also increasingly called context-sensitive .
3. The class of languages ​​that are generated by increasingly context-sensitive grammars are the increasingly context-sensitive languages ,

Alternative characterizations

GCSL can be described in different ways:

• through strictly monotonous grammars
• through shrinking two- cellar machines (sTPDA)
• through acyclic context-sensitive grammars

All languages ​​that are accepted by a deterministic, shrinking two-cellar machine are called deterministic, growing, context-sensitive .

properties

GCSL are compared to here

• DGCSL, the deterministic growing context sensitive languages
• CFL, the context-free languages
• CSL, the context-sensitive languages (equivalent to monotonous grammars )
• DCFL, the deterministic context-free languages
• DCSL, the deterministic context-sensitive languages

Real inclusions:

• CFL ⊊ GCSL ⊊ CSL
• DCFL ⊊ DGCSL ⊊ DCSL
• DGCSL ⊊ GCSL

GCSL is completed under

• Union
• Averaging with regular languages
• Concatenation
• Kleene star
• ${\displaystyle \varepsilon }$- free homomorphisms
• inverse homomorphisms

GCSL is not completed under

• average
• Homomorphisms

swell

1. ^ E. Dahlhaus and MK Warmuth: Membership for growing context-sensitive grammars is polynomial . In: Journal of Computer and System Sciences . Volume 33, pp. 456-472, 1986.
2. ^ Robert McNaughton: An Insertion into the Chomsky Hierarchy? . In: Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa . Pp. 204-212, 1999
3. ^ Gundula Niemann, Jens R. Woinowski: The Growing Context-Sensitive Languages ​​Are the Acyclic Context-Sensitive Languages . In: Developments in Language Theory . Lecture Notes in Computer Science, Volume 2295, Pages 197-205, 2002, doi : 10.1007 / 3-540-46011-X_16

literature

• Gerhard Buntrock and Krzysztof Lorys: On Growing Context-Sensitive Languages . In: Proceedings of the 19th International Colloquium on Automata, Languages ​​and Programming . Pp. 77-88, 1992.
• Gundula Niemann: Church-Rosser Languages ​​and Related Classes . Dissertation, Univ. Kassel, ISBN 3-89958-002-8 , 2002.

Web links

• GCSL . In: Complexity Zoo. (English)
• Growing context-sensitive languages