Some complete $\omega$-powers of a one-counter language in the difference hierarchy

Abstract

Fix a finite alphabet $\Sigma$ having at least two letters, and natural numbers $n,k\ge 1$. We denote by $D_n({\mathbf{\Pi }}_k^0)$ the class of differences of $n$ subsets of the Cantor space ${\Sigma }^{\omega }$ in ${\mathbf{\Pi }}_k^0$, and by $\checked{D}_n(\mathbfΠ^0_k)$ the class of complements of sets in $D_n({\mathbf{\Pi }}_k^0)$. We prove, for any natural numbers $n,k\ge 1$, the existence of a finite alphabet $\Sigma$ having at least two letters and a finitary language $U_{n,k}$ over $\Sigma$ accepted by a one-counter automaton such that the $\omega$-power $$U_{n,k}^{\infty }:=\{w_0{w}_1\cdots \in {\Sigma }^{\omega }\mid \forall i\in \omega w_i\in U_{n,k}\}$$ is $D_{2n-1}({\mathbf{\Pi }}_k^0)$-complete. We also prove a conditional result for the dual classes $\checked{D}\_{2n}(\mathbfΠ^0\_k)$: under the assumption that there exists a finitary language $V_{n,3}$ accepted by a one-counter automaton, such that its $\omega$-power $V_{n,3}^{\infty }$ is $\checked{D}_{2n}(\mathbfΠ^0_3)$-complete, there would also exist, for any integer $k>3$, a finitary language $V_{n,k}$ accepted by a one-counter automaton, such that its $\omega$-power $V_{n,k}^{\infty }$ is $\checked{D}_{2n}(\mathbfΠ^0_k)$-complete. Finally we add another conditionnal result about Wadge degrees of rational ${\mathbf{\Delta }}_2^0$ omega powers, which completes the recent results of [FGL26].