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.