Deciding the consistency of non-linear real arithmetic constraints with a conflict driven search using cylindrical algebraic coverings

E. Ábrahám, James H. Davenport, Matthew England, Gereon Kremer

Research output: Contribution to journalArticlepeer-review

2 Downloads (Pure)

Abstract

We present a new algorithm for determining the satisfiability of conjunctions of non-linear polynomial constraints over the reals, which can be used as a theory solver for satisfiability modulo theory (SMT) solving for non-linear real arithmetic. The algorithm is a variant of Cylindrical Algebraic Decomposition (CAD) adapted for satisfiability, where solution candidates (sample points) are constructed incrementally, either until a satisfying sample is found or sufficient samples have been sampled to conclude unsatisfiability. The choice of samples is guided by the input constraints and previous conflicts. The key idea behind our new approach is to start with a partial sample; demonstrate that it cannot be extended to a full sample; and from the reasons for that rule out a larger space around the partial sample, which build up incrementally into a cylindrical algebraic covering of the space. There are similarities with the incremental variant of CAD, the NLSAT method of Jovanović and de Moura, and the NuCAD algorithm of Brown; but we present worked examples and experimental results on a preliminary implementation to demonstrate the differences to these, and the benefits of the new approach.

Original languageEnglish
Article number100633
Number of pages41
JournalJournal of Logical and Algebraic Methods in Programming
Volume119
Early online date27 Nov 2020
DOIs
Publication statusPublished - Feb 2021

Bibliographical note

This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

Keywords

  • Cylindrical algebraic decomposition
  • Non-linear real arithmetic
  • Real polynomial systems
  • Satisfiability modulo theories

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software
  • Logic
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Deciding the consistency of non-linear real arithmetic constraints with a conflict driven search using cylindrical algebraic coverings'. Together they form a unique fingerprint.

Cite this