Max=Muller, up to Wadge equivalence

Prelegent(ci)

Alessandro Facchini

Afiliacja

Lozanna

Termin

30 września 2009 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---