Quantifier Elimination and Cylindrical Algebraic Decomposition [Paperback]

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 Tarskis 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.In addition to original contributions by S. Basu et al., L. Gonz?lez-Vega et al., G. Hagel, H. Hong and J.R. Sendra, J.R. Johnson, S. McCallum, D. Richardson, and V. Weispfenning and a survey by G.E. Collins outlining the twenty-year progress in CAD-based QE it brings together seminal publications from the area:A. Tarski: A Decision Method for Elementary Algebra and GeometryG.E. Collins: Quantifier Elimination for Real Closed Fields by CylindricalAlgebraic DecompositionM.J. Fischer and M.O. Rabin: Super-Exponential Complexity of Presburger ArithmeticD.S. Arnon et al.: Cylindrical Algebraic Decomposition I: The Basic Algorithm;II: An Adjacency Algorithm for the PlaneH. Hong: An Improvement of the Projectl#§