Some complete $ω$-powers of a one-counter language, for any Borel class of finite rank
Olivier Finkel, Dominique Lecomte · arXiv (Cornell University) · 2020
We prove that, for any natural number n $\ge$ 1, we can find a finite alphabet $Σ$ and a finitary language L over $Σ$ accepted by a one-counter automaton, such that the $ω$-power L $\infty$ := {w 0 w 1. .. $\in$ $Σ$ $ω$ | $\forall$i $\in$ $ω$ w i $\in$ L} is $Π$ 0 n-complete. We prove a similar result for the class $Σ$ 0 n .