Conditional membership query complexity splits into three clear categories

Conditional Membership in Regular Languages

Formal Languages and Automata Theory

Summary

This paper looks at a puzzle about checking if a word belongs to a smaller language inside a bigger promised language, using a limited way to look at the word one letter at a time. The authors find there are exactly three possible difficulty levels for this task depending on the two languages involved: it can be done by looking at only a few letters, or growing slowly with the word length, or needing to check every letter. They also show that figuring out which difficulty level applies is something computers can decide, but it can be quite complex to do. This helps us understand the boundaries of how hard it is to check membership under different conditions.

What this means in practice

  • For software testing teams: Optimize testing routines by knowing when checking partial input suffices to confirm membership in restricted language scenarios.
  • For compiler engineers: Determine when examining only parts of code tokens guarantees recognition of language subsets, improving parsing query efficiency.

A theory result. No direct application yet.

Authors

Antoine Amarilli, Sebastien Felipe Labbe, Charles Paperman

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$.
View PDFOpen arXiv