.png){kind=icon}
.png){kind=icon}
Return
Cylindrical Algebraic Decomposition in Coq/Rocq
.png){kind=icon}
PRE
AI
DOI：10.1145/3779031.3779100.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The Cylindrical Algebraic Decomposition (CAD in short) is a fundamental tool of semi-algebraic geometry. It is a doubly-exponential time algorithm that enables most famously to eliminate quantifiers from a formula in the theory of real closed fields. In particular, it allows to decide the satisfiability of problems involving sets of comparisons between polynomials. The present article describes the first formalization of a correctness proof of this algorithm in a proof assistant.
Keywords:
computer algebra
semi-algebraic geometry
sub-resultants
CAD
formal proofs
Rocq
Journal
P
IF:
0
Papers:
27
Citations:
0