On the Borel complexity of MSO definable sets of branches
- Prelegent(ci)
- Damian Niwiński
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 13 stycznia 2010 14:15
- Pokój
- p. 5870
- Seminarium
- Seminarium „Teoria automatów”
What sets of infinite words can be defined by means of MSO formulas
interpreted in a binary tree, if we additionally allow some monadic
predicates over the nodes ? We show that topologically these
languages are no more complex than ordinary omega-regular languages.
The proof goes via a characterization of this class by Buchi
automata with advice, which can be determinized by a suitable
adaptation of the classical Safra construction.