cs.LOOct 12, 2026

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

Authors: Jacques Duparc, Olivier Finkel, Dominique Lecomte

Organizations: UNIL · Université de Lausanne, Département des opérations, HEC Lausanne, CH-1015, Lausanne, Switzerland · EPFL, Mathematics Section, School of Basic Sciences, CH-1015, Lausanne, Switzerland · IMJ-PRG · 

Abstract

Fix a finite alphabet ΣΣ having at least two letters, and natural numbers n,k≥1n,k\geq 1. We denote by Dn(Πk0)D_n(\mathbfΠ^0_k) the class of differences of nn subsets of the Cantor space ΣωΣ^ω in Πk0\mathbfΠ^0_k, and by Dn−(Πk0)D^-_n(\mathbfΠ^0_k) the class of complements of sets in Dn(Πk0)D_n(\mathbfΠ^0_k). We prove, for any natural numbers n,k≥1n,k\geq 1, the existence of a finite alphabet ΣΣ having at least two letters and a finitary language Un,kU_{n,k} over ΣΣ accepted by a one-counter automaton such that the ωω-power Un,k∞:={w0w1⋯∈Σω∣∀i∈ω  wi∈Un,k}U_{n,k}^\infty:=\{ w_0w_1\cdots\inΣ^ω\mid\forall i\inω~~w_i\in U_{n,k}\} is D2n−1(Πk0)D_{2n-1}(\mathbfΠ^0_k)-complete. We also prove a conditional result for the dual classes D2n−(Πk0)D^-_{2n}(\mathbfΠ^0_k): under the assumption that there exists a finitary language Vn,3V_{n,3} accepted by a one-counter automaton, such that its ωω-power Vn,3∞V_{n,3}^\infty is D2n−(Π30)D^-_{2n}(\mathbfΠ^0_3)-complete, there would also exist, for any integer k>3k > 3, a finitary language Vn,kV_{n,k} accepted by a one-counter automaton, such that its ωω-power Vn,k∞V_{n,k}^\infty is D2n−(Πk0)D^-_{2n}(\mathbfΠ^0_k)-complete. Finally we add another conditionnal result about Wadge degrees of rational Δ20\mathbfΔ^0_2 omega powers, which completes the recent results of [FGL26].

Explore similar work

Aug 28, 2026

An algebraic proof of Colombo's difference-power determinant conjecture

Let n≥2n\ge2 be even, let λ=(λ1,…,λn)∈Rnλ=(λ_1,\ldots,λ_n)\in\mathbb{R}^n have pairwise distinct coordinates, and define the difference-power matrix Ad(λ):=[(λr−λs)d]r,s=1n,d∈N.A_d(λ) := \bigl[(λ_r-λ_s)^d\bigr]_{r,s=1}^n, \qquad d\in\mathbb{N}. In 1928, Colombo proved that det⁡An−1(λ)≠0\det A_{n-1}(λ)\ne0---and hence det⁡An−1(λ)>0\det A_{n-1}(λ)>0---and that rank⁡Ad(λ)=d+1\operatorname{rank} A_d(λ)=d+1 for 0≤d<n−10\le d<n-1. He conjectured that det⁡Ad(λ)≠0for every d≥n−1.\det A_d(λ)\ne0 \qquad\text{for every } d\ge n-1. For even dd, the conjectured nonsingularity follows from previously published results on distance-power matrices. The remaining open cases were therefore the supercritical odd exponents d≥n+1d\ge n+1. We prove nonsingularity for all these odd exponents, thereby completing Colombo's conjecture. Consequently, rank⁡Ad(λ)=min⁡{n,d+1}(d∈N).\operatorname{rank} A_d(λ)=\min\{n,d+1\} \qquad(d\in\mathbb{N}). Our proof converts a hypothetical kernel vector into a real binary form having more projective real linear factors, counted with multiplicity, than its real Waring length permits.
Jun 1, 2026

An Algebraic View of the Expressivity of Recurrent Language Models

What formal languages can a recurrent neural language model recognize? Formal results in the literature conflict: some authors report Turing-completeness, while others show equivalence to regular languages. The reason for this discrepancy is that the underlying arithmetic model differs. The paper develops a unified algebraic account of the expressivity of recurrent neural networks, starting with a formal account of various arithmetic models. This account reduces expressivity to an algebraic question, e.g., whether a network's syntactic monoid divides a certain wreath product. As a case study, the paper revisits diagonal state-space models: the same architecture cannot implement an even-modulus counter once floating-point recurrences are enforced, yet realizes every even-modulus counter under unsigned-integer quantization.
Sep 9, 2026

Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy

Language generation in the limit asks for valid unseen elements from every exhaustive positive presentation of an unknown infinite language. We characterize this task for arbitrary families over a countable universe. Generation is possible exactly when each target can be assigned a finite positive witness so that the targets activated by any finite sample have an infinite common intersection. The necessary direction follows from a universal normalization: a search through unconfirmed histories converts any successful generator into one depending only on the observed set. We then ask how large compatible witnesses must be. Positive separation width records the smallest uniform size bound, with two further levels for unbounded finite witnesses and the absence of any compatible finite-witness assignment. Every level occurs. Countable families admit singleton witnesses, explicit families realize every finite width, and a union of two families with infinite common cores requires unbounded finite witnesses. Finally, countable-support and finite-profile obstructions explain why local combinatorial data cannot determine generation in the limit. The characterization and full width hierarchy are checked in Lean, including the simplified normalization and a direct diagonal capture lemma. The accompanying Lean development is maintained at https://github.com/xiaoyulics/language-generation-characterization