Skip to Main content Skip to Navigation
New interface
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 metadata
Contributor : Sylvain Salvati Connect in order to contact the contributor
Submitted on : Monday, October 11, 2010 - 10:34:24 AM
Last modification on : Tuesday, July 5, 2022 - 8:38:48 AM

Links full text




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⟩



Record views