<p>An <a href="https://en.wikipedia.org/wiki/Unambiguous_finite_automaton" rel="nofollow noreferrer">unambiguous finite automaton</a> (UFA) is a nondeterministic finite automaton (NFA) such
that each word has at most one accepting path. In this post, for <span class="math-container">$n\in \mathbb{N}$</span>, what I call an <span class="math-container">$n$</span>-UFA (resp., <span class="math-container">$n$</span>-NFA) is a UFA (resp., NFA) <span class="math-container">$A$</span> over alphabet <span class="math-container">$\{0,1\}$</span> such that <span class="math-container">$L(A) \subseteq \{0,1\}^n$</span>. Without loss of generality, I will assume that such automata have exactly one initial state <span class="math-container">$q_I$</span> and one final state <span class="math-container">$q_F$</span> and that they are <em>trimmed</em> (meaning that each state is both accessible from <span class="math-container">$q_I$</span> and co-accessible from <span class="math-container">$q_F$</span>). This implies in particular that all the paths from <span class="math-container">$q_I$</span> to some state <span class="math-container">$q$</span> have the same length. I am interested in the following decision problem:</p>
<p><strong>INPUT</strong>: An <span class="math-container">$n$</span>-UFA <span class="math-container">$A$</span>, integer (or rational) weights <span class="math-container">$\beta_i \in \mathbb{N}$</span> for <span class="math-container">$1 \leq i \leq n$</span>, and a threshold <span class="math-container">$t\in \mathbb{N}$</span>.</p>
<p><strong>OUTPUT</strong>: YES if there exists a word <span class="math-container">$w \in \{0,1\}^n$</span> such that <span class="math-container">$w \notin L(A)$</span> and <span class="math-container">$\sum_{i=1}^n w_i \beta_i \geq t$</span>, NO otherwise.</p>
<p>Observe that this problem is in NP: guess a word <span class="math-container">$w \in \{0,1\}^n$</span>, check in polynomial time that <span class="math-container">$w \notin L(A)$</span> and <span class="math-container">$\sum_{i=1}^n w_i \beta_i \geq t$</span> and accept if this is the case.</p>
<p><strong>Question</strong>: is this problem NP-complete?</p>
<p>Some observations:</p>
<ul>
<li>If we replace “<span class="math-container">$w\notin L(A)$</span>” by “<span class="math-container">$w\in L(A)$</span>”, then the problem becomes solvable in polynomial time, even for NFAs. Indeed, given an <span class="math-container">$n$</span>-NFA, we can easily compute by induction, for every state <span class="math-container">$q$</span> that is at distance <span class="math-container">$i$</span> from <span class="math-container">$q_I$</span>, the quantity <span class="math-container">$\max_{w \in \{0,1\}^i \text{ s.t. } q \in \delta(q_I,w)}(\sum_{j=1}^i w_j \beta_j)$</span>, where <span class="math-container">$\delta(q_I,w)$</span> is the set of states that can be reached from <span class="math-container">$q_I$</span> by reading <span class="math-container">$w$</span>.</li>
<li>If we consider the problem for NFAs instead of UFAs, then this is NP-complete. Indeed, if we let <span class="math-container">$\beta_i=1$</span> for <span class="math-container">$1 \leq i \leq n$</span> and <span class="math-container">$t=0$</span>, then this is just asking if there exists a word of size <span class="math-container">$n$</span> 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 <a href="https://cstheory.stackexchange.com/q/46199/38111">this post</a> for instance).</li>
<li>If all the <span class="math-container">$\beta_i$</span>s are equal, then this is PTIME. Indeed, in that case the problem is simply
asking if there exists a word <span class="math-container">$w\in \{0,1\}^n$</span> of hamming weight <span class="math-container">$\geq \lceil \frac{t}{\beta} \rceil$</span> that is not in <span class="math-container">$L(A)$</span>. But for <span class="math-container">$1 \leq j \leq n$</span>, because <span class="math-container">$A$</span> is a UFA, we can easily compute in polynomial time the number of words <span class="math-container">$w \in \{0,1\}$</span> of hamming weight <span class="math-container">$j$</span> that are in <span class="math-container">$L(A)$</span>, and so by a counting argument we can detect if one such word is missing. Hence, any hardness proof will need to use distinct <span class="math-container">$\beta_i$</span> values.</li>
<li>As observed in the comments, this problem can be rephrased using special kinds of unambiguous (Max,+) automata (see e.g., Section 3 of
<em>Colcombet, Thomas</em>, <a href="https://www.irif.fr/%7Ecolcombe/Publications/DCFS15-colcombet.pdf" rel="nofollow noreferrer"><strong>Unambiguity in automata theory</strong></a>), where all the  edges that are at the same distance from the initial state have the same weight.</li>
</ul>
<p>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 <span class="math-container">$\neq$</span> 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 href="https://arxiv.org/abs/1711.03993" rel="nofollow noreferrer"><strong>A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton</strong></a> shows such a lower bound, but the UFAs that are used are cyclic, and the proof seems to crucially rely on this.</p>

CC BY-SA 4.0
2021-04-20T19:27:35.380Z
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
CC BY-SA 4.0
2021-04-21T08:20:20.120Z
I don't think it is true that all the paths from $q_I$ to some state $q$ have the same length.
domotorp
CC BY-SA 4.0
2021-04-21T13:45:01.087Z
@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
CC BY-SA 4.0
2021-04-21T15:59:44.950Z
OK, I haven't realized words of different length need to be rejected.
domotorp
CC BY-SA 4.0
2021-04-22T11:20:24.977Z
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
CC BY-SA 4.0
2021-04-22T20:09:45.283Z
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
CC BY-SA 4.0
2021-04-23T10:34:12.590Z
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
CC BY-SA 4.0
2021-04-29T09:27:57.167Z
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
CC BY-SA 4.0
2021-05-09T08:52:00.987Z
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
CC BY-SA 4.0
2021-05-09T08:56:01.700Z
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
CC BY-SA 4.0
2021-05-12T09:55:50.603Z
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
CC BY-SA 4.0
2023-01-24T13:46:50.410Z
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
<automata-theory><np-complete>
Is this problem on unambiguous finite automata NP-complete?
M.Monet
# Is this problem on unambiguous finite automata NP-complete?

(Asked by: username_0 on 2021-04-20)

An [unambiguous finite automaton](https://en.wikipedia.org/wiki/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](https://cstheory.stackexchange.com/q/46199/38111) 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**](https://www.irif.fr/%7Ecolcombe/Publications/DCFS15-colcombet.pdf)), 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**](https://arxiv.org/abs/1711.03993) shows such a lower bound, but the UFAs that are used are cyclic, and the proof seems to crucially rely on this.

**Tags:** automata-theory, np-complete
> **Comments:**
> **username_1**: 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  
> **username_2**: I don't think it is true that all the paths from $q_I$ to some state $q$ have the same length.  
> **username_0**: @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.  
> **username_2**: OK, I haven't realized words of different length need to be rejected.  
> **username_0**: 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  
> **username_3**: 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?  
> **username_0**: 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).  
> **username_4**: 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$.  
> **username_0**: 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  
> **username_0**: 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...  
> **username_4**: 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.  
> **username_5**: 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.  

---

## 0 answers

