nLab mildly context-sensitive grammar

Idea

Mildly context-sensitive grammar is a kind of formal grammar with an expressivity between that of context-free grammar and context-sensitive grammar. They have enough expressive power to capture natural languages, but not too much so that they are still parsable efficiently.

Definition

While there has been no consensus on the definition of “mild”, there is an equivalence [VW94] between several independent definitions, see Weir (1988). Borrowing the definition from Genkin et al. (2010), a grammar formalism is mildly context-sensitive if the languages it generates are semilinear, it is parsable in polynomial time, it contains all context-free languages as well as the following:

• multiple agreement $L1 = \{ a^n b^n c^n | a, b, c \in V, n \in \mathbb{N} \},$
• crossed dependency $L2 = \{ a^n b^m c^n d^m | a, b, c, d \in V, m, n \in \mathbb{N} \}$,
• duplication $L3 = \{w w | w \in V^\star\}$.

References

• Shieber, Stuart M. Evidence against the context-freeness of natural language. Philosophy, Language, and Artificial Intelligence. Springer, Dordrecht, 1985.
• Weir, David Jeremy. Characterizing mildly context-sensitive grammar formalisms, 1988.
• Daniel Genkin, Nissim Francez, and Michael Kaminski. Mildly Context-Sensitive Languages via Buffer Augmented Pregroup Grammars, In Essays in Memory of Amir Pnueli, 2010.