%0 Conference Paper %1 conf/focs/EhrigPS73 %A Ehrig, Hartmut %A Pfender, Michael %A Schneider, Hans Jürgen %B SWAT (FOCS) %D 1973 %I IEEE Computer Society %K dis grammars graph transformations %P 167-180 %T Graph-Grammars: An Algebraic Approach %U http://dblp.uni-trier.de/db/conf/focs/focs73.html#EhrigPS73 %X 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".

@inproceedings{conf/focs/EhrigPS73, 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".}, added-at = {2012-06-16T18:43:12.000+0200}, author = {Ehrig, Hartmut and Pfender, Michael and Schneider, Hans Jürgen}, biburl = {https://www.bibsonomy.org/bibtex/2cf142df83b1e1840adab57b955dcfc19/butonic}, booktitle = {SWAT (FOCS)}, crossref = {conf/focs/FOCS14}, ee = {http://doi.ieeecomputersociety.org/10.1109/SWAT.1973.11}, interhash = {b143d4db4f31f648974aa1f8d7bccf5a}, intrahash = {cf142df83b1e1840adab57b955dcfc19}, keywords = {dis grammars graph transformations}, pages = {167-180}, publisher = {IEEE Computer Society}, timestamp = {2012-06-16T18:43:12.000+0200}, title = {Graph-Grammars: An Algebraic Approach}, url = {http://dblp.uni-trier.de/db/conf/focs/focs73.html#EhrigPS73}, year = 1973 }