Limits of interpretations and unfoldings

Speaker(s)

Laurent Braud

Affiliation

Uniwersytet Warszawski

Date

April 20, 2011, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

The original motivation was the characterisation of more structures
with decidable MSO theory. We consider the transformation approach :
operations that preserve decidability include MSO-interpretations and
unfoldings, which can be used to build the Caucal hierarchy. In an
attempt to extend the latter, we consider a limit operation using
these operations. We prove that even with FO-interpretations and
starting with a finite tree, we can build a limit tree with
undecidable FO theory.

---