16
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\begingroup$ are $\epsilon$-transitions allowed? $\endgroup$
    – Denis
    Jun 4, 2014 at 20:17
  • $\begingroup$ Perhaps this can be helpful: in Kupke, On Separating Constant from Polynomial Ambiguity of Finite Automata 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 because it is behind paywall. $\endgroup$
    – Marzio De Biasi
    Jun 4, 2014 at 20:52
  • $\begingroup$ 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". $\endgroup$
    – R B
    Jun 4, 2014 at 21:41
  • $\begingroup$ 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. $\endgroup$
    – R B
    Jun 4, 2014 at 21:42
  • 1
    $\begingroup$ @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. $\endgroup$
    – R B
    Jun 4, 2014 at 21:43

1 Answer 1

Reset to default
5
+50
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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 ! $\endgroup$
    – R B
    Jun 10, 2014 at 18:04
  • $\begingroup$ 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? $\endgroup$
    – domotorp
    Jun 10, 2014 at 21:06
  • $\begingroup$ 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? $\endgroup$
    – R B
    Jun 11, 2014 at 13:04
  • $\begingroup$ There you go, I hope now it's clear. $\endgroup$
    – domotorp
    Jun 11, 2014 at 13:22

Your Answer

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

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