CS Paper Radar

Prime Accessible Deterministic Automata

Shen Zhao, Chenghe Xu

cs.FL ·submitted 2026-10-09 09:25 UTC · v1

Abstract

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$.

Comment
21 pages, 4 figures

Closest papers

Nearest neighbours by meaning across the whole index.

An Improved Lower Bound for Separating Words by Permutation Automata

cs.FL ·2026-10-08 ·Chen Xu, Kenneth Regan
theoryhot direction similarity 0.63
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

The Emptiness Problem for Quantum Finite Automata with Classical States

cs.FL ·2026-08-29 ·Jyun-Ao Lin, Patrick Totzke, Yun Chen Tsai, Di-De Yen
similarity 0.62
Abstract

Quantum Finite Automata with Classical states (QFACs) are nondeterministic finite automata over a finite alphabet of quantum operations. We study expressiveness of this model on finite words and the corresponding emptiness problem. We show that regular languages are incomparable with those definable by Quantum Finite Automata (QFAs) and that both are strictly subsumed by QFAC-definable languages. We show that the emptiness problem for a QFAC can be reduced to the emptiness of the language intersection of a QFA and a finite automaton. This intersection is known to be decidable for strict thresholds but undecidable for non-strict cases. Furthermore, we consider the problem for flat QFACs, a restriction where the underlying automata contain no nested loops, and relate it to the higher-dimensional orbit problem, a long-standing open challenge in dynamical systems. Finally, we propose a sound and semi-complete witness searching procedure to verify the non-emptiness of one-loop QFACs, which are sufficiently expressive to represent some prominent quantum algorithms, such as Grover's search and quantum random walks.

0.31

Pumping Constants for Infinite Alphabets

cs.FL ·2026-10-05 ·Yoav Danieli
publishedtheoryhot direction similarity 0.61
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

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.

0.68

Hardness and Approximation for Compressing Deterministic Finite Automata

cs.DS ·2026-10-22 ·Philip Bille, Inge Li Gørtz, Christoffer Krogh, Christian Møller Mikkelstrup
similarity 0.60
Abstract · 18 pages, 4 figures. Has been submitted for review

The delayed deterministic finite automaton ($\text{D}^2\text{FA}$) is a powerful tool for compressing the prohibitively large deterministic finite automata (DFAs) used in modern signature-based deep packet inspection systems. A $\text{D}^2\text{FA}$ augments a DFA with unlabeled default transitions to remove transitions that are similar. This technique works well in practice and has inspired numerous subsequent studies. However, existing approaches do not guarantee a $\text{D}^2\text{FA}$ of optimal size as they restrict the default transitions to form a forest. In this paper, we consider the problem of finding an optimal $\text{D}^2\text{FA}$. We make the key observation that cycles of default transitions can be valid and produce a smaller $\text{D}^2\text{FA}$, provided that for every character in the alphabet, at least one state in the cycle has an outgoing transition labeled by that character. This observation raises fundamental questions concerning the computational complexity of finding an optimal $\text{D}^2\text{FA}$ and the approximation guarantee of the standard (forest-restricted) approach. We answer both questions by showing that it is NP-hard to find an optimal $\text{D}^2\text{FA}$ and by proving that the standard approach provides a $3/2$-approximation to the optimum. To establish NP-hardness, we construct a reduction from set cover using a DFA with gadgets where valid default transition choices correspond to selecting sets. To prove our approximation ratio, we compare the cycles in an optimal solution to a variant where the default transitions form a forest. Finally, we demonstrate that this $3/2$ ratio is tight via a constructed family of DFAs.

0.17

Automata for MSO over Infinite Trees with Quantification over Borel Sets of Branches

cs.FL cs.LO ·2026-11-06 ·Mikołaj Bojańczyk, Antonio Casares, Sven Manthe, Paweł Parys
top venuetheory similarity 0.59
Abstract

Rabin's Tree Theorem says that the MSO theory of the infinite binary tree $2^*$ is decidable. Shelah showed that MSO logic becomes undecidable if this tree is extended to $2^{\le ω}$, i.e. by allowing quantification over sets of infinite branches. A longstanding open problem is whether the decidability can be recovered in $2^{\le ω}$ by restricting set quantification to Borel sets. We make some progress in this direction, by identifying a suitable automaton model, and showing that most of the automata-theoretic approach to Rabin's Theorem can be extended to the new framework. The only missing part is a conjecture about finite-memory determinacy in certain games. This paper states and explores the conjecture. We prove it in some restricted cases, and give lower bounds on the memory required in those games.

0.70

Shortest Synchronizing Words on Product Automata

cs.FL ·2026-11-06 ·Henning Fernau, Igor Rystsov
similarity 0.58
Abstract

We consider some operations on finite automata graphs, in particular various product, union and merge operations, and investigate how they relate to the parameter~$\mathrm{rt}$, the \emph{length of a shortest synchronizing word}. We derive some lower and upper bounds for the operations that we study. We also examine several classes of automata (for instance, partially ordered, commutative or idempotent automata) that are preserved under these operations and show in which way the parameter $\mathrm{rt}$ behaves in these automata classes. Also, we consider automata classes that can be constructed by combining automata from better known classes; in particular, these new classes of automata will also satisfy the bound of the famous Černý conjecture. This also motivates us to study even more closure properties. In particular, we show that certain automata classes related to synchronization form pseudo-varieties. We also commence a similar study concerning the length of shortest homing sequences of Mealy automata.

0.13

Unary Versus Binary Two-Way Automata

cs.FL ·2026-08-25 ·Viliam Geffert, Vincent Hlaváč, Rastislav Královič
publishedhot direction similarity 0.58
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

If L is a unary language, then its binary coded version bin(L) is a binary language containing all binary strings representing any 0^x in L. It is known that if a unary language L is regular and can be recognized by a minimal one-way deterministic finite automaton (1DFA) with n states, then its binary coded version is also regular and can be recognized by a 1DFA with at most n states, but at least 1+log(n) states. Here we shall present related results for two-way automata (2DFAs). First, we shall show that each unary 2DFA A' with n states can be converted to a 2DFA A'' recognizing bin(L(A')) with at most O(n.log n) states. If A' is minimal and uses only loops of odd lengths, A'' will use at most 2n+2 states, but it must use at least n states. For each n>=7, we shall also present a unary witness language for which a minimal 2DFA uses exactly n states, but any minimal 2DFA recognizing its binary coded version uses at least n states, but less than n+log(n) states.

0.46

Solution to Bucher's density problem for context-free languages

cs.FL ·2026-09-08 ·Rastko Maslic, Jeffrey Shallit
similarity 0.57
Abstract

In 1980 Bucher asked whether, given context-free languages $L\subseteq U$ with $U\setminus L$ infinite, there must be a context-free language $K$ between them for which both $K\setminus L$ and $U\setminus K$ are infinite. We give a negative answer. We first construct an infinite language $D$ with context-free complement such that, for every regular language $R$, either $D\cap R$ or $D\setminus R$ is finite. The words of $D$ encode computations of factorials; repetition of letters ensures that each finite automaton either accepts all but finitely many words of $D$ or rejects all but finitely many words of $D$, while a one-counter automaton recognizes errors in the encodings. We then construct $L$ and $U$ from the complement of $D$. A grammar argument shows that any context-free intermediate language $K$ would divide $D$ in the same way as some regular language. This proves the required impossibility. Both $L$ and $U$ can be taken over a binary alphabet.

0.30