A pumping lemma for context-free graph languages Export

@incollection{citeulike:6081268, abstract = {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.}, author = {Kreowski, Hans-J\"{o}rg}, citeulike-article-id = {6081268}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/BFb0025726}, citeulike-linkout-1 = {http://www.springerlink.com/content/mj671631t54j5887}, doi = {10.1007/BFb0025726}, journal = {Graph-Grammars and Their Application to Computer Science and Biology}, keywords = {grammars, graph}, pages = {270--283}, posted-at = {2009-11-06 16:51:32}, priority = {2}, title = {A pumping lemma for context-free graph languages}, url = {http://dx.doi.org/10.1007/BFb0025726}, year = {1979} }

TY - CHAP ID - citeulike:6081268 L3 - citeulike-article-id:6081268 N2 - 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. JF - Graph-Grammars and Their Application to Computer Science and Biology EP - 283 TI - A pumping lemma for context-free graph languages SP - 270 KW - grammars KW - graph AU - Kreowski, Hans-Jörg PY - 1979/// UR - http://dx.doi.org/10.1007/BFb0025726 ER -