Incomputational linguistics, the termmildly context-sensitive grammar formalisms refers to severalgrammar formalisms that have been developed in an effort to provideadequate descriptions of thesyntactic structure ofnatural language.
Every mildly context-sensitive grammar formalism defines a class ofmildly context-sensitive grammars (the grammars that can be specified in the formalism), and therefore also a class ofmildly context-sensitive languages (theformal languages generated by the grammars).
By 1985, several researchers indescriptive andmathematical linguistics had provided evidence against the hypothesis that the syntactic structure of natural language can be adequately described bycontext-free grammars.[1][2]At the same time, the step to the next level of theChomsky hierarchy, tocontext-sensitive grammars, appeared both unnecessary and undesirable.In an attempt to pinpoint the exact formal power required for the adequate description of natural language syntax,Aravind Joshi characterized "grammars (and associatedlanguages) that are only slightly more powerful than context-free grammars (context-free languages)".[3]He called these grammarsmildly context-sensitive grammars and the associated languagesmildly context-sensitive languages.
Joshi’s characterization of mildly context-sensitive grammars was biased toward his work ontree-adjoining grammar (TAG).However, together with his students Vijay Shanker and David Weir, Joshi soon discovered that TAGs are equivalent, in terms of the generated string languages, to the independently introducedhead grammar (HG).[4]This was followed by two similar equivalence results, forlinear indexed grammar (LIG)[5] andcombinatory categorial grammar (CCG),[6] which showed that the notion of mild context-sensitivity is a very general one and not tied to a specific formalism.
The TAG-equivalent formalisms were generalized by the introduction oflinear context-free rewriting systems (LCFRS).[7][8]These grammars define an infinite hierarchy of string languages in between the context-free and the context-sensitive languages, with the languages generated by the TAG-equivalent formalisms at the lower end[clarification needed] of the hierarchy.Independently of and almost simultaneously to LCFRS, Hiroyuki Seki et al. proposed the essentially identical formalism of multiple context-free grammar (MCFG).[9]LCFRS/MCFG is sometimes regarded as the most general formalism for specifying mildly context-sensitive grammars.However, several authors have noted that some of the characteristic properties of the TAG-equivalent formalisms are not preserved by LCFRS/MCFG,[10] and that there are languages that have the characteristic properties of mildly context-sensitivity but are not generated by LCFRS/MCFG.[11]
Recent years have seen increased interest in the restricted class ofwell-nested linear context-free rewriting systems/multiple context-free grammars,[10][12] which define a class of grammars that properly includes the TAG-equivalent formalisms but is properly included in the unrestricted LCFRS/MCFG hierarchy.
Despite a considerable amount of work on the subject, there is no generally accepted formal definition of mild context-sensitivity.
According to the original characterization by Joshi,[3] a class of mildly context-sensitive grammars should have the following properties:
In addition to these, it is understood that every class of mildly context-sensitive grammars should be able to generate all context-free languages.
Joshi’s characterization is not a formal definition. He notes:[3]
This is only a rough characterization because conditions 1 and 3 depend on the grammars, while condition 2 depends on the languages; further, condition 1 needs to be specified much more precisely than I have done so far.
Other authors have proposed alternative characterizations of mild context-sensitivity, some of which take the form of formal definitions.For example, Laura Kallmeyer[13] takes the perspective that mild context-sensitivity should be defined as a property of classes of languages rather than, as in Joshi’s characterization, classes of grammars.Such a language-based definition leads to a different notion of the concept than Joshi’s.
The termcross-serial dependencies refers to certain characteristic word ordering patterns, in particular to the verb–argument patterns observed in subordinate clauses in Dutch[1] and Swiss German.[2]These are the very patterns that can be used to argue against the context-freeness of natural language; thus requiring mildly context-sensitive grammars to model cross-serial dependencies means that these grammars must be more powerful than context-free grammars.
Kallmeyer[13] identifies the ability to model cross-serial dependencies with the ability to generate thecopy language
and its generalizations to two or more copies of w, up to some bound.These languages are not context-free, which can be shown using thepumping lemma.
A formal language is ofconstant growth if every string in the language is longer than the next shorter strings by at most a (language-specific) constant.Languages that violate this property are often considered to be beyond human capacity, although some authors have argued that certain phenomena in natural language do show a growth that cannot be bounded by a constant.[14]
Most mildly context-sensitive grammar formalisms (in particular, LCFRS/MCFG) actually satisfy a stronger property than constant growth calledsemilinearity.[7]A language is semilinear if its image under the Parikh-mapping (the mapping that "forgets" the relative position of the symbols in a string, effectively treating it as a bag of words) is aregular language.All semilinear languages are of constant growth, but not every language with constant growth is semilinear.[11]
A grammar formalism is said to havepolynomial parsing if its membership problem can be solved indeterministic polynomial time.This is the problem to decide, given a grammarG written in the formalism and a string w, whetherw is generated by G – that is, whetherw is "grammatical" according to G.The time complexity of this problem is measured in terms of the combined size of G and w.
Under the view on mild context-sensitivity as a property of classes of languages,polynomial parsing refers to the language membership problem.This is the problem to decide, for a fixed language L, whether a given string w belongs to L.The time complexity of this problem is measured in terms of the length of w; it ignores the question howL is specified.
Note that both understandings ofpolynomial parsing are idealizations in the sense that for practical applications one is interested not only in the yes/no question whether a sentence is grammatical, but also in the syntactic structure that the grammar assigns to the sentence.
Over the years, a large number of grammar formalisms have been introduced that satisfy some or all of the characteristic properties put forth by Joshi.Several of them have alternative, automaton-based characterizations that are not discussed in this article; for example, the languages generated by tree-adjoining grammar can be characterized byembedded pushdown automata.
Linear context-free rewriting systems/multiple context-free grammars form a two-dimensional hierarchy of generative power with respect to two grammar-specific parameters calledfan-out andrank.[22]More precisely, the languages generated by LCFRS/MCFG with fan-out f ≥ 1 and rank r ≥ 3 are properly included in the class of languages generated by LCFRS/MCFG with rank r + 1 and fan-out f, as well as the class of languages generated by LCFRS/MCFG with rank r and fan-out f + 1.In the presence of well-nestedness, this hierarchy collapses to a one-dimensional hierarchy with respect to fan-out; this is because every well-nested LCFRS/MCFG can be transformed into an equivalent well-nested LCFRS/MCFG with the same fan-out and rank 2.[10][12]Within the LCFRS/MCFG hierarchy, the context-free languages can be characterized by the grammars with fan-out 1; for this fan-out there is no difference between general and well-nested grammars.The TAG-equivalent formalisms can be characterized as well-nested LCFRS/MCFG of fan-out 2.