The Copying Power of Well-Nested Multiple Context-Free Grammars

Kanazawa Makoto 1 Sylvain Salvati 2, 3
2 SIGNES - Linguistic signs, grammar and meaning: computational logic for natural language
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Résumé : Nous démontrons un théorème de copie pour les grammaires hors-contexte multiples bien imbriquées : si L = { w#w | w ∈ L0 } est décrit par une m-MCFG bien imbriquée, alors L peut être décrit par une m-MCFG bien imbriquée non-branchante. Ce théorème peut être utilisé pour donner des exemples simples de languages hors contexte multiples qui ne sont générés par aucune MCFG bien imbriquée.
Type de document :
Communication dans un congrès
Adrian-Horia Dediu, Henning Fernau, and Carlos Martín-Vide. Language and Automata Theory and Applications, 2010, Trier, Germany. Springer, 6031, pp.344-355, 2010, LNCS. 〈http://www.springerlink.com/content/b8w7r53761614lk7/〉. 〈10.1007/978-3-642-13089-2_29〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00525077
Contributeur : Sylvain Salvati <>
Soumis le : lundi 11 octobre 2010 - 10:34:24
Dernière modification le : mercredi 25 avril 2018 - 15:13:07

Lien texte intégral

Identifiants

Collections

Citation

Kanazawa Makoto, Sylvain Salvati. The Copying Power of Well-Nested Multiple Context-Free Grammars. Adrian-Horia Dediu, Henning Fernau, and Carlos Martín-Vide. Language and Automata Theory and Applications, 2010, Trier, Germany. Springer, 6031, pp.344-355, 2010, LNCS. 〈http://www.springerlink.com/content/b8w7r53761614lk7/〉. 〈10.1007/978-3-642-13089-2_29〉. 〈inria-00525077〉

Partager

Métriques

Consultations de la notice

129