42 citations · 161 across the 23 of their papers we have counts for
12 papers · 1 filter
On the Computation of the Zariski Closure of Finitely Generated Groups of Matrices
Klara Nosan, Amaury Pouly, Sylvain Schmitz +2
We investigate the complexity of computing the Zariski closure of a finitely generated group of matrices. The Zariski closure was previously shown to be computable by Derksen, Jean…
Reachability in Dynamical Systems with Rounding
Christel Baier, Florian Funke, Simon Jantsch +6
We consider reachability in dynamical systems with discrete linear updates, but with fixed digital precision, i.e., such that values of the system are rounded at each step. Given a…
A Survey on Analog Models of Computation
Olivier Bournez, Amaury Pouly
We present a survey on analog models of computations. Analog can be understood both as computing by analogy, or as working on the continuum. We consider both approaches, often inte…
Semialgebraic Invariant Synthesis for the Kannan-Lipton Orbit Problem
Nathanaël Fijalkow, Pierre Ohlmann, Joël Ouaknine +2
The \emph{Orbit Problem} consists of determining, given a linear transformation on , together with vectors and , whether the orbit of under repeated ap…
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…
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…
Computational complexity of solving polynomial differential equations over unbounded domains
Amaury Pouly, Daniel S. Graça
In this paper we investigate the computational complexity of solving ordinary differential equations (ODEs) over \emph{unbounded time domains}, where is a vec…
Turing machines can be efficiently simulated by the General Purpose Analog Computer
Amaury Pouly, Olivier Bournez, Daniel S. Graça
The Church-Turing thesis states that any sufficiently powerful computational model which captures the notion of algorithm is computationally equivalent to the Turing machine. This…