Papers for

automata theory tool developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

One-counter languages produce complex infinite word sets in difference hierarchy

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\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].

Mon 12 OctLogic in Computer Science
The gist
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.
Open → 2610.16473v1