2
$\begingroup$

Consider a transition system defined by $\langle S,T \rangle$, where $S$ is a set of states and $T \subseteq S \times S$ is a set of transitions, where $T$ is total, i.e. for every state $s$ there is at least one outgoing transitions $(s,s') \in T$.

Each path corresponds to a set of states, namely, the states visited along that path. Given a transition system $\langle S,T \rangle$ and an initial state $s_0 \in S$, I would like an algorithm that outputs the list of all sets of states that can arise from all infinite paths in $\langle S,T \rangle$ that start at $s_0$.

As a trivial example consider $S = \{s_0, s_1, s_2 \}$, $T = \{(s_0,s_1),(s_0,s_2),(s_1,s_1),(s_2,s_2)\}$, with initial state $s_0$; I would like the algorithm to output $\{s_0,s_1\}, \{s_0,s_2\}$.

Is there an algorithm for this problem? I believe this can be accomplished with strongly connected components, but I don't know what to search for in the literature.

$\endgroup$
2
  • $\begingroup$ It is not actually clear what you're asking, can you please clearly define what your problem is? $\endgroup$ – Watercrystal Mar 8 at 12:31
  • 1
    $\begingroup$ Could you check whether my edited version of the question accurately captures the problem you are looking to solve? $\endgroup$ – D.W. Mar 9 at 6:23
2
$\begingroup$

Since the set you want to output can be exponential in the size of the transition system, there is clearly no polynomial algorithm to enumerate it.

Thus, let's focus on an exponential time solution. To this end, it is actually quite easy to find a naive algorithm:

For every subset $Q\subseteq S$ (that contains $s_0$), in order to check whether $Q$ should be outputted by the algorithm, look at the subgraph induced by $Q$, and check whether there is a path from $s_0$ that goes through all the vertices in the induced subgraph.

One way to do the latter, is to indeed decompose the subgraph to its strongly connected components (SCCs), then look at the tree of SCCs, and make sure it's simply a directed path from $s_0$. If it is not a path, then you cannot traverse the entire set $Q$, as you would need to select a branching in the tree from which you cannot go back.

Thus, the test of whether $Q$ should be outputted can be done in polynomial time.

$\endgroup$
2
  • $\begingroup$ Yes, that was also my intuition for the naive algorithm. I was hoping there was a known algorithm to this problem. I've tried using the search terms "initial maximal execution fragments" with variations, but haven't found anything. Would you have an idea of what I could search for, or do you believe there isn't an established algorithm for this problem? $\endgroup$ – Sindri P. Mar 9 at 11:42
  • $\begingroup$ Since the algorithm above is quite simple, I don't believe there is any published work on this. Not that I know of, anyway. $\endgroup$ – Shaull Mar 9 at 12:01

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.