Finite Model Theory characterization of some graph grammars
Alex Glikson
aglik@cs.technion.ac.il
(joint work with J. Makowsky,
janos@cs.technion.ac.il
)
Abstract
There are several graph sparsity conditions, that allow polynomial recognition
and/or model-checking over graphs and hypergraphs. Two of them are tree-width
and clique-width. We examine graph classes generated by various graph grammars
and other grammar-like methods. Although most of them are already known to
be of bounded tree-width/
clique-width, for some of them no strait-forward way to find these bounds
is known. We use several old and recent techniques in order to classify these
classes and to find explicitly the bounds for tree-width and clique-width
of corresponding graphs.