On context-free sets of graphs and their monadic second-order theory. (English) Zbl 0643.68105

Graph-grammars and their application to computer science, 3rd Int. Workshop, Warrenton/Va. 1986, Lect. Notes Comput. Sci. 291, 133-146 (1987).
[For the entire collection see Zbl 0636.00013.]
The algebraic framework for studying graphs yields a notion of system of equations defining equational sets of graphs. Context-free graph grammars (where the rewriting step is the substitution a graph for an hyperedge) are defined. The context-free and the equational sets of graphs are the same. The monadic second-order theory of a context-free set of graphs is decidable.


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


Zbl 0636.00013