conference paper published yes Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Laurent Doyen author Moshe Vardi author KrCh department ICALP: Automata, Languages and Programming Modern Graph Algorithmic Techniques in Formal Verification project Game Theory project Quantitative Graph Games: Theory and Applications project 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. Springer Nature2015Kyoto, Japan eng 978-3-662-47665-9 1502.04844 00036431790000910.1007/978-3-662-47666-6_9 9135108 - 120 K. Chatterjee, L. Doyen, M. Vardi, in:, 42nd International Colloquium, Springer Nature, 2015, pp. 108–120. Chatterjee, K., Doyen, L., &#38; Vardi, M. (2015). The complexity of synthesis from probabilistic components. In <i>42nd International Colloquium</i> (Vol. 9135, pp. 108–120). Kyoto, Japan: Springer Nature. <a href="https://doi.org/10.1007/978-3-662-47666-6_9">https://doi.org/10.1007/978-3-662-47666-6_9</a> K. Chatterjee, L. Doyen, and M. Vardi, “The complexity of synthesis from probabilistic components,” in <i>42nd International Colloquium</i>, Kyoto, Japan, 2015, vol. 9135, pp. 108–120. Chatterjee, Krishnendu, Laurent Doyen, and Moshe Vardi. “The Complexity of Synthesis from Probabilistic Components.” In <i>42nd International Colloquium</i>, 9135:108–20. Springer Nature, 2015. <a href="https://doi.org/10.1007/978-3-662-47666-6_9">https://doi.org/10.1007/978-3-662-47666-6_9</a>. Chatterjee, Krishnendu, et al. “The Complexity of Synthesis from Probabilistic Components.” <i>42nd International Colloquium</i>, vol. 9135, Springer Nature, 2015, pp. 108–20, doi:<a href="https://doi.org/10.1007/978-3-662-47666-6_9">10.1007/978-3-662-47666-6_9</a>. Chatterjee K, Doyen L, Vardi M. 2015. The complexity of synthesis from probabilistic components. 42nd International Colloquium. ICALP: Automata, Languages and Programming, LNCS, vol. 9135, 108–120. Chatterjee K, Doyen L, Vardi M. The complexity of synthesis from probabilistic components. In: <i>42nd International Colloquium</i>. Vol 9135. Springer Nature; 2015:108-120. doi:<a href="https://doi.org/10.1007/978-3-662-47666-6_9">10.1007/978-3-662-47666-6_9</a> 16092018-12-11T11:53:00Z2025-09-23T13:48:35Z