Ebook: Quantifier Elimination and Cylindrical Algebraic Decomposition

George Collins’ discovery of Cylindrical Algebraic Decomposition (CAD) as a method for Quantifier Elimination (QE) for the elementary theory of real closed fields brought a major breakthrough in automating mathematics with recent important applications in high-tech areas (e.g. robot motion), also stimulating fundamental research in computer algebra over the past three decades. This volume is a state-of-the-art collection of important papers on CAD and QE and on the related area of algorithmic aspects of real geometry. It contains papers from a symposium held in Linz in 1993, reprints of seminal papers from the area including Tarski’s landmark paper as well as a survey outlining the developments in CAD based QE that have taken place in the last twenty years.

---

George Collins’ discovery of Cylindrical Algebraic Decomposition (CAD) as a method for Quantifier Elimination (QE) for the elementary theory of real closed fields brought a major breakthrough in automating mathematics with recent important applications in high-tech areas (e.g. robot motion), also stimulating fundamental research in computer algebra over the past three decades. This volume is a state-of-the-art collection of important papers on CAD and QE and on the related area of algorithmic aspects of real geometry. It contains papers from a symposium held in Linz in 1993, reprints of seminal papers from the area including Tarski’s landmark paper as well as a survey outlining the developments in CAD based QE that have taken place in the last twenty years.

---

George Collins’ discovery of Cylindrical Algebraic Decomposition (CAD) as a method for Quantifier Elimination (QE) for the elementary theory of real closed fields brought a major breakthrough in automating mathematics with recent important applications in high-tech areas (e.g. robot motion), also stimulating fundamental research in computer algebra over the past three decades. This volume is a state-of-the-art collection of important papers on CAD and QE and on the related area of algorithmic aspects of real geometry. It contains papers from a symposium held in Linz in 1993, reprints of seminal papers from the area including Tarski’s landmark paper as well as a survey outlining the developments in CAD based QE that have taken place in the last twenty years.
Content:
Front Matter....Pages i-xix
Introduction....Pages 1-7
Quantifier Elimination by Cylindrical Algebraic Decomposition — Twenty Years of Progress....Pages 8-23
A Decision Method for Elementary Algebra and Geometry....Pages 24-84
Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition....Pages 85-121
Super-Exponential Complexity of Presburger Arithmetic....Pages 122-135
Cylindrical Algebraic Decomposition I: The Basic Algorithm....Pages 136-151
Cylindrical Algebraic Decomposition II: An Adjacency Algorithm for the Plane....Pages 152-165
An Improvement of the Projection Operator in Cylindrical Algebraic Decomposition....Pages 166-173
Partial Cylindrical Algebraic Decomposition for Quantifier Elimination....Pages 174-200
Simple Solution Formula Construction in Cylindrical Algebraic Decomposition Based Quantifier Elimination....Pages 201-219
Recent Progress on the Complexity of the Decision Problem for the Reals....Pages 220-241
An Improved Projection Operation for Cylindrical Algebraic Decomposition....Pages 242-268
Algorithms for Polynomial Real Root Isolation....Pages 269-299
Sturm—Habicht Sequences, Determinants and Real Roots of Univariate Polynomials....Pages 300-316
Characterizations of the Macaulay Matrix and Their Algorithmic Impact....Pages 317-326
Computation of Variant Resultants....Pages 327-340
A New Algorithm to Find a Point in Every Cell Defined by a Family of Polynomials....Pages 341-350
Local Theories and Cylindrical Decomposition....Pages 351-364
A Combinatorial Algorithm Solving Some Quantifier Elimination Problems....Pages 365-375
A New Approach to Quantifier Elimination for Real Algebra....Pages 376-392
Back Matter....Pages 393-431

---

George Collins’ discovery of Cylindrical Algebraic Decomposition (CAD) as a method for Quantifier Elimination (QE) for the elementary theory of real closed fields brought a major breakthrough in automating mathematics with recent important applications in high-tech areas (e.g. robot motion), also stimulating fundamental research in computer algebra over the past three decades. This volume is a state-of-the-art collection of important papers on CAD and QE and on the related area of algorithmic aspects of real geometry. It contains papers from a symposium held in Linz in 1993, reprints of seminal papers from the area including Tarski’s landmark paper as well as a survey outlining the developments in CAD based QE that have taken place in the last twenty years.
Content:
Front Matter....Pages i-xix
Introduction....Pages 1-7
Quantifier Elimination by Cylindrical Algebraic Decomposition — Twenty Years of Progress....Pages 8-23
A Decision Method for Elementary Algebra and Geometry....Pages 24-84
Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition....Pages 85-121
Super-Exponential Complexity of Presburger Arithmetic....Pages 122-135
Cylindrical Algebraic Decomposition I: The Basic Algorithm....Pages 136-151
Cylindrical Algebraic Decomposition II: An Adjacency Algorithm for the Plane....Pages 152-165
An Improvement of the Projection Operator in Cylindrical Algebraic Decomposition....Pages 166-173
Partial Cylindrical Algebraic Decomposition for Quantifier Elimination....Pages 174-200
Simple Solution Formula Construction in Cylindrical Algebraic Decomposition Based Quantifier Elimination....Pages 201-219
Recent Progress on the Complexity of the Decision Problem for the Reals....Pages 220-241
An Improved Projection Operation for Cylindrical Algebraic Decomposition....Pages 242-268
Algorithms for Polynomial Real Root Isolation....Pages 269-299
Sturm—Habicht Sequences, Determinants and Real Roots of Univariate Polynomials....Pages 300-316
Characterizations of the Macaulay Matrix and Their Algorithmic Impact....Pages 317-326
Computation of Variant Resultants....Pages 327-340
A New Algorithm to Find a Point in Every Cell Defined by a Family of Polynomials....Pages 341-350
Local Theories and Cylindrical Decomposition....Pages 351-364
A Combinatorial Algorithm Solving Some Quantifier Elimination Problems....Pages 365-375
A New Approach to Quantifier Elimination for Real Algebra....Pages 376-392
Back Matter....Pages 393-431
....