You are not logged in |
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.
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.
