2012 | OriginalPaper | Buchkapitel
Beyond First-Order Satisfaction: Fixed Points, Interpolants, Automata and Polynomials
verfasst von : Thomas Ball, Nikolaj Bjørner, Leonardo de Moura, Kenneth L. McMillan, Margus Veanes
Erschienen in: Model Checking Software
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In the last decade, advances in satisfiability-modulo-theories (SMT) solvers have powered a new generation of software tools for verification and testing. These tools transform various program analysis problems into the problem of satisfiability of formulas in propositional or first-order logic, where they are discharged by SMT solvers, such as Z3 from Microsoft Research. This paper briefly summarizes four initiatives from Microsoft Research that build upon Z3 and move beyond first-order satisfaction:
Fixed points
—
μZ
is a scalable, efficient engine for discharging fixed point queries over recursive predicates with logical constraints, integrated in Z3;
Interpolants
—Interpolating Z3 uses Z3’s proof generation capability to generate Craig interpolants in the first-order theory of uninterpreted functions, arrays and linear arithmetic;
Automata
—The symbolic automata toolkit lifts classical automata analyses to work modulo symbolic constraints on alphabets;
Polynomials
—a new decision procedure for the existential theory of the reals allows efficient solving of systems of non-linear arithmetic constraints.