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 Sciences, t. 32, 1986, p. 251-264. Zbl0634.03031MR87m:03056
2. [2] BERKOWITZ (S.J.). — On computing the determinant in small parallel time using a small number of processors, Information Processing Letter, t. 18, 1984, p. 147-150. Zbl0541.68019MR85k:65111
3. [3] BOCHNAK (J.), COSTE (M.), ROY (M.-F.). — Géométrie algébrique réelle. — Springer Verlag, 1987. Zbl0633.14016MR90b:14030
4. [4] CANNY (J.). — Some algebraic and geometric computations in PS-PACE, ACM Symposium on the theory of computation, 1988, p. 460-467. 
5. [5] CANNY (J.). — The complexity of robot motion planning. — MIT Press, 1989. 
6. [6] COLLINS (G.). — Quantifier elimination for real closed fields by cylindric algebraic decomposition, in Second GI Conference on Automata Theory and Formal Languages. — Lect. Notes in Comp. Sciences. — Springer-Verlag, Berlin, t. 33, 1975, p. 134-183. Zbl0318.02051MR53 #7771
7. [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, t. 357, p. 131-151. Zbl0685.68044MR90j:13001
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 Computation, t. 5, 1988, p. 121-129. Zbl0689.14006MR89g:12002
9. [9] DAVENPORT (J.), HEINTZ (J.). — Real quantifier elimination is doubly exponential, J. of Symbolic Computation, t. 5, 1988, p. 29-35. Zbl0663.03015MR89g:03009
10. [10] FITCHAS (N.), GALLIGO (A.), MORGENSTERN (J.). — Algorithmes rapides en séquentiel et en parallèle pour l'élimination des quantificateurs en géométrie élémentaire, Séminaire Structures Ordonnées, U.E.R. de Math. Univ. Paris VII, 1987. Version finale à paraître aux Publications de l'Université de Paris VII (1990). Zbl0704.03014
11. [11] FITCHAS (N.), GALLIGO (A.), MORGENSTERN (J.). — Precise sequential and parallel complexity bounds for the quantifier elimination of algebraically closed fields, à paraître dans Journal of Pure and Applied Algebra. Zbl0716.03023
12. [12] VON ZUR GATHEN (J.). — Parallel arithmetic computations : a survey, Proc 13th Conf. MFCS, 1986. Zbl0616.68037MR874591
13. [13] GONZALEZ (L.), LOMBARDI (H.), RECIO (T.), ROY (M.-F.). — Sturm-Habicht sequences, Proceedings ISSAC, ACM Press, 1989, p. 136-145. 
14. [14] GONZALEZ (L.), LOMBARDI (H.), RECIO (T.), ROY (M.-F.). — Sous-résultants et spécialisation de la suite de Sturm, à paraître au RAIRO Informatique théorique. Zbl0732.68059
15. [15] GRIGOR'EV (D.). — Complexity of deciding Tarski algebra, J. Symbolic Computation, t. 5, 1988, p. 65-108. Zbl0689.03021MR90b:03054
16. [16] GRIGOR'EV (D.), VOROBJOV (N.). — Solving systems of polynomial inequalities in subexponential time, J. Symbolic Computation, t. 5, 1988, p. 37-64. Zbl0662.12001MR89h:13001
17. [17] HEINTZ (J.). — Definability and fast quantifier elimination in algebraically closed fields, Theor. Comput. Sci., t. 24, 1983, p. 239-277. Zbl0546.03017MR85a:68062
18. [18] HEINTZ (J.), ROY (M.-F.), SOLERNÓ (P.). — On the complexity of semialgebraic sets, Proc. IFIP (San Francisco, 1989), North Holland, 1989, p. 293-298. 
19. [19] HEINTZ (J.), ROY (M.-F.), SOLERNO (P.). — Complexité du principe de Tarski-Seidenberg, C.R.A.S. Paris, t. 309, 1989, p. 825-830. Zbl0704.03013MR92c:12012
20. [20] KOBAYASHI (H.), MORITSUGU (S.), HOGAN (R.W.). — On solving systems of algebraic equations, soumis au Journal of Symbolic Computation. 
21. [21] KRICK (T.), LOGAR (A.). — Membership problems, representations and the computation of the radical of one-dimensional ideals, à paraître dans les Actes de MEGA, 1990. 
22. [22] LOOS (R.). — Generalized poynomial reaminder sequences, in Computer Algebra, Symbolic and Algebraic Computation. — Ed. Buchberger, Collins, Loos, Springer Verlag, 1982, p. 115-138. Zbl0577.13001
23. [23] RENEGAR (J.). — A faster PSPACE algorithm for deciding the existential theory of the reals, Technical Report 792, Cornell University Ithaca, 1988. 
24. [24] RENEGAR (J.). — On the computational complexity and geometry of the first order theory of the reals, Technical Report 856, Cornell University Ithaca, 1989. 
25. [25] ROY (M.-F.), SZPIRGLAS (A.). — Complexity of computations with real algebraic numbers, à paraître au Journal of Symbolic Computation. 
26. [26] SEIDENBERG (A.). — A new decision method for elementary algebra and geometry, Ann. Math., t. 60, 1954, p. 365-374. Zbl0056.01804MR16,209a
27. [27] SHAFAREVITCH (I.S.). — Algebraic geometry. — Springer Verlag, 1974. 
28. [28] SOLERNÓ (P.). — Complejidad de conjuntos semialgebraicos, Thèse, Université de Buenos Aires, 1989. 
29. [29] STURM (C.). — Mémoire sur la résolution des équations numériques, Ins. France Sc. Math. Phys., t. 6, 1835. Zbl15.0063.02
30. [30] SYLVESTER (J.T.). — 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. N.Y., vol. 1, 1983, p. 429-586. 
31. [31] TARSKI (A.). — A decision method for elementary algebra and geometry. — Berkeley, 1951. Zbl0044.25102MR13,423a
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., t. 13, p. 7-19. 
33. [33] WALKER (R.). — Algebraic curves. — Princeton University Press, 1950. Zbl0039.37701MR11,387e
34. [34] WEIPSFENNING (V.). — The complexity of linear problems in fields, J. Symbolic Computation, t. 5, 1988, p. 3-27. Zbl0646.03005MR89g:11123

1. Pablo Solerno, Une inégalité de Lojasiewicz effective
2. Bernd Bank, Joos Heintz, Teresa Krick, Reinhard Mandel, Pablo Solernó, Une borne optimale pour la programmation entière quasi-convexe
3. Marie-Françoise Roy, Introduction à la géométrie algébrique réelle
4. Felice Ronga, Un procédé d'élimination effective et quelques applications
5. Bernd Bank, Marc Giusti, Joos Heintz, Luis M. Pardo, Generalized polar varieties and an efficient real elimination
6. Gal Binyamini, Sergei Yakovenko, Polynomial bounds for the oscillation of solutions of Fuchsian systems