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: https://drops.dagstuhl.de/opus/volltexte/2009/2312/
Cabessa, Jérémie ; Duparc, Jacques ; Facchini, Alessandro ; Murlak, Filip
The Wadge Hierarchy of Max-Regular Languages
| pdf-format: |
|
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 | |
| Seminar: | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science | |
| Issue date: | 2009 | |
| Date of publication: | 14.12.2009 |
