Abstract
Cylindrical Algebraic Decomposition was introduced by Collins in 1975, to help understand and analyse the real algebraic geometry of a system of polynomials. Nine years later, McCallum's thesis introduced a cheaper algorithm, but it could have problems when polynomials, input or generated, vanished identically (nullified) over a set. Several people have built on McCallum's work to improve the algorithm further when there are equational constraints. Lazard's approach, which was justified in 2019, avoids the nullification problem. The first author investigated translating these equational constraint methods to the Lazard projection. Nullification reappears along subsets called curtains. In this paper we summarise the work done by the first author under the supervision of the other authors for his PhD on propagating the work by Lazard and Brown-McCallum to exploit equational constraints with the help of curtains.
Original language | English |
---|---|
Pages (from-to) | 50-58 |
Number of pages | 9 |
Journal | CEUR Workshop Proceedings |
Volume | 3273 |
Publication status | Published - 12 Oct 2022 |
Event | 6th Satisfiability Checking and Symbolic Computation-Square Workshop, SC-Square 2021 - Virtual, Online, USA United States Duration: 19 Aug 2021 → 20 Aug 2021 |
Keywords
- Curtains
- Cylindrical Algebraic Decomposition
- Equational Constraint
- Lazard Projection
- Nullification
ASJC Scopus subject areas
- General Computer Science