3
$\begingroup$

Let $A = \{\Sigma,Q,\delta,q_{0}, Q_{m}\}$ be a finite state machine (FSM). A state $q \in Q$ is reachable if there exists a string $s \in \Sigma^{*}$ such that $\delta(q_{0},s) = q$. The state $q$ is coreachable if there exists a string $s$ such that $\delta(q,s) \in Q_{m}$.

I'm wondering what is the computational complexity of the reachability-coreachability analysis of a FSM, as a function of $|Q|=n$. In particular, the input is a FSM $A$, and I'd like the algorithm to output a list of all states that are reachable, and a list of all states that are coreachable. What is the worst-case asymptotic complexity of this function, as a function of $n$?

$\endgroup$
1
$\begingroup$

Since the nature of the OP's question relates to discrete-event systems (as he/she indicated in one of the comments), the argument to derive the complexity can be different compared to what Apass.Jack proposed, as follows.

Given $n = |Q|$, $m = |Q_{m}|$, and $k = |\delta|$,

Reachability test shall be applied to every state in $Q\setminus\{Q_{m}\dot{\cup}\{q_{0}\}\}$ since the initial state does not need to be reachable, and the reachability of marked states are taken into account by coreachability. So, one has to check the reachability of $n-m-1$ states. Furthermore, coreachability test is only meaningful to $Q_{m}$, and we have to examine it $m$ times. In the worst case, one has to traverse the whole DFA to check (co)reacahbility. Thus, according to the complexity of BFS/DFS, which is, $O(|Q|+|\delta|) = O(n+k)$, one reads

$O((n+k)(n-m-1)) + O((n+k)m) = O((n+k)(n-1)) = O(n^2 + kn -n -k)$.

$n$ and $k$ are negligible since they are much less than $n^2$ and $kn$ yielding

$O(n^2+kn)$

$\endgroup$
  • $\begingroup$ This shows that there exists an algorithm whose running time is $O(n^2+kn)$, but not that this is the best possible running time (i.e., it doesn't rule out the possibility of some other, faster algorithm). $\endgroup$ – D.W. Jan 6 '19 at 1:02
  • 1
    $\begingroup$ @D.W.: (Regarding your comments) do you mean that it is possible to check both the reachbility and the correachability of all nodes using only a single DFS? If so, please share it as an answer, and then I'd delete mine which would be reasonably not the best approach anymore. $\endgroup$ – Roboticist Jan 6 '19 at 9:55
  • 1
    $\begingroup$ @D.W.: I believe that you mean there exists an algorithm with $O(n+k)$. If I got it right, can you elaborate a little bit on the sketch of its proof? $\endgroup$ – Roboticist Jan 6 '19 at 10:13
  • 1
    $\begingroup$ Nope, that's not what I'm saying. It's possible to find all reachable nodes in $O(nk)$ time using a single DFS (use do a DFS starting from the initial start state). That's faster than $O(n^2+kn)$ (if $k$ is smaller than $n$). Also, it's possible to find all coreachable nodes in $O(nk)$ time as well using a single DFS (create a new state $q_f$; add edges from each state in $Q_m$ to $q_f$; now do a DFS backwards starting from $q_f$). This is already described in Apass.Jack's answer, so I'm not writing a new answer as that would just duplicate what Apass.Jack has already explained. $\endgroup$ – D.W. Jan 6 '19 at 19:37
1
$\begingroup$

Let $m\ge1$ be the size of the alphabet $\Sigma$.


Let us restrict our attention to the two most common models of finite state machines (FSM), deterministic finite automatons (DFA) and non-deterministic finite automatons (NFA). We know that FSM corresponds naturally to the directed multi-graph as explained by Wikipedia entry on state diagram.

A $n$-state $DFA$ $D=(Q,\Sigma,\delta,q_0,F)$ corresponds a directed multi-graph $G$, whose nodes are also $Q$ and all of whose nodes have outdegree $m$. Whenever we mention some $q\in Q$, it will be clear whether we mean the state $q$ in $D$ or the node $q$ in $G$. It takes $O(mn)$ time to convert $D$ to $G$.

  • The problem of determining all reachable states from state $q_0$ in $D$ corresponds to the problem of determining all reachable nodes from node $q_0$ in $G$. If we use the classic breadth first traversal starting from node $q_0$ to solve the later problem, the worst case happens when we have to go through all arcs in $G$, which is $\Theta(mn)$ time-complexity. In fact, for any algorithm to determine the set of all reachable nodes, all edges must be checked.

  • The problem of determining all co-reachable states in $D$ corresponds to the problem of determining all reachable nodes from $q'$ in graph $G'$, where $G'$ is $G$ with all edges reversed and with one extra node $q'$ that is connected to all node $q_i\in F$. The conversion from $G$ to $G'$ takes $O(mn+n) = O(mn)$ time. If we use the classic breadth first traversal starting from node $q'$ to solve the later problem of all reachable nodes, the worst case happens when we have to go through all arcs in $G'$, which is $\Theta(m(n+1)=\Theta(mn)$ time-complexity. In fact, it is easy to see that asymptotically, solving the problem of co-reachability has the same worst-case time-complexity as solving the problem of reachability.

To summarize, the worse case to determine the reachability or co-reachability of a $n$-state DFA takes $\Theta(mn)$ time.


In this section, we will explain the exact meaning of the statement "all edges must be checked" for the case of reachable states.

(All edges by adversary) Let $G$ be a multi-graph $G$ of $n$ nodes and a start node $q_0$. Each node $q$ has exactly $m$ outgoing edges $\{q_\sigma\mid \sigma\in\Sigma \}$. The only way for us to know the other endpoint of $q_\sigma$ is to inquire from a truthful smart adversary $A$, who can config the other endpoint on the fly. Each inquiry must be "which node is the endpoint of $q_\sigma$ other than $q$?" for some $v$ and $\sigma$. The minimal number of inquiries needed to determine the set of reachable nodes from $q_0$ is $mn$.

Proof. Let $Q=\{q_0, q_1, \cdots, q_{n-1}\}$.

Here is $A$'s strategy to reply to the inquiry. Initialize $n$ empty set $S_q$, $q\in Q$. For an inquiry about $q_\sigma$ with $q=q_i$, there are five cases.

  • if $i\lt n-2$ and $\#S_q\lt m-1$, reply that $q_\sigma$ is the loop from $q$ to $q$. Add $\sigma$ to $S_q$.
  • if $i\lt n-2$ and $\#S_q= m-1$, reply that $q_\sigma= (q,q_{i+1})$. Add $\sigma$ to $S_q$.
  • if $i\ge n-2$ and $\#S_{q_{n-2}} + \#S_{q_{n-1}}\lt 2m-1$, reply that $q_\sigma$ is the loop from $q$ to $q$. Add $\sigma$ to $S_q$.
  • if $i\ge n-2$ and $\#S_{q_{n-2}} + \#S_{q_{n-1}}= 2m-1$, reply $q_\sigma=(q_{n-2}, q_{n-1})$ when $q=q_{n-2}$ and reply $q_\sigma=(q_{n-1}, q_0)$ when $q=q_{n-1}$. Add $\sigma$ to $S_q$.
  • if $\#S_\sigma= m$, the inquiry must have been done before and, hence, reply the same as before.

I will leave the rest of the proof as an exercise.


Exercise 1. Finish the proof of "all edges by adversary". Show that $A$'s strategy is consistent in the sense that there is one such $G$ that all replies of $A$ are true. Furthermore, after $mn-1$ inquires, we cannot determine whether $q_{n-1}$ is reachable from $q_0$ or not.

Interested readers can do the following exercise that deals with NFA.

Exercise 2. the worse case to determine the reachability or co-reachability of a $n$-state NFA takes $\Theta(mn^2)$ time.

$\endgroup$
  • $\begingroup$ You might have a different definition of DFA. However, mine is the standard one, as have been confirmed by Raphael, Wikipedia and the book introduction to the theory of computation. Anyway, in your definition, the number of edges is not greater than $nm$, correct? It can reach $nm$, right? Then my argument still holds for your version of DFA as well. $\endgroup$ – John L. Jan 5 '19 at 13:02
  • 1
    $\begingroup$ Considering $n$ and $m$ as the state size and the number of transitions, each DFS/BFS requires $O(n+m)$. One needs to check all $n$ states, thereby $O(n^2 + mn)$. Do I miss something?! $\endgroup$ – Roboticist Jan 5 '19 at 13:14
  • 1
    $\begingroup$ @Roboticist, yes, you are missing something. Rather than doing $n$ separate DFSs, it is possible to do a single DFS. $m$ is not the number of transitions; $m$ is the out-degree (so the total number of edges is at most $nm$, or is exactly $nm$, depending on which definition of a DFA you use). $\endgroup$ – D.W. Jan 6 '19 at 1:05

Your Answer

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

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