CS Paper Radar

Pumping Constants for Infinite Alphabets

Yoav Danieli

cs.FL ·submitted 2026-10-05 17:08 UTC · v1
publishedtheoryhot direction

Abstract

It is well known that the pumping lemma for regular languages over finite alphabets does not extend to infinite alphabets. Instead, the generalized version of the pumping lemma for infinite alphabets states that the pumped patterns need not be identical, but only equivalent up to a finite-order permutation of the alphabet. This generalized variant of the pumping lemma involves two parameters: the length of the pumped pattern and an upper bound on the order of the permutation. We improve the known permutation-order bounds from factorial to tight bounds governed by Landau's function. We also show that, if the pumping length is sufficiently large, then permutations of order at most two always suffice. Our main structural result concerns the one-register case: every one-register automaton satisfies the classical pumping lemma, with no alphabet permutation. We prove a quadratic upper bound on the pumping length and give a matching quadratic lower bound up to constant factors. The same classical pumping phenomenon is shown for hierarchical register automata. Finally, we prove that, in general, deciding whether a quasi-regular language is pumpable for given constants is undecidable, while the minimal classical pumping length is computable for non-guessing one-register automata.

Comment
In Proceedings AFL 2026, arXiv:2608.23071
Journal ref
EPTCS 451, 2026, pp. 104-122
DOI
10.4204/EPTCS.451.8

Closest papers

Nearest neighbours by meaning across the whole index.

Witness Languages for Pumping Lemmata

cs.FL ·2026-10-11 ·Pamela Fleischmann, Annika Huch, Christian Rauch
similarity 0.68
Abstract

In 2022 Dassow and Jecker started investigations on the operational complexity of the pumping constant w.r.t.~two pumping lemmata. Since then, the research on pumping lemmata emerged to several variants for regular as well as context-free languages. Within this work, we further investigate the \emph{witnesses} of regular languages (firstly introduced by Rauch) w.r.t.~different pumping lemmata: For a language $L$ and a minimal pumping constant $K$, a \emph{witness} of a language is a word that cannot be \emph{pumped} by $K$ w.r.t.~the given pumping lemma. Here, the pumping constant is minimal if for all smaller numbers, the pumping lemma condition is not satisfied. Alongside combinatorial investigations on (unary) witness languages, we introduce and study the measure of scattered factor distance, which is related to minimal pumping constants. We present bounds on minimal pumping constants by the scattered factor distance and show that deciding, given two regular languages, whether one of them is equal to the witness language of the second is \coNP-complete.

0.30

Turn Complexity and Bounded Languages

cs.FL ·2026-08-25 ·Giovanni Pighizzini
publishedtheoryhot direction similarity 0.67
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

A turn or reversal in a computation of a pushdown automaton is a switch from a phase in which the height of the pushdown store increases to a phase in which it decreases. Given a pushdown automaton, we first consider, for each string in its language, the minimum number of turns made in accepting computations (weak measure). We prove that it is decidable whether a pushdown automaton accepts a bounded language in a constant number of turns and whether it accepts a bounded language in k turns, for any given k>=0. This is in contrast to the general case, in which these problems are known to be undecidable, with the exception of acceptance in 0 turns, which is decidable. Furthermore, we prove that when the number of turns sufficient to accept a bounded language is not limited by any constants, it linearly grows with respect to the input length. Also this is in contrast with the general case where, for each nonnegative k, there exists a language for which the number of turns necessary and sufficient is of the order of log^(k), the k times composition of the logarithm with itself. We also prove that, when the costs of all accepting computations are taken into account (accept measure), a linear lower bound for the number of turns, if not limited by any constants, holds even removing the restriction to bounded languages.

0.43

Deterministic Bandwidth of Finite Languages

cs.FL ·2026-08-25 ·Da-Jung Cho, Szilárd Zsolt Fazekas, Max Wiedenhöft
publishedtheory similarity 0.62
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

Bandwidth restricts how far transitions can move under an ordering of the states in an automaton. While every finite language admits a bandwidth-2 NFA representation, the deterministic setting is substantially more restrictive. We investigate the bandwidth of partial DFAs accepting finite languages. We show that bounded bandwidth imposes strong structural restrictions on deterministic representations. We prove that there is an infinite hierarchy of classes of finite languages defined by deterministic bandwidth. As a special case of interest, we consider finite languages accepted by bandwidth-1 partial DFAs, and show that they admit a positional characterization, which yields a polynomial-time decision algorithm. We further study how the minimum DFA bandwidth can be estimated from the structure of the minimal DFA. We derive computable upper and lower bounds based on position-unfolding, and local growth of reachable residual states. These bounds can be computed efficiently and differ by at most a linear factor in the maximum word length. We also present a simple language family where the bounds match exactly.

0.48

Prime Accessible Deterministic Automata

cs.FL ·2026-10-09 ·Shen Zhao, Chenghe Xu
similarity 0.61
Abstract · 21 pages, 4 figures

We classify prime accessible deterministic automata over finite alphabets, both among finite automata and among automata with arbitrary state sets. Every one-state automaton is prime. Over a one-letter alphabet, a finite nontrivial automaton is prime exactly when it is a cycle of prime-power length or a finite chain ending in a fixed state. The unique infinite accessible unary automaton, up to isomorphism, is also prime. Every nontrivial automaton over an alphabet with at least two letters is not prime. Shen proved the finite case; we give a shorter proof. We also characterize a decomposition of the automaton whose states are all finite input words. The reachable product of the quotients by the least right congruences identifying the empty word with nonempty words $p$ and $q$, respectively, is isomorphic to this automaton exactly when $p^r\ne q^s$ for all positive integers $r,s$.

0.39

An Improved Lower Bound for Separating Words by Permutation Automata

cs.FL ·2026-10-08 ·Chen Xu, Kenneth Regan
theoryhot direction similarity 0.61
Abstract

We prove that some pairs of binary words of every sufficiently large prescribed length $n$ require $Ω(\log n\log\log n)$ states to separate by a deterministic finite automaton whose letters act as permutations. We obtain this bound by constructing distinct equal-length positive binary words that form an identity of $\mathfrak{S}_k$ of length $\exp(O(k/\log k))$. This improves the previous lower bound $(3/2-o(1))\log n$ of Bulatov, Karpova, Shur, and Startsev (arXiv:1609.03199). The proof combines a positive-word construction with a cover of permutation orders. Consecutive segments of prime powers reduce the covering problem to enumerating sets of positive integers with bounded sum. The required estimates use the central binomial coefficient and the classical asymptotic formula for partitions into distinct parts. An appendix gives sharper constants and lower-order terms using a greedy cover and a quantitative prime number theorem.

0.28

Algebraic Decomposition Theory for Transformer Length Generalization

cs.FL cs.AI ·2026-08-13 ·Andy Yang, Blerta Veseli, Corentin Barloy, Michaël Cadilhac, Andreas Krebs +3 more
similarity 0.60
Abstract · 54 pages, 12 figures

Transformer-based language models are known to sometimes generalize to sequences longer than seen during training, but we lack a precise characterization of which tasks admit length generalization. It is not even known which regular languages transformers length-generalize on -- and this is a foundational class of languages. Our contributions are to establish the first complete characterization of which regular languages transformers length-generalize on and provide a decision algorithm running in polynomial time in the size of the language's syntactic monoid. These results rely on an effective characterization of the regular languages in C-RASP, a recently-established formalism that expresses which languages transformers length-generalize on. This characterization is challenging because classical tools like Krohn-Rhodes decomposition theory for finite semigroups are insufficient for C-RASP. Firstly, the basic building blocks of Krohn-Rhodes theory -- flip-flop and simple groups -- are not expressible in C-RASP. Secondly, the basic building block of C-RASP (unbounded counting) is not expressible by the finite semigroups of Krohn-Rhodes theory. Thus, length generalization on regular languages is controlled by an algebraic property that is invisible to classical finite decomposition theory. We generalize classical decomposition theory from finite semigroups to the infinite additive group on the integers, allowing us to characterize C-RASP in terms of iterated wreath products of the integers and derive a provable polynomial-time decision algorithm for regular language membership. Experiments across a broad test suite of regular languages confirm that our theory captures transformers' length-generalization behavior more accurately than existing classifications.

0.43

Semi-Linearity and Generalized Stratified Semi-Linearity beyond Context-Free Languages

cs.FL cs.CC ·2026-10-14 ·Tomoyuki Yamakami
theory similarity 0.60
Abstract · (10pt, 6 figures, 21 pages) This is a preliminary report

Parikh's famous theorem relates to the semi-linearity of context-free languages. We seek for expanding the scope of the semi-linear property from context-free languages to languages beyond them. Of those languages, this work focuses on the languages that are particularly recognized by one-way nondeterministic depth-k storage automata under a natural restriction of frozen blank sensitivity. Those languages (which are called $k$-storable languages) have been already proven to satisfy a natural generalization of the well-known pumping lemmas for regular and context-free languages. The semi-linearity of k-storable languages generalizes Parikh's theorem on the semi-linearity of context-free languages. As for bounded languages, Ginsburg and Spanier's well-known theorem characterizes context-free languages in terms of stratified semi-linearity. This notion is further generalized and is used to characterize the k-storable languages as well. Such a generalization is interesting in its own right. This helps us take an abstract treatment of k-storable languages without relying on "machines". Our results strengthen the belief that those languages are "natural" generalizations of context-free languages.

0.47

Subsequence Analysis Problems for Binary Parikh Matrices

cs.FL cs.CC ·2026-10-05 ·Szilárd Zsolt Fazekas, Xinhao Huang, Robert Mercaş
publishedtheory similarity 0.60
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

The universality index corresponding to a word is the largest integer k such that every word of length k over the given alphabet occurs in it as a subsequence. Relative to languages this notion can be investigated with respect to both existential and universal quantifiers, with the former corresponding to the existence of a word in the language with universality index at least k, while the latter considers the index across all words that the language contains. In this work we study the existential (exists-universality) and universal (forall-universality) subsequence universality (as introduced in [Adamson et al., ISAAC 2023]) for binary languages consisting of all words with a fixed number of letters a, letters b, and subsequences ab. We prove that both exists- and forall-universality admit exact arithmetic characterizations for these languages. Extending the above notions, we end the paper by initiating the analysis of the probability of a fixed word occurring as subsequence of the words in such a language. To this end, we prove that, for every fixed pattern word w and an error tolerance, given as input the subsequence counts describing a language, the ratio of words in the language having the pattern w as a subsequence admits an additive approximation scheme that is polynomial-time in the binary encoding of the input counts.

0.49