Sur la complexité du principe de Tarski-Seidenberg
Heintz, Joos ; Roy, Marie-Françoise ; Solernó, Pablo
Bulletin de la Société Mathématique de France, Tome 118 (1990), p. 101-126 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{BSMF_1990__118_1_101_0,
     author = {Heintz, Joos and Roy, Marie-Fran\c coise and Solern\'o, Pablo},
     title = {Sur la complexit\'e du principe de Tarski-Seidenberg},
     journal = {Bulletin de la Soci\'et\'e Math\'ematique de France},
     volume = {118},
     year = {1990},
     pages = {101-126},
     doi = {10.24033/bsmf.2138},
     mrnumber = {92g:03047},
     zbl = {0767.03017},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/BSMF_1990__118_1_101_0}
}

Heintz, Joos; Roy, Marie-Françoise; Solernó, Pablo. Sur la complexité du principe de Tarski-Seidenberg. Bulletin de la Société Mathématique de France, Tome 118 (1990) pp. 101-126. doi : 10.24033/bsmf.2138. http://gdmltest.u-ga.fr/item/BSMF_1990__118_1_101_0/

[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. | MR 87m:03056 | Zbl 0634.03031

[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. | MR 85k:65111 | Zbl 0541.68019

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

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

[5] Canny (J.). - The complexity of robot motion planning. - MIT Press, 1989.

[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. | MR 53 #7771 | 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, t. 357, p. 131-151. | MR 90j:13001 | 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, t. 5, 1988, p. 121-129. | MR 89g:12002 | Zbl 0689.14006

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

[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). | Zbl 0704.03014

[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. | 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, ACM Press, 1989, p. 136-145.

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

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

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

[17] Heintz (J.). - Definability and fast quantifier elimination in algebraically closed fields, Theor. Comput. Sci., t. 24, 1983, p. 239-277. | MR 85a:68062 | Zbl 0546.03017

[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] Heintz (J.), Roy (M.-F.), Solerno (P.). - Complexité du principe de Tarski-Seidenberg, C.R.A.S. Paris, t. 309, 1989, p. 825-830. | MR 92c:12012 | 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.), Logar (A.). - Membership problems, representations and the computation of the radical of one-dimensional ideals, à paraître dans les Actes de MEGA, 1990.

[22] Loos (R.). - Generalized poynomial reaminder sequences, in Computer Algebra, Symbolic and Algebraic Computation. - Ed. Buchberger, Collins, Loos, Springer Verlag, 1982, p. 115-138. | 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.

[25] Roy (M.-F.), Szpirglas (A.). - Complexity of computations with real algebraic numbers, à paraître au Journal of Symbolic Computation.

[26] Seidenberg (A.). - A new decision method for elementary algebra and geometry, Ann. Math., t. 60, 1954, p. 365-374. | MR 16,209a | Zbl 0056.01804

[27] Shafarevitch (I.S.). - Algebraic geometry. - Springer Verlag, 1974.

[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., t. 6, 1835.

[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] Tarski (A.). - A decision method for elementary algebra and geometry. - Berkeley, 1951. | MR 13,423a | 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., t. 13, p. 7-19.

[33] Walker (R.). - Algebraic curves. - Princeton University Press, 1950. | MR 11,387e | Zbl 0039.37701

[34] Weipsfenning (V.). - The complexity of linear problems in fields, J. Symbolic Computation, t. 5, 1988, p. 3-27. | MR 89g:11123 | Zbl 0646.03005