Number of accepting path of a non deterministic automaton

Question

I have a question that seems to me really natural and have probably already been studied. But keyword search on this site or google does not seems to help me to find any relevent paper.

I have got a finite non deterministic automaton $A$ over an alphabet $\alpha$ without epsilon-transition.

What can I tell about the number of different path the automaton could take for accepting a word ? In particular, I want to know if this number is bounded, or if for every $c$ I can find a word $w_c$ that is accepted in at least $c$ different way by the automaton.

Right now, I can find some necessary, and some sufficient condition, but not any necessary and sufficient condition, for the number to be unbounded

By clarity, I'll define the way I cound the number of accepting path. Let $w\in\alpha^*$ and $q$ a state, I can define the number of path to $q$ by inuction on $|w|$ by $N(\epsilon,q)=1$ if $q\in I$ else $0$, where $I$ is the set of initial state and $F$ of final state. $N(ws,q)=\sum_{q'\in Q\atop \delta(q',s)=q}N(w,q')$.

Then the number of path is $\sum_{q \in F}N(w,q)$.

Answer 1

This concept is called the ambiguity of the NFA. Typically, there are 3 classes of ambiguity in this context: Bounded, polynomially bounded, and exponentially bounded.

Every NFA has at most an exponential number of runs on a given word (this is easy to see).

Interestingly, there is a simple syntactic characterization of polynomially bounded NFAs:

An NFA has a polynomial number of runs on a word $w$ iff for every state $q$, there is at most one cycle from $q$ to itself on every word $x\in \Sigma^*$. See this for details.

Testing for bounded ambiguity is PSPACE-complete. A good starting point is this paper