42 citations · 161 across the 23 of their papers we have counts for
8 papers · 1 filter
Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length (Journal version)
Olivier Bournez, Daniel S. Gracaa, Amaury Pouly
The outcomes of this paper are twofold. Implicit complexity. We provide an implicit characterization of polynomial time computation in terms of ordinary differential equations: we…
Computational complexity of solving polynomial differential equations over unbounded domains with non-rational coefficients
Amaury Pouly
In this note, we extend the result of \cite{PoulyG16} about the complexity of solving polynomial differential equations over unbounded domains to work with non-rational input. In o…
Model Checking Flat Freeze LTL on One-Counter Automata
Antonia Lechner, Richard Mayr, Joël Ouaknine +2
Freeze LTL is a temporal logic with registers that is suitable for specifying properties of data words. In this paper we study the model checking problem for Freeze LTL on one-coun…
On the Functions Generated by the General Purpose Analog Computer
Olivier Bournez, Daniel Graça, Amaury Pouly
We consider the General Purpose Analog Computer (GPAC), introduced by Claude Shannon in 1941 as a mathematical model of Differential Analysers, that is to say as a model of continu…
Computing with Polynomial Ordinary Differential Equations
Olivier Bournez, Daniel Graça, Amaury Pouly
In 1941, Claude Shannon introduced the General Purpose Analog Computer(GPAC) as a mathematical model of Differential Analysers, that is to say as a model of continuous-time analog…
Polynomial Time corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length
Olivier Bournez, Daniel S. Graça, Amaury Pouly
We provide an implicit characterization of polynomial time computation in terms of ordinary differential equations: we characterize the class of languages co…
On the complexity of bounded time and precision reachability for piecewise affine systems
Hugo Bazille, Olivier Bournez, Walid Gomaa +1
Reachability for piecewise affine systems is known to be undecidable, starting from dimension . In this paper we investigate the exact complexity of several decidable variants o…
Solvability of Matrix-Exponential Equations
Joël Ouaknine, Amaury Pouly, João Sousa-Pinto +1
We consider a continuous analogue of Babai et al.'s and Cai et al.'s problem of solving multiplicative matrix equations. Given square matrices , all…