Computer-Aided Verification of Coordinating Processes

Formal verification increasingly has become recognized as an answer to the problem of how to create ever more complex control systems, which nonetheless are required to behave reliably. To be acceptable in an industrial setting, formal verification must be highly algorithmic; to cope with design complexity, it must support a top-down design methodology that leads from an abstract design to its detailed implementation.

Of the verification methodologies in use today, that combination of requirements points to automata-theoretic verification, on account of its expressiveness; computational complexity, and general utility. This book develops the theory of automata-theoretic verification from its foundations. A principal focus is heuristics to reduce the computational complexity of analysis, essential for verification in an industrial setting.

The book is suitable as a text for a one- or two-semester graduate course, as well as for anyone planning to use a verification tool such as COSPAN or SMV. An extensive bibliography points to many recent sources. Discussions of methodology and comparisons with other techniques provide a resource for research and verification tool development, as well.