113 citations · 260 across the 57 of their papers we have counts for
6 papers · 1 filter
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…
Sequential Relational Decomposition
Dror Fried, Axel Legay, Joël Ouaknine +1
The concept of decomposition in computer science and engineering is considered a fundamental component of computational thinking and is prevalent in design of algorithms, software…
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…
On Reachability Problems for Low-Dimensional Matrix Semigroups
Thomas Colcombet, Joël Ouaknine, Pavel Semukhin +1
We consider the Membership and the Half-Space Reachability problems for matrices in dimensions two and three. Our first main result is that the Membership Problem is decidable for…
Termination of Linear Loops over the Integers
Mehran Hosseini, Joël Ouaknine, James Worrell
We consider the problem of deciding termination of single-path while loops with integer variables, affine updates, and affine guard conditions. The question is whether such a loop…
The Semialgebraic Orbit Problem
Shaull Almagor, Joël Oukanine, James Worrell
The Semialgebraic Orbit Problem is a fundamental reachability question that arises in the analysis of discrete-time linear dynamical systems such as automata, Markov chains, recurr…