{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,27]],"date-time":"2023-12-27T00:05:59Z","timestamp":1703635559498},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T00:00:00Z","timestamp":1689120000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T00:00:00Z","timestamp":1689120000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2023,12]]},"DOI":"10.1007\/s00037-023-00240-1","type":"journal-article","created":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T12:01:50Z","timestamp":1689163310000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Characterization of Functions over the Integers Computable in Polynomial Time Using Discrete Ordinary Differential Equations"],"prefix":"10.1007","volume":"32","author":[{"given":"Olivier","family":"Bournez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnaud","family":"Durand","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,12]]},"reference":[{"key":"240_CR1","unstructured":"V.I. Arnold (1978). Ordinary Differential Equations. MIT Press."},{"key":"240_CR2","doi-asserted-by":"crossref","unstructured":"Stephen Bellantoni & Stephen Cook (1992). A new recursion_\ntheoretic characterization of the poly-time functions. Computational\nComplexity 2, 97\u2013110.","DOI":"10.1007\/BF01201998"},{"key":"240_CR3","unstructured":"Garrett Birkhoff & Gian-Carlo Rota (1989). Ordinary Differential\nEquations. John Wiley & Sons, 4th edition."},{"key":"240_CR4","unstructured":"Olivier Bournez & Arnaud Durand (2019). Recursion Schemes,\nDiscrete Differential Equations and Characterization of Polynomial\nTime Computations. In 44th International Symposium on Mathematical\nFoundations of Computer Science, MFCS 2019, August 26\u201330, 2019,\nAachen, Germany, Peter Rossmanith, Pinar Heggernes & Joost-\nPieter Katoen, editors, volume 138 of LIPIcs, 23:1\u201323:14. Schloss\nDagstuhl - Leibniz-Zentrum f\u00a8ur Informatik. URL https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.23."},{"key":"240_CR5","doi-asserted-by":"crossref","unstructured":"Olivier Bournez, Daniel S. Gra\u03c2a & Amaury Pouly (2017).\nPolynomial Time corresponds to Solutions of Polynomial Ordinary Differential\nEquations of Polynomial Length. Journal of the ACM 64(6),\n38:1\u201338:76.","DOI":"10.1145\/3127496"},{"key":"240_CR6","unstructured":"Olivier Bournez & Amaury Pouly (2018). A Survey on Analog\nModels of Computation. In Handbook of Computability and Complexity\nin Analysis, Vasco Brattka & Peter Hertling, editors. Springer.\nTo appear."},{"key":"240_CR7","doi-asserted-by":"crossref","unstructured":"Manuel L. Campagnolo (2001). Computational Complexity of Real\nValued Recursive Functions and Analog Circuits. Ph.D. thesis, Universidade\nT\u00b4ecnica de Lisboa.","DOI":"10.1007\/3-540-45833-6_1"},{"key":"240_CR8","doi-asserted-by":"crossref","unstructured":"Manuel L. Campagnolo, Cristopher Moore & Jos\u00e9 F\u00e9lix\nCosta (2002a). An analog characterization of the Grzegorczyk hierarchy\n18(4), 977\u20131000.","DOI":"10.1006\/jcom.2002.0655"},{"key":"240_CR9","doi-asserted-by":"crossref","unstructured":"Manuel L. Campagnolo, Cristopher Moore & Jos\u00e9   F\u00e9lix\nCosta (2002b).An analog characterization of the Grzegorczyk hierarchy .\nJournal of Complexity 18(4), 977\u20131000.","DOI":"10.1006\/jcom.2002.0655"},{"key":"240_CR10","doi-asserted-by":"crossref","unstructured":"P. Clote (1998). Computational Models and Function Algebras. In\nHandbook of Computability Theory, Edward R. Griffor, editor, 589\u2013\n681. North-Holland, Amsterdam. ISBN 0-444-89882-4.","DOI":"10.1016\/S0049-237X(99)80033-0"},{"key":"240_CR11","unstructured":"Peter Clote & Evangelos Kranakis (2013).Boolean functions\nand computation models . Springer Science & Business Media."},{"key":"240_CR12","unstructured":"Alan Cobham (1962). The intrinsic computational difficulty of functions.\nIn Proceedings of the International Conference on Logic, Methodology,\nand Philosophy of Science, Y. Bar-Hillel, editor, 24\u201330. North-\nHolland, Amsterdam."},{"key":"240_CR13","unstructured":"Earl A. Coddington & Norman Levinson (1955).Theory of Ordinary\nDifferential Equations . Mc-Graw-Hill."},{"key":"240_CR14","doi-asserted-by":"crossref","unstructured":"Pieter Collins & Daniel S Gra\u03c2a (2008). Effective computability\nof solutions of ordinary differential equations the thousand monkeys\napproach. Electronic Notes in Theoretical Computer Science 221, 103\u2013\n114.","DOI":"10.1016\/j.entcs.2008.12.010"},{"key":"240_CR15","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest\n& Clifford Stein (2009). Introduction to algorithms (third edition).\nMIT press."},{"key":"240_CR16","unstructured":"A.O. Gelfand (1963). Calcul des diff\u00e9rences finies. Dunod."},{"key":"240_CR17","unstructured":"David Gleich (2005). Finite calculus: A tutorial for solving nasty\nsums. Stanford University ."},{"key":"240_CR18","doi-asserted-by":"crossref","unstructured":"Ronald L. Graham, Donald E. Knuth, Oren Patashnik & Stanley\nLiu (1989). Concrete mathematics: a foundation for computer\nscience. Computers in Physics 3(5), 106\u2013107.","DOI":"10.1063\/1.4822863"},{"key":"240_CR19","doi-asserted-by":"crossref","unstructured":"F.A. Izadi, N. Aliev & G Bagirov (2009). Discrete Calculus by\nAnalogy. Bentham Science Publishers.","DOI":"10.2174\/97816080508641090101"},{"key":"240_CR20","unstructured":"Charles Jordan & K\u00e1roly Jord\u00e1n (1965).Calculus of finite differences ,\nvolume 33. American Mathematical Soc."},{"key":"240_CR21","unstructured":"L\u00e1szl\u00f3. Kalm\u00e1r (1943). Egyzzer\u00fc p\u00e9lda eld\u00f6nthetetlen aritmetikai\nprobl\u00e9m\u00e1ra. Mate \u00e9s Fizikai Lapok 50, 1\u201323."},{"key":"240_CR22","doi-asserted-by":"crossref","unstructured":"Akitoshi Kawamura (2009). Lipschitz continuous ordinary differential\nequations are polynomial-space complete. In 2009 24th Annual\nIEEE Conference on Computational Complexity, 149\u2013160. IEEE.","DOI":"10.1109\/CCC.2009.34"},{"key":"240_CR23","doi-asserted-by":"crossref","unstructured":"Ker-I Ko (1983). On the Computational Complexity of Ordinary Differential\nEquations. Information and Control 58(1\u20133), 157\u2013194.","DOI":"10.1016\/S0019-9958(83)80062-X"},{"key":"240_CR24","unstructured":"Gustavo Lau (2018). URL http:\/\/www.acm.ciens.ucv.ve\/main\/entrenamiento\/material\/DiscreteCalculus.pdf.Discrete calculus."},{"key":"240_CR25","doi-asserted-by":"crossref","unstructured":"Daniel Leivant (1994). Predicative recurrence and computational\ncomplexity I: Word recurrence and poly-time. In Feasible Mathematics\nII, Peter Clote & Jeffery Remmel, editors, 320\u2013343. Birkh\u00e4user.","DOI":"10.1007\/978-1-4612-2566-9_11"},{"key":"240_CR26","doi-asserted-by":"crossref","unstructured":"Daniel Leivant & Jean-Yves Marion (1993). Lambda Calculus\nCharacterizations of Poly-Time. Fundamenta Informatica 19(1,2),\n167,184.","DOI":"10.3233\/FI-1993-191-207"},{"key":"240_CR27","unstructured":"Daniel Leivant & Jean-Yves Marion (1995). Ramified recurrence\nand computational complexity II: substitution and poly-space.\nIn Computer Science Logic, 8th Workshop, CSL\u201994, L. Pacholski &\nJ. Tiuryn, editors, volume 933 of Lecture Notes in Computer Science,\n369\u2013380. Springer, Kazimierz, Poland."},{"key":"240_CR28","unstructured":"Bruno Loff, Jos\u00e9 F\u00e9lix Costa & Jerzy Mycka (2007). The New\nPromise of Analog Computation. In Computability in Europe 2007:\nComputation and Logic in the Real World."},{"key":"240_CR29","doi-asserted-by":"crossref","unstructured":"Cristopher Moore (1996). Recursion theory on the reals and\ncontinuous-time computation. Theoretical Computer Science 162(1),\n23\u201344.","DOI":"10.1016\/0304-3975(95)00248-0"},{"key":"240_CR30","unstructured":"Jerzy Mycka & Jos\u00e9 F\u00e9lix Costa (2005). What lies beyond the\nmountains? Computational systems beyond the Turing limit. European\nAssociation for Theoretical Computer Science Bulletin 85, 181\u2013189."},{"key":"240_CR31","doi-asserted-by":"crossref","unstructured":"Jerzy Mycka & Jos\u00e9 F\u00e9lix Costa (2006). The P\u2260NP conjecture\nin the context of real and complex analysis. Journal of Complexity\n22(2), 287\u2013303.","DOI":"10.1016\/j.jco.2005.07.003"},{"key":"240_CR32","unstructured":"Piergiorgio Odifreddi (1992). Classical Recursion Theory, volume\n125 of Studies in Logic and the foundations of mathematics .North-\nHolland."},{"key":"240_CR33","unstructured":"Amaury Pouly (2015). Continuous models of computation: from computability\nto complexity. Ph.D. thesis, Ecole Polytechnique and Unidersidade\nDo Algarve. https:\/\/pastel.archives-ouvertes.fr\/tel-01223284,\nAckermann Award 2017."},{"key":"240_CR34","unstructured":"H.E. Rose (1984).Subrecursion . Oxford university press."},{"key":"240_CR35","unstructured":"Michael Sipser (1997). Introduction to the Theory of Computation.\nPWS Publishing Company."},{"key":"240_CR36","doi-asserted-by":"crossref","unstructured":"David B Thompson (1972). Subrecursiveness: Machine-independent\nnotions of computability in restricted time and storage. Mathematical\nSystems Theory 6(1-2), 3\u201315.","DOI":"10.1007\/BF01706069"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00240-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-023-00240-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00240-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,26]],"date-time":"2023-12-26T19:03:50Z","timestamp":1703617430000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-023-00240-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,12]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["240"],"URL":"https:\/\/doi.org\/10.1007\/s00037-023-00240-1","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,12]]},"assertion":[{"value":"22 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"7"}}