From barwise@cs.indiana.edu Tue Mar 30 14:59:51 1999 From: barwise@cs.indiana.edu (Jon Barwise) Date: Tue, 30 Mar 1999 09:59:51 -0500 Subject: FOM: cylindric algebraic decompositions of R^n Message-ID: In connection with some current research, a student colleague and I have come to realize that what we are doing seems to be intimately linked with so-called cylindric algebraic decomposition, a topic having to do with more efficient quantifier elimination methods for real closed fields. So far we have only found incremental research papers on the topic and have found no good reference to the general method. If any reader of this message knows of a good introduction to the topic, please let me know. Thanks, Jon From simpson@math.psu.edu Tue Mar 30 18:56:57 1999 From: simpson@math.psu.edu (Stephen G Simpson) Date: Tue, 30 Mar 1999 13:56:57 -0500 (EST) Subject: FOM: cylindric algebraic decompositions of R^n In-Reply-To: References: Message-ID: <14081.7801.866145.667832@mordred.cs.utk.edu> On the model theory side, I think a reference for this would be Lou van den Dries's recent book, `Tame Topology and O-Minimal Structures', London Mathematical Society Lecture Note Series, no. 248, 1998, ISBN 0521598389. On the engineering side, there are papers by James Renegar. One is `Computational complexity of solving real algebraic formulae', International Congress of Mathematicians, Tokyo, 1991, pp 1595-1606. I don't know whether these are the best references, but it is a start. These references tend to underline the many-sided (f.o.m., model theory, engineering, ...) importance of Tarski's work on quantifier elimination for the real number system. Another such reference is in the earlier discussion here on FOM of Tarski's elementary geometry. To my mind it's regrettable that quantifier elimination for the reals is not usually regarded as part of the standard syllabus for mathematical logic and f.o.m. I almost always include this topic in my courses -- see my lecture notes at . In this respect I am following the old Kreisel/Krivine mathematical logic textbook. -- Steve From fgeerts@luc.ac.be Wed Mar 31 09:47:18 1999 From: fgeerts@luc.ac.be (Floris Geerts) Date: Wed, 31 Mar 1999 11:47:18 +0200 (MET DST) Subject: FOM: Cylindrical Algebraic Decomposition Message-ID: There is this book : "Quantifier Elimination and Cylindrical Algebraic Decomposition" edited by Caviness and Johnson. It appeared in 1998 by Springer in their series texts and monographs in symbolic computation. It contains the original decision method of Tarski, Collins's CAD and complexity issues by Renegar. From marker@math.uic.edu Wed Mar 31 13:58:14 1999 From: marker@math.uic.edu (Dave Marker) Date: Wed, 31 Mar 1999 07:58:14 -0600 (CST) Subject: FOM: re: cylindric decomposition Message-ID: One excellent reference on cylindric decomposition in real closed fields is Bochank, Coste & Roy "Geometrie algebrique reele" Springer 1987. Recently they have published a second edition in English "Real Algebraic Geometry". Dave Marker