Noleen Köhler (University of Leeds) – MSO-transducing tree-like graph decompositions

Thatcher and Wright showed that a property of trees of bounded degree is MSO-definable if and only if it is recognizable by a tree-automaton. In this talk we explore the question of when MSO-definability of a property of graphs is equivalent to the existence of a tree automata which, given a suitable expression encoding the input graph, recognizes the property. In this talk, I will survey the state of the art of the "definability equals recognizability" problem. For proving "definability equals recognizability" results the key step is to transduce a suitable tree-like decomposition of the input graph. I will present a new MSO-transduction which forms the core for transducing a particular type of graph decompositions.