Given a directed graph. For a vertex $v$, consider a "walk function" $w_v$ on natural numbers, such that $w_v(n)$ is the number of walks, consisting of exactly $n$ edges, starting at $v$. Let's call vertices equivalent if they have identical "walk functions".
What's needed is a computation of this equivalence. Say, an algorithm that assigns a number to each vertex of a given digraph, so that vertices are equivalent iff they get the same number.
It's the 3rd time I face this kind of problem. Is it known? What about its complexity? (It resembles DFA minimization a little bit, and a solution can be built using straightforward "subdivision idea" and some analogy with Hopcroft's algorithm for DFAs, but it feels that this problem must be much simpler.)
UPDATE I did a cross-post of this to CSSE (this is the first and the last time I do so I believe). I think the further discussion (if any) should continue there, as it seems to be the more appropriate place for that.
Here's one possible approach, though I'm not sure how it compares with your approach based on Hopcroft's algorithm.
Let $\mathbf j$ be the all-ones vector in $|V|$ dimensions, and let $A$ be the $|V| \times |V|$ adjacency matrix of the graph. Then the vector $$ \sum_{n \ge 0} (A^n \mathbf j)z^n = (I - zA)^{-1} \mathbf j $$ gives the generating function for the walk function from every vertex: its $i^{\text{th}}$ entry is the sum $$ \sum_{n \ge 0} w_v(n) z^n. $$ This sum converges for $|z| < \frac1{|V|}$, since $w_v(n)$ grows at most as fast as $|V|^n$. Computing $(I-zA)^{-1} \mathbf j$ for any such value of $z$ gives a vector in which entries corresponding to equivalent vertices have equal values. Moreover, each component should be a rational function in $z$, so all values of $z$ apart from finitely many exceptional values should successfully distinguish all inequivalent vertices.