Mild context-sensitivity

Context-free grammars undergenerate some attested cross-serial patterns, while unrestricted context-sensitive grammars provide more power than those patterns appear to require. What might lie between them? Joshi used mild context-sensitivity to name this region (Joshi 1985).

The criteria

Mild context-sensitivity is not one formally fixed class. It is an informal characterization of grammar families that satisfy several criteria:

They properly include the context-free languages.
They describe limited cross-serial dependencies.
Their membership problem is solvable in polynomial time for a fixed grammar.
Their languages have the constant-growth property.

Constant growth concerns gaps between attainable string lengths. For a language $L$, there must be a constant $c$ such that whenever $L$ contains a string of length $n$ and a longer string exists, some string in $L$ has length between $n+1$ and $n+c$. Semilinearity, which many proposed families satisfy, is a stronger property. It should not be paraphrased as “string lengths grow polynomially.”

The cross-serial criterion is also intentionally limited. A candidate family must go beyond CFGs, but it should not admit arbitrary context-sensitive dependencies merely because some crossing pattern is possible.

Two relevant families

The first family is the TAG-equivalent family. Tree-Adjoining Grammars, Linear Indexed Grammars, Head Grammars, and the CCG formalism studied by Vijay-Shanker and Weir (1994) generate the same string languages.

The second is the more general MCFG/LCFRS family (Seki et al. 1991; Kallmeyer 2013). It properly contains the TAG-equivalent languages. Both families are often described as mildly context-sensitive because they satisfy the broad criteria above, but they are not the same language class.

We can summarize the weak-generative containments relevant here as

\[ \text{Context-Free} \subsetneq \text{TAG-equivalent} \subsetneq \text{Multiple Context-Free} \subseteq \text{Context-Sensitive}. \]

Question

Does calling two formalisms “mildly context-sensitive” imply that they generate exactly the same string languages?

Answer

No. The label refers to the criteria above, not to one universally agreed-upon class. Weak equivalence must be established separately for the particular formalisms under comparison.

We next examine TAG and MCFG/LCFRS, the latter of which supplies the formal basis of the final project. We then introduce type-logical grammar, CCG, and Minimalist Grammars. The final section proves the weak-equivalence claims by constructing the translations in both directions and checking their invariants.

References

Joshi, Aravind K. 1985. “Tree Adjoining Grammars: How Much Context-Sensitivity Is Required to Provide Reasonable Structural Descriptions?” In Natural Language Parsing: Psychological, Computational, and Theoretical Perspectives, edited by David R. Dowty, Lauri Karttunen, and Arnold M. Zwicky. Cambridge University Press. https://doi.org/10.1017/CBO9780511597855.007.

Kallmeyer, Laura. 2013. “Linear Context-Free Rewriting Systems.” Language and Linguistics Compass 7 (1): 22–38. https://doi.org/10.1002/lnc3.359.

Seki, Hiroyuki, Takashi Matsumura, Mamoru Fujii, and Tadao Kasami. 1991. “On Multiple Context-Free Grammars.” Theoretical Computer Science 88 (2): 191–229. https://doi.org/10.1016/0304-3975(91)90374-B.

Vijay-Shanker, K., and David J. Weir. 1994. “The Equivalence of Four Extensions of Context-Free Grammars.” Mathematical Systems Theory 27 (6): 511–46. https://doi.org/10.1007/BF01191624.

--- title: Mild context-sensitivity bibliography: ../../references.bib --- Context-free grammars undergenerate some attested cross-serial patterns, while unrestricted context-sensitive grammars provide more power than those patterns appear to require. What might lie between them? Joshi used **mild context-sensitivity** to name this region [@joshi1985tree]. ## The criteria Mild context-sensitivity is not one formally fixed class. It is an informal characterization of grammar families that satisfy several criteria: 1. They properly include the context-free languages. 2. They describe limited cross-serial dependencies. 3. Their membership problem is solvable in polynomial time for a fixed grammar. 4. Their languages have the constant-growth property. Constant growth concerns gaps between attainable string lengths. For a language $L$, there must be a constant $c$ such that whenever $L$ contains a string of length $n$ and a longer string exists, some string in $L$ has length between $n+1$ and $n+c$. Semilinearity, which many proposed families satisfy, is a stronger property. It should not be paraphrased as “string lengths grow polynomially.” The cross-serial criterion is also intentionally limited. A candidate family must go beyond CFGs, but it should not admit arbitrary context-sensitive dependencies merely because some crossing pattern is possible. ## Two relevant families The first family is the **TAG-equivalent family**. Tree-Adjoining Grammars, Linear Indexed Grammars, Head Grammars, and the CCG formalism studied by @vijayshanker1994equivalence generate the same string languages. The second is the more general **MCFG/LCFRS family** [@seki1991multiple; @kallmeyer_linear_2013]. It properly contains the TAG-equivalent languages. Both families are often described as mildly context-sensitive because they satisfy the broad criteria above, but they are not the same language class. We can summarize the weak-generative containments relevant here as $$ \text{Context-Free} \subsetneq \text{TAG-equivalent} \subsetneq \text{Multiple Context-Free} \subseteq \text{Context-Sensitive}. $$ ::: {.callout-caution} ## Question Does calling two formalisms “mildly context-sensitive” imply that they generate exactly the same string languages? ::: ::: {.callout-tip collapse=true} ## Answer No. The label refers to the criteria above, not to one universally agreed-upon class. Weak equivalence must be established separately for the particular formalisms under comparison. ::: We next examine TAG and MCFG/LCFRS, the latter of which supplies the formal basis of the final project. We then introduce type-logical grammar, CCG, and Minimalist Grammars. The final section proves the weak-equivalence claims by constructing the translations in both directions and checking their invariants.