Sur la complexité du principe de Tarski-Seidenberg
Publications mathématiques et informatique de Rennes no. 4  (1989), p. 103-120 
@article{PSMIR_1989___4_103_0,
     author = {Heintz, Joos and Roy, Marie-Fran\c coise and Solerno, Pablo},
     title = {Sur la complexit\'e du principe de Tarski-Seidenberg},
     journal = {Publications math\'ematiques et informatique de Rennes},
     publisher = {D\'epartement de Math\'ematiques et Informatique, Universit\'e de Rennes},
     number = {4},
     year = {1989},
     pages = {103-120},
     language = {fr},
     url = {http://www.numdam.org/item/PSMIR_1989___4_103_0}
}

Heintz, Joos; Roy, Marie-Françoise; Solerno, Pablo. Sur la complexité du principe de Tarski-Seidenberg. Publications mathématiques et informatique de Rennes, no. 4 (1989), pp. 103-120. http://www.numdam.org/item/PSMIR_1989___4_103_0/

[1]Ben-Or M. , Kozen D. , Reif J. : The complexity of elementary algebra and geometry. J. of Computation and Systems Sciences 32 251-264 (1986). | MR 851192 | Zbl 0634.03031

[2]Berkowitz S. J.: On Computing the determinant in small parallel time using a small number of processors. Information Processing Letter 18 (1984), 147-150. | MR 760366 | Zbl 0541.68019

[3]Bochnak J., Coste M., Roy M.-F.: Géométrie algébrique réelle. Springer Verlag (1987). | MR 949442 | Zbl 0633.14016

[4]Canny J.: Some algebraic and geometric computations in PSPACE. ACM Symposium on the theory of computation, 460-467 (1988).

[5]Canny J.: The complexity of robot motion planning. MIT Press (1989). | MR 952555

[6]Collins G. : Quantifier elimination for real closed fields by cylindric algebraic decomposition. In Second GI Conference on Automata Theory and Formal Languages. Lecture Notes in Computer Sciences, vol. 33, pp. 134-183, Springer-Verlag, Berlin (1975). | MR 403962 | Zbl 0318.02051

[7]Caniglia L., Galligo A., Heintz J.: Some new effectivity bounds in computational geometry. Proc. AAECC-6 (Rome 1988) - Best Paper Award AAECC-6 - Springer Lecture Notes in Computer Science 357 131-151. | MR 1008498 | Zbl 0685.68044

[8]Coste M. , Roy M.-F. : Thom's lemma, the coding of real algebraic numbers and the topology of semi-algebraic sets. J. of Symbolic Computation 5 121-129 (1988). | MR 949115 | Zbl 0689.14006

[9]Davenport J., Heintz J.: Real quantifier elimination is doubly exponential. J. of Symbolic Computation 5 29-35 (1988). | MR 949111 | Zbl 0663.03015

[10]Fitchas N., Galligo A., Morgenstern J.: Algorithmes rapides en séquentiel et en parallle pour l'élimina- tion des quantificateurs en géométrie élémentaire. Séminaire Structures Ordonnées, U.E.R. de Math. Univ. Paris VII (1987). | Zbl 0704.03014

[11]Fitchas N., Galligo A., Morgenstern J.: Precise sequential and parallel complexity bounds for the quantifier elimination of algebraically closed fields. A paraître dansJournal of Pure and Applied Algebra. | MR 1076744 | Zbl 0716.03023

[12]Von Zur Gathen J.: Parallel arithmetic computations: a survey. Proc 13th Conf. MFCS (1986). | MR 874591 | Zbl 0616.68037

[13]Gonzalez L., Lombardi H., Recio T., Roy M.-F.: Sturm-Habicht sequences. Proceedings ISSAC 1989.

[14]Gonzalez L., Lombardi H., Recio T., Roy M.-F.: Sous-résultants et spécialisation de la suite de Sturm. A paraitre au RAIRO Informatique théorique. | Numdam | Zbl 0732.68059

[15]Grigor'Ev D.: Complexity of deciding Tarski algebra. J. Symbolic Computation 5 (1988) 65-108. | MR 949113 | Zbl 0689.03021

[16]Grigor'Ev D., Vorobjov N.: Solving systems of polynomial inequalities in subexponential time. J. Symbolic Computation 5 (1988) 37-64. | MR 949112 | Zbl 0662.12001

[17]Heintz J.Definability and fast quantifier elimination in algebraically closed fields Theor. Comput. Sci. 24 (1983) 239-27. | MR 716823 | Zbl 0546.03017

[18]Heintz J., Roy M.F., Solerno P. : On the complexity of semialgebraic sets. Proc. IFIP (San Francisco 1989).

[19]Heintz J., Roy M.-F., Solerno P.: Complexité du principe de Tarski- Seidenberg. Compte-Rendus de l'Académie des Sciences Paris. 309 825-830 (1989). | MR 1055203 | Zbl 0704.03013

[20]Kobayashi H., Moritsugu S., Hogan R.W.: On solving systems of algebraic equations. Soumis au Journal of Symbolic Computation.

[21]Krick T. : Thèse. Université de Buenos Aires (en préparation).

[22]Loos R.: Generalized poynomial reaminder sequences. Dans Computer Algebra, Symbolic and Algebraic Computation 115-138. Edit par Buchberger, Collins, Loos. Springer Verlag 1982. | Zbl 0577.13001

[23]Renegar J.: A faster PSPACE algorithm for deciding the existential theory of the reals. Technical Report 792, Cornell University Ithaca (1988).

[24]Renegar J.: On the computational complexity and geometry of the first order theory of the reals. Technical Report 856, Cornell University Ithaca (1989). | Zbl 0798.68073

[25]Roy M.-F., Szpirglas A.: Complexity of computations with real algebraic numbers. A paraitre au Journal of Symbolic Computation. | Zbl 0723.68054

[26]Seidenberg A.: A new decision method for elementary algebra and geometry. Ann. Math. 60 365-374 (1954). | MR 63994 | Zbl 0056.01804

[27]Shafarevitch I.S. Algebraic geometry. Springer Verlag (1974) | MR 366917

[28]Solernó P.: Complejidad de conjuntos semialgebraicos. Thèse. Université de Buenos Aires 1989.

[29]Sturm C : Mémoire sur la résolution des équations numériques. Ins. France Sc. Math. Phys. 6 (1835).

[30]Sylvester T. J. : On a theory of syzygetic relations of two rational integral functions,comprising an application to the theory of Sturm's function. Trans. Roy. Soc. London (1853). Reprint in: Sylvester : Collected Math Papers. Chelsea Pub. Comp. NY 1983 vol 1 429-586.

[31]Tarski A.: A decision method for elementary algebra and geometry. Berkeley (1951). | MR 44472 | Zbl 0044.25102

[32]Vorobjov N.: Bounds of real roots of a system of algebraic equations. Notes of Sci. Seminars of Leningrad Department of Math. Steklov Inst. 13 7-19. | MR 762095

[33]Walker R.: Algebraic curves. Princeton University Press (1950). | MR 33083 | Zbl 0039.37701

[34]Weipsfenning V.: The complexity of lieanr problems in fields. J. Symbolic Computation 5 3-27 (1988). | MR 949110 | Zbl 0646.03005