License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2016.8
URN: urn:nbn:de:0030-drops-61742
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6174/
Go to the corresponding LIPIcs Volume Portal

Brenguier, Romain

Optimal Assumptions for Synthesis

pdf-format:
LIPIcs-CONCUR-2016-8.pdf (0.5 MB)

Abstract

Controller synthesis is the automatic construction a correct system from its specification.
This often requires assumptions about the behaviour of the environment.
It is difficult for the designer to identify the assumptions that ensures the existence of a correct controller, and doing so manually can lead to assumptions that are stronger than necessary.
As a consequence the generated controllers are suboptimal in terms of robustness.
In this work, given a specification, we identify the weakest assumptions that ensure the existence of a controller.
We also consider two important classes of assumptions: the ones that can be ensured by the environment and assumptions that restricts only inputs of the systems.
We show that optimal assumptions correspond to strongly winning strategies, admissible strategies and remorse-free strategies depending on the classes.
Using these correspondences, we then propose an algorithm for computing optimal assumptions that can be ensured by the environment.

BibTeX - Entry

@InProceedings{brenguier:LIPIcs:2016:6174,
  author =	{Romain Brenguier},
  title =	{{Optimal Assumptions for Synthesis}},
  booktitle =	{27th International Conference on Concurrency Theory (CONCUR 2016)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-017-0},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{59},
  editor =	{Jos{\'e}e Desharnais and Radha Jagadeesan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6174},
  URN =		{urn:nbn:de:0030-drops-61742},
  doi =		{10.4230/LIPIcs.CONCUR.2016.8},
  annote =	{Keywords: Controller synthesis, Parity games, Admissible strategies}
}

Keywords: Controller synthesis, Parity games, Admissible strategies
Collection: 27th International Conference on Concurrency Theory (CONCUR 2016)
Issue Date: 2016
Date of publication: 24.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI