CS Paper Radar

Stronger bounds on the degree of ambiguity of finite automata

Stefan Kiefer, Filip Mazowiecki, Andrew Ryzhikov, Antoni Wiśniewski

cs.FL ·submitted 2026-10-06 15:21 UTC · v1

Abstract

Ambiguity measures the number of accepting runs in nondeterministic finite automata (NFA). We consider finitely ambiguous NFA, where there exists a constant $N$ such that over every word $w$ there are at most $N$ accepting runs. In such a case we also say that the NFA is $N$-ambiguous. Importantly $N$ depends only on the NFA, it does not depend on the length of the word. Weber and Seidl showed that every NFA is $N$-ambiguous for $N = 2^{O(n \log n)}$, where $n$ is the number of states. We improve this to $N = 2^{O(n)}$, which is asymptotically tight.

Closest papers

Nearest neighbours by meaning across the whole index.

Exact versus unique nondeterministic automatic complexity

cs.FL math.LO ·2026-08-23 ·Bjørn Kjos-Hanssen, Travis Rivera Petit
similarity 0.66
Abstract

The exact nondeterministic automatic complexity $A_{Ne}(x)$ of a word $x$ is the minimum number of states of a nondeterministic finite automaton that accepts $x$ and no other word of length $|x|$; the unique nondeterministic automatic complexity $A_N(x)$ additionally requires the accepting computation to be unique. Chen, Kjos-Hanssen, Koswara, Richter, and Stephan (FSTTCS 2025) asked whether the two measures can differ. We answer this affirmatively: the binary word $w=1101000000100$ satisfies $A_{Ne}(w)=6<7=A_N(w)$. The separation is witnessed by a six-state automaton whose sole accepted word of length $13$ is $w$, accepted along exactly three computation paths. The matching lower bounds were established by exhaustive search and by SAT solvers, with proofs of unsatisfiability certified in the DRAT format. An exhaustive census shows that $13$ is the least length of a separating word over any alphabet, binary or not, and that up to renaming of letters the separating words of length $13$ are precisely $365$ letter-mergings of the single seven-letter word $0123444445126$, all with $A_{Ne}=6<7=A_N$; exactly eight of them are binary. The separating word and the core of the verification were found by an artificial intelligence agent.

0.22

An Elementary Proof of the $\widetilde O(n^{1/3})$ Bound for Separating Words

cs.FL cs.CCmath.CO ·2026-09-08 ·Chen Xu
theory similarity 0.63
Abstract

For two distinct binary words of length $n$, the separating words problem asks for a small deterministic finite automaton that accepts exactly one of them. Chase proved a $\widetilde O(n^{1/3})$ upper bound using a complex-analytic estimate for sparse polynomials. We replace that estimate by a finite-difference argument and a second-order real recurrence cutoff. The resulting elementary proof gives an explicit bound of $O(n^{1/3}(\log n)^{7/3})$ states.

0.09

Separating Words with Automata in the Half-adversarial Case

cs.FL ·2026-08-28 ·Gabriel Bathie
theory similarity 0.63
Abstract

We consider the problem of separating words with deterministic finite automata (DFA) (Goral{č}{í}k and Koubek, 1986). This problem asks: given two distinct words $u,v$ of length at most $n$, what is the size of the smallest DFA that accepts one and rejects the other? The best upper bound on the worst-case over all pairs of words of length at most $n$ is $\tilde{O}(n^{1/3})$ states (Chase, 2021), while the best lower bound is $Ω(\log n)$. In this work, we consider the half-random, half-adversarial case: we show that if $u$ is a uniformly random binary word of length $n$, then with high probability, for any word $v$ not equal to $u$, there is a DFA with $O(\log^{7/3} n \mathrm{poly}\log\log n)$ states that separates $u$ and $v$. Our results are based on a novel analysis that exploits the structural sparsity of random words: we show how to apply block-wise compaction with small deterministic transducers to reduce the separation problem to the case of words with short run-length encodings.

0.21

A Factor-Two Lower Bound for Complementing Two-Way Deterministic Finite Automata

cs.FL cs.CC ·2026-10-10 ·Sudais Arif
theoryhot direction similarity 0.63
Abstract · 18 pages, 1 figure

For every $n\ge22$, we construct a language over a fixed three-letter alphabet whose two-way deterministic state complexity is $n$ and whose complement has state complexity $2n$. Acceptance is at the left endmarker, and infinite computations reject. The lower bound holds for arbitrary deterministic recognizers. The proof uses the group of transformations induced by the witness to constrain the behavior of a smaller recognizer, then derives a contradiction from a permutation query problem. A matching halting complement follows from a $2n$-state construction for sources whose destination states determine the direction of each transition. Splitting states by incoming direction gives a $2n+2b$ upper bound for general sources, where $b$ counts states entered in both directions. In the acceptance-anywhere model of Geffert, Mereghetti, and Pighizzini, the same family has exact complexities $N$ and $2N-1$ for every $N\ge23$.

0.39

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

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

Towards A Parametrized Complexity of Determinization

cs.FL ·2026-11-07 ·Ivan Baburin, Ryan Cotterell
similarity 0.60
Abstract

Given a nondeterministic finite automaton (NFA), we want to estimate the difficulty of finding an equivalent deterministic finite automaton (DFA). We demonstrate that computing the state complexity of an NFA within polynomial precision is \textsf{PSPACE}-hard, and furthermore the same holds for the complexity of the subset construction, Brzozowski's algorithm, or, indeed, \emph{any} determinization algorithm which runs at least as fast. This result implies that making any \textit{a priori} estimate of the running time of the major determinization algorithms is inherently hard. To circumvent this---in the spirit of parametrized complexity---we try to identify complexity measures which can guarantee efficient determinization. Our main idea rests on linking the complexity of the subset construction to transition monoids using the semigroup complexity. We show that the semigroup complexity by itself can be reasonably approximated for certain classes of NFAs, and then introduce \emph{subset complexity}---a refinement of the semigroup complexity which has a tighter connection with the subset construction. In certain scenarios, the subset complexity can be approximated in polynomial time, making it potentially viable for more practical applications.

0.25

Unary Versus Binary Two-Way Automata

cs.FL ·2026-08-25 ·Viliam Geffert, Vincent Hlaváč, Rastislav Královič
publishedhot direction similarity 0.60
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