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

    5 Citations (Scopus)
    10 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