A min-plus weighted automaton (WFA) is a nondeterministic automaton with a weight function that assigns each transition a weight in $\mathbb{N}$. The weights along a run are summed, and the value of a word is the value of the minimal accepting run of the automaton on it.

In a beautiful paper, Kirsten and Lombardy show that deciding unambiguity and sequentiality (i.e. determinizability) for WFAs is decidable for polynomially ambiguous WFA (the general case has been open for years).

Working on related problems, I am trying to tackle the following:

Is there an example of an exponentially-ambiguous WFA for which there is no equivalent polynomially ambiguous WFA?

Note that by "equivalent" we mean that they represent the same (perhaps partial) function $f:\Sigma^*\to \mathbb{N}$.

Some side-notes:

  • It is known that exponentially-ambiguous NFAs are exponentially more succinct than polynomially-ambiguous NFAs. But this is non-trivial. This suggests that in the WFA case this would also be not easy.

  • It is well known that WFAs are, in general, non-determinizable. For example, it is easy to construct a WFA for the function that returns the minimal number of occurrences of a certain letter in a word, but this cannot be done with a deterministic WFA. This suggests that the hierarchy between different classes of ambiguity might also be proper (hence my question).

  • Exponentially ambiguous automata have a very simple syntactic structure: an automaton is exponentially ambiguous iff there is a state $q$ and a word $w$ such that $q$ is reachable from itself using $w$ in at least two different paths.


1 Answer 1


Here is a natural candidate: the alphabet is $\{a,b,c\}$, and to a word $v=u_1cu_2c\dots cu_k$ with each $u_i\in\{a,b\}^*$, you want to associate $$f(v)=\sum_{i=1}^k \min(|u_i|_a,|u_i|_b)$$

There is a straigthforward exponentially ambiguous automaton for this $f$: each time you see a $c$, guess if you go to a state counting $a$'s or to a state counting $b$'s. It should not be too hard to prove that only exponentially ambigous automata recognize this function $f$. As a very sketchy argument, consider the fact that between two $c$'s, you must either count the number of $a$ or the number of $b$, so you need two different states to do so. Since you must be able to oscillate between these states, it means that you have distinct paths of the form $p\stackrel{w}{\longrightarrow} p$ for some state $p$ and word $w$ (containing some $c$'s).

  • $\begingroup$ Thanks! I actually played with the same example, only for a fixed $k$. Didn't occur to me to let $k$ be unbounded... $\endgroup$
    – Shaull
    Jan 22, 2016 at 12:28

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.