{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,23]],"date-time":"2025-12-23T12:29:36Z","timestamp":1766492976930,"version":"3.44.0"},"reference-count":25,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2022,9,1]],"date-time":"2022-09-01T00:00:00Z","timestamp":1661990400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2023,1,19]]},"abstract":"<jats:p> In this paper we show that several classes of languages from computational complexity theory, such as [Formula: see text], can be characterized in a continuous manner by using only polynomial differential equations. This characterization applies not only to languages, but also to classes of functions, such as the classes defining the Grzegorczyk hierarchy, which implies an analog characterization of the class of elementary computable functions and the class of primitive recursive functions. <\/jats:p>","DOI":"10.3233\/com-210384","type":"journal-article","created":{"date-parts":[[2022,9,2]],"date-time":"2022-09-02T11:22:25Z","timestamp":1662117745000},"page":"23-57","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":4,"title":["Characterizing time computational complexity classes with polynomial differential equations"],"prefix":"10.1177","volume":"12","author":[{"given":"Riccardo","family":"Gozzi","sequence":"first","affiliation":[{"name":"Instituto Superior T\u00e9cnico, Universidade de Lisboa, Portugal"},{"name":"Instituto de Telecomunica\u00e7\u00f5es, Portugal"}]},{"given":"Daniel","family":"Gra\u00e7a","sequence":"additional","affiliation":[{"name":"Instituto de Telecomunica\u00e7\u00f5es, Portugal"},{"name":"Universidade do Algarve, Portugal"}]}],"member":"179","published-online":{"date-parts":[[2022,9,1]]},"reference":[{"key":"ref001","doi-asserted-by":"publisher","DOI":"10.1007\/11750321_60"},{"key":"ref002","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2006.12.005"},{"key":"ref003","unstructured":"O.\u00a0Bournez, D.S.\u00a0Gra\u00e7a and A.\u00a0Pouly, Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length \u2013 the general purpose analog computer and computable analysis are two efficiently equivalent models of computations, in: Proc. 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), I.\u00a0Chatzigiannakis, M.\u00a0Mitzenmacher, Y.\u00a0Rabani and D.\u00a0Sangiorgi, eds, Leibniz International Proceedings in Informatics (LIPIcs), Vol.\u00a055, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016, pp.\u00a0109:1\u2013109:15."},{"key":"ref004","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2016.05.002"},{"key":"ref005","doi-asserted-by":"publisher","DOI":"10.1145\/3127496"},{"key":"ref006","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.09.015"},{"key":"ref007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_25"},{"key":"ref008","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.010"},{"key":"ref009","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00147-B"},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68546-5_18"},{"key":"ref011","doi-asserted-by":"publisher","DOI":"10.1016\/S0016-0032(31)90616-9"},{"key":"ref012","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-0313-4_12"},{"key":"ref013","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.2000.0559"},{"key":"ref014","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.2002.0655"},{"key":"ref015","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106"},{"key":"ref016","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200310113"},{"key":"ref017","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2007.02.003"},{"key":"ref018","doi-asserted-by":"publisher","DOI":"10.1016\/S0885-064X(03)00034-7"},{"key":"ref019","first-page":"1","volume":"4","author":"Grzegorczyk A.","year":"1953","journal-title":"Rozprawy matematyczne"},{"key":"ref020","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4192-8"},{"key":"ref021","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(82)80003-0"},{"key":"ref022","unstructured":"P.\u00a0Odifreddi, Classical Recursion Theory, Vol.\u00a02, Elsevier, 1999."},{"key":"ref023","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.02.002"},{"key":"ref024","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1941201337"},{"key":"ref025","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56999-9"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-210384","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-210384","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-210384","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T12:22:15Z","timestamp":1757420535000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-210384"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,1]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,19]]}},"alternative-id":["10.3233\/COM-210384"],"URL":"https:\/\/doi.org\/10.3233\/com-210384","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"type":"print","value":"2211-3568"},{"type":"electronic","value":"2211-3576"}],"subject":[],"published":{"date-parts":[[2022,9,1]]}}}