Assume-Guarantee Synthesis

Krishnendu Chatterjee, Thomas A. HenzingerTACAS 2007 · OpenReview

Abstract

The classical synthesis problem for reactive systems asks, given a proponent process A and an opponent process B, to refine A so that the closed-loop system A||B satisfies a given specification Φ. The solution of this problem requires the computation of a winning strategy for proponent A in a game against opponent B. We define and study the co-synthesis problem, where the proponent A consists itself of two independent processes, A = A 1||A 2, with specifications Φ 1 and Φ 2, and the goal is to refine both A 1 and A 2 so that A 1||A 2||B satisfies Φ 1 ∧ Φ 2. For example, if the opponent B is a fair scheduler for the two processes A 1 and A 2, and Φ i specifies the requirements of mutual exclusion for A i (e.g., starvation freedom), then the co-synthesis problem asks for the automatic synthesis of a mutual-exclusion protocol.
BibTeX
@inproceedings{chatterjee2007assume,
  author = {Krishnendu Chatterjee and Thomas A. Henzinger},
  title = {{Assume-Guarantee Synthesis}},
  booktitle = {TACAS},
  year = {2007},
  url = {https://openreview.net/forum?id=oTmRFx5zhK},
}

Loading related content...

Figure