License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.23
URN: urn:nbn:de:0030-drops-109670
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10967/
Go to the corresponding LIPIcs Volume Portal

Bournez, Olivier ; Durand, Arnaud

Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations

pdf-format:
LIPIcs-MFCS-2019-23.pdf (0.5 MB)

Abstract

This paper studies the expressive and computational power of discrete Ordinary Differential Equations (ODEs). It presents a new framework using discrete ODEs as a central tool for computation and algorithm design. We present the general theory of discrete ODEs for computation theory, we illustrate this with various examples of algorithms, and we provide several implicit characterizations of complexity and computability classes.
The proposed framework presents an original point of view on complexity and computation classes. It unifies several constructions that have been proposed for characterizing these classes including classical approaches in implicit complexity using restricted recursion schemes, as well as recent characterizations of computability and complexity by classes of continuous ordinary differential equations. It also helps understanding the relationships between analog computations and classical discrete models of computation theory.
At a more technical point of view, this paper points out the fundamental role of linear (discrete) ordinary differential equations and classical ODE tools such as changes of variables to capture computability and complexity measures, or as a tool for programming many algorithms.

BibTeX - Entry

@InProceedings{bournez_et_al:LIPIcs:2019:10967,
  author =	{Olivier Bournez and Arnaud Durand},
  title =	{{Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10967},
  URN =		{urn:nbn:de:0030-drops-109670},
  doi =		{10.4230/LIPIcs.MFCS.2019.23},
  annote =	{Keywords: Implicit complexity, discrete ordinary differential equations, recursion scheme}
}

Keywords: Implicit complexity, discrete ordinary differential equations, recursion scheme
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI