License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09501.2
URN: urn:nbn:de:0030-drops-26702
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2670/
Go to the corresponding Portal

Schewe, Sven

Software Synthesis is Hard -- and Simple

pdf-format:
09501.ScheweSven.ExtAbstract.2670.pdf (0.1 MB)

Abstract

While the components of distributed hardware systems can reasonably be assumed to be synchronised, this is not the case for the components of distributed software systems. This has a strong impact on the class of synthesis problems for which decision procedures exist: While there is a rich family of distributed systems, including pipelines, chains, and rings, for which the realisability and synthesis problem is decidable if the system components are composed synchronously, it is well known that the asynchronous synthesis problem is only decidable for monolithic systems. From a theoretical point of view, this renders distributed software synthesis undecidable, and one is tempted to conclude that synthesis of asynchronous systems, and hence of software, is much harder than the synthesis of synchronous systems. Taking a more practical approach, however, reveals that bounded synthesis, one of the most promising synthesis techniques, can easily be extended to asynchronous systems. This merits the hope that the promising results from bounded synthesis will carry over to asynchronous systems as well.

BibTeX - Entry

@InProceedings{schewe:DagSemProc.09501.2,
  author =	{Schewe, Sven},
  title =	{{Software Synthesis is Hard – and Simple}},
  booktitle =	{Software Synthesis},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9501},
  editor =	{Ratislav Bodik and Orna Kupferman and Douglas R. Smith and Eran Yahav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2010/2670},
  URN =		{urn:nbn:de:0030-drops-26702},
  doi =		{10.4230/DagSemProc.09501.2},
  annote =	{Keywords: Synthesis, Temporal Logics}
}

Keywords: Synthesis, Temporal Logics
Collection: 09501 - Software Synthesis
Issue Date: 2010
Date of publication: 08.07.2010

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