Max=Muller, up to Wadge equivalence

Speaker(s)

Alessandro Facchini

Affiliation

Lozanna

Date

Sept. 30, 2009, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

Recently, Mikolaj Bojanczyk introduced a class of max-regular languages, an extension of regular languages of infinite words preserving many of its usual properties. This new class can be seen as a different way of generalizing the notion of regularity from finite to infinite words. This paper compares regular and max-regular languages in terms of topological complexity. It is proved that up to Wadge equivalence the classes coincide. Moreover, when restricted to $\mathbf{\Delta}^0_2$-languages, the classes contain virtually the same languages. On the other hand, separating examples of arbitrary complexity exceeding $\mathbf{\Delta}^0_2$ are constructed.

---