×

zbMATH — the first resource for mathematics

A representation of graphs by algebraic expressions and its use for graph rewriting systems. (English) Zbl 0643.68104
Graph-grammars and their application to computer science, 3rd Int. Workshop, Warrenton/Va. 1986, Lect. Notes Comput. Sci. 291, 112-132 (1987).
[For the entire collection see Zbl 0636.00013.]
We define a set of operations on graphs and an algebraic notation for finite graphs. A complete axiomatization of the equivalence of graph expressions by equational rules is given. Graph rewriting systems can be defined as rewriting systems on graph expressions. This new definition is equivalent to the classical one using double push-outs.

MSC:
68Q45 Formal languages and automata
08B05 Equational logic, Mal’tsev conditions
68R10 Graph theory (including graph drawing) in computer science
03B10 Classical first-order logic
68Q65 Abstract data types; algebraic specification