A pumping lemma for context-free graph languages

Autor:	Hans-Jörg Kreowski
Rok vydání:	2005
Předmět:	Discrete mathematics Voltage graph Pumping lemma for regular languages law.invention Planar graph Combinatorics symbols.namesake law Line graph Graph minor symbols Cubic graph Pumping lemma for context-free languages Null graph Mathematics
Zdroj:	Graph-Grammars and Their Application to Computer Science and Biology ISBN: 354009525X Graph-Grammars and Their Application to Computer Science and Biology
DOI:	10.1007/bfb0025726
Popis:	Each sufficiently large graph belonging to a context-free graph language (generated by an edge-replacement system) can be decomposed in three subgraphs FIRST, LINK and LAST, such that a suitable chain gluing of FIRST, LAST and N examples of LINK for each natural number N is also member of the language. This generalization of the well-known pumping lemma (also called Bar-Hillel's lemma, uvwxy lemma etc.) for context-free Chomsky languages is formulated and proved, where the iteration of LINK in the chain gluing leads to the pumping effect. The proof is based in canonical derivations and the embedding theorems studied in the algebraic theory of graph grammars.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::e87c8d423ce1ad6a1d24d3051b5aad53 https://doi.org/10.1007/bfb0025726 Zobrazit plný text záznamu