paperbot · PL 论文追踪

RSS

Regular tree languages in low levels of the Wadge Hierarchy

LMCS vol.Volume 15, Issue 32019
Mikołaj Bojańczyk, Filippo Cavallari, Thomas Place, Michał Skrzypczak

尚未生成 AI 速览(可能缺少 API key 或等待下次运行补跑)。

原文摘要(Abstract)

In this article we provide effective characterisations of regular languages of infinite trees that belong to the low levels of the Wadge hierarchy. More precisely we prove decidability for each of the finite levels of the hierarchy; for the class of the Boolean combinations of open sets $BC(\Sigma_1^0)$ (i.e. the union of the first $\omega$ levels); and for the Borel class $\Delta_2^0$ (i.e. for the union of the first $\omega_1$ levels).

链接与引用

DOI 原文 ·

BibTeX
@article{paperbot758,
  title = {Regular tree languages in low levels of the Wadge Hierarchy},
  author = {Mikołaj Bojańczyk and Filippo Cavallari and Thomas Place and Michał Skrzypczak},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 15, Issue 3},
  year = {2019},
  doi = {10.23638/lmcs-15(3:27)2019}
}