CS Paper Radar

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

Kehinde Adeogun, Christos A. Kapoutsis

cs.FL ·submitted 2026-09-12 08:12 UTC · v2
theory

Abstract

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.

Comment
16 pages; 1 figure; to be submitted to SOFSEM 2027

Closest papers

Nearest neighbours by meaning across the whole index.

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

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

Towards A Parametrized Complexity of Determinization

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

Deterministic Bandwidth of Finite Languages

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

From k+1 to k heads the descriptive trade-off is non-recursive

cs.FL ·2026-10-08 ·Christos Kapoutsis
theoryhot directionhighly cited similarity 0.58
Abstract · Proceedings of DCFS 2004, pp. 213-224. Number of pages: 13. Number of figures: 0

We prove that no recursive function can upper bound the increase in the size of description when a two-way deterministic finite automaton with k+1 heads is replaced by an equivalent two-way deterministic finite automaton with k heads. This is true for all k, and remains true if the automata are unary and/or nondeterministic.

0.61

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

Hankel Submatrices with Bounded Word Length: Dimension Tradeoffs in Probabilistic and Quantum Automata

cs.IT quant-ph ·2026-10-15 ·Yixin Zhao
similarity 0.56
Abstract

We characterize the largest admissible side length of fixed-margin square Hankel submatrices generated by probabilistic realizations on a \(d\)-point carrier and quantum linear realizations on a \(d\)-dimensional Hilbert space, when prefix and suffix word lengths are bounded by \(T\). Using a four-symbol transition alphabet shared by all selected rows and columns, we show that, for fixed margins \(λ_2>0\) and \(λ_1+λ_2<1\), the corresponding side lengths satisfy \(\ln N_{\mathsf Q,4}=Θ_{λ_1,λ_2}(\min\{d^2,T\})\) for completely positive trace-preserving (CPTP) quantum realizations and \(\ln N_{\mathsf S,4}=Θ_{λ_1,λ_2}(\min\{d,T\})\) for probabilistic automata. Four unitary and four permutation transition maps attain the corresponding orders. At zero false-acceptance tolerance (\(λ_2=0\) with \(0\leqλ_1<1\)), all four model classes satisfy \(\ln N=Θ(\min\{\ln d,T\})\). The upper bounds follow from state-space packing and word counting, while the lower bounds combine explicit transition tuples with Grassmannian and positive-rate codebooks whose existence follows from the probabilistic method. These results establish sharp dimension--word-length tradeoffs for bounded-word Hankel tables.

0.26

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