Sur la complexité du principe de Tarski-Seidenberg

 Access to full text

 Full (PDF)

1. [1] Ben-Or M. , Kozen D. , Reif J. : The complexity of elementary algebra and geometry. J. of Computation and Systems Sciences32251-264 (1986). Zbl0634.03031MR851192
2. [2] Berkowitz S. J.: On Computing the determinant in small parallel time using a small number of processors. Information Processing Letter18 (1984), 147-150. Zbl0541.68019MR760366
3. [3] Bochnak J., Coste M., Roy M.-F.: Géométrie algébrique réelle. Springer Verlag (1987). Zbl0633.14016MR949442
4. [4] Canny J.: Some algebraic and geometric computations in PSPACE. ACM Symposium on the theory of computation, 460-467 (1988). 
5. [5] Canny J.: The complexity of robot motion planning. MIT Press (1989). MR952555
6. [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). Zbl0318.02051MR403962
7. [7] Caniglia L., Galligo A., Heintz J.: Some new effectivity bounds in computational geometry. Proc. AAECC-6 (Rome1988) - Best Paper Award AAECC-6 - SpringerLecture Notes in Computer Science357131-151. Zbl0685.68044MR1008498
8. [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 Computation5121-129 (1988). Zbl0689.14006MR949115
9. [9] Davenport J., Heintz J.: Real quantifier elimination is doubly exponential. J. of Symbolic Computation529-35 (1988). Zbl0663.03015MR949111
10. [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). Zbl0704.03014
11. [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. Zbl0716.03023
12. [12] von zur Gathen J.: Parallel arithmetic computations: a survey. Proc 13th Conf.MFCS (1986). Zbl0616.68037
13. [13] Gonzalez L., Lombardi H., Recio T., Roy M.-F.: Sturm-Habicht sequences. Proceedings ISSAC1989. 
14. [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. Zbl0732.68059
15. [15] Grigor'ev D.: Complexity of deciding Tarski algebra. J. Symbolic Computation5 (1988) 65-108. Zbl0689.03021MR949113
16. [16] Grigor'ev D., Vorobjov N.: Solving systems of polynomial inequalities in subexponential time. J. Symbolic Computation5 (1988) 37-64. Zbl0662.12001MR949112
17. [17] Heintz J.Definability and fast quantifier elimination in algebraically closed fieldsTheor. Comput. Sci.24 (1983) 239-27. Zbl0546.03017MR716823
18. [18] Heintz J., Roy M.F., Solerno P. : On the complexity of semialgebraic sets. Proc. IFIP (San Francisco1989). Zbl0704.03013
19. [19] Heintz J., Roy M.-F., Solerno P.: Complexité du principe de Tarski- Seidenberg. Compte-Rendus de l'Académie des Sciences Paris. 309825-830 (1989). Zbl0704.03013MR1055203
20. [20] Kobayashi H., Moritsugu S., Hogan R.W.: On solving systems of algebraic equations. Soumis au Journal of Symbolic Computation. Zbl0693.68020
21. [21] Krick T. : Thèse. Université de Buenos Aires (en préparation). 
22. [22] Loos R.: Generalized poynomial reaminder sequences. Dans Computer Algebra, Symbolic and Algebraic Computation115-138. Edit par Buchberger, Collins, Loos. Springer Verlag1982. Zbl0577.13001
23. [23] Renegar J.: A faster PSPACE algorithm for deciding the existential theory of the reals. Technical Report792, Cornell University Ithaca (1988). 
24. [24] Renegar J.: On the computational complexity and geometry of the first order theory of the reals. Technical Report856, Cornell University Ithaca (1989). Zbl0798.68073
25. [25] Roy M.-F., Szpirglas A.: Complexity of computations with real algebraic numbers. A paraitre au Journal of Symbolic Computation. Zbl0723.68054
26. [26] Seidenberg A.: A new decision method for elementary algebra and geometry. Ann. Math.60365-374 (1954). Zbl0056.01804MR63994
27. [27] Shafarevitch I.S.Algebraic geometry. Springer Verlag (1974) 
28. [28] Solernó P.: Complejidad de conjuntos semialgebraicos. Thèse. Université de Buenos Aires1989. 
29. [29] Sturm C : Mémoire sur la résolution des équations numériques. Ins. France Sc. Math. Phys.6 (1835). 
30. [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. ChelseaPub. Comp.NY1983 vol 1429-586. 
31. [31] Tarski A.: A decision method for elementary algebra and geometry. Berkeley (1951). Zbl0044.25102
32. [32] Vorobjov N.: Bounds of real roots of a system of algebraic equations. Notes of Sci. Seminars of Leningrad Department of Math.Steklov Inst.137-19. 
33. [33] Walker R.: Algebraic curves. Princeton University Press (1950). Zbl0039.37701MR33083
34. [34] Weipsfenning V.: The complexity of lieanr problems in fields. J. Symbolic Computation53-27 (1988). Zbl0646.03005