Regular tree languages in low levels of the Wadge Hierarchy

LOGICAL METHODS IN COMPUTER SCIENCE(2018)

引用 2|浏览11
暂无评分
摘要
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(Σ_1^0) (i.e. the union of the first ω levels); and for the Borel class Δ_2^0 (i.e. for the union of the first ω_1 levels).
更多
查看译文
关键词
regular tree languages,topology,algebraic characterisation
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要