4
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.