{"id":"arxiv/2610.16473","url":"https://arxiv.org/abs/2610.16473","tags":["cs.LO","cs.FL","cs.GT","math.GN","math.LO"],"score":0,"title":"Some complete $ω$-powers of a one-counter language in the difference hierarchy","domain":"cs.LO","source":"arxiv","authors":["Jacques Duparc","Olivier Finkel","Dominique Lecomte"],"reviews":0,"subject":"cs.LO","summary":"Fix a finite alphabet $Σ$ having at least two letters, and natural numbers $n,k\\geq 1$. We denote by $D_n(\\mathbfΠ^0_k)$ the class of differences of $n$ subsets of the Cantor space $Σ^ω$ in $\\mathbfΠ0_k$, and by $D_n-(\\mathbfΠ^0_k)$ the class of complements of sets in $D_n(\\mathbfΠ^0_k)$. We prove, for any natural numbers $n,k\\geq 1$, the existence of a finite alphabet $Σ$ having at least two letters and a finitary language $U_{n,k}$ over $Σ$ accepted by a one-counter automaton such that the $ω$-power $$U_{n,k}^\\infty:={ w_0w_1\\cdots\\inΣ^ω\\mid\\forall i\\inω~~w_i\\in U_{n,k}}$$ is…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-12","reactions":{}}