Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Mildly context-sensitive grammar formalism
Résumé
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).
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.