Computer Science – Logic in Computer Science
Scientific paper
2011-02-21
EPTCS 50, 2011, pp. 33-45
Computer Science
Logic in Computer Science
In Proceedings iWIGP 2011, arXiv:1102.3741
Scientific paper
10.4204/EPTCS.50.3
The idea of automatic synthesis of reactive programs starting from temporal logic (LTL) specifications is quite old, but was commonly thought to be infeasible due to the known double exponential complexity of the problem. However, new ideas have recently renewed the interest in LTL synthesis: One major new contribution in this area is the recent work of Piterman et al. who showed how polynomial time synthesis can be achieved for a large class of LTL specifications that is expressive enough to cover many practical examples. These LTL specifications are equivalent to omega-automata having a so-called GR(1) acceptance condition. This approach has been used to automatically synthesize implementations of real-world applications. To this end, manually written deterministic omega-automata having GR(1) conditions were used instead of the original LTL specifications. However, manually generating deterministic monitors is, of course, a hard and error-prone task. In this paper, we therefore present algorithms to automatically translate specifications of a remarkable large fragment of LTL to deterministic monitors having a GR(1) acceptance condition so that the synthesis algorithms can start with more readable LTL specifications.
Morgenstern Andreas
Schneider Klaus
No associations
LandOfFree
A LTL Fragment for GR(1)-Synthesis does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A LTL Fragment for GR(1)-Synthesis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A LTL Fragment for GR(1)-Synthesis will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-519857