On topological complexity of MSO+U over infinite words

Speaker(s)

Michał Skrzypczak

Affiliation

Uniwersytet Warszawski

Date

March 24, 2010, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

In [1] Bojańczyk considered WMSO+U logic and a new type of automata: max-automata. His main result is a conclusion that this logic is decidable over Ω. There arise the natural questions about expressive power of MSO+U. There is still no adequate automata model for this logic. In [2] autors showed that BS-automata (model strictly weaker then MSO+U) define some Σ0_4-complete languages. The aim of the speach is to show examples of languages definable in MSO+U, complete for all finite levels of Borel hierarchy.

[1] Mikołaj Bojanczyk, Weak MSO with the Unbounding Quantifier, CSTACS 2009 (2009) p. 159-170.
[2] Szymon Torunczyk, Szczepan Hummel, Topological complexity of Ω BS-regular languages, unpublished, 2010.

---