FOM: cylindric algebraic decompositions of R^n

Stephen G Simpson simpson at
Tue Mar 30 13:56:57 EST 1999

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

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

More information about the FOM mailing list