<p>I claim that if for some language there is a CFA with with $s$ states and $0$ or $c$ accepting paths for every word, then there is a UFA with $C_ss^c$ states. The basic idea is that the states of the UFA are the (ordered) c-tuples of the states of the CFA and it accepts if and only if all c states accept. Of course we also have to make sure that these were indeed different computations and that we do not count all $c!$ permutations, so for these we need some extra $C_s$ bits of storage.</p>

<p>A bit more detailed description of the basic idea: If $(s_1,\ldots,s_c)$ is a state of the UFA, then it has a transition from it (reading some letter $a$) to the state $(s_1',\ldots,s_c')$ if and only if the CFA has a transition (reading letter $a$) from $s_i$ to $s_i'$ for every $i$. A state $(s_1,\ldots,s_c)$ is accepting if and only if $s_i$ is accepting for every $i$. Of course the starting state of the UFA is $(s_0,\ldots,s_0)$ where $s_0$ is the starting state of the CFA.</p>

<p>The problem with the above is that the $c$ simulated runs of the CFA might be the same. So we add some extra information, encoded, say, in a graph on $c$ vertices that has an edge between vertex $i$ and vertex $j$ if during the run so far at least once we had that $c_i\ne c_j$.</p>

<p>Now we still have a problem, that we have counted everything $c!$ times because of the possible permutations. We can remedy this by requiring that if the $i$-th and $j$-th states have been the same until now and in the next step they would differ, then in the next step the $i$-th state should have a larger index. </p>

CC BY-SA 3.0
2014-06-10T18:04:03.993Z
Thanks for you answer @domotorp. Unfortunately, I can't say I understand it. Can you give more details (e.g. How would the proof of primality be encoded?). Thanks !
R B
CC BY-SA 3.0
2014-06-10T21:06:12.693Z
I have anyhow realized that there is also a UFA for that language, so forget about it. What about the remaining part of my answer?
domotorp
CC BY-SA 3.0
2014-06-11T13:04:48.227Z
I'm not sure I follow. If $M$ is CFA with $k=c$, then it doesn't mean there could only be $c$ paths for every word $w$, just that only $c$ of them will end in an accepting state. What would the states of the UFA be? Can you please try to formalize it?
R B
CC BY-SA 3.0
2014-06-11T13:22:31.683Z
There you go, I hope now it's clear.
domotorp
CC BY-SA 3.0
2014-06-08T14:30:57.270Z
2014-06-11T13:21:21.600Z
2014-06-11T13:21:21.600Z
domotorp
<p>We say that NFA $M$ is <em>Constantly Ambiguous</em> if there exist $k\in \mathbb{N}$ such that any word $w\in \Sigma^*$ is accepted by either $0$ or (exactly) $k$ paths.</p>

<p>If automaton $M$ is constantly ambiguous for $k=1$, then $M$ is called <em>Unambiguous FA</em> (UFA).</p>

<p>Let $L$ be a regular language.</p>

<p><strong>Can some constantly ambiguous automaton $M_c$ for $L$ be smaller than the smallest UFA that accepts $L$? How much smaller could it be?</strong></p>

<p><strong>Can Finitely ambiguous automaton be exponentially smaller than the smallest CFA for the same language?</strong></p>

<p>It is known that there are <em>Finitely</em> ambiguous automatons (there exists $k$, such that every word is accepted by <strong>up to</strong> $k$ paths) which are exponentially smaller than the smallest UFA for the same language, but I haven't seen something about constant ambiguity.</p>

<h2>Also, here's a <a href="https://cstheory.stackexchange.com/questions/20562/how-small-can-a-nfa-be-compared-to-the-minimal-unambiguous-finite-automaton-uf?rq=1">related question</a> I've posted here a few months ago.</h2>

<p>EDIT:</p>

<p>Domotorp's answer shows that $CFA$ is polynomially reducible to $UFA$, but doesn't address the question of whether we can gain that polynomial space reduction by $CFA$s.</p>

<p>So the new question becomes: <strong>How much smaller (linearly/quadratically/etc.) can a $CFA$ be compared to the minimal $UFA$? for the same language?</strong></p>

CC BY-SA 3.0
2014-06-04T20:17:02.650Z
are $\epsilon$-transitions allowed?
Denis
CC BY-SA 3.0
2014-06-04T20:52:48.703Z
Perhaps this can be helpful: in [Kupke, On Separating Constant from Polynomial Ambiguity of Finite Automata](http://www.sofsem.cz/sofsem06/data/prezentace/23/A/kupke.pdf) the following hierarchy is presented: $\text{dfa} \prec_{2^n} \text{unfa} \prec_{2^n} \text{cafa} \prec_{2^n}  \text{???} \prec_{2^n} \text{pafa} \prec_{2^n} {nfa}$
I didn't check the [related paper](http://link.springer.com/chapter/10.1007%2F11611257_36) because it is behind paywall.
Marzio De Biasi
CC BY-SA 3.0
2014-06-04T21:41:59.850Z
Thanks @MarzioDeBiasi, but unfortunately this doesn't help (I was also hopeful when I saw the presentation). They use different notation than the one I use (and I've seen in different papers). Their "Constant Ambiguity" is what I called finite ambiguity, so the relation between their Cafa and UFA was already known to me. Since my application is counting solutions for NPC problems, my language is always finite, and as such, every word is accepted by $O(1)$ paths, which they called "constant".
R B
CC BY-SA 3.0
2014-06-04T21:42:38.487Z
I'm wondering if my definition helps reduce state complexity, as I have CFA which is exponentially smaller than the smallest UFA I know to construct, and I was wondering if it's possible that there is no small UFA for the language.
R B
CC BY-SA 3.0
2014-06-04T21:43:23.480Z
@Denis, yes, but would it help you reduce the state complexity? I'd assume you could only reduce the number of edges by such moves.
R B
CC BY-SA 4.0
2023-09-01T03:55:32.403Z
Note that, for the related definition of "constant ambiguity" as meaning the NFA has *at most $k$* accepting paths for some constant $k$, the result is different: for $k=2$ already you cannot rewrite in polynomial-time to an unambiguous automaton. https://cstheory.stackexchange.com/questions/53257/converting-2-ambiguous-nfa-to-unambiguous-nfa
Antoine Amarilli 'a3nm'
<complexity-classes><fl.formal-languages><automata-theory><regular-language>
Can constant ambiguity reduce the state complexity of a regular languages?
R B
# Can constant ambiguity reduce the state complexity of a regular languages?

(Asked by: username_0 on 2014-06-02)

We say that NFA $M$ is *Constantly Ambiguous* if there exist $k\in \mathbb{N}$ such that any word $w\in \Sigma^\*$ is accepted by either $0$ or (exactly) $k$ paths.

If automaton $M$ is constantly ambiguous for $k=1$, then $M$ is called *Unambiguous FA* (UFA).

Let $L$ be a regular language.

**Can some constantly ambiguous automaton $M\_c$ for $L$ be smaller than the smallest UFA that accepts $L$? How much smaller could it be?**

**Can Finitely ambiguous automaton be exponentially smaller than the smallest CFA for the same language?**

It is known that there are *Finitely* ambiguous automatons (there exists $k$, such that every word is accepted by **up to** $k$ paths) which are exponentially smaller than the smallest UFA for the same language, but I haven't seen something about constant ambiguity.

## Also, here's a [related question](https://cstheory.stackexchange.com/questions/20562/how-small-can-a-nfa-be-compared-to-the-minimal-unambiguous-finite-automaton-uf?rq=1) I've posted here a few months ago.

EDIT:

Domotorp's answer shows that $CFA$ is polynomially reducible to $UFA$, but doesn't address the question of whether we can gain that polynomial space reduction by $CFA$s.

So the new question becomes: **How much smaller (linearly/quadratically/etc.) can a $CFA$ be compared to the minimal $UFA$? for the same language?**

**Tags:** complexity-classes, fl.formal-languages, automata-theory, regular-language
> **Comments:**
> **username_1**: are $\epsilon$-transitions allowed?  
> **username_2**: Perhaps this can be helpful: in [Kupke, On Separating Constant from Polynomial Ambiguity of Finite Automata](http://www.sofsem.cz/sofsem06/data/prezentace/23/A/kupke.pdf) the following hierarchy is presented: $\text{dfa} \prec_{2^n} \text{unfa} \prec_{2^n} \text{cafa} \prec_{2^n}  \text{???} \prec_{2^n} \text{pafa} \prec_{2^n} {nfa}$ I didn't check the [related paper](http://link.springer.com/chapter/10.1007%2F11611257_36) because it is behind paywall.  
> **username_0**: Thanks @MarzioDeBiasi, but unfortunately this doesn't help (I was also hopeful when I saw the presentation). They use different notation than the one I use (and I've seen in different papers). Their "Constant Ambiguity" is what I called finite ambiguity, so the relation between their Cafa and UFA was already known to me. Since my application is counting solutions for NPC problems, my language is always finite, and as such, every word is accepted by $O(1)$ paths, which they called "constant".  
> **username_0**: I'm wondering if my definition helps reduce state complexity, as I have CFA which is exponentially smaller than the smallest UFA I know to construct, and I was wondering if it's possible that there is no small UFA for the language.  
> **username_0**: @Denis, yes, but would it help you reduce the state complexity? I'd assume you could only reduce the number of edges by such moves.  
> **username_3**: Note that, for the related definition of "constant ambiguity" as meaning the NFA has *at most $k$* accepting paths for some constant $k$, the result is different: for $k=2$ already you cannot rewrite in polynomial-time to an unambiguous automaton. https://cstheory.stackexchange.com/questions/53257/converting-2-ambiguous-nfa-to-unambiguous-nfa  

---

## 1 answers

### Answer by username_4 on 2014-06-08. Score: 5

I claim that if for some language there is a CFA with with $s$ states and $0$ or $c$ accepting paths for every word, then there is a UFA with $C\_ss^c$ states. The basic idea is that the states of the UFA are the (ordered) c-tuples of the states of the CFA and it accepts if and only if all c states accept. Of course we also have to make sure that these were indeed different computations and that we do not count all $c!$ permutations, so for these we need some extra $C\_s$ bits of storage.

A bit more detailed description of the basic idea: If $(s\_1,\ldots,s\_c)$ is a state of the UFA, then it has a transition from it (reading some letter $a$) to the state $(s\_1',\ldots,s\_c')$ if and only if the CFA has a transition (reading letter $a$) from $s\_i$ to $s\_i'$ for every $i$. A state $(s\_1,\ldots,s\_c)$ is accepting if and only if $s\_i$ is accepting for every $i$. Of course the starting state of the UFA is $(s\_0,\ldots,s\_0)$ where $s\_0$ is the starting state of the CFA.

The problem with the above is that the $c$ simulated runs of the CFA might be the same. So we add some extra information, encoded, say, in a graph on $c$ vertices that has an edge between vertex $i$ and vertex $j$ if during the run so far at least once we had that $c\_i\ne c\_j$.

Now we still have a problem, that we have counted everything $c!$ times because of the possible permutations. We can remedy this by requiring that if the $i$-th and $j$-th states have been the same until now and in the next step they would differ, then in the next step the $i$-th state should have a larger index.

> **Comments:**
> **username_0**: Thanks for you answer @domotorp. Unfortunately, I can't say I understand it. Can you give more details (e.g. How would the proof of primality be encoded?). Thanks !  
> **username_4**: I have anyhow realized that there is also a UFA for that language, so forget about it. What about the remaining part of my answer?  
> **username_0**: I'm not sure I follow. If $M$ is CFA with $k=c$, then it doesn't mean there could only be $c$ paths for every word $w$, just that only $c$ of them will end in an accepting state. What would the states of the UFA be? Can you please try to formalize it?  
> **username_4**: There you go, I hope now it's clear.  

---

