{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:11:00Z","timestamp":1757542260637,"version":"3.38.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,12,1]],"date-time":"2010-12-01T00:00:00Z","timestamp":1291161600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math.Comput.Sci."],"published-print":{"date-parts":[[2010,12]]},"DOI":"10.1007\/s11786-011-0071-8","type":"journal-article","created":{"date-parts":[[2011,10,4]],"date-time":"2011-10-04T06:15:16Z","timestamp":1317708916000},"page":"481-506","source":"Crossref","is-referenced-by-count":7,"title":["A General Approach to Isolating Roots of a Bitstream Polynomial"],"prefix":"10.1007","volume":"4","author":[{"given":"Michael","family":"Sagraloff","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,10,5]]},"reference":[{"key":"71_CR1","doi-asserted-by":"crossref","first-page":"297","DOI":"10.15388\/NA.2005.10.4.15110","volume":"10","author":"A. Akritas","year":"2005","unstructured":"Akritas A., Strzebonski A.: A comparative study of two root isolation methods. Nonlinear Anal. Model. Control 10, 297\u2013304 (2005)","journal-title":"Nonlinear Anal. Model. Control"},{"issue":"4","key":"71_CR2","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/BF02237816","volume":"24","author":"A.G. Akritas","year":"1980","unstructured":"Akritas A.G.: The fastest exact algorithms for the isolation of the real roots of a polynomial equation. Computing 24(4), 299\u2013313 (1980)","journal-title":"Computing"},{"key":"71_CR3","first-page":"219","volume":"44","author":"A. Alesina","year":"1998","unstructured":"Alesina A., Galuzzi M.: A new proof of Vicent\u2019s theorem. L\u2019Enseignement Mathematique 44, 219\u2013256 (1998)","journal-title":"L\u2019Enseignement Mathematique"},{"key":"71_CR4","doi-asserted-by":"crossref","unstructured":"Beberich, E., Emeliyanenko, P., Sagraloff, M.: An elimination method for solving bivariate polynomial systems: eliminating the usual drawbacks. In: ALENEX, pp. 35\u201347. SIAM, Philadelphia (2011)","DOI":"10.1137\/1.9781611972917.4"},{"issue":"3","key":"71_CR5","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/j.comgeo.2009.01.009","volume":"43","author":"E. Berberich","year":"2009","unstructured":"Berberich E., Kerber M., Sagraloff M.: An efficient algorithm for the stratification and triangulation of an algebraic surface. Comput. Geom. Theory Appl. (CGTA) 43(3), 257\u2013278 (2009)","journal-title":"Comput. Geom. Theory Appl. (CGTA)"},{"key":"71_CR6","first-page":"143","volume":"34","author":"G. Collins","year":"2002","unstructured":"Collins G., Johnson J., Krandick W.: Interval arithmetic in cylindrical algebraic decomposition. JSC 34, 143\u2013155 (2002)","journal-title":"JSC"},{"key":"71_CR7","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1145\/800205.806346","volume-title":"Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation","author":"G.E. Collins","year":"1976","unstructured":"Collins G.E., Akritas A.G.: Polynomial real root isolation using Descartes\u2019 rule of signs. In: Jenks, R.D. (eds) Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, pp. 272\u2013275. ACM Press, New York (1976)"},{"key":"71_CR8","doi-asserted-by":"crossref","unstructured":"Du, Z., Sharma, V., Yap, C.: Amortized bounds for root isolation via Sturm sequences. In: SNC, pp. 113\u2013130 (2007)","DOI":"10.1007\/978-3-7643-7984-1_8"},{"issue":"1","key":"71_CR9","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1016\/j.cam.2005.12.016","volume":"200","author":"A. Eigenwillig","year":"2007","unstructured":"Eigenwillig A.: On multiple roots in Descartes\u2019 rule and their distance to roots of higher derivatives. J. Comput. Appl. Math. 200(1), 226\u2013230 (2007)","journal-title":"J. Comput. Appl. Math."},{"key":"71_CR10","unstructured":"Eigenwillig, A.: Real root isolation for exact and approximate polynomials using Descartes\u2019 rule of signs. PhD thesis, Universit\u00e4t des Saarlandes (2008)"},{"key":"71_CR11","doi-asserted-by":"crossref","unstructured":"Eigenwillig, A., Kerber, M., Wolpert, N.: Fast and exact geometric analysis of real algebraic plane curves. In: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation (ISSAC 2007), pp. 151\u2013158 (2007)","DOI":"10.1145\/1277548.1277570"},{"key":"71_CR12","doi-asserted-by":"crossref","unstructured":"Eigenwillig, A., Kettner, L., Krandick, W., Mehlhorn, K., Schmitt, S., Wolpert, N.: An exact descartes algorithm with approximate coefficients. In: CASC. LNCS, vol. 3718, pp. 138\u2013149 (2005)","DOI":"10.1007\/11555964_12"},{"key":"71_CR13","doi-asserted-by":"crossref","unstructured":"Eigenwillig, A., Sharma, V., Yap, C.: Almost tight complexity bounds for the Descartes method. In: ISSAC, pp. 71\u201378 (2006)","DOI":"10.1145\/1145768.1145786"},{"key":"71_CR14","first-page":"3218","volume-title":"Modular algorithms in symbolic summation and symbolic integration. LNCS","author":"J. Gerhard","year":"2004","unstructured":"Gerhard J.: Modular algorithms in symbolic summation and symbolic integration. LNCS, pp. 3218. Springer, Berlin (2004)"},{"key":"71_CR15","unstructured":"Gourdon, X.: Combinatoire, Algorithmique et G\u00e9om\u00e9trie des Polyn\u00f4mes. Th\u00e8se, \u00c9cole polytechnique (1996)"},{"key":"71_CR16","doi-asserted-by":"crossref","unstructured":"Hemmer, M., Tsigaridas, E.P., Zafeirakopoulos, Z., Emiris, I.Z., Karavelas, M.I., Mourrain, B.: Experimental evaluation and cross benchmarking of univariate real solvers. In: SNC, pp. 45\u201354 (2009)","DOI":"10.1145\/1577190.1577202"},{"key":"71_CR17","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/978-3-7091-9459-1_13","volume-title":"Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and monographs in Symbolic Computation","author":"J. Johnson","year":"1998","unstructured":"Johnson J.: Algorithms for polynomial real root isolation. In: Caviness, B., Johnson, J. (eds) Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and monographs in Symbolic Computation, pp. 269\u2013299. Springer, Berlin (1998)"},{"key":"71_CR18","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1145\/258726.258790","volume-title":"ISSAC","author":"J.R. Johnson","year":"1997","unstructured":"Johnson J.R., Krandick W.: Polynomial real root isolation using approximate arithmetic. In: K\u00fcchlin, W. (eds) ISSAC, pp. 225\u2013232. ACM Press, New York (1997)"},{"key":"71_CR19","unstructured":"Kerber, M.: Geometric Algorithms for Algebraic Curves and Surfaces. PhD thesis, Universit\u00e4t des Saarlandes (2009)"},{"issue":"1","key":"71_CR20","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.jsc.2005.02.004","volume":"41","author":"W. Krandick","year":"2006","unstructured":"Krandick W., Mehlhorn K.: New bounds for the Descartes method. J. Symb. Comput. 41(1), 49\u201366 (2006)","journal-title":"J. Symb. Comput."},{"key":"71_CR21","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1006\/jsco.2000.0427","volume":"31","author":"T. Lickteig","year":"2001","unstructured":"Lickteig T., Roy M.-F.: Sylvester-Habicht sequences and fast Cauchy index computation. J. Symb. Comput. 31, 315\u2013341 (2001)","journal-title":"J. Symb. Comput."},{"issue":"6","key":"71_CR22","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1016\/j.jsc.2010.02.002","volume":"45","author":"K. Mehlhorn","year":"2010","unstructured":"Mehlhorn K., Ray S.: Faster algorithms for computing Hong\u2019s bound on absolute positiveness. J. Symb. Comput. 45((6), 677\u2013683 (2010)","journal-title":"J. Symb. Comput."},{"issue":"1","key":"71_CR23","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1016\/j.jsc.2010.09.004","volume":"46","author":"K. Mehlhorn","year":"2011","unstructured":"Mehlhorn K., Sagraloff M.: A deterministic algorithm for isolating real roots of a real polynomial. J. Symb. Comput. 46(1), 70\u201390 (2011)","journal-title":"J. Symb. Comput."},{"key":"71_CR24","unstructured":"Mitchell, D.P.: Robust ray intersection with interval arithmetic. In: Graphics Interface\u201990, pp. 68\u201374 (1990)"},{"key":"71_CR25","unstructured":"Mourrain, B., Rouillier, F., Roy, M.-F.: The Bernstein basis and real root isolation. In: Goodman, J.E., Pach, J., Welzl, E. (eds.) Combinatorial and Computational Geometry, number 52 in MSRI Publications, pp. 459\u2013478. Cambridge University Press, Cambridge (2005)"},{"issue":"8","key":"71_CR26","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1016\/0898-1221(87)90186-6","volume":"14","author":"V.Y. Pan","year":"1987","unstructured":"Pan V.Y.: Sequential and parallel complexity of approximate evaluation of polynomial zeros. Comput. Math. Appl. 14(8), 591\u2013622 (1987)","journal-title":"Comput. Math. Appl."},{"issue":"2","key":"71_CR27","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1137\/S0036144595288554","volume":"39","author":"V.Y. Pan","year":"1997","unstructured":"Pan V.Y.: Solving a polynomial equation: some history and recent progress. SIAM Rev. 39(2), 187\u2013220 (1997)","journal-title":"SIAM Rev."},{"key":"71_CR28","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/j.cam.2003.08.015","volume":"162","author":"F. Rouillier","year":"2004","unstructured":"Rouillier F., Zimmermann P.: Efficient isolation of [a] polynomial\u2019s real roots. J. Comput. Appl. Math. 162, 33\u201350 (2004)","journal-title":"J. Comput. Appl. Math."},{"key":"71_CR29","doi-asserted-by":"crossref","unstructured":"Sagraloff, M., Yap, C.: A simple but exact and efficient algorithm for complex root isolation. In: International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 353\u2013360 (2011)","DOI":"10.1145\/1993886.1993938"},{"key":"71_CR30","unstructured":"Sch\u00f6nhage, A.: The fundamental theorem of algebra in terms of computational complexity, 1982. Manuscript, Department of Mathematics, University of T\u00fcbingen. Updated (2004)"},{"issue":"1","key":"71_CR31","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/0885-064X(85)90024-X","volume":"1","author":"A. Sch\u00f6nhage","year":"1985","unstructured":"Sch\u00f6nhage A.: Quasi-GCD computations. J. Complex. 1(1), 118\u2013137 (1985)","journal-title":"J. Complex."},{"key":"71_CR32","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1016\/j.tcs.2008.09.017","volume":"409","author":"V. Sharma","year":"2008","unstructured":"Sharma V.: Complexity of real root isolation using continued fractions. Theor. Comput. Sci. 409, 292\u2013310 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"71_CR33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1981-14858-8","volume":"4","author":"S. Smale","year":"1981","unstructured":"Smale S.: The fundamental theorem of algebra and complexity theory. Bull. (N.S.) AMS 4(1), 1\u201336 (1981)","journal-title":"Bull. (N.S.) AMS"},{"issue":"4","key":"71_CR34","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1145\/321607.321615","volume":"17","author":"B.T. Smith","year":"1970","unstructured":"Smith B.T.: Error bounds for zeros of a polynomial based upon Gerschgorin\u2019s theorems. J. ACM 17(4), 661\u2013674 (1970)","journal-title":"J. ACM"},{"issue":"1\u20133","key":"71_CR35","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/j.tcs.2007.10.010","volume":"392","author":"E.P. Tsigaridas","year":"2008","unstructured":"Tsigaridas E.P., Emiris I.Z.: On the complexity of real root isolation using continued fractions. Theor. Comput. Sci. 392(1\u20133), 158\u2013173 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"71_CR36","first-page":"341","volume":"1","author":"A.J.H. Vincent","year":"1836","unstructured":"Vincent A.J.H.: Sur la r\u00e9solution des equations num\u00e9riques. Journal de Math\u00e9matiques Pures et Appliqu\u00e9es 1, 341\u2013372 (1836)","journal-title":"Journal de Math\u00e9matiques Pures et Appliqu\u00e9es"},{"key":"71_CR37","volume-title":"Fundamental Problems in Algorithmic Algebra","author":"C.K. Yap","year":"2000","unstructured":"Yap C.K.: Fundamental Problems in Algorithmic Algebra. Oxford University Press, UK (2000)"}],"container-title":["Mathematics in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-011-0071-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11786-011-0071-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-011-0071-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,12]],"date-time":"2025-03-12T11:45:57Z","timestamp":1741779957000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11786-011-0071-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["71"],"URL":"https:\/\/doi.org\/10.1007\/s11786-011-0071-8","relation":{},"ISSN":["1661-8270","1661-8289"],"issn-type":[{"type":"print","value":"1661-8270"},{"type":"electronic","value":"1661-8289"}],"subject":[],"published":{"date-parts":[[2010,12]]}}}