On topological complexity of MSO+U over infinite words

Prelegent(ci)

Michał Skrzypczak

Afiliacja

Uniwersytet Warszawski

Termin

24 marca 2010 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---