<p>I think that <strong>this is in fact not possible</strong>, thanks to the (recent and difficult!) <a href="https://drops.dagstuhl.de/opus/volltexte/2022/16467/" rel="nofollow noreferrer">ICALP'22 results of Göös et al.</a>.</p>
<p>They show that there are UFAs <span class="math-container">$A_1$</span> and <span class="math-container">$A_2$</span> with <span class="math-container">$n$</span> states such that the language <span class="math-container">$L = L(A_1) \cup L(A_2)$</span> is not recognized by a UFA of polynomial size in <span class="math-container">$n$</span>.</p>
<p>However, from two such UFAs <span class="math-container">$A_1$</span> and <span class="math-container">$A_2$</span>, you can construct a 2-UFA <span class="math-container">$A$</span> recognizing <span class="math-container">$L(A_1)$</span> and <span class="math-container">$L(A_2)$</span>, simply by taking their disjoin union and keeping as initial states the initial states of <span class="math-container">$A_1$</span> and <span class="math-container">$A_2$</span>. Then <span class="math-container">$A$</span> clearly recognizes <span class="math-container">$L(A_1) \cup L(A_2)$</span>, and <span class="math-container">$A$</span> is a 2-UFA because for every run you have at most one run in the <span class="math-container">$A_1$</span> part and at most one run in the <span class="math-container">$A_2$</span> part given that <span class="math-container">$A_1$</span> and <span class="math-container">$A_2$</span> are UFAs. The result of Göös et al. implies that <span class="math-container">$A$</span> has no equivalent UFA of polynomial size, which a putative PTIME 2-UFA to UFA conversion algorithm would compute.</p>
<p>As a side remark, <span class="math-container">$k$</span>-UFAs for fixed <span class="math-container">$k$</span> are not so badly behaved, as you can count how many words they accept, and solve inclusion and containment for them in PTIME. This is in <a href="https://epubs.siam.org/doi/abs/10.1137/0214044" rel="nofollow noreferrer">Stearns and Hunt, SIAM J. Comput., 1985</a>. There are similar results for <span class="math-container">$k$</span>-ambiguous tree automata, in <a href="https://epubs.siam.org/doi/abs/10.1137/0219027" rel="nofollow noreferrer">Seidl, SIAM J. Comput., 1990</a>. (Unfortunately, no open-access versions of these papers that I can see.)</p>

CC BY-SA 4.0
2023-09-01T09:35:12.600Z
Interesting result! I wonder whether this construction can be reversed: Can every $k$-UFA language $L$ be expressed as the union of $k$ $1$-UFA languages $L=L_1\cup L_2\cup\cdots \cup L_k$? My guess would be: probably not.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2023-09-01T09:48:11.637Z
I do not think this reversed result has been studied for unambiguity but similar results exists for non-determinism, see e.g. Martin Sauerhoff:
*Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.* J. Comput. Syst. Sci. 66(3): 473-495 (2003)
holf
CC BY-SA 4.0
2023-09-01T16:57:06.647Z
Interesting question! (Of course I guess "can be expressed" means "with a polynomial-time translation", as otherwise you can always express any regular language with a single UFA with an exponential blowup.) I don't know, and as @holf points out I guess you could ask a similar question on decision diagrams: can you efficiently rewrite uOBDDs (OBDDs with unambiguous disjunction) so that the disjunctions are at the top level?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-09-01T00:29:30.010Z
2023-09-03T17:15:18.390Z
2023-09-03T17:15:18.390Z
Antoine Amarilli 'a3nm'
<p>This must be known, but somehow I can't locate a reference about this. Let <span class="math-container">$A$</span> be a <a href="https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton" rel="nofollow noreferrer">nondeterministic finite automaton</a> (NFA) over words of an alphabet <span class="math-container">$\Sigma$</span>. I say that <span class="math-container">$A$</span> is <em><a href="https://en.wikipedia.org/wiki/Unambiguous_finite_automaton" rel="nofollow noreferrer">unambigous</a></em> if, for every word <span class="math-container">$w \in \Sigma^*$</span>, then <span class="math-container">$A$</span> has at most one accepting run over <span class="math-container">$w$</span>. I say that <span class="math-container">$A$</span> is <em>2-ambiguous</em> if, for every word <span class="math-container">$w \in \Sigma^*$</span>, then <span class="math-container">$A$</span> has at most two accepting runs over <span class="math-container">$w$</span>.</p>
<p><strong>Can I transform in polynomial time an input 2-ambiguous NFA into an unambiguous NFA which is equivalent?</strong> (i.e., recognizes the same language) <strong>Or is it known that it is not possible?</strong> e.g., there is a family of 2-ambiguous NFAs where the number of states of any equivalent unambiguous NFAs must be exponential?</p>
<p>In terms of related work, I found the 1989 SIAM J. Comput. paper by Ravikumar and Ibarra <em><a href="https://epubs.siam.org/doi/abs/10.1137/0218083" rel="nofollow noreferrer">Relating the type of ambiguity of finite automata to the succinctness of their representation</a></em> (unfortunately I didn't find an open-access version) which shows that, given a <span class="math-container">$k$</span>-ambiguous NFA, there is an exponential blowup in <span class="math-container">$k$</span> to convert it to an unambiguous NFA. But this does not imply anything for <span class="math-container">$k=2$</span>. I also found lots of works about more exotic automata models. But I guess the result on vanilla NFAs must be known (or simple to show)?</p>

<automata-theory><regular-language><nondeterminism><nfa><ambiguity>
Converting 2-ambiguous NFA to unambiguous NFA
Antoine Amarilli 'a3nm'
# Converting 2-ambiguous NFA to unambiguous NFA

(Asked by: username_0 on 2023-08-31)

This must be known, but somehow I can't locate a reference about this. Let $A$ be a [nondeterministic finite automaton](https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton) (NFA) over words of an alphabet $\Sigma$. I say that $A$ is *[unambigous](https://en.wikipedia.org/wiki/Unambiguous_finite_automaton)* if, for every word $w \in \Sigma^\*$, then $A$ has at most one accepting run over $w$. I say that $A$ is *2-ambiguous* if, for every word $w \in \Sigma^\*$, then $A$ has at most two accepting runs over $w$.

**Can I transform in polynomial time an input 2-ambiguous NFA into an unambiguous NFA which is equivalent?** (i.e., recognizes the same language) **Or is it known that it is not possible?** e.g., there is a family of 2-ambiguous NFAs where the number of states of any equivalent unambiguous NFAs must be exponential?

In terms of related work, I found the 1989 SIAM J. Comput. paper by Ravikumar and Ibarra *[Relating the type of ambiguity of finite automata to the succinctness of their representation](https://epubs.siam.org/doi/abs/10.1137/0218083)* (unfortunately I didn't find an open-access version) which shows that, given a $k$-ambiguous NFA, there is an exponential blowup in $k$ to convert it to an unambiguous NFA. But this does not imply anything for $k=2$. I also found lots of works about more exotic automata models. But I guess the result on vanilla NFAs must be known (or simple to show)?

**Tags:** automata-theory, regular-language, nondeterminism, nfa, ambiguity


---

## 1 answers

### Answer by username_0 on 2023-09-01. Score: 10 | Accepted answer

I think that **this is in fact not possible**, thanks to the (recent and difficult!) [ICALP'22 results of Göös et al.](https://drops.dagstuhl.de/opus/volltexte/2022/16467/).

They show that there are UFAs $A\_1$ and $A\_2$ with $n$ states such that the language $L = L(A\_1) \cup L(A\_2)$ is not recognized by a UFA of polynomial size in $n$.

However, from two such UFAs $A\_1$ and $A\_2$, you can construct a 2-UFA $A$ recognizing $L(A\_1)$ and $L(A\_2)$, simply by taking their disjoin union and keeping as initial states the initial states of $A\_1$ and $A\_2$. Then $A$ clearly recognizes $L(A\_1) \cup L(A\_2)$, and $A$ is a 2-UFA because for every run you have at most one run in the $A\_1$ part and at most one run in the $A\_2$ part given that $A\_1$ and $A\_2$ are UFAs. The result of Göös et al. implies that $A$ has no equivalent UFA of polynomial size, which a putative PTIME 2-UFA to UFA conversion algorithm would compute.

As a side remark, $k$-UFAs for fixed $k$ are not so badly behaved, as you can count how many words they accept, and solve inclusion and containment for them in PTIME. This is in [Stearns and Hunt, SIAM J. Comput., 1985](https://epubs.siam.org/doi/abs/10.1137/0214044). There are similar results for $k$-ambiguous tree automata, in [Seidl, SIAM J. Comput., 1990](https://epubs.siam.org/doi/abs/10.1137/0219027). (Unfortunately, no open-access versions of these papers that I can see.)

> **Comments:**
> **username_1**: Interesting result! I wonder whether this construction can be reversed: Can every $k$-UFA language $L$ be expressed as the union of $k$ $1$-UFA languages $L=L_1\cup L_2\cup\cdots \cup L_k$? My guess would be: probably not.  
> **username_2**: I do not think this reversed result has been studied for unambiguity but similar results exists for non-determinism, see e.g. Martin Sauerhoff: *Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.* J. Comput. Syst. Sci. 66(3): 473-495 (2003)  
> **username_0**: Interesting question! (Of course I guess "can be expressed" means "with a polynomial-time translation", as otherwise you can always express any regular language with a single UFA with an exponential blowup.) I don't know, and as @username_2 points out I guess you could ask a similar question on decision diagrams: can you efficiently rewrite uOBDDs (OBDDs with unambiguous disjunction) so that the disjunctions are at the top level?  

---

