42 citations · 161 across the 23 of their papers we have counts for
25 papers
Positivity of Second-Order Nearly Linearly Recurrent Sequences
Amaury Pouly, Mahsa Shirmohammadi, James Worrell
Nearly linear recurrences generalise linear recurrences and can be represented as special cases of both linear time-invariant systems in control theory and linear-constraint loops…
On Polynomial-Time Decidability of k-Negations Fragments of First-Order Theories
Christoph Haase, Alessio Mansutti, Amaury Pouly
This paper introduces a generic framework that provides sufficient conditions for guaranteeing polynomial-time decidability of fixed-negation fragments of first-order theories that…
The Membership Problem for Hypergeometric Sequences with Rational Parameters
Klara Nosan, Amaury Pouly, Mahsa Shirmohammadi +1
We investigate the Membership Problem for hypergeometric sequences: given a hypergeometric sequence of rational numbers and a target $t \in \math…
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…
On the Decidability of Reachability in Continuous Time Linear Time-Invariant Systems
Mohan Dantam, Amaury Pouly
We consider the decidability of state-to-state reachability in linear time-invariant control systems over continuous time. We analyse this problem with respect to the allowable con…
On the Monniaux Problem in Abstract Interpretation
Nathanaël Fijalkow, Engel Lefaucheux, Pierre Ohlmann +3
The Monniaux Problem in abstract interpretation asks, roughly speaking, whether the following question is decidable: given a program , a safety (\emph{e.g.}, non-reachability) s…
Algebraic Invariants for Linear Hybrid Automata
Rupak Majumdar, Joël Ouaknine, Amaury Pouly +1
We exhibit an algorithm to compute the strongest algebraic (or polynomial) invariants that hold at each location of a given unguarded linear hybrid automaton (i.e., a hybrid automa…
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…
On the Decidability of Reachability in Linear Time-Invariant Systems
Nathanaël Fijalkow, Joël Ouaknine, Amaury Pouly +2
We consider the decidability of state-to-state reachability in linear time-invariant control systems over discrete time. We analyse this problem with respect to the allowable contr…
Polynomial Invariants for Affine Programs
Ehud Hrushovski, Joël Ouaknine, Amaury Pouly +1
We exhibit an algorithm to compute the strongest polynomial (or algebraic) invariants that hold at each location of a given affine program (i.e., a program having only non-determin…
Explicit Error Bounds for Carleman Linearization
Marcelo Forets, Amaury Pouly
We revisit the method of Carleman linearization for systems of ordinary differential equations with polynomial right-hand sides. This transformation provides an approximate lineari…
A Universal Ordinary Differential Equation
Olivier Bournez, Amaury Pouly
An astonishing fact was established by Lee A. Rubel (1981): there exists a fixed non-trivial fourth-order polynomial differential algebraic equation (DAE) such that for any positiv…
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…
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…
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…