{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:57:58Z","timestamp":1725663478145},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540541950"},{"type":"electronic","value":"9783540474890"}],"license":[{"start":{"date-parts":[[1991,1,1]],"date-time":"1991-01-01T00:00:00Z","timestamp":662688000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54195-0_35","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:35:21Z","timestamp":1330209321000},"page":"11-23","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Geometric problems solvable in single exponential time"],"prefix":"10.1007","author":[{"given":"Joos","family":"Heintz","sequence":"first","affiliation":[]},{"given":"Teresa","family":"Krick","sequence":"additional","affiliation":[]},{"given":"Marie-Fran\u00e7oise","family":"Roy","sequence":"additional","affiliation":[]},{"given":"Pablo","family":"Solern\u00f3","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0022-0000(86)90029-2","volume":"32","author":"M. Ben-Or","year":"1986","unstructured":"Ben-Or M., Kozen D., Reif J.: The complexity of elementary algebra and geometry. J. of Comp. and Syst. Sci. 32 (1986) 251\u2013264","journal-title":"J. of Comp. and Syst. Sci."},{"key":"2_CR2","unstructured":"Bochnak J., Coste M., Roy M-F.: G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle. Springer-Verlag (1987)"},{"issue":"3","key":"2_CR3","doi-asserted-by":"crossref","first-page":"287","DOI":"10.2307\/1971361","volume":"126","author":"W. Brownawell","year":"1987","unstructured":"Brownawell W.: Bounds for the degrees in the Nullstellensatz. Ann. Math. Vol. 126 No 3 (1987) 287\u2013290","journal-title":"Ann. Math."},{"key":"2_CR4","first-page":"131","volume":"357","author":"L. Caniglia","year":"1988","unstructured":"Caniglia L., Galligo A., Heintz J.: Some new effectivity bounds in computational geometry. Proc. AAECC-6 LN Comp. Sci. 357 (1988) 131\u2013151","journal-title":"Proc. AAECC-6 LN Comp. Sci."},{"key":"2_CR5","first-page":"255","volume":"307","author":"L. Caniglia","year":"1988","unstructured":"Caniglia L., Galligo A., Heintz J.: Borne simple exponentielle pour les degr\u00e9s dans le th\u00e9or\u00e8me des z\u00e9ros sur un corps de caract\u00e9ristique quelconque. CR Acad. Sci. Paris, t.307 (1988) 255\u2013258","journal-title":"CR Acad. Sci. Paris"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Canny J.: The complexity of motion planning. MIT Thesis 1986, MIT Press (1988)","DOI":"10.1109\/SFCS.1988.21947"},{"key":"2_CR7","unstructured":"Canny J.: A new algebraic method for robot motion planning and real algebraic geometry. Proc. 28th FOCS (1987) 39\u201348"},{"key":"2_CR8","unstructured":"Canny J., Grigor'ev D.Yu., Vorobjov N.N. (Jr.): Finding connected components of a semialgebraic set in subexponential time. Manuscript Steklov Math. Inst. Leningrad LOMI (1990)"},{"key":"2_CR9","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0747-7171(88)80008-7","volume":"5","author":"M. Coste","year":"1988","unstructured":"Coste M., Roy M-F.: Thom's Lemma, the coding of real algebraic numbers and the topology of semialgebraic sets. J. of Symb. Comp. 5 (1988) 121\u2013129","journal-title":"J. of Symb. Comp."},{"key":"2_CR10","unstructured":"Dickenstein A., Fitchas N., Giusti M., Sessa C.: The membership problem for unmixed polynomial ideals is solvable in single exponential time. To appear in Proc. AAECC 7, Toulouse (1989)"},{"issue":"32","key":"2_CR11","first-page":"29","volume":"I","author":"N. Fitchas","year":"1990","unstructured":"Fitchas N., Galligo A., Morgenstern J.: Algorithmes en s\u00e9quentiel et en parall\u00e8le pour l'\u00e9limination des quantificateurs en g\u00e9om\u00e9trie \u00e9l\u00e9mentaire. S\u00e9minaire Structures Alg\u00e9briques Ordonn\u00e9es, S\u00e9lection d'expos\u00e9s 1984\u20131987 Vol I. Publ. Univ. Paris VII, No. 32, (1990) 29\u201335","journal-title":"S\u00e9minaire Structures Alg\u00e9briques Ordonn\u00e9es, S\u00e9lection d'expos\u00e9s 1984\u20131987"},{"key":"2_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-4049(90)90159-F","volume":"67","author":"N. Fitchas","year":"1990","unstructured":"Fitchas N., Galligo A., Morgenstern J.: Precise sequential and parallel complexity bounds for the quantifier elimination of algebraically closed fields. Journal of Pure and Applied Algebra 67 (1990) 1\u201314","journal-title":"Journal of Pure and Applied Algebra"},{"key":"2_CR13","unstructured":"Fitchas N., Galligo A.: Nullstellensatz effectif et conjecture de Serre (Th\u00e9or\u00e8me de Quillen-Suslin) pour le Calcul Formel. S\u00e9m. Structures Alg. Ord. Univ. Paris VII; final version to appear in Math. Nachrichten"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Fulton W.: Intersection Theory. Springer Verlag (1984)","DOI":"10.1007\/978-3-662-02421-8"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"von zur Gathen J.: Parallel arithmetic computations: a survey. Proc. 13th Conf. MFCS (1986)","DOI":"10.1007\/BFb0016236"},{"key":"2_CR16","unstructured":"Gonz\u00e1lez L., Lombardi H., Recio T., Roy M-F.: Sous-r\u00e9sultants et sp\u00e9cialisations de la suite de Sturm. To appear in RAIRO, Inf. Th\u00e9orique."},{"key":"2_CR17","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0747-7171(88)80006-3","volume":"5","author":"D. Y. Grigor'ev","year":"1988","unstructured":"Grigor'ev D. Yu.: Complexity of deciding Tarski algebra. J. Symb. Comp. 5 (1988) 65\u2013108","journal-title":"J. Symb. Comp."},{"key":"2_CR18","unstructured":"Grigor'ev D.Yu., Heintz J., Roy M-F., Solern\u00f3 P., Vorobjov N.N. (Jr.): Comptage des composantes connexes d'un ensemble semi-alg\u00e9brique en temps simplement exponentiel. To appear in C.R. Acad. Sci. Paris"},{"key":"2_CR19","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/S0747-7171(88)80005-1","volume":"5","author":"D. Grigor'ev","year":"1988","unstructured":"Grigor'ev D.Yu., Vorobjov N.N. (Jr.): Solving systems of polynomial inequalities in subexponential time. J. Symb. Comp. 5 (1988) 37\u201364","journal-title":"J. Symb. Comp."},{"key":"2_CR20","unstructured":"Grigor'ev D.Yu., Vorobjov N.N. (Jr.): Counting connected components of a semialgebraic set in subexponential time. Manuscript Steklov Math. Inst. Leningrad LOMI (1990)"},{"key":"2_CR21","unstructured":"Guillemin V., Pollack A.: Differential Topology. Prentice-Hall (1974)"},{"key":"2_CR22","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(83)90002-6","volume":"24","author":"J. Heintz","year":"1983","unstructured":"Heintz J.: Definability and fast quantifier elimination over algebraically closed fields. Theor. Comp. Sci. 24 (1983) 239\u2013277","journal-title":"Theor. Comp. Sci."},{"key":"2_CR23","unstructured":"Heintz J., Roy M-F., Solern\u00f3 P.: Complexity of semialgebraic sets. Manuscript IAM (1988)"},{"key":"2_CR24","unstructured":"Heintz J., Roy M-F., Solern\u00f3 P.: On the complexity of semialgebraic sets (ext. abst.). Proc. IFIP'89, 293\u2013298"},{"key":"2_CR25","first-page":"825","volume":"309","author":"J. Heintz","year":"1989","unstructured":"Heintz J., Roy M-F., Solern\u00f3 P.: Complexit\u00e9 du principe de Tarski-Seidenberg. C.R. Acad. Sci. Paris t.309 (1989) 825\u2013830","journal-title":"C.R. Acad. Sci. Paris"},{"key":"2_CR26","doi-asserted-by":"crossref","first-page":"101","DOI":"10.24033\/bsmf.2138","volume":"118","author":"J. Heintz","year":"1990","unstructured":"Heintz J., Roy M-F., Solern\u00f3 P.: Sur la complexit\u00e9 du principe de Tarski-Seidenberg. Bull. de la Soc. Math. de France 118 (1990) 101\u2013126","journal-title":"Bull. de la Soc. Math. de France"},{"key":"2_CR27","unstructured":"Heintz J., Roy M-F., Solern\u00f3 P.: Single exponential path finding in semialgebraic sets. Preprint (1990)"},{"key":"2_CR28","unstructured":"Heintz J., Roy M-F., Solern\u00f3 P.: Construction de chemins dans un ensemble semialg\u00e9brique. Manuscript (1990)"},{"key":"2_CR29","unstructured":"Ji S., Shiffman B.: A global \u0141ojasiewicz inequality for complete intersections in Cn. Preprint (1989)"},{"key":"2_CR30","first-page":"963","volume":"1","author":"J. Koll\u00e1r","year":"1988","unstructured":"Koll\u00e1r J.: Sharp effective Nullstellensatz. J. AMS 1 (1988) 963\u2013975","journal-title":"J. AMS"},{"key":"2_CR31","unstructured":"Koll\u00e1r J.: A \u0141ojasiewicz-type Inequality for Algebraic Varieties. Preprint (1989)"},{"key":"2_CR32","unstructured":"Milnor J.: Morse Theory. Princeton Univ. Press (1963)"},{"key":"2_CR33","unstructured":"Renegar J.: On the computational complexity and geometry of the first order theory of the reals I, II, III Technical Reports 853, 854, 856 (1989)"},{"key":"2_CR34","unstructured":"Solern\u00f3 P.: Complejidad de conjuntos semialgebraicos. Thesis Univ. de Buenos Aires (1989)"},{"key":"2_CR35","unstructured":"Solern\u00f3 P.: Construction de fonctions de Morse pour une hypersurface r\u00e9guli\u00e8re en temps admissible. Manuscript IAM (1989)"},{"key":"2_CR36","unstructured":"Solern\u00f3 P.: Effective Lojasiewicz inequalities. To appear in AAECC Springer-Verlag (1990)"},{"key":"2_CR37","unstructured":"Teissier B.: R\u00e9sultats r\u00e9cents d'alg\u00e8bre commutative effective. S\u00e9minaire Bourbaki 718 (1989)"},{"key":"2_CR38","unstructured":"Trotman D.: On Canny's roadmap algorithm: orienteering in semialgebraic sets. Manuscript Univ. Aix-Marseille (1989)"}],"container-title":["Lecture Notes in Computer Science","Applied Algebra, Algebraic Algorithms and Error-Correcting Codes"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54195-0_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T12:06:18Z","timestamp":1558267578000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54195-0_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540541950","9783540474890"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/3-540-54195-0_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]},"assertion":[{"value":"8 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}