Question

I have a set of tasks, and a LTL specification that describes which orders of the tasks are legal. I want to find a way to enumerate all permutations of the tasks that meet the specification.

For example, suppose there are two tasks, A and B, and the LTL spec <>(A&<>B) is. This spec says that A should eventually be done and after A eventually B should be done. In this case, there is only one legal sequence: (A,B).

enter image description here

We can convert the LTL formula to a Buchi automaton, as shown above. Then since this example is so trivial, it is easy to see that the only legal sequence is A-->B.

But what if we had a more complex LTL formula? How could we enumerate all legal sequences (permutations) of the tasks that satisfy the spec? Is there an efficient algorithm to do this?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top