Graph-grammars: An algebraic approach

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".