Symbolic model checking with rich assertional languages

The paper shows that, by an appropriate choice of a rich assertional language, it is possible to extend the utility of symbolic model checking beyond the realm of BDD-represented finite-state systems into the domain of infinite-state systems, leading to a powerful technique for uniform verification of unbounded (parameterized) process networks. The main contributions of the paper are a formulation of a general framework for symbolic model checking of infinite-state systems, a demonstration that many individual examples of uniformly verified parameterized designs that appear in the literature are special cases of our general approach, verifying the correctness of the Futurebus+ design for all single-bus configurations, and extending the technique to tree architectures.

Authors

• Y. Kesten
• O. Maler
• M. Marcus
• A. Pnueli
• E. Shahar

Keywords

• Symbolic model checking
• Parametric systems
• Tree automata
• Regular expressions