The unknown component problem: theory and applications
Villa T., Yevtushenko N., Brayton R., Mishchenko A., Petrenko A., Sangiovanni-Vincentelli A.
Springer, New York, Inc., 2011.
ACM CR categories:
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.