For an NFA $A$ with $n$ states and a word $w$, we can associate an $n$-dimensional vector $v_w$ with entries in $\mathbb{N}\cup\{0\}$ denoting the number of copies of the NFA in each state after reading $w$.

For standard NFAs, this vector doesn't have much meaning, only it's support does (e.g. for the subset construction). However, when considering certain cumulative properties of NFAs, this vector is meaningful (see example at the end of the post).

It would make sense that in an NFA, the behavior of the possible reachable vectors will be fairly "regular". Or at least have some nice properties.

I am looking for any results concerning these vectors.

Note that this problem has some resemblance to the matrix mortality problem. Thus, it may be the case that determining whether a certain vector is reachable is undecidable.

Example of when such vectors are meaningful: consider a semantics for a weighted NFA where there are weights on the edges, and the value of a word is the sum of the edges along all the runs of the NFA. In such NFAs, the state in the middle of a run is captured by such a vector and the accumulated sum along the run so far.

  • $\begingroup$ You probably mean $\mathbb N\cup\{\bot\}$ ? $\endgroup$ – Denis Sep 8 '13 at 16:41
  • 1
    $\begingroup$ can you assume that your automaton is complete (i.e. add a sink state if necessary) ? This does not change the meaning of the automaton, but makes the problem a lot easier, since the sum of elements of a vector can only grow or stay the same, decidability becomes easy to show. $\endgroup$ – Denis Sep 8 '13 at 16:53
  • $\begingroup$ We don't need $\bot$ - if a state is unreachable, the number of copies is 0. And sure - we can add a sink. The vector-reachability problem is not that interesting by itself, I'm looking for results on the sequence of reachable vectors (e.g. asymptotic results). $\endgroup$ – Shaull Sep 8 '13 at 17:03
  • $\begingroup$ It's not clear what you mean by "asymptotics results" or "the sequence of reachable vectors", when you don't have a sequence of vectors but rather a tree of vectors (where the directions are labelled by the alphabet). $\endgroup$ – Denis Sep 8 '13 at 17:30
  • 2
    $\begingroup$ What do you mean by "the number of copies of the NFA"? $\endgroup$ – J.-E. Pin Sep 8 '13 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.