Converting 2-ambiguous NFA to unambiguous NFA

Question

This must be known, but somehow I can't locate a reference about this. Let $A$ be a nondeterministic finite automaton (NFA) over words of an alphabet $\Sigma$. I say that $A$ is unambigous 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 (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)?

Answer 1

I think that this is in fact not possible, thanks to the (recent and difficult!) ICALP'22 results of Göös et al..

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. There are similar results for $k$-ambiguous tree automata, in Seidl, SIAM J. Comput., 1990. (Unfortunately, no open-access versions of these papers that I can see.)