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.
The Monadic Second-Order Transduction Hierarchy
27.01.2011 15:00 - 16:30
Organiser:
KGRC
Location:
SR 101, 2. St., Währinger Str. 25