Villa T., Yevtushenko N., Brayton R., Mishchenko A., Petrenko A., Sangiovanni-Vincentelli A.

Springer, New York, Inc., 2011.

F.1.1 Automata

B.1.2 Control structure performance analysis and design aids - automatic synthesis

B.6.3 Performance analysis and design aids - formal models

Some of the authors of this book wrote a couple of influential books
in the 1990s (with Timothy Kam) on the synthesis of finite state
machines. In this new monograph, they consider a broader problem: given
a partial system *A* and a specification *C*, how does one
synthesize the (unknown) component *X* that, when composed with the
partial system, will give a system *A * X* that meets the
specification *A * X ⊂ C*? Two
operations are considered: synchronous composition, where the two
systems must work in lockstep, and parallel composition, where the two
systems synchronize on a common alphabet but interleave other actions
outside this alphabet. Various settings are considered, where *A*
and *C* are regular languages over finite and infinite words, or
finite state machines (recognizers as well as transducers) over finite
and infinite words, and the largest solutions are provided.
The authors also describe a software package they designed with co-workers
for this purpose. Finally, they consider the computation of flexibility,
that is, all possible replacements of the current finite state machine
that still allow the specification to be met.
The book could do with more references (Ernst Leiss's book [1] comes to
mind). On page 94, the authors credit Thatcher and Wright (1968) with a
result that is due to Büchi (1960). The index could be much expanded.
But these are small problems. Synthesis is a hard computational area that
is now becoming accessible, thanks to increasing computational power. It
is good to have a book from experts that surveys the techniques available.

[1] Leiss, E. *Language equations*. Springer, New York, 1999.