Nie jesteś zalogowany | Zaloguj się

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.