Skip to Main content Skip to Navigation
Conference papers

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
Abstract : We prove a copying theorem for well-nested multiple context- free languages: if L = { w#w | w ∈ L0 } has a well-nested m-MCFG, then L has a 'non-branching' well-nested m-MCFG. This can be used to give simple examples of multiple context-free languages that are not generated by any well-nested MCFGs.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/inria-00525077
Contributor : Sylvain Salvati <>
Submitted on : Monday, October 11, 2010 - 10:34:24 AM
Last modification on : Wednesday, April 25, 2018 - 3:13:07 PM

Identifiers

Collections

Citation

Kanazawa Makoto, Sylvain Salvati. The Copying Power of Well-Nested Multiple Context-Free Grammars. Language and Automata Theory and Applications, 2010, Trier, Germany. pp.344-355, ⟨10.1007/978-3-642-13089-2_29⟩. ⟨inria-00525077⟩

Share

Metrics

Record views

176