Some regular ω-powers in the Hausdorff-Kuratowski hierarchy

Theoretical Computer Science 2026 Open access

Read full text
Authors: Olivier Finkel, Johan Girardot, Dominique Lecomte
DOI: 10.1016/j.tcs.2026.115838
Cited by: 0

Abstract

Fix a finite alphabet Σ having at least two letters, and an arbitrary natural number n . We denote by D n ( Π 2 0 ) the class of differences of n Π 2 0 subsets of the Cantor space Σ ω , and by D n − ( Π 2 0 ) the class of complements of sets in D n ( Π 2 0 ) . We prove the existence of finitary regular languages U n and V n such that ( U n ) ω is D 2 n + 1 ( Π 2 0 ) -complete and ( V n ) ω is D 2 n + 2 − ( Π 2 0 ) -complete.

Fields of Study & Subjects

semigroups and automata theory Advanced Algebra and Logic Computability Logic AI Algorithms

Publication details

Journal / source
Theoretical Computer Science
Volume
1072
Pages
115838–115838
Publication date
1 March 2026
Language
EN