{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:01:01Z","timestamp":1725516061926},"publisher-location":"Berlin, Heidelberg","reference-count":44,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540855200"},{"type":"electronic","value":"9783540855217"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85521-7_12","type":"book-chapter","created":{"date-parts":[[2008,8,5]],"date-time":"2008-08-05T06:45:26Z","timestamp":1217918726000},"page":"193-237","source":"Crossref","is-referenced-by-count":6,"title":["Theory of Real Computation According to EGC"],"prefix":"10.1007","author":[{"given":"Chee","family":"Yap","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"12_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/11555964_12","volume-title":"Computer Algebra in Scientific Computing","author":"A. Eigenwillig","year":"2005","unstructured":"Eigenwillig, A., Kettner, L., Krandick, W., Mehlhorn, K., Schmitt, S., Wolpert, N.: A Descartes algorithm for polynomials with bit stream coefficients. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) CASC 2005. LNCS, vol.\u00a03718, pp. 138\u2013149. Springer, Heidelberg (2005)"},{"key":"12_CR2","volume-title":"The Design and Analysis of Computer Algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)"},{"key":"12_CR3","unstructured":"Allender, E., B\u00fcrgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P.B.: On the complexity of numerical analysis. In: Proc. 21st IEEE Conf. on Computational Complexity (to appear, 2006)"},{"key":"12_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-68952-9","volume-title":"Foundations of Constructive Mathematics","author":"M.J. Beeson","year":"1985","unstructured":"Beeson, M.J.: Foundations of Constructive Mathematics. Springer, Berlin (1985)"},{"issue":"1","key":"12_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1142\/S0218127496001818","volume":"6","author":"L. Blum","year":"1996","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and real computation: A manifesto. Int. J. of Bifurcation and Chaos\u00a06(1), 3\u201326 (1996)","journal-title":"Int. J. of Bifurcation and Chaos"},{"key":"12_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and Real Computation","author":"L. Blum","year":"1998","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, New York (1998)"},{"key":"12_CR7","volume-title":"The Computational Complexity of Algebraic and Numeric Problems","author":"A. Borodin","year":"1975","unstructured":"Borodin, A., Munro, I.: The Computational Complexity of Algebraic and Numeric Problems. American Elsevier Publishing Company, Inc., New York (1975)"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1145\/321941.321944","volume":"23","author":"R.P. Brent","year":"1976","unstructured":"Brent, R.P.: Fast multiple-precision evaluation of elementary functions. J. of the ACM\u00a023, 242\u2013251 (1976)","journal-title":"J. of the ACM"},{"key":"12_CR9","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/B978-0-12-697560-4.50014-9","volume-title":"Proc. Symp. on Analytic Computational Complexity","author":"R.P. Brent","year":"1976","unstructured":"Brent, R.P.: Multiple-precision zero-finding methods and the complexity of elementary function evaluation. In: Traub, J.F. (ed.) Proc. Symp. on Analytic Computational Complexity, pp. 151\u2013176. Academic Press, London (1976)"},{"key":"12_CR10","series-title":"Series of Comprehensive Studies in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic Complexity Theory","author":"P. B\u00fcrgisser","year":"1997","unstructured":"B\u00fcrgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. Series of Comprehensive Studies in Mathematics, vol.\u00a0315. Springer, Berlin (1997)"},{"key":"12_CR11","first-page":"341","volume-title":"Proc. 15th ACM Symp. Comp. Geom.","author":"C. Burnikel","year":"1999","unstructured":"Burnikel, C., Fleischer, R., Mehlhorn, K., Schirra, S.: Exact efficient geometric computation made easy. In: Proc. 15th ACM Symp. Comp. Geom., pp. 341\u2013450. ACM Press, New York (1999)"},{"issue":"5-6","key":"12_CR12","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1142\/S0218195906002191","volume":"16","author":"E.-C. Chang","year":"2006","unstructured":"Chang, E.-C., Choi, S.W., Kwon, D., Park, H., Yap, C.: Shortest paths for disc obstacles is computable. Int\u2019l. J. Comput. Geometry and Appl.\u00a016(5-6), 567\u2013590 (2006); Special Issue of IJCGA on Geometric Constraints. (Gao, X.S., Michelucci, D (eds.))","journal-title":"Int\u2019l. J. Comput. Geometry and Appl."},{"key":"12_CR13","volume-title":"Introduction to Algorithms","author":"T.H. Corman","year":"2001","unstructured":"Corman, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press and McGraw-Hill Book Company, Cambridge, Massachusetts and New York (2001)","edition":"2"},{"key":"12_CR14","unstructured":"Demmel, J.: The complexity of accurate floating point computation. In: Proc. of the ICM, Beijing, vol.\u00a03, pp. 697\u2013706 (2002)"},{"key":"12_CR15","unstructured":"Demmel, J., Dumitriu, I., Holtz, O.: Toward accurate polynomial evaluation in rounded arithmetic (2005) Paper ArXiv:math.NA\/0508350, download from http:\/\/lanl.arxiv.org\/"},{"key":"#cr-split#-12_CR16.1","unstructured":"Du, Z., Sharma, V., Yap, C.: Amortized bounds for root isolation via Sturm sequences. In: Wang, D., Zhi, L. (eds.) Proc. Internat. Workshop on Symbolic-Numeric Computation. School of Science, Beihang University, Beijing, China, pp. 81???93 (2005);"},{"key":"#cr-split#-12_CR16.2","unstructured":"Int???l Workshop on Symbolic-Numeric Computation, Xi???an, China, July 19???21 (2005)"},{"key":"12_CR17","unstructured":"Fabri, A., Fogel, E., G\u00e4rtner, B., Hoffmann, M., Kettner, L., Pion, S., Teillaud, M., Veltkamp, R., Yvinec, M.: The CGAL manual, Release 3.0 (2003)"},{"issue":"950","key":"12_CR18","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1098\/rsta.1956.0003","volume":"248","author":"A. Fr\u00f6hlich","year":"1956","unstructured":"Fr\u00f6hlich, A., Shepherdson, J.: Effective procedures in field theory. Philosophical Trans. Royal Soc. of London. Series A, Mathematical and Physical Sciences\u00a0248(950), 407\u2013432 (1956)","journal-title":"Philosophical Trans. Royal Soc. of London. Series A, Mathematical and Physical Sciences"},{"key":"12_CR19","volume-title":"Naive Set Theory","author":"P.R. Halmos","year":"1960","unstructured":"Halmos, P.R.: Naive Set Theory. Van Nostrand Reinhold Company, New York (1960)"},{"issue":"2","key":"12_CR20","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1145\/505372.505375","volume":"3","author":"J.V. Tucker","year":"2002","unstructured":"Tucker, J.V., Zucker, J.I.: Abstract computability and algebraic specification. ACM Trans. on Computational Logic\u00a03(2), 279\u2013333 (2002)","journal-title":"ACM Trans. on Computational Logic"},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"Karamcheti, V., Li, C., Pechtchanski, I., Yap, C.: A Core library for robust numerical and geometric computation. In: 15th ACM Symp. Computational Geometry, pp. 351\u2013359 (1999)","DOI":"10.1145\/304893.304989"},{"key":"12_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1007\/978-3-540-30140-0_62","volume-title":"Algorithms \u2013 ESA 2004","author":"L. Kettner","year":"2004","unstructured":"Kettner, L., Mehlhorn, K., Pion, S., Schirra, S., Yap, C.: Classroom examples of robustness problems in geometric computation. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 702\u2013713. Springer, Heidelberg (2004)"},{"key":"12_CR23","series-title":"Progress in Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-6802-1","volume-title":"Complexity Theory of Real Functions","author":"K.-I. Ko","year":"1991","unstructured":"Ko, K.-I.: Complexity Theory of Real Functions. Progress in Theoretical Computer Science. Birkh\u00e4user, Boston (1991)"},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(85)90208-7","volume":"38","author":"C. Kreitz","year":"1985","unstructured":"Kreitz, C., Weihrauch, K.: Theory of representations. Theoretical Computer Science\u00a038, 35\u201353 (1985)","journal-title":"Theoretical Computer Science"},{"key":"12_CR25","unstructured":"Lambov, B.: Topics in the Theory and Practice of Computable Analysis. Phd thesis, University of Aarhus, Denmark (2005)"},{"key":"12_CR26","first-page":"1937","volume-title":"The Metamethematics of Algebraic Systems. Collected papers: 1937\u20131967","author":"A.I. Mal\u2019cev","year":"1971","unstructured":"Mal\u2019cev, A.I.: The Metamethematics of Algebraic Systems. Collected papers: 1937\u20131967. North-Holland, Amsterdam (1971); Translated and edited by Wells, III, B.F"},{"key":"12_CR27","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/978-3-7091-6280-4_16","volume-title":"Symbolic Algebraic Methods and Verification Methods","author":"K. Mehlhorn","year":"2001","unstructured":"Mehlhorn, K., Schirra, S.: Exact computation with leda_real \u2013 theory and geometric applications. In: Alefeld, G., Rohn, J., Rump, S., Yamamoto, T. (eds.) Symbolic Algebraic Methods and Verification Methods, Vienna, pp. 163\u2013172. Springer, Heidelberg (2001)"},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"Mueller, N., Escardo, M., Zimmermann, P.: Guest editor\u2019s introduction: Practical development of exact real number computation. J. of Logic and Algebraic Programming\u00a064(1) (2004) (special Issue)","DOI":"10.1016\/j.jlap.2004.07.001"},{"key":"12_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1007\/3-540-16761-7_78","volume-title":"Proc. 13th Int\u2019l Colloq. on Automata, Languages and Programming","author":"N.T. M\u00fcler","year":"1986","unstructured":"M\u00fcler, N.T.: Subpolynomial complexity classes of real functions and real numbers. In: Kott, L. (ed.) Proc. 13th Int\u2019l Colloq. on Automata, Languages and Programming. LNCS, vol.\u00a0226, pp. 284\u2013293. Springer, Berlin (1986); I cite this paper for Weihrauch\u2019s broken arrow notation for partial functions... apparently, it is the older of the two notation from Weihrauch!"},{"key":"12_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/3-540-45335-0_14","volume-title":"Computability and Complexity in Analysis","author":"N.T. M\u00fcller","year":"2001","unstructured":"M\u00fcller, N.T.: The iRRAM: Exact arithmetic in C++. In: Blank, J., Brattka, V., Hertling, P. (eds.) CCA 2000. LNCS, vol.\u00a02064, pp. 222\u2013252. Springer, Heidelberg (2001)"},{"key":"12_CR31","series-title":"Perspectives in Mathematical Logic","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-21717-7","volume-title":"Computability in Analysis and Physics","author":"M.B. Pour-El","year":"1989","unstructured":"Pour-El, M.B., Richards, J.I.: Computability in Analysis and Physics. Perspectives in Mathematical Logic. Springer, Berlin (1989)"},{"key":"12_CR32","unstructured":"Research Triangle Park (RTI). Planning Report 02-3: The economic impacts of inadequate infrastructure for software testing. Technical report, National Institute of Standards and Technology (NIST), U.S.\u00a0Department of Commerce (May 2002)"},{"key":"12_CR33","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1006\/jsco.1997.0157","volume":"24","author":"D. Richardson","year":"1997","unstructured":"Richardson, D.: How to recognize zero. J. of Symbolic Computation\u00a024, 627\u2013645 (1997)","journal-title":"J. of Symbolic Computation"},{"issue":"1 & 2","key":"12_CR34","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.comgeo.2004.02.005","volume":"33","author":"D. Richardson","year":"2006","unstructured":"Richardson, D., El-Sonbaty, A.: Counterexamples to the uniformity conjecture. Comput. Geometry: Theory and Appl.\u00a033(1 & 2), 58\u201364 (2006); Special Issue on Robust Geometric Algorithms and its Implementations, Yap , C., Pion, S. (eds.) (to appear)","journal-title":"Comput. Geometry: Theory and Appl."},{"key":"12_CR35","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers","year":"1967","unstructured":"Rogers, H.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967)"},{"key":"12_CR36","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1137\/0209036","volume":"9","author":"A. Sch\u00f6nhage","year":"1980","unstructured":"Sch\u00f6nhage, A.: Storage modification machines. SIAM J. Computing\u00a09, 490\u2013508 (1980)","journal-title":"SIAM J. Computing"},{"key":"12_CR37","unstructured":"Spreen, D.: On some problems in computational topology. Schriften zur Theoretischen Informatik Bericht Nr.05-03, Fachberich Mathematik, Universitaet Siegen, Siegen, Germany (submitted, 2003)"},{"key":"12_CR38","volume-title":"Algebra","author":"B.L. Waerden van der","year":"1970","unstructured":"van der Waerden, B.L.: Algebra, vol.\u00a01. Frederick Ungar Publishing Co., New York (1970)"},{"key":"12_CR39","volume-title":"Handbook of Computability Theory","author":"V. Stoltenberg-Hansen","year":"1999","unstructured":"Stoltenberg-Hansen, V., Tucker, J.V.: Computable rings and fields. In: Griffor, E. (ed.) Handbook of Computability Theory. Elsevier, Amsterdam (1999)"},{"key":"12_CR40","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-56999-9","volume-title":"Computable Analysis","author":"K. Weihrauch","year":"2000","unstructured":"Weihrauch, K.: Computable Analysis. Springer, Berlin (2000)"},{"key":"12_CR41","volume-title":"Fundamental Problems of Algorithmic Algebra","author":"C.K. Yap","year":"2000","unstructured":"Yap, C.K.: Fundamental Problems of Algorithmic Algebra. Oxford University Press, Oxford (2000)"},{"key":"12_CR42","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1142\/9789812794833_0012","volume-title":"Geometric Computation, ch. 12","author":"C.K. Yap","year":"2004","unstructured":"Yap, C.K.: On guaranteed accuracy computation. In: Chen, F., Wang, D. (eds.) Geometric Computation, ch. 12, pp. 322\u2013373. World Scientific Publishing Co., Singapore (2004)"},{"key":"12_CR43","first-page":"927","volume-title":"Handbook of Discrete and Computational Geometry, ch. 41","author":"C.K. Yap","year":"2004","unstructured":"Yap, C.K.: Robust geometric computation. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, ch. 41, 2nd edn., pp. 927\u2013952. Chapman & Hall\/CRC, Boca Raton (2004)","edition":"2"}],"container-title":["Lecture Notes in Computer Science","Reliable Implementation of Real Number Algorithms: Theory and Practice"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85521-7_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:39:06Z","timestamp":1619523546000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85521-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540855200","9783540855217"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85521-7_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}