16

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.

M.Monet
  • 1,429
  • 7
  • 19
  • On the same topic, a nontrivial (linear exponential) upper bound for complementing general UFAs has been obtained only recently: https://doi.org/10.1142/S012905411842008X – Hermann Gruber Apr 20 '21 at 19:27
  • I don't think it is true that all the paths from $q_I$ to some state $q$ have the same length. – domotorp Apr 21 '21 at 08:20
  • 1
    @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. – M.Monet Apr 21 '21 at 13:45
  • OK, I haven't realized words of different length need to be rejected. – domotorp Apr 21 '21 at 15:59
  • To clarify: in the formulation of the problem we can replace "An $n$-UFA $A$" by An UFA $A$" and this gives the same problem. Actually this problem is not so much about automata theory, as it doesn't really matter that $L(A)$ is regular, in the end this is just a problem on finite graphs – M.Monet Apr 22 '21 at 11:20
  • In "As for the context", what do you mean by "complement a UFA?" Do you mean come up with an NFA for the complement of the language of the UFA? – Neal Young Apr 22 '21 at 20:09
  • Yes, this is what I meant. But the language of the input UFA should be finite, otherwise by Raskin's result we know this is not possible (in ptime). – M.Monet Apr 23 '21 at 10:34
  • 1
    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$. – Denis Apr 29 '21 at 09:27
  • Ah yes, you are right that the automata I consider I special kinds of (max,+) automata. However, note that in my problem I am looking for the maximal weight of a word that is not accepted by the automata; and I don't see a natural way of defining the weight of a word that is not accepted could be defined for (max,+) automata, since the weights are defined for specific runs – M.Monet May 09 '21 at 08:52
  • Ah, one possibility would be to "complete up to n" the (max,+) automata and define the weight of a non-accepted word as the maximal weight of a non-accepting run, which would then amount to what I want since as you say all edges that are at the same distance from the initial state have the same weight. I'll update the post, but I don't know if this is a more natural way of phrasing the problem though... – M.Monet May 09 '21 at 08:56
  • Indeed it is less natural when you are interested in words not accepted by the automaton. Maybe the simplest way is to say that your automaton is not unambiguous but "co-unambiguous": there is at most one rejecting run, and a word is accepted if all runs are accepting. The weight will be the same for all runs so you can take any definition (min, max, accepting runs, rejecting runs). It is a very particular kind of alternating weighted automaton. – Denis May 12 '21 at 09:55
  • 1
    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. – Lê Thành Dũng 'Tito' Nguyễn Jan 24 '23 at 13:46

0 Answers0