Kurt Gödel Research Center

2011 seminar talk: The Monadic Second-Order Transduction Hierarchy

Talk held by Achim Blumensath (TU Darmstadt, Darmstadt, Germany) at the KGRC seminar on 2011-01-27.

Abstract

We study monadic second-order transductions between classes of finite structures. The main result is a complete description of the resulting hierarchy. It is linear of order type omega + 3. Each level has a combinatorial characterisation in terms of a suitable variant of tree-width. Canonical representatives of the various levels are: the class of (i) all trees of height n, for n < omega; (ii) all paths; (iii) all trees; and (iv) all grids.