Abraham, Erika ;
Corzilius, Florian ;
Loup, Ulrich ;
Sturm, Thomas
A Lazy SMTSolver for a NonLinear Subset of Real Algebra
Abstract
There are several methods for the synthesis and analysis of hybrid
systems that require efficient algorithms and tools for satisfiability
checking. For analysis, e.g., bounded model checking describes
counterexamples of a fixed length by logical formulas, whose
satisfiability corresponds to the existence of such a counterexample.
As an example for parameter synthesis, we can state the correctness of
a parameterized system by a logical formula; the solution set of
the formula gives us possible safe instances of the parameters.
For discrete systems, which can be described by propositional logic
formulas, SATsolvers can be used for the satisfiability checks. For
hybrid systems, having mixed discretecontinuous behavior, SMTsolvers
are needed. SMTsolving extends SAT with theories, and has its main
focus on linear arithmetic, which is sufficient to handle, e.g.,
linear hybrid systems. However, there are only few solvers for
more expressive but still decidable logics like the
firstorder theory of the reals with addition and multiplication 
real algebra. Since the synthesis and analysis of nonlinear
hybrid systems requires such a powerful logic, we need efficient
SMTsolvers for real algebra. Our goal is to develop such an
SMTsolver for the real algebra, which is both complete and
efficient.
BibTeX  Entry
@InProceedings{abraham_et_al:DSP:2010:2790,
author = {Erika Abraham and Florian Corzilius and Ulrich Loup and Thomas Sturm},
title = {A Lazy SMTSolver for a NonLinear Subset of Real Algebra},
booktitle = {Verification over discretecontinuous boundaries},
year = {2010},
editor = {Bernd Becker and Luca Cardelli and Holger Hermanns and Sofiene Tahar},
number = {10271},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2790},
annote = {Keywords: SMTsolving, Real Algebra, Hybrid Systems, Verification, Synthesis}
}
Keywords: 

SMTsolving, Real Algebra, Hybrid Systems, Verification, Synthesis 
Seminar: 

10271  Verification over discretecontinuous boundaries

Issue date: 

2010 
Date of publication: 

02.11.2010 