---
res:
  bibo_abstract:
  - The synthesis problem asks for the automatic construction of a system from its
    specification. In the traditional setting, the system is “constructed from scratch”
    rather than composed from reusable components. However, this is rare in practice,
    and almost every non-trivial software system relies heavily on the use of libraries
    of reusable components. Recently, Lustig and Vardi introduced dataflow and controlflow
    synthesis from libraries of reusable components. They proved that dataflow synthesis
    is undecidable, while controlflow synthesis is decidable. The problem of controlflow
    synthesis from libraries of probabilistic components was considered by Nain, Lustig
    and Vardi, and was shown to be decidable for qualitative analysis (that asks that
    the specification be satisfied with probability 1). Our main contribution for
    controlflow synthesis from probabilistic components is to establish better complexity
    bounds for the qualitative analysis problem, and to show that the more general
    quantitative problem is undecidable. For the qualitative analysis, we show that
    the problem (i) is EXPTIME-complete when the specification is given as a deterministic
    parity word automaton, improving the previously known 2EXPTIME upper bound; and
    (ii) belongs to UP ∩ coUP and is parity-games hard, when the specification is
    given directly as a parity condition on the components, improving the previously
    known EXPTIME upper bound.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Krishnendu
      foaf_name: Chatterjee, Krishnendu
      foaf_surname: Chatterjee
      foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-4561-241X
  - foaf_Person:
      foaf_givenName: Laurent
      foaf_name: Doyen, Laurent
      foaf_surname: Doyen
  - foaf_Person:
      foaf_givenName: Moshe
      foaf_name: Vardi, Moshe
      foaf_surname: Vardi
  bibo_doi: 10.1007/978-3-662-47666-6_9
  bibo_volume: 9135
  dct_date: 2015^xs_gYear
  dct_identifier:
  - UT:000364317900009
  dct_isPartOf:
  - http://id.crossref.org/issn/978-3-662-47665-9
  dct_language: eng
  dct_publisher: Springer Nature@
  dct_title: The complexity of synthesis from probabilistic components@
...