Limits of interpretations and unfoldings

Prelegent(ci)

Laurent Braud

Afiliacja

Uniwersytet Warszawski

Termin

20 kwietnia 2011 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---