7
$\begingroup$

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)?

$\endgroup$

1 Answer 1

10
$\begingroup$

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.)

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Sep 1, 2023 at 9:35
  • $\begingroup$ 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) $\endgroup$
    – holf
    Sep 1, 2023 at 9:48
  • $\begingroup$ 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? $\endgroup$
    – a3nm
    Sep 1, 2023 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.