Some complete ω-powers of a one-counter language in the difference hierarchy

Abstract

Fix a finite alphabet Σ having at least two letters, and natural numbers n,k≥ 1. We denote by D_n(Π⁰_k) the class of differences of n subsets of the Cantor space Σ^ω in Π⁰_k, and by D^-_n(Π⁰_k) the class of complements of sets in D_n(Π⁰_k). We prove, for any natural numbers n,k≥ 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^∞:={ w₀w₁⋯∈Σ^ω|∀ i∈ω w_i∈ U_n,k} is D_2n−1(Π⁰_k)-complete. We also prove a conditional result for the dual classes D^-_2n(Π⁰_k): under the assumption that there exists a finitary language V_n,3 accepted by a one-counter automaton, such that its ω-power V_n,3^∞ is D^-_2n(Π⁰₃)-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 ω-power V_n,k^∞ is D^-_2n(Π⁰_k)-complete. Finally we add another conditionnal result about Wadge degrees of rational Δ⁰₂ omega powers, which completes the recent results of [FGL26].

On omega-powers of infinite difference rank
Maxim Vishnikin
arXiv7 Oct 2026PreprintarXiv licenceFull textLogic & foundationsarXiv
On the variety of sum of powers of certain complete intersection forms
Meghana Bhat, Ronnie Sebastian
arXiv15 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance
Fengqi Hou
arXiv30 Sep 2026PreprintarXiv licenceFull textGeneral mathematicsarXiv
Four-arm polyominoes in Golomb's hierarchy: A complete classification with Lean verification
Angel Ivanov Raychev
arXiv12 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Complete Bernstein functions and real powers of P-matrices
Wei Xie
arXiv1 Nov 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeX RIS

BibTeX

@misc{duparc2026some,
  title = {{Some complete ω-powers of a one-counter language in the difference hierarchy}},
  author = {Jacques Duparc and Olivier Finkel and Dominique Lecomte},
  howpublished = {HAL},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.16473},
  eprint = {2610.16473},
  archivePrefix = {arXiv},
  url = {https://hal.science/hal-05790654v1},
  note = {CC BY-NC-SA 4.0},
}

RIS

TY  - UNPB
TI  - Some complete ω-powers of a one-counter language in the difference hierarchy
AU  - Jacques Duparc
AU  - Olivier Finkel
AU  - Dominique Lecomte
PY  - 2026
DA  - 2026/10/09
PB  - HAL
DO  - 10.48550/arxiv.2610.16473
UR  - https://hal.science/hal-05790654v1
AB  - Fix a finite alphabet Σ having at least two letters, and natural numbers n,k≥ 1. We denote by D_n(Π^0_k) the class of differences of n subsets of the Cantor space Σ^ω in Π^0_k, and by D^-_n(Π^0_k) the class of complements of sets in D_n(Π^0_k). We prove, for any natural numbers n,k≥ 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^∞:={ w_0w_1⋯∈Σ^ω|∀ i∈ω w_i∈ U_n,k} is D_2n−1(Π^0_k)-complete. We also prove a conditional result for the dual classes D^-_2n(Π^0_k): under the assumption that there exists a finitary language V_n,3 accepted by a one-counter automaton, such that its ω-power V_n,3^∞ is D^-_2n(Π^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 ω-power V_n,k^∞ is D^-_2n(Π^0_k)-complete. Finally we add another conditionnal result about Wadge degrees of rational Δ^0_2 omega powers, which completes the recent results of [FGL26].
ER  -

Abstract

Related

Cite