CS Paper Radar

Pushdown Model Checking Above the Cubic Bottleneck

A. R. Balasubramanian, Dmitry Chistikov, Rupak Majumdar

cs.FL cs.CCcs.LO ·submitted 2026-08-25 14:23 UTC · v1
top venuetheory

Abstract

Many problems in the verification of recursive programs can be reduced to pushdown model checking. In this problem, we are given as input a pushdown automaton (PDA) over a constant-sized stack alphabet, and a description of undesirable behaviors given by an intersection of NFAs, and the problem is to decide if there is a behavior of the PDA that belongs to the set of undesirable behaviors. It is well-known that there is an algorithm for this problem that runs in time $O(n^{2k} |Σ| + n^{3k})$, where $n$ is the maximum number of states of the PDA and the NFAs, $Σ$ is the common input alphabet, and $k-1$ is the number of NFAs. Despite the importance of this problem, no better algorithm is known for it. In this paper, we provide an explanation for this lack of progress using the lens of fine-grained complexity theory. We prove that if the $3k$-Clique hypothesis (resp. combinatorial $3k$-Clique hypothesis) is true, then for any $ε> 0$, there is no algorithm (resp. combinatorial algorithm) that solves this problem in time $O((n^{(ω-1)k} |Σ| + n^{ωk})^{1-ε})$ (resp. $O((n^{2k} |Σ| + n^{3k})^{1-ε})$) where $ω$ is the matrix multiplication exponent. Furthermore, using the combinatorial hypothesis, we also show that pushdown model checking over constant-sized input alphabets cannot be solved in time faster than $O(n^{3(k-1)-ε})$ for any $ε> 0$. Finally, we investigate the possibility of an $O(N^{3k-ε})$ time algorithm for this problem where $N$ is the total bit size of the input. We formulate a new hypothesis, the 2NPDA$(k)$ hypothesis, that helps explain the lack of $O(N^{3k-ε})$ time algorithms for this problem. To corroborate this hypothesis, we show a web of linear-time reductions between the 2NPDA$(k)$ hypothesis, pushdown model checking, and other problems in formal language and automata theory.

Comment
Full version of the LICS 2025 paper "Pushdown Model Checking above the Cubic Bottleneck". Abstract shortened to fit arXiv requirements

Closest papers

Nearest neighbours by meaning across the whole index.

Weak Bisimulation Finiteness of Pushdown Systems With Deterministic $\varepsilon$-Transitions Is 2-ExpTime-Complete

cs.FL ·2026-08-11 ·Stefan Göller, Paweł Parys
top venuetheory similarity 0.62
Abstract

We consider the problem of deciding whether a given pushdown system all of whose $\varepsilon$-transitions are deterministic is weakly bisimulation finite, that is, whether it is weakly bisimulation equivalent to a finite system. We prove that this problem is 2-ExpTime-complete. This consists of three elements: First, we prove that the smallest finite system that is weakly bisimulation equivalent to a fixed pushdown system, if exists, has size at most doubly exponential in the description size of the pushdown system. Second, we propose a fast algorithm deciding whether a given pushdown system is weakly bisimulation equivalent to a finite system of a given size. Third, we prove 2-ExpTime-hardness of the problem. The problem was known to be decidable, but the previous algorithm had Ackermannian complexity (6-ExpSpace in the easier case of pushdown systems without $\varepsilon$-transitions); concerning lower bounds, only ExpTime-hardness was known.

0.40

The smallest programmable machine and the hardness of analyzing it

cs.CC ·2026-10-07 ·J. Andres Montoya
theory similarity 0.61
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

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

Turn Complexity and Bounded Languages

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

Towards A Parametrized Complexity of Determinization

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

How Can Size, Ceiling, and Time Bounds Affect the Complexity of Nonuniform Automata Families?

cs.CC cs.FL ·2026-11-16 ·Tomoyuki Yamakami
similarity 0.59
Abstract · (A4 size, 10pt, 34 pages, 6 figures) This paper is a modified, extended version of arxiv.org/abs/2606.26685v1 (2026). This paper is an exten…

In the past literature, families of two-way finite automata and pushdown automata having limited resource-bounded complexity have been studied in direct connection to (mainstream) space-bounded complexity classes equipped with Karp-Lipton style advice of limited size when all inputs given to the automata have bounded length. We acknowledge three major factors--size, ceiling, and time--of such families, which have a significant impact on the computational/descriptional complexity of finite and pushdown automata families, where the "size" refers to the (stack-)state complexity, the "ceiling" refers to the maximum input length, and the "time" refers to the execution time of underlying automata. In this line of study, we further explore these effects caused by different sizes and ceilings. We exploit automata-based reducibility and translatability to space-bounded advised Turing machines and auxiliary automata.

0.39

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

Tolerant Testers for Subgraph-Freeness

cs.DS ·2026-10-14 ·Reut Levi, Jonathan Meiri
published similarity 0.56
Abstract

In this paper we study the problem of tolerantly testing the property of being $H$-free (which also implies distance approximation from being $H$-free). In the general-graphs model, we show that tolerant $K_k$-freeness testing can be achieved with query complexity that is polynomial in the arboricity of the input graph $G$, $arb(G)$, and independent of the size of $G$ (for graphs in which the average degree is $Ω(1))$. Specifically for triangles, our algorithm distinguishes graphs which are $ε$-close to being triangle-free from graphs that are $3ε(1+η)$-far from being triangle-free with expected query complexity which is $\tilde{O}(arb^3(G))$ (for constant $η$ and $ε$). For general $k$-cliques our algorithm distinguishes graphs which are $ε$-close to being $K_k$-free from graphs which are ${k \choose 2}ε(1+η)$-far from being $K_k$-free with expected query complexity which is polynomial in $k$, $1/ε$, $1/η$ and $arb(G)$. We then generalize our result and provide a similar result for any motif $H$ which is $2$-connected and has radius $1$. This includes for example the wheel graph. Finally, we show that our tester can be applied to the bounded-degree model for tolerantly testing $H$-freeness for any motif $H$. The query complexity of the algorithm is polynomial in the degree bound, $d$, improving the previous state-of-the-art by Marko and Ron (TALG 2009) that obtained quasi-polynomial query complexity in $d$.

0.32