License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-27907
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2790/
Go to the corresponding Portal


Abraham, Erika ; Corzilius, Florian ; Loup, Ulrich ; Sturm, Thomas

A Lazy SMT-Solver for a Non-Linear Subset of Real Algebra

pdf-format:
Document 1.pdf (290 KB)


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, SAT-solvers can be used for the satisfiability checks. For hybrid systems, having mixed discrete-continuous behavior, SMT-solvers are needed. SMT-solving 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 first-order theory of the reals with addition and multiplication -- real algebra. Since the synthesis and analysis of non-linear hybrid systems requires such a powerful logic, we need efficient SMT-solvers for real algebra. Our goal is to develop such an SMT-solver 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 SMT-Solver for a Non-Linear Subset of Real Algebra},
  booktitle =	{Verification over discrete-continuous boundaries},
  year =	{2010},
  editor =	{Bernd Becker and Luca Cardelli and Holger Hermanns and Sofiene Tahar},
  number =	{10271},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2790},
  annote =	{Keywords: SMT-solving, Real Algebra, Hybrid Systems, Verification, Synthesis}
}

Keywords: SMT-solving, Real Algebra, Hybrid Systems, Verification, Synthesis
Seminar: 10271 - Verification over discrete-continuous boundaries
Issue Date: 2010
Date of publication: 02.11.2010


DROPS-Home | Fulltext Search | Imprint Published by LZI