<p>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$.</p>

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

<p>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.</p>

<blockquote>
  <p>I am looking for any results concerning these vectors.</p>
</blockquote>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-09-08T16:41:50.533Z
You probably mean $\mathbb N\cup\{\bot\}$ ?
Denis
CC BY-SA 3.0
2013-09-08T16:53:28.850Z
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.
Denis
CC BY-SA 3.0
2013-09-08T17:03:09.443Z
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).
Shaull
CC BY-SA 3.0
2013-09-08T17:30:49.017Z
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).
Denis
CC BY-SA 3.0
2013-09-08T17:53:43.437Z
What do you mean by "the number of copies of the NFA"?
J.-E. Pin
CC BY-SA 3.0
2013-09-08T20:14:23.267Z
Consider the run tree of the NFA, and count, for each state, in how many leafs it appears.

@dkuper - I know it's not clear. I am looking for any results, and I don't want to restrict anything.
Shaull
<automata-theory>
Properties of the number of copies of an NFA in each state
Shaull
# Properties of the number of copies of an NFA in each state

(Asked by: username_0 on 2013-09-08)

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.

**Tags:** automata-theory

> **Comments:**
> **username_1**: You probably mean $\mathbb N\cup\{\bot\}$ ?  
> **username_1**: 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.  
> **username_0**: 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).  
> **username_1**: 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).  
> **username_2**: What do you mean by "the number of copies of the NFA"?  
> **username_0**: Consider the run tree of the NFA, and count, for each state, in how many leafs it appears.  @dkuper - I know it's not clear. I am looking for any results, and I don't want to restrict anything.  

---

## 0 answers

