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

Tytuł w języku angielskim

joint work with Alexander Rabinovich and Adam Radziwonczyk-Syta

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.

---