Javier Esparza and Keijo Heljanko:
Unfoldings --A Partial-Order Approach to Model Checking
EATCS Monographs in Theoretical Computer Science, 2008.



Preface:


Model checking is a very popular technique for the automatic verification of systems, widely applied by the hardware industry and already receiving considerable attention from software companies. It is based on the (possibly exhaustive) exploration of the states reached by the system along all its executions. Model checking is very successful in finding bugs in concurrent systems. These systems are notoriously hard to design correctly, mostly because of the inherent uncertainty about the order in which components working in parallel execute actions. Since $n$ independent actions can occur in $n!$ different orders, humans easily overlook some of them, often the one causing a bug. On the contrary, model checking exhaustively examines all execution orders. Unfortunately, naive model checking techniques can only be applied to very small systems. The number of reachable states grows so quickly, that even a modern computer fails to explore them all in reasonable time. In this book we show that concurrency theory, the study of mathematical formalisms for the description and analysis of concurrent systems, helps to solve this problem. Unfoldings are one of these formalisms, belonging to the class of so-called true concurrency models. They were introduced in the early 1980s as a mathematical model of causality. Our reason for studying them is far more pragmatic: unfoldings of highly concurrent systems are often far smaller and can be explored much faster than the state space. Being at the crossroads of automatic verification and concurrency theory, this book is addressed to researchers and graduate students working in either of these two fields. It is self-contained, although some previous exposure to models of concurrent systems, like communicating automata or Petri nets, can help to understand the material.


Contents:

  1. Introduction
  2. Transition Systems and Products
    1. Transition Systems
    2. Products of Transition Systems
    3. Petri Ne Representation of Products
    4. Interleaving Representation of Products
  3. Unfolding Products
    1. Branching Processes and Unfoldings
    2. Some Properties of Branching Processes
    3. Verification Using Unfoldings
    4. Constructing the Unfolding of a Product
    5. Search Procedures
    6. Goals and Milestones for Next Chapters
  4. Search Procedures for the Executability Problem
    1. Search Strategies for Transition Systems
    2. Search Scheme for Transition Systems
    3. Search Strategies for Products
    4. Search Scheme for Products
    5. Adequate Search Strategies
    6. Complete Search Scheme for Arbitrary Strategies
  5. More on the Executability Problem
    1. Complete Prefixes
    2. Least Representatives
    3. Breadth-First and Depth-First Strategies
    4. Strategies Preserved by Extensions are Well-Founded
  6. Search Procedures for the Repeated Executability Problem
    1. Search Scheme for Transition Systems
    2. Search Scheme for Products
  7. Search Procedures for the Livelock Problem
    1. Search Scheme for Transition Systems
    2. Search Scheme for Products
  8. Model Checking LTL
    1. Linear Temporal Logic
    2. Interpreting LTL on Products
    3. Testers for LTL Properties
    4. Model Checking with Testers: A First Attempt
    5. Stuttering Synchronization
  9. Summary, Applications, Extensions, and Tools
    1. Looking Back: A Two-Page Summary of This Book
    2. Some Experiments
    3. Some Applications
    4. Some Extensions
    5. Some Tools
  10. References

Archived copy: PDF file


This is the final draft of the book, as produced by Keijo and myself. Our publishing agreement with Springer allows us to make the file available in our homepages. Notice, however, that it cannot be made available through any other web page.
The book can be purchased from the publisher. If you're interested, or if you wish your library to order a copy, click here.

Back to: Javier Esparza