Simultaneous reachability of NFA states

Question

Suppose I have a $n$-state non-deterministic finite automaton $F$ over alphabet $\Sigma$. Let $S(x)$ be the set of states reachable from the starting state by consuming string $x$.

I am interested for a given NFA to compute a $n \times n$ simultaneous reachability matrix $R$, such that $R_{ij} = [\exists x : \{i, j\} \subseteq S(x)]$.

From NFA product construction of $F$ with itself and then checking the reachability from the starting state I can compute $R$ in $O(n^4 \cdot |\Sigma|)$ time. Is there a better algorithm?

Answer 1

The Floyd-Warshall algorithm is typically used for computing the transitive closure of a directed graph, which is similar to finding the simultaneous reachability matrix in an NFA.

The time complexity of the Floyd-Warshall algorithm is 𝑂(𝑛^3⋅|Σ|), which is an improvement over the 𝑂(𝑛^4⋅|Σ|) complexity of the NFA product construction approach.