View in EDS

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

Saved in:
Bibliographic Details
Title: A Characterization of Polynomial Time Computable Functions from the Integers to the Reals Using Discrete Ordinary Differential Equations.
Authors: Blanc, Manon1,2 (AUTHOR) manon.blanc@lix.polytechnique.fr, Bournez, Olivier1 (AUTHOR) olivier.bournez@lix.polytechnique.fr
Source: International Journal of Foundations of Computer Science. Nov2025, Vol. 36 Issue 7, p989-1016. 28p.
Subjects: Computable functions, Computable analysis, Ordinary differential equations, Linear differential equations, Polynomial time algorithms, Mathematical functions, Computational complexity
Abstract: In a recent article, the class of functions from the integers to the integers computable in polynomial time has been characterized using discrete ordinary differential equations (ODE), also known as finite differences. Doing so, the authors pointed out 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. 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. [ABSTRACT FROM AUTHOR]
Copyright of International Journal of Foundations of Computer Science is the property of World Scientific Publishing Company and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 189134534
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: A Characterization of Polynomial Time Computable Functions from the Integers to the Reals Using Discrete Ordinary Differential Equations.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Blanc%2C+Manon%22">Blanc, Manon</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<i> manon.blanc@lix.polytechnique.fr</i><br /><searchLink fieldCode="AR" term="%22Bournez%2C+Olivier%22">Bournez, Olivier</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> olivier.bournez@lix.polytechnique.fr</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22International+Journal+of+Foundations+of+Computer+Science%22">International Journal of Foundations of Computer Science</searchLink>. Nov2025, Vol. 36 Issue 7, p989-1016. 28p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Computable+functions%22">Computable functions</searchLink><br /><searchLink fieldCode="DE" term="%22Computable+analysis%22">Computable analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Ordinary+differential+equations%22">Ordinary differential equations</searchLink><br /><searchLink fieldCode="DE" term="%22Linear+differential+equations%22">Linear differential equations</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomial+time+algorithms%22">Polynomial time algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+functions%22">Mathematical functions</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: In a recent article, the class of functions from the integers to the integers computable in polynomial time has been characterized using discrete ordinary differential equations (ODE), also known as finite differences. Doing so, the authors pointed out 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. 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. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of International Journal of Foundations of Computer Science is the property of World Scientific Publishing Company and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=189134534
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1142/S0129054124470014
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 28
        StartPage: 989
    Subjects:
      – SubjectFull: Computable functions
        Type: general
      – SubjectFull: Computable analysis
        Type: general
      – SubjectFull: Ordinary differential equations
        Type: general
      – SubjectFull: Linear differential equations
        Type: general
      – SubjectFull: Polynomial time algorithms
        Type: general
      – SubjectFull: Mathematical functions
        Type: general
      – SubjectFull: Computational complexity
        Type: general
    Titles:
      – TitleFull: A Characterization of Polynomial Time Computable Functions from the Integers to the Reals Using Discrete Ordinary Differential Equations.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Blanc, Manon
      – PersonEntity:
          Name:
            NameFull: Bournez, Olivier
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 11
              Text: Nov2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 01290541
          Numbering:
            – Type: volume
              Value: 36
            – Type: issue
              Value: 7
          Titles:
            – TitleFull: International Journal of Foundations of Computer Science
              Type: main
ResultId 1