Abstract:

In system synthesis, we transform a desired specification into a
system that is guaranteed to satisfy the specification. The talk will
survey the development of synthesis algorithms for reactive systems. We
will start with early work on synthesis of closed systems (which do
not interact with an environment, making the synthesis problem similar
to the satisfiability problem) and will reach synthesis of open
systems (which interact with an environment, making the synthesis problem
similar to the problem of generating winning strategies in two-player
games), synthesis of open systems with incomplete information (where
the system cannot read all the signals that the environment generates),
and synthesis of distributed systems. The talk assumes no previous
knowledge in specification and synthesis.

Joint work with Moshe Vardi.