Algorithmic Model Theory

Expressive Power of Monadic Second-Order Logic

In the last two decades the beginnings of a model theory for monadic second-order logics were developed. Of particular interest are questions of definability and interpretability in given structures.

On one hand, there are structures whose monadic theory is simple enough to admit a structure theory. All known examples of such structures have the property of being interpretable in a tree.

On the other hand, there are structures whose monadic theory is extremely complicated. A prominent example are structures containing large definable grids. According to a conjecture of Seese these two extremes form a dichotomy: either a structure can be interpreted in a tree, or it contains a large grid.

  1. One emphasis of our work is on different kinds of interpretations. In particular, we try to characterise all structures that can be interpreted in a given one and to develop concrete combinatorial criteria for the existence ofan interpretation between two given (classes of) structures [BC10]. Considering the conjecture of Seese, interpretations in trees are of particular importance [B06].
  2. A further topic of our work concerns variants of monadic second-order logic. An important extension of this logic is guarded second-order logic, which in general is strictly more expressive. According to a result of Courcelle, however, on countable sparse structures the expressive power of guarded second-order logic collapses to that of monadic second-order logic.[B10]

Bibliography

[BC10] Achim Blumensath and Bruno Courcelle, On the Monadic Second-Order Transduction Hierarchy, Logical Methods in Computer Science, 6(2010).

[B06] Achim Blumensath, A Model Theoretic Characterisation of Clique-Width, Annals of Pure and Applied Logic, 142(2006), pp. 321-350.

[B10] Achim Blumensath, Guarded Second-Order Logic, Spanning Trees, and Network Flows, Logical Methods in Computer Science, 6(2010).

A A A | Print Print | Impressum Legal note | Contact Contact
    zum Seitenanfangzum Seitenanfang