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 languageEnglish
Pages (from-to)50-58
Number of pages9
JournalCEUR Workshop Proceedings
Volume3273
Publication statusPublished - 12 Oct 2022
Event6th Satisfiability Checking and Symbolic Computation-Square Workshop, SC-Square 2021 - Virtual, Online, USA United States
Duration: 19 Aug 202120 Aug 2021

Keywords

  • Curtains
  • Cylindrical Algebraic Decomposition
  • Equational Constraint
  • Lazard Projection
  • Nullification

ASJC Scopus subject areas

  • General Computer Science

Fingerprint

Dive into the research topics of 'Equational Constraints, the Lazard Projection and the Curtain Problem'. Together they form a unique fingerprint.

Cite this