 Mildly contextsensitive language

In formal grammar theory, mildly contextsensitive languages are a class of formal languages which can be efficiently parsed, but still possess enough context sensitivity to allow the parsing of natural languages. The concept was first introduced by Aravind Joshi in 1985.
Contents
Definition
Mild contextsensitivity is defined in terms of sets of languages. A set of languages is mildly contextsensitive if and only if
 it contains all contextfree languages.
 it admits limited crossserial dependencies.
 all the languages are parsable in polynomial time.
 all the languages have constant growth; this means that the distribution of string lengths should be linear rather than supralinear. This is often guaranteed by proving a pumping lemma for some class of mildly contextsensitive languages.
Formalisms
Some attempts at creating mildly contextsensitive language formalisms include:
 Linear contextfree rewriting systems developed by D. J. Weir
 Minimalist grammars of Edward P. Stabler, Alain Lecomte, Christian Retoré, etc.
 Head grammars of Carl Pollard
 Combinatory categorial grammars developed by Mark Steedman
 Linear indexed grammars defined by Gerald Gazdar
 Treeadjoining grammars developed by Aravind Joshi
The first two of these grammar classes define the same set of languages, while the last four define another single, strictly smaller class.^{[citation needed]} The larger of the two classes may be parsed by thread automatons, while the other smaller one may be parsed by embedded pushdown automatons.
While all languages in both classes are mildly contextsensitive and both classes support some crossserial dependency, neither class exhausts the full set of mildly contextsensitive languages.
Control Language Hierarchy
A more precisely defined hierarchy of languages that correspond to the mildly contextsensitive class was defined by David J. Weir. Based on the work of Nabil A. Khabbaz, Weir's Control Language Hierarchy is a containment hierarchy of countable set of language classes where the Level1 is defined as contextfree, and Level2 is the class of treeadjoining and the other three grammars.
Following are some of the properties of Levelk languages in the hierarchy:
 Levelk languages are properly contained by Level(k + 1) language class
 Levelk languages can be parsed in time
 Levelk contains the language , but not
 Levelk contains the language , but not
Those properties correspond well (at least for small k > 1) to the conditions of mildly contextsensitive languages imposed by Joshi, and as k gets bigger, the language class become, in a sense, less mildly contextsensitive.
See also
Further reading
 Joshi, Aravind; VijayShanker, K.; Weir, David (1991), "The Convergence of Mildly ContextSensitive Grammar Formalisms", in Sells, Peter; Shieber, Stuart; Wasow, Thomas, Foundational Issues in Natural Language Processing, Cambridge, MA: MIT Press, pp. 31–81, ISBN 0262193035, http://repository.upenn.edu/cgi/viewcontent.cgi?article=1571&context=cis_reports.
 VijayShanker, K.; Weir, David (1994), "The Equivalence of Four Extensions of ContextFree Grammars", Mathematical Systems Theory 27 (6): 511–546, doi:10.1007/BF01191624, ISSN 00255661, http://citeseer.ist.psu.edu/vijayshanker94equivalence.html.
 Villemonte de La Clergerie, Eric (2002), "Parsing Mildly ContextSensitive Languages with Thread Automata", Proceedings of the 19th international conference on Computational linguistics, 1, pp. 1–7, http://acl.ldc.upenn.edu/C/C02/C021028.pdf.
 Weir, D. J. (1992), "A geometric hierarchy beyond contextfree languages", Theoretical computer science 104 (2): 235–261, doi:10.1016/03043975(92)90124X..
External links
 Parsing Beyond ContextFree Grammar, by Laura Kallmeyer
 Seminar on treeadjoining grammars and mildly contextsensitive languages and formalisms, by Laura Kallmeyer
 Mildly ContextSensitive Grammars, by Aravind Joshi
Automata theory: formal languages and formal grammars Chomsky hierarchy Type0—Type1———Type2——Type3—Grammars (no common name)Linear contextfree rewriting systems etc.Treeadjoining etc.—Languages Mildly contextsensitiveMinimal automaton Thread automataEach category of languages is a proper subset of the category directly above it.  Any automaton and any grammar in each category has an equivalent automaton or grammar in the category directly above it. Categories: Formal languages
Wikimedia Foundation. 2010.
Look at other dictionaries:
Contextsensitive language — In theoretical computer science, a context sensitive language is a formal language that can be defined by a context sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy. Of the four, this is the least often used,… … Wikipedia
Contextsensitive grammar — A context sensitive grammar (CSG) is a formal grammar in which the left hand sides and right hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context sensitive grammars are more general than… … Wikipedia
Contextfree language — In formal language theory, a context free language is a language generated by some context free grammar. The set of all context free languages is identical to the set of languages accepted by pushdown automata. Contents 1 Examples 2 Closure… … Wikipedia
Deterministic contextfree language — A deterministic context free language is a formal language which is defined by a deterministic context free grammar.[1] The set of deterministic context free languages is called DCFL[2] and is identical to the set of languages accepted by a… … Wikipedia
Contextfree grammar — In formal language theory, a context free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty). The… … Wikipedia
Indexed language — Indexed languages are a class of formal languages discovered by Alfred Aho [ cite journal  last = Aho  first = Alfred  year = 1968  title = Indexed grammars an extension of context free grammars  journal = Journal of the ACM  volume = 15 … … Wikipedia
Recursive language — This article is about a class of formal languages as they are studied in mathematics and theoretical computer science. For computer languages that allow a function to call itself recursively, see Recursion (computer science). In mathematics,… … Wikipedia
Recursively enumerable language — In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing acceptable. It is known as a type 0 language in the Chomsky hierarchy of formal… … Wikipedia
Deterministic contextfree grammar — In formal grammar theory, the deterministic context free grammars (DCFGs) are a proper subset of the context free grammars. The deterministic context free grammars are those a deterministic pushdown automaton can recognize. A DCFG is the finite… … Wikipedia
Bach language — In theoretical computer science, the Bach language is the formal language over an alphabet of three distinct symbols containing all strings in which the three symbols occur equally often. The Bach language is a context sensitive language. Pullum… … Wikipedia