Mildly Context-Sensitive Language
Jump to navigation
Jump to search
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)