Repository logo
 
Publication

Computing with polynomial ordinary differential equations

2016-10Journal article Restricted access
Simple item page
dc.contributor.authorBournez, Olivier
dc.contributor.authorGraça, Daniel
dc.contributor.authorPouly, Amaury
dc.date.accessioned2017-04-07T15:55:57Z
dc.date.available2017-04-07T15:55:57Z
dc.date.issued2016-10
dc.description.abstractIn 1941, Claude Shannon introduced the General Purpose Analog Computer (GPAC) as a mathematical model of Differential Analysers, that is to say as a model of continuous-time analog (mechanical, and later on electronic) machines of that time.Following Shannon's arguments, functions generated by the GPAC must satisfy a polynomial differential algebraic equation (DAE). As it is known that some computable functions like Euler's Gamma(x) = integral(infinity)(0) t(x-1)e(-t) dt or Riemann's Zeta function zeta(x) = Sigma(infinity)(k=0)k(1/x), do not satisfy any polynomial DAE, this argument has often been used to demonstrate in the past that the GPAC is less powerful than digital computation.It was proved in Bournez et al. (2007), that if a more modern notion of computation is considered, i.e. in particular if computability is not restricted to real-time generation of functions, the GPAC is actually equivalent to Turing machines.Our purpose is first to discuss the robustness of the notion of computation involved in Bournez et al. (2007), by establishing that many natural variants of the notion of computation from this paper lead to the same computability result.Second, to go from these computability results towards considerations about (time) complexity: we explore several natural variants for measuring time space complexity of a computation.Quite surprisingly, whereas defining a robust time complexity for general continuous time systems is a well known open problem, we prove that all variants are actually equivalent even at the complexity level. As a consequence, it seems that a robust and well defined notion of time complexity exists for the GPAC, or equivalently for computations by polynomial ordinary differential equations.Another side effect of our proof is also that we show in some way that polynomial ordinary differential equations can actually be used as a kind of programming model, and that there is a rather nice and robust notion of ordinary differential equation (ODE) programming. (C) 2016 Published by Elsevier Inc.
dc.identifier.doi10.1016/j.jco.2016.05.002
dc.identifier.issn0885-064X
dc.identifier.otherAUT: DGR01772;
dc.identifier.urihttp://hdl.handle.net/10400.1/9271
dc.language.isoeng
dc.peerreviewedyes
dc.relationInstituto de Telecomunicações
dc.relation.isbasedonWOS:000381529500005
dc.titleComputing with polynomial ordinary differential equations
dc.typejournal article
dspace.entity.typePublication
oaire.awardTitleInstituto de Telecomunicações
oaire.awardURIinfo:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UID%2FEEA%2F50008%2F2013/PT
oaire.citation.endPage140
oaire.citation.startPage106
oaire.citation.titleJournal of Complexity
oaire.citation.volume36
oaire.fundingStream6817 - DCRRNI ID
person.familyNameGraça
person.givenNameDaniel
person.identifier.ciencia-id2D11-56DE-3F11
person.identifier.orcid0000-0002-0330-833X
person.identifier.ridD-2335-2011
person.identifier.scopus-author-id8882791800
project.funder.identifierhttp://doi.org/10.13039/501100001871
project.funder.nameFundação para a Ciência e a Tecnologia
rcaap.rightsrestrictedAccess
rcaap.typearticle
relation.isAuthorOfPublicationba0c1461-5d2d-4f06-b648-df4a1a505bdf
relation.isAuthorOfPublication.latestForDiscoveryba0c1461-5d2d-4f06-b648-df4a1a505bdf
relation.isProjectOfPublicationa9e89a6f-83c2-40cc-b146-7417405a213c
relation.isProjectOfPublication.latestForDiscoverya9e89a6f-83c2-40cc-b146-7417405a213c

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
handle9271.pdf
Size:
655.36 KB
Format:
Adobe Portable Document Format
Download

Collections

FCT2-Artigos (em revistas ou actas indexadas)