An algebraic theory of graph reduction. (English) Zbl 0765.68062

Graph grammars and their application to computer science, Proc. 4th Int. Workshop, Bremen/Ger. 1990, Lect. Notes Comput. Sci. 532, 70-83 (1991).
Summary: [For the entire collection see Zbl 0753.00023.]
We show how membership in classes of graphs definable in monadic second order logic and of bounded treewidth can be decided by finite sets of terminating reduction rules. The method is constructive in the sense that we describe an algorithm which will produce, from a formula in monadic second order logic and an integer \(k\) such that the class defined by the formula is of treewidth \(\leq k\), a set of rewrite rules that reduces any member of the class to one of finitely many graphs, in a number of steps bounded by the size of the graph. This reduction system corresponds to an algorithm that runs in time linear in the size of the graph.


68Q42 Grammars and rewriting systems
68R10 Graph theory (including graph drawing) in computer science


Zbl 0753.00023