While model-checking of pushdown models is by now an established technique in software verification, temporal logics and automata traditionally used in this area are unattractive on two counts. First, logics and automata traditionally used in model-checking cannot express requirements such as pre/post-conditions that are basic to software analysis. Second, unlike in the finite-state world, where the μ-calculus has a symbolic model-checking algorithm and serves as an “assembly language” of temporal logics, there is no unified formalism to model-check linear and branching requirements on pushdown models. In this survey, we discuss a recently-proposed re-phrasing of the model-checking problem for pushdown models that addresses these issues. The key idea is to view a program as a generator of structures known as nested words and nested trees (respectively in the linear and branching-time cases) as opposed to words and trees. Automata and temporal logics accepting languages of these structures are now defined, and linear and branching time model-checking phrased as language inclusion and membership problems for these languages. We discuss two of these formalisms—automata on nested words and a fixpoint calculus on nested trees—in detail. While these formalisms allow a new frontier of program specifications, their model-checking problem has the same worst-case complexity as their traditional analogs, and can be solved symbolically using a fixpoint computation that generalizes, and includes as a special case, “summary”-based computations traditionally used in interprocedural program analysis.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com