Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Mildly context-sensitive grammar formalism
Summary
In computational linguistics, the term mildly context-sensitive grammar formalisms refers to several grammar formalisms that have been developed in an effort to provide adequate descriptions of the syntactic structure of natural language.
Every mildly context-sensitive grammar formalism defines a class of mildly context-sensitive grammars (the grammars that can be specified in the formalism), and therefore also a class of mildly context-sensitive languages (the formal languages generated by the grammars).
By 1985, several researchers in descriptive and mathematical linguistics had provided evidence against the hypothesis that the syntactic structure of natural language can be adequately described by context-free grammars.
At the same time, the step to the next level of the Chomsky hierarchy, to context-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 associated languages) that are only slightly more powerful than context-free grammars (context-free languages)".
He called these grammars mildly context-sensitive grammars and the associated languages mildly context-sensitive languages.
Joshi’s characterization of mildly context-sensitive grammars was biased toward his work on tree-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 introduced head grammar (HG).
This was followed by two similar equivalence results, for linear indexed grammar (LIG) and combinatory categorial grammar (CCG), 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 of linear context-free rewriting systems (LCFRS).
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.