An exponentially-ambiguous weighted automaton without an equivalent polynomially-ambiguous automaton

Question

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.

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