Complexity theory with discrete ODEs

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

Recent Changes- Printable Version - Search:


  1. Olivier {Bournez}, {Dur and Arnaud }. A characterization of functions over the integers computable in polynomial time using discrete differential equations.
    Technical report Available on \url{https://arxiv.org/abs/2209.12168}. Submitted.
    (2022) (BibTeX)
  2. Mathieu Hemery and Fran{\c{c}}ois Fages. Algebraic Biochemistry: a Framework for Analog Online Computation in Cells.
    In {{CMSB'22}: Proceedings of the twentieth international conference on } # cmsb. sep. lnbi. springer.
    (2022) (URL) (BibTeX)
  3. Olivier Bournez. Programming with Ordinary Differential Equations: Some First Steps Towards a Programming Language.
    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) (DOI: 10.1007/978-3-031-08740-0\_4) (URL) (BibTeX)
  4. Manon Blanc and Olivier Bournez. A Characterization of Polynomial Time Computable Functions from the Integers to the Reals Using Discrete Ordinary Differential Equations.
    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) (DOI: 10.1007/978-3-031-13502-6\_4) (URL) (BibTeX)
  5. Julien Martinelli, Jeremy Grignard, Sylvain Soliman, Annabelle Ballesta and Fran{\c{c}}ois Fages. Reactmine: a search algorithm for inferring chemical reaction networks from time series data.
    Technical report, Inria working paper or preprint.
    (2022) (URL) (PDF) (BibTeX)
  6. Olivier Bournez , Riccardo Gozzi , Daniel Gra{\c c}a and Amaury Pouly. A continuous characterization of PSPACE using polynomial ordinary differential equations.
    (2022) (BibTeX)
  7. Julien Cervelle and Theo Grente. Constructing constrained cellular automata rules using multivariate polynomials.
    (2022) (BibTeX)
  8. Olivier Bournez and Quentin Guilmant. Surreal fields stable under exponential and logarithmic functions.
    (2022) (BibTeX)
  9. Alexey Barsukov , Kaustav Bose and Bodhayan Roy. Maximum cut on interval graphs of interval count two is NP-complete.
    CoRR, abs/2203.06630.
    (2022) (DOI: 10.48550/arXiv.2203.06630) (URL) (BibTeX)
  10. Alin Bostan, Fr{\'e}d{\'e}ric Chyzak, Hadrien Notarantonio and Mohab Safey El Din. Algorithms for discrete differential equations of order 1.
    In Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation. Pages 101-110.
    (2022) (BibTeX)
  11. Mathieu Hemery , Fran{\c{c}}ois Fages and Sylvain Soliman. A Polynomialization Algorithm for Elementary Functions and ODEs, and their Compilation into Chemical Reaction Networks.
    In {CASC'21}: Computer Algebra in Scientific Computing, proceedings of short papers. sep.
    (2021) (URL) (BibTeX)
  12. Mathieu Hemery , Fran{\c{c}}ois Fages and Sylvain Soliman. Compiling Elementary Mathematical Functions into Finite Chemical Reaction Networks via a Polynomialization Algorithm for ODEs.
    In {{CMSB'21}: Proceedings of the nineteenth international conference on } # cmsb. sep. lnbi. springer.
    (2021) (DOI: 10.1007/978-3-030-85633-5_5) (URL) (BibTeX)
  13. Catarina Carvalho , Florent R. Madelaine , Barnaby Martin and Dmitriy Zhuk. The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation.
    CoRR, abs/2106.13154.
    (2021) (arXiv version) (BibTeX)
  14. Alexey Barsukov and Mamadou Moustapha Kant{\'{e}}. Generalisations of Matrix Partitions : Complexity and Obstructions.
    CoRR, abs/2107.13809.
    (2021) (arXiv version) (BibTeX)
  15. Alin Bostan, Mireille Bousquet-M{\'e}lou and Stephen Melczer. Counting walks with large steps in an orthant.
    Journal of the European Mathematical Society, 23(7):2221-2297.
    (2021) (BibTeX)
  16. Mathieu Hemery , Fran{\c{c}}ois Fages and Sylvain Soliman. On the Complexity of Quadratization for Polynomial Differential Equations.
    In {{CMSB'20}: Proceedings of the eighteenth international conference on } # cmsb. sep. lnbi. springer.
    (2020) (DOI: 10.1007/978-3-030-60327-4_7) (URL) (BibTeX)
  17. Alin Bostan and Antonio Jim{\'e}nez-Pastor. On the exponential generating function of labelled trees.
    Comptes Rendus. Math{\'e}matique, 358(9-10):1005-1009.
    (2020) (BibTeX)
  18. Antonio Jim{\'e}nez-Pastor, Alin Bostan, Fr{\'e}d{\'e}ric Chyzak and Pierre Lairez. The sage package comb\_walks for walks in the quarter plane.
    ACM Communications in Computer Algebra, 54(2):30-38.
    (2020) (BibTeX)
  19. Alin Bostan, Lucia Di Vizio and Kilian Raschel. Differential transcendence of Bell numbers and relatives: a Galois theoretic approach.
    arXiv preprint arXiv:2012.15292.
    (2020) (BibTeX)
  20. Elisabeth Degr, , Fran{\c{c}}ois Fages and Sylvain Soliman. Graphical Conditions for Rate Independence in Chemical Reaction Networks.
    In {{CMSB'20}: Proceedings of the eighteenth international conference on } # cmsb. sep. lnbi. springer.
    (2020) (DOI: 10.1007/978-3-030-60327-4_7) (URL) (BibTeX)
  21. Serge Grigorieff and Pierre Valarcher. Class of algorithms.
    work in progress.
  22. Julien Cervelle , Patrick Cegielski and Pierre Valarcher. A gap between linear and quadratic time complexity in system $T'_0$ \`a la G\"odel.
    work in progress.
  23. Alexey Barsukov and Florent Madelaine. Towards a dichotomy for guarded fragments below SNP and above MMSNP.
    In preparation.
  24. Olivier Bournez. Le Calcul Analogique.
    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