Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Model-Checking LTL with Regular Valuations for Pushdown Systems


Javier Esparza, Antonín Kučera, and Stefan Schwoon. Model-checking LTL with regular valuations for pushdown systems. In Naoki Kobayashi and Benjamin C. Pierce, editors, Proceedings of TACS 2001, volume 2215 of Lecture Notes in Computer Science, pages 306–339. Springer, October 2001.


Recent works have proposed pushdown systems as a tool for analyzing programs with (recursive) procedures. In particular, the model-checking problem for LTL has been studied. In this paper we examine an extension of this, namely model-checking with regular valuations. The problem is solved via two different techniques, with an eye on efficiency both techniques can be shown to be essentially optimal. Our methods are applicable to problems in different areas, e.g., data-flow analysis, analysis of systems with checkpoints, etc., and provide a general, unifying and efficient framework for solving these problems.

Suggested BibTeX entry:

    author = {Javier Esparza and Anton\'{\i}n Ku\v{c}era and Stefan Schwoon},
    booktitle = {Proceedings of TACS 2001},
    editor = {Naoki Kobayashi and Benjamin C. Pierce},
    month = {October},
    pages = {306--339},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {Model-Checking {LTL} with Regular Valuations for Pushdown Systems},
    volume = {2215},
    year = {2001}

GZipped PostScript (154 kB)
Tech report version, Journal version