Suggesting variable order for cylindrical algebraic decomposition via reinforcement learning
Abstract Cylindrical Algebraic Decomposition (CAD) is one of the pillar algorithms of
symbolic computation, and its worst-case complexity is double exponential to the number of …
symbolic computation, and its worst-case complexity is double exponential to the number of …
[HTML][HTML] Deciding the consistency of non-linear real arithmetic constraints with a conflict driven search using cylindrical algebraic coverings
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 …
polynomial constraints over the reals, which can be used as a theory solver for satisfiability …
Programming Z3
This tutorial provides a programmer's introduction to the Satisfiability Modulo Theories
Solver Z3. It describes how to use Z3 through scripts, provided in the Python scripting …
Solver Z3. It describes how to use Z3 through scripts, provided in the Python scripting …
Improving bit-blasting for nonlinear integer constraints
Nonlinear integer constraints are common and difficult in the verification and analysis of
software/hardware. SMT (QF_NIA) generalizes such constraints, which is a boolean …
software/hardware. SMT (QF_NIA) generalizes such constraints, which is a boolean …
Satisfiability modulo finite fields
We study satisfiability modulo the theory of finite fields and give a decision procedure for this
theory. We implement our procedure for prime fields inside the cvc5 SMT solver. Using this …
theory. We implement our procedure for prime fields inside the cvc5 SMT solver. Using this …
Verifying and improving halide's term rewriting system with program synthesis
Halide is a domain-specific language for high-performance image processing and tensor
computations, widely adopted in industry. Internally, the Halide compiler relies on a term …
computations, widely adopted in industry. Internally, the Halide compiler relies on a term …
When less is more: consequence-finding in a weak theory of arithmetic
This paper presents a theory of non-linear integer/real arithmetic and algorithms for
reasoning about this theory. The theory can be conceived of as an extension of linear …
reasoning about this theory. The theory can be conceived of as an extension of linear …
[HTML][HTML] Levelwise construction of a single cylindrical algebraic cell
J Nalbach, E Ábrahám, P Specht, CW Brown… - Journal of Symbolic …, 2024 - Elsevier
Satisfiability modulo theories (SMT) solvers check the satisfiability of quantifier-free first-
order logic formulae over different theories. We consider the theory of non-linear real …
order logic formulae over different theories. We consider the theory of non-linear real …
Theory combination: beyond equality sharing
MP Bonacina, P Fontaine, C Ringeissen… - Description Logic, Theory …, 2019 - Springer
Satisfiability is the problem of deciding whether a formula has a model. Although it is not
even semidecidable in first-order logic, it is decidable in some first-order theories or …
even semidecidable in first-order logic, it is decidable in some first-order theories or …
Satisfiability modulo theories and assignments
MP Bonacina, S Graham-Lengrand… - … Deduction–CADE 26: 26th …, 2017 - Springer
The CDCL procedure for SAT is the archetype of conflict-driven procedures for satisfiability
of quantifier-free problems in a single theory. In this paper we lift CDCL to CDSAT (Conflict …
of quantifier-free problems in a single theory. In this paper we lift CDCL to CDSAT (Conflict …