An unambiguous finite automaton (UFA) is a nondeterministic finite automaton (NFA) such that each word has at most one accepting path. In this post, for $n\in \mathbb{N}$, what I call an $n$-UFA (resp., $n$-NFA) is a UFA (resp., NFA) $A$ over alphabet $\{0,1\}$ such that $L(A) \subseteq \{0,1\}^n$. Without loss of generality, I will assume that such automata have exactly one initial state $q_I$ and one final state $q_F$ and that they are trimmed (meaning that each state is both accessible from $q_I$ and co-accessible from $q_F$). This implies in particular that all the paths from $q_I$ to some state $q$ have the same length. I am interested in the following decision problem:

INPUT: An $n$-UFA $A$, integer (or rational) weights $\beta_i \in \mathbb{N}$ for $1 \leq i \leq n$, and a threshold $t\in \mathbb{N}$.

OUTPUT: YES if there exists a word $w \in \{0,1\}^n$ such that $w \notin L(A)$ and $\sum_{i=1}^n w_i \beta_i \geq t$, NO otherwise.

Observe that this problem is in NP: guess a word $w \in \{0,1\}^n$, check in polynomial time that $w \notin L(A)$ and $\sum_{i=1}^n w_i \beta_i \geq t$ and accept if this is the case.

Question: is this problem NP-complete?

Some observations:

  • If we replace “$w\notin L(A)$” by “$w\in L(A)$”, then the problem becomes solvable in polynomial time, even for NFAs. Indeed, given an $n$-NFA, we can easily compute by induction, for every state $q$ that is at distance $i$ from $q_I$, the quantity $\max_{w \in \{0,1\}^i \text{ s.t. } q \in \delta(q_I,w)}(\sum_{j=1}^i w_j \beta_j)$, where $\delta(q_I,w)$ is the set of states that can be reached from $q_I$ by reading $w$.
  • If we consider the problem for NFAs instead of UFAs, then this is NP-complete. Indeed, if we let $\beta_i=1$ for $1 \leq i \leq n$ and $t=0$, then this is just asking if there exists a word of size $n$ that is not in the language, and there is an easy reduction from DNF falsifiability (the automaton nondeterministically branches to a gadget that checks a clause, or see this post for instance).
  • If all the $\beta_i$s are equal, then this is PTIME. Indeed, in that case the problem is simply asking if there exists a word $w\in \{0,1\}^n$ of hamming weight $\geq \lceil \frac{t}{\beta} \rceil$ that is not in $L(A)$. But for $1 \leq j \leq n$, because $A$ is a UFA, we can easily compute in polynomial time the number of words $w \in \{0,1\}$ of hamming weight $j$ that are in $L(A)$, and so by a counting argument we can detect if one such word is missing. Hence, any hardness proof will need to use distinct $\beta_i$ values.
  • As observed in the comments, this problem can be rephrased using special kinds of unambiguous (Max,+) automata (see e.g., Section 3 of Colcombet, Thomas, Unambiguity in automata theory), where all the edges that are at the same distance from the initial state have the same weight.

As for the context: ultimately, I would like to obtain superpolynomial lower bounds on the size of UFAs recognizing the complement of UFAs that recognize finite languages. Since this seems hard, I'd like to at least obtain this conditionally to P $\neq$ NP. So I came up with this problem which, if proven NP-complete, would show that we cannot complement a UFA recognizing a finite language in PTIME. Note that Raskin, Michael, A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton shows such a lower bound, but the UFAs that are used are cyclic, and the proof seems to crucially rely on this.

  • $\begingroup$ On the same topic, a nontrivial (linear exponential) upper bound for complementing general UFAs has been obtained only recently: doi.org/10.1142/S012905411842008X $\endgroup$ Apr 20, 2021 at 19:27
  • $\begingroup$ I don't think it is true that all the paths from $q_I$ to some state $q$ have the same length. $\endgroup$
    – domotorp
    Apr 21, 2021 at 8:20
  • 1
    $\begingroup$ @domotorp Notice that all the words in the language have length $n$. If there was a state $q$ with $q \in \delta(q_I,w) \cap \delta(q_I,w') $ for some words with $|w| \neq |w'|$ then, since $q$ is co-accessible, there would be two words in $L(A)$ that have different lengths. $\endgroup$
    – M.Monet
    Apr 21, 2021 at 13:45
  • 1
    $\begingroup$ About your remark with (max,+) automata: you say that your weights are not on the edges so the problem is different, but in fact you could put the weights on the edges, making your automaton a (max,+) automaton. Indeed, since for each edge you know that there is an integer $i$ such that the edge can only be taken after exactly $i$ steps, you can weight the edge by $\beta_i$ if its letter is $1$ and by $0$ if its letter is $0$. $\endgroup$
    – Denis
    Apr 29, 2021 at 9:27
  • 1
    $\begingroup$ The problem seems to be pseudo-polynomial, i.e. in P when the weights are given in unary. Indeed, you can use dynamic programming to compute, for each possible weight below $\beta_1 + \dots + \beta_n$, the number of words in the language that have exactly this weight. From this you can deduce the highest weight realized by at least one word not in the language. $\endgroup$ Jan 24, 2023 at 13:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.