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.


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.

Bottom menu

Kurt Gödel Research Center for Mathematical Logic. Währinger Straße 25, 1090 Wien, Austria. Phone +43-1-4277-50501. Last updated: 2010-12-16, 04:37.