Conditional Membership in Regular Languages

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\le i\le 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, $\Theta (\log n)$ queries, and $\Theta (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$.