Synthesis from Probabilistic Components
Vardi, Moshe Y.
Doctor of Philosophy
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.
Reactive synthesis; Synthesis from components; Partial-information stochastic games