文章基本信息

标题：The Wadge Hierarchy of Max-Regular Languages
本地全文：下载
作者：J{\'e}r{\'e}mie Cabessa ; Jacques Duparc ; Alessandro Facchini 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2009
卷号：4
页码：121-132
DOI：10.4230/LIPIcs.FSTTCS.2009.2312
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Max-regular languages; Wadge hierarchy; Wagner hierarchy