The Borel hierarchy is infinite in the class of regular sets of trees

DOI10.1016/0304-3975(93)90030-WzbMath0771.68077OpenAlexW1984317147MaRDI QIDQ1210306

Jerzy Skurczyński

Publication date: 24 May 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90030-w

zbMATH Keywords

Borel hierarchyinfinite treesweakly acceptable sets

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive set theory (03E15) Descriptive set theory (topological aspects of Borel, analytic, projective, etc. sets) (54H05)

Related Items (9)

Index Problems for Game Automata ⋮ Regular languages of thin trees ⋮ On the Weak Index Problem for Game Automata ⋮ Borel hierarchy and omega context free languages. ⋮ A gap property of deterministic tree languages. ⋮ On the Strength of Unambiguous Tree Automata ⋮ Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata ⋮ A Characterisation of Pi^0_2 Regular Tree Languages ⋮ An upper bound on the complexity of recognizable tree languages

Cites Work

• Topological characterizations of infinite tree languages
• On ω-regular sets
• Some examples of Borel sets
• Definability in the monadic second-order theory of successor
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The Borel hierarchy is infinite in the class of regular sets of trees