首页    期刊浏览 2024年09月18日 星期三
登录注册

文章基本信息

  • 标题: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
国家哲学社会科学文献中心版权所有