13
$\begingroup$

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)$, an 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.

$\endgroup$
11
  • $\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$ – Hermann Gruber Apr 20 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 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 at 13:45
  • $\begingroup$ OK, I haven't realized words of different length need to be rejected. $\endgroup$ – domotorp Apr 21 at 15:59
  • 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 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.