  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 contributions for controlflow synthesis
from probabilistic components are 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 $\cap$ 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.

Logic in Computer Science