Verification of digital and hybrid systems

This state-of-the-art tutorial overview of computer-aided verification, hybrid systems, and publicly available tools for design and verification is based on a NATO workshop. It has two parts. Part 1 addresses the basics of computer-aided verification of discrete event systems from two perspectives: automated theorem proving and model checking. In model checking, the essential problem of computational complexity is addressed, and the basic heuristics for dealing with this problem are presented. Part 2 formulates and classifies hybrid systems that capture continuous dynamics interacting with activated discrete event interruptions modeled by automata, and presents and discusses properties relevant to design and verification such as decidability, complexity, and expressibility for computer tools. The theory is illustrated with real-life examples. One novel and industrially relevant example is that of an intelligent highway transport system.