Abstract | ||
---|---|---|
Recently, Mikoaj Boja ´ nczyk 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 generalising 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 D0 2-languages, the classes contain virtually the same languages. On the other hand, separating examples of arbitrary complexity exceeding D0 2 are constructed. |
Year | DOI | Venue |
---|---|---|
2009 | 10.4230/LIPIcs.FSTTCS.2009.2312 | FSTTCS |
Field | DocType | Citations |
Discrete mathematics,Combinatorics,Abstract family of languages,Equivalence (measure theory),Regular language,Pumping lemma for regular languages,Wadge hierarchy,Mathematics | Conference | 0 |
PageRank | References | Authors |
0.34 | 6 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jérémie Cabessa | 1 | 38 | 8.47 |
Jacques Duparc | 2 | 109 | 18.35 |
Alessandro Facchini | 3 | 35 | 9.47 |
Filip Murlak | 4 | 184 | 19.14 |