A Characterization of Polynomial Time Computable Functions from the Integers to the Reals Using Discrete Ordinary Differential Equations

Manon Blanc; Olivier Bournez

doi:10.1007/978-3-031-13502-6_4

A Characterization of Polynomial Time Computable Functions from the Integers to the Reals Using Discrete Ordinary Differential Equations

Manon Blanc
, Olivier Bournez

ENS Paris-Saclay

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

The class of functions from the integers to the integers computable in polynomial time has been recently characterized using discrete ordinary differential equations (ODE), also known as finite differences. Doing so, the fundamental role of linear (discrete) ODEs and classical ODE tools such as changes of variables to capture computability and complexity measures, or as a tool for programming was pointed out. In this article, we extend the approach to a characterization of functions from the integers to the reals computable in polynomial time in the sense of computable analysis. In particular, we provide a characterization of such functions in terms of the smallest class of functions that contains some basic functions, and that is closed by composition, linear length ODEs, and a natural effective limit schema.

Original language	English
Title of host publication	Machines, Computations, and Universality - 9th International Conference, MCU 2022, Proceedings
Editors	Jérôme Durand-Lose, György Vaszil
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	58-74
Number of pages	17
ISBN (Print)	9783031135019
DOIs	https://doi.org/10.1007/978-3-031-13502-6_4
Publication status	Published - 1 Jan 2022
Event	9th International Conference on Machines, Computations, and Universality, MCU 2022 - Debrecen, Hungary Duration: 31 Aug 2022 → 2 Sept 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13419 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Conference on Machines, Computations, and Universality, MCU 2022
Country/Territory	Hungary
City	Debrecen
Period	31/08/22 → 2/09/22

Access to Document

10.1007/978-3-031-13502-6_4

Cite this

Blanc, M., & Bournez, O. (2022). A Characterization of Polynomial Time Computable Functions from the Integers to the Reals Using Discrete Ordinary Differential Equations. In J. Durand-Lose, & G. Vaszil (Eds.), Machines, Computations, and Universality - 9th International Conference, MCU 2022, Proceedings (pp. 58-74). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13419 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-13502-6_4

Blanc, Manon ; Bournez, Olivier. / A Characterization of Polynomial Time Computable Functions from the Integers to the Reals Using Discrete Ordinary Differential Equations. Machines, Computations, and Universality - 9th International Conference, MCU 2022, Proceedings. editor / Jérôme Durand-Lose ; György Vaszil. Springer Science and Business Media Deutschland GmbH, 2022. pp. 58-74 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{156804f3020d4b74bef14e4bb4aa9c98,

title = "A Characterization of Polynomial Time Computable Functions from the Integers to the Reals Using Discrete Ordinary Differential Equations",

abstract = "The class of functions from the integers to the integers computable in polynomial time has been recently characterized using discrete ordinary differential equations (ODE), also known as finite differences. Doing so, the fundamental role of linear (discrete) ODEs and classical ODE tools such as changes of variables to capture computability and complexity measures, or as a tool for programming was pointed out. In this article, we extend the approach to a characterization of functions from the integers to the reals computable in polynomial time in the sense of computable analysis. In particular, we provide a characterization of such functions in terms of the smallest class of functions that contains some basic functions, and that is closed by composition, linear length ODEs, and a natural effective limit schema.",

author = "Manon Blanc and Olivier Bournez",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 9th International Conference on Machines, Computations, and Universality, MCU 2022 ; Conference date: 31-08-2022 Through 02-09-2022",

year = "2022",

month = jan,

day = "1",

doi = "10.1007/978-3-031-13502-6\_4",

language = "English",

isbn = "9783031135019",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "58--74",

editor = "J{\'e}r{\^o}me Durand-Lose and Gy{\"o}rgy Vaszil",

booktitle = "Machines, Computations, and Universality - 9th International Conference, MCU 2022, Proceedings",

}

Blanc, M & Bournez, O 2022, A Characterization of Polynomial Time Computable Functions from the Integers to the Reals Using Discrete Ordinary Differential Equations. in J Durand-Lose & G Vaszil (eds), Machines, Computations, and Universality - 9th International Conference, MCU 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13419 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 58-74, 9th International Conference on Machines, Computations, and Universality, MCU 2022, Debrecen, Hungary, 31/08/22. https://doi.org/10.1007/978-3-031-13502-6_4

A Characterization of Polynomial Time Computable Functions from the Integers to the Reals Using Discrete Ordinary Differential Equations. / Blanc, Manon; Bournez, Olivier.
Machines, Computations, and Universality - 9th International Conference, MCU 2022, Proceedings. ed. / Jérôme Durand-Lose; György Vaszil. Springer Science and Business Media Deutschland GmbH, 2022. p. 58-74 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13419 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A Characterization of Polynomial Time Computable Functions from the Integers to the Reals Using Discrete Ordinary Differential Equations

AU - Blanc, Manon

AU - Bournez, Olivier

PY - 2022/1/1

Y1 - 2022/1/1

N2 - The class of functions from the integers to the integers computable in polynomial time has been recently characterized using discrete ordinary differential equations (ODE), also known as finite differences. Doing so, the fundamental role of linear (discrete) ODEs and classical ODE tools such as changes of variables to capture computability and complexity measures, or as a tool for programming was pointed out. In this article, we extend the approach to a characterization of functions from the integers to the reals computable in polynomial time in the sense of computable analysis. In particular, we provide a characterization of such functions in terms of the smallest class of functions that contains some basic functions, and that is closed by composition, linear length ODEs, and a natural effective limit schema.

AB - The class of functions from the integers to the integers computable in polynomial time has been recently characterized using discrete ordinary differential equations (ODE), also known as finite differences. Doing so, the fundamental role of linear (discrete) ODEs and classical ODE tools such as changes of variables to capture computability and complexity measures, or as a tool for programming was pointed out. In this article, we extend the approach to a characterization of functions from the integers to the reals computable in polynomial time in the sense of computable analysis. In particular, we provide a characterization of such functions in terms of the smallest class of functions that contains some basic functions, and that is closed by composition, linear length ODEs, and a natural effective limit schema.

UR - https://www.scopus.com/pages/publications/85135819027

U2 - 10.1007/978-3-031-13502-6_4

DO - 10.1007/978-3-031-13502-6_4

M3 - Conference contribution

AN - SCOPUS:85135819027

SN - 9783031135019

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 58

EP - 74

BT - Machines, Computations, and Universality - 9th International Conference, MCU 2022, Proceedings

A2 - Durand-Lose, Jérôme

A2 - Vaszil, György

PB - Springer Science and Business Media Deutschland GmbH

T2 - 9th International Conference on Machines, Computations, and Universality, MCU 2022

Y2 - 31 August 2022 through 2 September 2022

ER -

Blanc M, Bournez O. A Characterization of Polynomial Time Computable Functions from the Integers to the Reals Using Discrete Ordinary Differential Equations. In Durand-Lose J, Vaszil G, editors, Machines, Computations, and Universality - 9th International Conference, MCU 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 58-74. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-13502-6_4