I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - A BDD-based Model Checker for Recursive Programs


Javier Esparza and Stefan Schwoon. A BDD-based model checker for recursive programs. In Gérard Berry, Hubert Comon, and Alain Finkel, editors, Proceedings of CAV 2001, volume 2102 of Lecture Notes in Computer Science, pages 324–336. Springer, July 2001.


We present a model-checker for boolean programs with (possibly recursive) procedures and the temporal logic LTL. The checker is guaranteed to terminate even for (usually faulty) programs in which the depth of the recursion is not bounded. The algorithm uses automata to finitely represent possibly infinite sets of stack contents and BDDs to compactly represent finite sets of values of boolean variables. We illustrate the checker on some examples and compare it with the Bebop tool of Ball and Rajamani.

Suggested BibTeX entry:

    author = {Javier Esparza and Stefan Schwoon},
    booktitle = {Proceedings of CAV 2001},
    editor = {G{\'e}rard Berry and Hubert Comon and Alain Finkel},
    month = {July},
    pages = {324--336},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {A {BDD}-based Model Checker for Recursive Programs},
    volume = {2102},
    year = {2001}

GZipped PostScript (61 kB)
See www.fmi.uni-stuttgart.de ...