Sur la complexité du principe de Tarski-Seidenberg
Publications de l'Institut de recherche mathématiques de Rennes, Groupe de travail de calcul formel, no. 4 (1989), pp. 103-120. 
@article{PSMIR_1989___4_103_0,
     author = {Heintz, Joos and Roy, Marie-Fran\c{c}oise and Solerno, Pablo},
     title = {Sur la complexit\'e du principe de {Tarski-Seidenberg}},
     journal = {Publications de l'Institut de recherche math\'ematiques de Rennes},
     pages = {103--120},
     publisher = {D\'epartement de Math\'ematiques et Informatique, Universit\'e de Rennes},
     number = {4},
     year = {1989},
     language = {fr},
     url = {http://archive.numdam.org/item/PSMIR_1989___4_103_0/}
}
TY  - JOUR
AU  - Heintz, Joos
AU  - Roy, Marie-Françoise
AU  - Solerno, Pablo
TI  - Sur la complexité du principe de Tarski-Seidenberg
JO  - Publications de l'Institut de recherche mathématiques de Rennes
PY  - 1989
SP  - 103
EP  - 120
IS  - 4
PB  - Département de Mathématiques et Informatique, Université de Rennes
UR  - http://archive.numdam.org/item/PSMIR_1989___4_103_0/
LA  - fr
ID  - PSMIR_1989___4_103_0
ER  - 
%0 Journal Article
%A Heintz, Joos
%A Roy, Marie-Françoise
%A Solerno, Pablo
%T Sur la complexité du principe de Tarski-Seidenberg
%J Publications de l'Institut de recherche mathématiques de Rennes
%D 1989
%P 103-120
%N 4
%I Département de Mathématiques et Informatique, Université de Rennes
%U http://archive.numdam.org/item/PSMIR_1989___4_103_0/
%G fr
%F PSMIR_1989___4_103_0
Heintz, Joos; Roy, Marie-Françoise; Solerno, Pablo. Sur la complexité du principe de Tarski-Seidenberg. Publications de l'Institut de recherche mathématiques de Rennes, Groupe de travail de calcul formel, no. 4 (1989), pp. 103-120. http://archive.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 | Zbl

[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 | Zbl

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

[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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

[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

[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 | Zbl

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

[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

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

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

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

[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 | Zbl

[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

[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

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

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

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

[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 | Zbl

[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. | EuDML | MR

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

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