License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2312
URN: urn:nbn:de:0030-drops-23122
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2312/
Cabessa, Jérémie ;
Duparc, Jacques ;
Facchini, Alessandro ;
Murlak, Filip
The Wadge Hierarchy of Max-Regular Languages
Abstract
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.
BibTeX - Entry
@InProceedings{cabessa_et_al:LIPIcs:2009:2312,
author = {J{\'e}r{\'e}mie Cabessa and Jacques Duparc and Alessandro Facchini and Filip Murlak},
title = {{The Wadge Hierarchy of Max-Regular Languages}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {121--132},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-13-2},
ISSN = {1868-8969},
year = {2009},
volume = {4},
editor = {Ravi Kannan and K. Narayan Kumar},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2312},
URN = {urn:nbn:de:0030-drops-23122},
doi = {10.4230/LIPIcs.FSTTCS.2009.2312},
annote = {Keywords: Max-regular languages, Wadge hierarchy, Wagner hierarchy}
}
Keywords: |
|
Max-regular languages, Wadge hierarchy, Wagner hierarchy |
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
Issue Date: |
|
2009 |
Date of publication: |
|
14.12.2009 |