Skip to main content
Erschienen in:
Buchtitelbild

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.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadaten
Titel
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
Copyright-Jahr
2012
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-31759-0_1