Witness for Unambiguous Finite Automata (LFWITNESS)

Input

Let $M = (Q, \Sigma, \delta, s, F)$ be an unambiguous finite automaton and $n$ an integer encoded in unary.

Problem

Find the lexicographically first witness string for $M$.

Definitions

A finite automaton is unambiguous if all strings accepted by the machine have a unique accepting computation.

The lexicographically first witness string is the lexicographically first string that “witnesses” the inequality $L(M) \cap \Sigma^{\leq n} \neq \Sigma^{\leq n}$, where $L(M)$ denotes the language accepted by $M$ and $\Sigma^{\leq n}$ denotes all strings over $\Sigma$ of length less than or equal to $n$.

Status

Open (Sang Cho and Huynh [1]).

Remarks

In [1] the problem is proved to be in $\P$. For deterministic finite automata the problem is $\NC^1$-complete for $\mathsf{NLOG}$ [1]. See [1] for other results regarding related problems.