SYNTHESIS FROM PROBABILISTIC COMPONENTS
Yoad Lustig A, Sumit Nain B, Moshe, Y. Vardi · 2012
Synthesis is the automatic construction of a system from its specification. In classical synthesis algorithms, it is always assumed that the system is ``constructed from scratch'' rather than composed from reusable components. This, of course, rarely happens in real life, where almost every non-trivial commercial software system relies heavily on using libraries of reusable components. Furthermore, other contexts, such as web-service orchestration, can be modeled as synthesis of a system from a library of components. In contrast to classical synthesis, synthesis from components aims to build the desired system using components from a given library. In this dissertation, we consider the problem of control-flow synthesis from libraries of probabilistic components. We develop an automata-theoretic approach to solve the problem, investigate the expressive power of probabilistic control-flow, and examine the close relationship between synthesis from components and games with partial information.