Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Cabessa, Jérémie; Duparc, Jacques; Facchini, Alessandro; Murlak, Filip http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-23122
URL:

; ; ;

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 =		{http://dx.doi.org/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: 2009


DROPS-Home | Fulltext Search | Imprint Published by LZI