Mildly Context-Sensitive Language

A Mildly Context-Sensitive Language is a Context-Sensitive Language that ..

• AKA: MCSL.
• See: Mildly Context-Sensitive Grammar, Tree Adjoining Grammar, Context-Sensitive Language, Context-Free Grammar.

---

---

References

2007

• '(Joshi, 2007) ⇒ Aravind K. Joshi. (2007). “Complexity of Dependencies in Natural Language. Presentation, Vancouver, Feb 22. (presentation.ppt)
  • “TAGs (more precisely, languages of TAGs) belong to the class of languages called Mildly Context-Sensitive Languages (MCSL) characterized by: 1) polynomial parsing complexity 2) Grammars for the languages in this class can characterize a limited set of patterns of nested and crossed dependencies and their combinations. 3) languages in this class have the constant growth property (i.e., sentences, if arranged in increasing order of length, grow only by a bounded amount). 4) this class properly includes CFLs” (Joshi, 2007)