{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T14:59:27Z","timestamp":1775228367699,"version":"3.50.1"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[1974,8,1]],"date-time":"1974-08-01T00:00:00Z","timestamp":144547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGSAM Bull."],"published-print":{"date-parts":[[1974,8]]},"abstract":"<jats:p>Tarski in 1948, [18] published a quantifier elimination method for the elementary theory of real closed fields (which he had discovered in 1930). As noted by Tarski, any quantifier elimination method for this theory also provides a decision method, which enables one to decide whether any sentence of the theory is true or false. Since many important and difficult mathematical problems can be expressed in this theory, any computationally feasible quantifier elimination algorithm would be of utmost significance.<\/jats:p>","DOI":"10.1145\/1086837.1086852","type":"journal-article","created":{"date-parts":[[2007,1,17]],"date-time":"2007-01-17T18:32:02Z","timestamp":1169058722000},"page":"80-90","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":43,"title":["Quantifier elimination for real closed fields by cylindrical algebraic decomposition--preliminary report"],"prefix":"10.1145","volume":"8","author":[{"given":"George E.","family":"Collins","sequence":"first","affiliation":[{"name":"University of Wisconsin"}]}],"member":"320","published-online":{"date-parts":[[1974,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/321662.321664"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/321662.321665"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160220202"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/321371.321381"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/321662.321666"},{"key":"e_1_2_1_6_1","volume-title":"Am. Math. Monthly","author":"Collins G. E.","unstructured":"Collins , G. E. , Computer Algebra of Polynomials and Rational Functions , Am. Math. Monthly , vol. 80 , no. 7 (Aug.-Sept. 1973), pp. 725--755. Collins, G. E., Computer Algebra of Polynomials and Rational Functions, Am. Math. Monthly, vol. 80, no. 7 (Aug.-Sept. 1973), pp. 725--755."},{"key":"e_1_2_1_7_1","volume-title":"Symposium on Complexity of Sequential and Parallel Numerical Algorithms, Carnegie-Mellon University","author":"Collins G. E.","year":"1973","unstructured":"Collins , G. E. , Efficient Quantifier Elimination for Elementary Algebra (abstract) , Symposium on Complexity of Sequential and Parallel Numerical Algorithms, Carnegie-Mellon University , May 1973 . Collins, G. E., Efficient Quantifier Elimination for Elementary Algebra (abstract), Symposium on Complexity of Sequential and Parallel Numerical Algorithms, Carnegie-Mellon University, May 1973."},{"key":"e_1_2_1_8_1","unstructured":"Collins G. E. Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition to appear.  Collins G. E. Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition to appear."},{"key":"e_1_2_1_9_1","volume-title":"MAC Tech. Memo.","author":"Fischer M. J.","year":"1974","unstructured":"Fischer , M. J. , and Rabin , M. O ., Super-Exponential Complexity of Presburger Arithmetic, M.I.T . MAC Tech. Memo. 43, Feb. 1974 . Fischer, M. J., and Rabin, M. O., Super-Exponential Complexity of Presburger Arithmetic, M.I.T. MAC Tech. Memo. 43, Feb. 1974."},{"key":"e_1_2_1_10_1","volume-title":"Algebra","author":"Goldhaber J. K.","year":"1970","unstructured":"Goldhaber , J. K. , and Ehrlich , G. , Algebra , MacMillan Co. , 1970 . Goldhaber, J. K., and Ehrlich, G., Algebra, MacMillan Co., 1970."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/321662.321667"},{"key":"e_1_2_1_12_1","unstructured":"Loos R. G. K. and Collins G. E. Resultant Algorithms for Exact Arithmetic on Algebraic Numbers to appear in SIAM J. on Comp.  Loos R. G. K. and Collins G. E. Resultant Algorithms for Exact Arithmetic on Algebraic Numbers to appear in SIAM J. on Comp."},{"key":"e_1_2_1_13_1","volume-title":"Am. Math. Soc.","author":"Marden M.","year":"1949","unstructured":"Marden , M. , The Geometry of the Zeros of a Polynomial in a Complex Variable , Am. Math. Soc. , Providence , 1949 . Marden, M., The Geometry of the Zeros of a Polynomial in a Complex Variable, Am. Math. Soc., Providence, 1949."},{"key":"e_1_2_1_15_1","unstructured":"Musser D. R. Multivariate Polynomial Factorization to appear in J. ACM.  Musser D. R. Multivariate Polynomial Factorization to appear in J. ACM."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969640"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","DOI":"10.1525\/9780520348097","volume-title":"A Decision Method for Elementary Algebra and Geometry","author":"Tarski A.","year":"1951","unstructured":"Tarski , A. , A Decision Method for Elementary Algebra and Geometry , second ed., rev., Univ. of California Press , Berkeley , 1951 . Tarski, A., A Decision Method for Elementary Algebra and Geometry, second ed., rev., Univ. of California Press, Berkeley, 1951."},{"key":"e_1_2_1_19_1","volume-title":"Modern Algebra","author":"van der Waerden B. L.","year":"1953","unstructured":"van der Waerden , B. L. , Modern Algebra , vol. I , F. Ungar Co. , New York , 1953 . van der Waerden, B. L., Modern Algebra, vol. I, F. Ungar Co., New York, 1953."}],"container-title":["ACM SIGSAM Bulletin"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1086837.1086852","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1086837.1086852","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:13Z","timestamp":1750262893000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1086837.1086852"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1974,8]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1974,8]]}},"alternative-id":["10.1145\/1086837.1086852"],"URL":"https:\/\/doi.org\/10.1145\/1086837.1086852","relation":{},"ISSN":["0163-5824"],"issn-type":[{"value":"0163-5824","type":"print"}],"subject":[],"published":{"date-parts":[[1974,8]]},"assertion":[{"value":"1974-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}