Synthesis of Succinct Systems

Details Synthesis of Succinct Systems Synthesis of Succinct Systems

2012-02-24

arxiv.org/abs/1202.5449v1

Computer Science

Formal Languages and Automata Theory

Scientific paper

Synthesis of correct by design systems from specification has recently attracted much attention. The theoretical results imply that this problem is highly intractable, e.g., synthesizing a system is 2EXPTIME-complete for an LTL specification, and EXPTIME-complete for a CTL specification. However, an argument against it is that the temporal specification is highly compact, and the complexity reflects the large size of the system constructed. In that respect, the complexity should, perhaps, be specified relative to the size of the minimal satisfying system. A careful observation reveals that the size of the system is presented in such arguments as the size of its state space. This view is a bit nonstandard, in the sense that the state space can be exponentially larger than the size of a reasonable implementation such as a circuit or a program. Although this alternative measure of the size of the synthesized system is more intuitive (e.g., this is the standard way model checking problems are measured), research on synthesis has so far stayed with measuring the system in terms of the explicit state space. This raises the question of whether or not there always exists a small system. In this paper, we show that this is the case if, and only if, PSPACE = EXPTIME.

Affiliated with

Also associated with

No associations

Rating

Synthesis of Succinct Systems 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 Synthesis of Succinct Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Synthesis of Succinct Systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-78613