CS Paper Radar

Hardness and Approximation for Compressing Deterministic Finite Automata

Philip Bille, Inge Li Gørtz, Christoffer Krogh, Christian Møller Mikkelstrup

cs.DS ·submitted 2026-10-22 13:43 UTC · v1

Abstract

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.

Comment
18 pages, 4 figures. Has been submitted for review

Closest papers

Nearest neighbours by meaning across the whole index.

Deterministic Bandwidth of Finite Languages

cs.FL ·2026-08-25 ·Da-Jung Cho, Szilárd Zsolt Fazekas, Max Wiedenhöft
publishedtheory similarity 0.69
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

Unrestricted 2DFA simulation of 1NFAs: A Quadratic Limitation to a New Lower Bound

cs.FL ·2026-09-12 ·Kehinde Adeogun, Christos A. Kapoutsis
theory similarity 0.68
Abstract · 16 pages; 1 figure; to be submitted to SOFSEM 2027

A recent result by the present authors established a quadratic lower bound, in the worst case, for the increase in the number of states when a one-way nondeterministic finite automaton is converted to a two-way deterministic finite automaton. Although this simply matched a well-known pre-existing quadratic lower bound by Chrobak, it used a distinct proof method. We show that, much like Chrobak's, this new method is also unable to deliver any lower bound strictly greater than quadratic.

0.27

Towards A Parametrized Complexity of Determinization

cs.FL ·2026-11-07 ·Ivan Baburin, Ryan Cotterell
similarity 0.67
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.66
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

The smallest programmable machine and the hardness of analyzing it

cs.CC ·2026-10-07 ·J. Andres Montoya
theory similarity 0.65
Abstract

We investigate the computational complexity of analyzing the structural and behavioral properties of deterministic k-pebble automata, which represent a natural framework for studying minimal programmable machines. First, we provide an explicit construction of a three-pebble automaton U capable of simulating any deterministic finite automaton (DFA) on a given input word, establishing a link between pebble automata capabilities, Kolmogorov complexity, and automatic complexity. Next, we restrict our architectural framework to two-pebble programmable machines U(2,N) simulating DFAs with at most N states. We analyze the decision problem ANAL(U(2,5)), which asks whether a five-state program can separate two distinct finite words. By establishing a polynomial-time reduction from the quasi-identity checking problem for finite semigroups, we prove that ANAL(U(2,5)) is NP-complete. Finally, we explore the complexity of separating binary strings under the Exponential Time Hypothesis (ETH), showing how computational hardness implies polynomial lower bounds for the size of the smallest DFAs separating binary strings.

0.29

Stronger bounds on the degree of ambiguity of finite automata

cs.FL ·2026-10-06 ·Stefan Kiefer, Filip Mazowiecki, Andrew Ryzhikov, Antoni Wiśniewski
similarity 0.62
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.

0.32

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

Turn Complexity and Bounded Languages

cs.FL ·2026-08-25 ·Giovanni Pighizzini
publishedtheoryhot direction similarity 0.62
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