Generalised Rabin(1) synthesis

Details Generalised Rabin(1) synthesis Generalised Rabin(1) synthesis

2010-03-08

arxiv.org/abs/1003.1684v2

Computer Science

Logic in Computer Science

14 pages

Scientific paper

We present a novel method for the synthesis of finite state systems that is a generalisation of the generalised reactivity(1) synthesis approach by Piterman, Pnueli and Sa'ar. In particular, we describe an efficient method to synthesize systems from linear-time temporal logic specifications for which all assumptions and guarantees have a Rabin index of one. We show how to build a parity game with at most five colours that captures all solutions to the synthesis problem from such a specification. This parity game has a structure that is amenable to symbolic implementations. We furthermore show that the results obtained are in some sense tight, i.e., that there does not exist a similar synthesis method for assumptions and specifications of higher Rabin index, unless P=NP.

Affiliated with

Also associated with

No associations

Rating

Generalised Rabin(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 Generalised Rabin(1) synthesis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generalised Rabin(1) synthesis will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-678011