Graph-grammars: An algebraic approach
Ehrig H, Pfender M, Schneider HJ (1973)
Publication Language: English
Publication Type: Conference contribution, Original article
Publication year: 1973
Publisher: IEEE
Pages Range: 167-180
Conference Proceedings Title: IEEE Conference Record of 14th Annual Symposium on Switching and Automata Theory (SWAT 1973)
Event location: Iowa
ISBN: 0272-4847
URI: http://www2.informatik.uni-erlangen.de/publication/download/schneider_EPS1973.pdf
DOI: 10.1109/SWAT.1973.11
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".
Authors with CRIS profile
How to cite
APA:
Ehrig, H., Pfender, M., & Schneider, H.J. (1973). Graph-grammars: An algebraic approach. In IEEE Conference Record of 14th Annual Symposium on Switching and Automata Theory (SWAT 1973) (pp. 167-180). Iowa, US: IEEE.
MLA:
Ehrig, Hartmut, Marion Pfender, and Hans Jürgen Schneider. "Graph-grammars: An algebraic approach." Proceedings of the 14th Annual Symposium on Switching and Automata Theory (SWAT 1973), Iowa IEEE, 1973. 167-180.
BibTeX: Download