CS Paper Radar

Conditional Membership in Regular Languages

Antoine Amarilli, Sebastien Felipe Labbe, Charles Paperman

cs.FL ·submitted 2026-10-12 11:26 UTC · v1

Abstract

We study a formulation of regular language membership as a promise problem, which we dub conditional membership: we fix a promise language $P$ and a target language $T \subseteq P$, we are given a word $w$ which is promised to belong to $P$, and we must determine whether $w$ belongs to $T$. We study the deterministic worst-case query complexity of this task, when the length $n$ of $w$ is known in advance and where each query examines the $i$-th position of $w$ for some $1 \leq i \leq n$ and returns the $i$-th letter $w_i$ of $w$. Our goal is to characterize the asymptotic complexity as a function of the word length $n$, depending on the fixed languages $P$ and $T$. Our main result is to show that the complexity of this task admits a trichotomy between three regimes: $O(1)$ queries, $Θ(\log n)$ queries, and $Θ(n)$ queries. We further show that the trichotomy criterion is decidable, namely, it is PSPACE-complete to decide which regime applies, given nondeterministic automata $A_P$ and $A_T$ respectively representing $P$ and $T$.

Closest papers

Nearest neighbours by meaning across the whole index.

Query Complexity of Testing Structured Parenthesis Languages

cs.DS cs.CC ·2026-09-29 ·Tim Jackman, Diptaksho Palit, Sofya Raskhodnikova
theory similarity 0.72
Abstract

We study the query complexity of testing membership in structured string languages, focusing on Dyck languages and natural generalizations. A tester receives query access to a word and must distinguish valid inputs from words that are far in Hamming distance, while inspecting only a sublinear number of positions. Our results sharpen the boundary between constant-query testability and polynomial query complexity. First, we prove an $Ω(n^{2/5})$ lower bound for testing Dyck languages $D_m$ with any fixed number $m\ge2$ of parenthesis types, improving the previous $Ω(n^{1/5})$ lower bound of Fischer, Magniez, and Starikovskaya (SODA `18) and nearly matching their upper bound of $O(n^{2/5+o(1)})$. Furthermore, we show that all nonadaptive algorithms for these problems require $Ω(n^{1/2})$ queries. Our lower bounds use a Pólya-urn process to construct the hard distribution; Second, we identify a broad class of weighted-parenthesis languages, which we call {\em excursion languages,} that remain constant-query testable. These languages encode bounded-step walks that stay nonnegative and return to zero. For every fixed excursion language, we give a nonadaptive tester with query complexity $O(1/\varepsilon^2)$, and we prove this dependence on $\varepsilon$ is optimal, even for adaptive algorithms. As a special case, we obtain the tight $Θ(1/\varepsilon^2)$ query complexity of testing $D_1$, improving the previous $O(\log(1/\varepsilon)/\varepsilon^2)$ upper bound and giving the first matching two-sided-error lower bound. Third, we construct a simple hard language, Hidden String, that is generated by a deterministic linear grammar but nevertheless requires $Ω(n^{2/5})$ adaptive queries and $Ω(n^{1/2})$ nonadaptive queries to test. This shows that polynomial query complexity appears even for highly restricted string languages.

0.18

Unconditional Boolean Dynamic Lower Bounds from Disjointness

cs.DS cs.CC ·2026-10-07 ·Young Kun Ko
theory similarity 0.65
Abstract · 48 pages, 3 figures. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised.…

We prove an unconditional $Ω((\log n/\log\log n)^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth $2$. This improves the $\widetildeΩ(\log^{3/2} n)$ bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length $M$ over a polynomial-size alphabet, a deterministic algorithm uses $O(1)$ amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size $w=Θ(\log M)$ requires $Ω((\log M/\log\log M)^2)$ time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

0.24

A Circuit Complexity Trichotomy For Regular Languages

cs.CC cs.FL ·2026-11-02 ·Stefan Göller, Amaldev Manuel
similarity 0.61
Abstract

We establish a trichotomy for the non-uniform, unbounded-fan-in circuit complexity of regular languages: the complexity of every regular language lies in exactly one of $O(1)$, $Ω(\log n)\cap O(\log n\log\log n)$, or $Ω(n)\cap O(n)$. Our main technical contribution is a characterization of the sublinear class in terms of algebra, word congruences, regular expressions, and logic. This class consists precisely of the regular languages computable by constant-depth circuits of size $O(\log^2 n)$, or, equivalently, by circuits of size $O(\log n\log\log n)$ and depth $O((\log\log n)^2)$. Consequently, every regular language of sublinear circuit complexity is definable in $\mathrm{FO}^2[Σ,<,\mathrm{mod}]$, which is contained in wire-linear $\mathbf{AC}^0$. For each of the three classes, deciding membership is $\mathbf{PSPACE}$-complete when the language is specified by a nondeterministic finite automaton. We also obtain a corresponding classification for regular languages with a neutral letter.

0.15

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

Witness Languages for Pumping Lemmata

cs.FL ·2026-10-11 ·Pamela Fleischmann, Annika Huch, Christian Rauch
similarity 0.60
Abstract

In 2022 Dassow and Jecker started investigations on the operational complexity of the pumping constant w.r.t.~two pumping lemmata. Since then, the research on pumping lemmata emerged to several variants for regular as well as context-free languages. Within this work, we further investigate the \emph{witnesses} of regular languages (firstly introduced by Rauch) w.r.t.~different pumping lemmata: For a language $L$ and a minimal pumping constant $K$, a \emph{witness} of a language is a word that cannot be \emph{pumped} by $K$ w.r.t.~the given pumping lemma. Here, the pumping constant is minimal if for all smaller numbers, the pumping lemma condition is not satisfied. Alongside combinatorial investigations on (unary) witness languages, we introduce and study the measure of scattered factor distance, which is related to minimal pumping constants. We present bounds on minimal pumping constants by the scattered factor distance and show that deciding, given two regular languages, whether one of them is equal to the witness language of the second is \coNP-complete.

0.30

Average-Case Optimal Encodings and Efficient Worst-Case Indices for Element Distinctness Queries

cs.DS ·2026-08-18 ·Philip Bille, Johannes Fischer, Inge Li Gørtz, Filippo Lari
publishedtheoryhot direction similarity 0.60
Abstract · Accepted at SPIRE 2026. Full version

We study the data structure version of the \emph{element distinctness problem}: preprocess an array of $n$ elements from an alphabet of size $σ$ to answer \textsc{All-Distinct} queries, asking whether a given range contains only distinct elements. We first focus on \emph{uniformly random arrays}: in the encoding model, where access to the input at query time is not allowed, we prove a lower bound on the expected space; for instance, the lower bound is $n$, $1.3627n$, $1.5153n$, $1.5824n$ bits for $σ= 2,3,4,5$, and approximately $n\sqrt{π/(2σ)}\,\logσ$ bits for $σ=ω(1)$. We complement this by designing different average-case optimal encodings, supporting \textsc{All-Distinct} queries in worst-case time $O(1)$, $o(\log^{2}{\log{n}})$, or $O(\log\log{n})$ depending on $σ$, and $O(1)$ expected time for any $σ= ω(1)$. We then switch to worst-case (non-random) arrays: in the indexing model, where access to the input is allowed, we prove a cell-probe space-time tradeoff lower bound showing that any index using $n/b$ bits must have $Ω(b/\log{b})$ query time. We conclude by presenting a simple index almost matching this lower bound.

0.39

Independent Languages and Witnesses of Dependence (Non-satisfaction)

cs.FL ·2026-08-25 ·Stavros Konstantinidis
published similarity 0.60
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

We consider the independent language property defined by the language equation φ(X)=\emptyset, where the expression φ involves the language variable X, constant languages, and standard regular operations including transductions, but not complementation. This property consists of all languages L satisfying φ(L)=\emptyset. Depending on the choice of the operations in φ, the equation defines a broad class of codes, including combinations of standard variable-length codes and error-detecting codes. We show that any φ-independence is a Jürgensen independence, we define what a witness of non-satisfaction of φ(X)=\emptyset is, for a language L, and we show how to compute a witness of non-satisfaction when L is regular. We also discuss the complexity of the problem, showing that the decision version of the problem is PSPACE-complete.

0.48

The Gap Between Average-Case and Worst-Case Complexity

cs.CC ·2026-10-13 ·Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor C. Oliveira
publishedtheory similarity 0.60
Abstract

Understanding the average-case complexity of $\mathsf{NP}$ is a central goal in complexity theory and cryptography. A necessary milestone is to understand the corresponding average-case versus worst-case question for the polynomial hierarchy ($\mathsf{PH}$). In a celebrated result, Hirahara [Hir21] proved that if every distributional problem in $\mathsf{PH}$ is easy on average, then every language in $\mathsf{PH}$ admits worst-case algorithms running in time $2^{O(n/\log n)}$. Remarkably, although the statement of Hirahara's theorem makes no reference to meta-complexity, all known proofs appear to use time-bounded Kolmogorov complexity and its associated meta-computational problems in an essential way. We show that the reliance on techniques and perspectives from meta-complexity is not simply a coincidence. Building on previous work of Hirahara [Hir20] and on a recent result of Hu, Lu, and Oliveira [HLO25], we prove that relating the average-case and worst-case complexities of $\mathsf{PH}$ is in fact equivalent to a purely meta-computational implication: efficient algorithms for a standard gap version of $\mathsf{MINpKT}$ with $\mathsf{PH}$ oracle access imply efficient algorithms for a mild gap version. Crucially, in these promise problems the standard gap separates a YES instance with time bound $t$ from a NO instance with time bound $\mathsf{poly}(t)$, whereas the mild gap keeps the YES threshold $t$ and moves the NO threshold to $t+\mathsf{poly}(n)$. Together with prior work, this equivalence points to the study of gap reductions as a potentially promising route toward understanding the relation between average-case and worst-case complexity. We make progress by proving that the gap in running time can be eliminated in the average-case setting. Finally, we prove that in the worst-case setting any efficient reduction between the two problems must use nonrelativizing techniques.

0.28