Title :
Graph-grammars: An algebraic approach
Author :
Ehrig, H. ; Pfender, M. ; Schneider, H.J.
Abstract :
The paper presents an algebraic theory of graph-grammars using homomorphisms and pushout-constructions to specify embeddings and direct derivations constructively. We consider the case of arbitrary directed graphs permitting loops and parallel edges. The gluing of two arbitrary labeled graphs (push-out) is defined allowing a strictly symmetric definition of direct derivations and the embedding of derivations into a common frame. A two-dimensional hierarchy of graph-grammars is given including the classical case of Chomsky-grammars and several other graphgrammar constructions as special types. The use of well-known categorical constructions and results allows simplification of the proofs and pregnant formulation of concepts like "parallel composition" and "translation of grammars".
Keywords :
Labeling; Pattern recognition; Pregnancy; Production;
Conference_Titel :
Switching and Automata Theory, 1973. SWAT '08. IEEE Conference Record of 14th Annual Symposium on
Conference_Location :
USA
DOI :
10.1109/SWAT.1973.11