3 papers
cs.CC2024
The complexity of computing in continuous time: space complexity is precision
Manon Blanc, Olivier Bournez
Models of computations over the integers are equivalent from a computability and complexity theory point of view by the Church-Turing thesis. It is not possible to unify discrete-t…
cs.DM2024
The domino problem is decidable for robust tilesets
Nathalie Aubrun, Manon Blanc, Olivier Bournez
One of the most fundamental problems in tiling theory is the domino problem: given a set of tiles and tiling rules, decide if there exists a way to tile the plane using copies of t…
cs.CC2022
Polynomial time computable functions over the reals characterized using discrete ordinary differential equations
Manon Blanc, Olivier Bournez
The class of functions from the integers to the integers computable in polynomial time has been characterized recently using discrete ordinary differential equations (ODE), also kn…