Complexity theory with discrete ODEs

Théorie de la complexité avec des équations différentielles discrètes

Recent Changes- Printable Version - Search:


A characterization of functions over the integers computable in polynomial time using discrete differential equations. (full details)
{Bournez}, Olivier , {Dur and }, Arnaud
Technical report. 2022. (BibTeX)
Algebraic Biochemistry: a Framework for Analog Online Computation in Cells. (full details)
Mathieu Hemery and Fran{\c{c}}ois Fages
In {{CMSB'22}: Proceedings of the twentieth international conference on } # cmsb. sep. lnbi. springer. 2022. (PUBLISHER URL) (BibTeX)
Programming with Ordinary Differential Equations: Some First Steps Towards a Programming Language. (full details)
Olivier Bournez
In Revolutions and Revelations in Computability - 18th Conference on Computability in Europe, CiE 2022, Swansea, UK, July 11-15, 2022, Proceedings. (Ulrich Berger and Johanna N. Y. Franklin and Florin Manea and Arno Pauly, Eds.) Volume 13359 of Lecture Notes in Computer Science. Springer, pages 39-51. 2022. (PUBLISHER URL) (BibTeX)
A Characterization of Polynomial Time Computable Functions from the Integers to the Reals Using Discrete Ordinary Differential Equations. (full details)
Manon Blanc and Olivier Bournez
In Machines, Computations, and Universality - 9th International Conference, {MCU} 2022, Debrecen, Hungary, August 31 - September 2, 2022, Proceedings. (J{\'{e}}r{\^{o}}me Durand{-}Lose and Gy{\"{o}}rgy Vaszil, Eds.) Volume 13419 of Lecture Notes in Computer Science. Springer, pages 58-74. 2022. (PUBLISHER URL) (BibTeX)
Reactmine: a search algorithm for inferring chemical reaction networks from time series data. (full details)
Martinelli, Julien , Grignard, Jeremy , Soliman, Sylvain , Ballesta, Annabelle and Fages, Fran{\c{c}}ois
Technical report, Inria. 2022. (PUBLISHER URL) (PDF) (BibTeX)
A continuous characterization of PSPACE using polynomial ordinary differential equations. (full details)
Olivier Bournez , Riccardo Gozzi , Daniel Gra{\c c}a and Amaury Pouly
. 2022. (BibTeX)
Constructing constrained cellular automata rules using multivariate polynomials. (full details)
Julien Cervelle and Theo Grente
. 2022. (BibTeX)
Surreal fields stable under exponential and logarithmic functions. (full details)
Olivier Bournez and Quentin Guilmant
. 2022. (BibTeX)
Maximum cut on interval graphs of interval count two is NP-complete. (full details)
Alexey Barsukov , Kaustav Bose and Bodhayan Roy
CoRR, abs/2203.06630. 2022. (PUBLISHER URL) (BibTeX)
Algorithms for discrete differential equations of order 1. (full details)
Bostan, Alin , Chyzak, Fr{\'e}d{\'e}ric , Notarantonio, Hadrien and Safey El Din, Mohab
In Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation. Pages 101-110. 2022. (BibTeX)
A Polynomialization Algorithm for Elementary Functions and ODEs, and their Compilation into Chemical Reaction Networks. (full details)
Mathieu Hemery , Fran{\c{c}}ois Fages and Sylvain Soliman
In {CASC'21}: Computer Algebra in Scientific Computing, proceedings of short papers. sep. 2021. (PUBLISHER URL) (BibTeX)
Compiling Elementary Mathematical Functions into Finite Chemical Reaction Networks via a Polynomialization Algorithm for ODEs. (full details)
Mathieu Hemery , Fran{\c{c}}ois Fages and Sylvain Soliman
In {{CMSB'21}: Proceedings of the nineteenth international conference on } # cmsb. sep. lnbi. springer. 2021. (PUBLISHER URL) (BibTeX)
The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation. (full details)
Catarina Carvalho , Florent R. Madelaine , Barnaby Martin and Dmitriy Zhuk
CoRR, abs/2106.13154. 2021. (PUBLISHER URL) (BibTeX)
Generalisations of Matrix Partitions : Complexity and Obstructions. (full details)
Alexey Barsukov and Mamadou Moustapha Kant{\'{e}}
CoRR, abs/2107.13809. 2021. (PUBLISHER URL) (BibTeX)
Counting walks with large steps in an orthant. (full details)
Bostan, Alin , Bousquet-M{\'e}lou, Mireille and Melczer, Stephen
Journal of the European Mathematical Society, 23(7):2221-2297. 2021. (BibTeX)
On the Complexity of Quadratization for Polynomial Differential Equations. (full details)
Mathieu Hemery , Fran{\c{c}}ois Fages and Sylvain Soliman
In {{CMSB'20}: Proceedings of the eighteenth international conference on } # cmsb. sep. lnbi. springer. 2020. (PUBLISHER URL) (BibTeX)
On the exponential generating function of labelled trees. (full details)
Bostan, Alin and Jim{\'e}nez-Pastor, Antonio
Comptes Rendus. Math{\'e}matique, 358(9-10):1005-1009. 2020. (BibTeX)
The sage package comb\_walks for walks in the quarter plane. (full details)
Jim{\'e}nez-Pastor, Antonio , Bostan, Alin , Chyzak, Fr{\'e}d{\'e}ric and Lairez, Pierre
ACM Communications in Computer Algebra, 54(2):30-38. 2020. (BibTeX)
Differential transcendence of Bell numbers and relatives: a Galois theoretic approach. (full details)
Bostan, Alin , Di Vizio, Lucia and Raschel, Kilian
arXiv preprint arXiv:2012.15292. 2020. (BibTeX)
Graphical Conditions for Rate Independence in Chemical Reaction Networks. (full details)
Elisabeth Degr, , Fran{\c{c}}ois Fages and Sylvain Soliman
In {{CMSB'20}: Proceedings of the eighteenth international conference on } # cmsb. sep. lnbi. springer. 2020. (PUBLISHER URL) (BibTeX)
Class of algorithms. (full details)
Serge Grigorieff and Pierre Valarcher
. (BibTeX)
A gap between linear and quadratic time complexity in system $T'_0$ \`a la G\"odel. (full details)
Julien Cervelle , Patrick Cegielski and Pierre Valarcher
. (BibTeX)
Towards a dichotomy for guarded fragments below SNP and above MMSNP. (full details)
Alexey Barsukov and Florent Madelaine
. (BibTeX)
Le Calcul Analogique. (full details)
Olivier Bournez
In Informatique Math{\'e}matique Une photographie en 2022. Cours donn{\'e}s {\`a} l'Ecole Jeunes Chercheurs en Informatique Math{\'e}matiques... (PDF) (BibTeX)
Edit - History - Print - Recent Changes - Search - Edit menu - Private
Page last modified on October 05, 2022, at 10:16 PM