2026-07-23T04:53:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2312 2024-03-06T10:33:16Z ddc:004 open_access

The Wadge Hierarchy of Max-Regular Languages Cabessa, Jérémie Duparc, Jacques Facchini, Alessandro Murlak, Filip Max-regular languages Wadge hierarchy Wagner hierarchy Recently, Miko{\l}aj Boja{\'n}czyk introduced a class of max-regular languages, an extension of regular languages of infinite words preserving manyof 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 $\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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jérémie Cabessa and Jacques Duparc and Alessandro Facchini and Filip Murlak 2009 Is Part Of LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2009.2312 urn:nbn:de:0030-drops-23122 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2312 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode