One-counter languages produce complex infinite word sets in difference hierarchy
Some complete $ω$-powers of a one-counter language in the difference hierarchy
Logic in Computer Science
Summary
Classifying infinite sequences of symbols can be very complicated, and mathematicians use a hierarchy to describe this complexity. The authors show that for any level in this hierarchy, there is a simple computational model called a one-counter automaton that can generate infinite sequences matching that level of complexity exactly. They also give conditional results about other related complexity classes under certain assumptions. This work helps us better understand the limits of simple machines in generating complex infinite patterns.
What this means in practice
- •For formal verification engineers: Identify precisely how complex infinite behaviors generated by simple automata can be classified, aiding in designing verification methods for systems with counters.
- •For automata theory tool developers: Improve tools analyzing infinite word languages by incorporating completeness results of omega-powers generated by one-counter automata within difference hierarchies.
A theory result. No direct application yet.
Authors
Jacques Duparc, Olivier Finkel, Dominique Lecomte
Abstract
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 $\checked{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 $D_{2n-1}(\mathbfΠ^0_k)$-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 $ω$-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 $ω$-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Δ^0_2$ omega powers, which completes the recent results of [FGL26].