113 citations · 260 across the 57 of their papers we have counts for
6 papers · 1 filter
Effective Divergence Analysis for Linear Recurrence Sequences
Shaull Almagor, Brynmor Chapman, Mehran Hosseini +2
We study the growth behaviour of rational linear recurrence sequences. We show that for low-order sequences, divergence is decidable in polynomial time. We also exhibit a polynomia…
Convex Language Semantics for Nondeterministic Probabilistic Automata
Gerco van Heerdt, Justin Hsu, Joël Ouaknine +1
We explore language semantics for automata combining probabilistic and nondeterministic behavior. We first show that there are precisely two natural semantics for probabilistic aut…
On the Expressiveness and Monitoring of Metric Temporal Logic
Hsi-Ming Ho, Joël Ouaknine, James Worrell
It is known that Metric Temporal Logic (MTL) is strictly less expressive than the Monadic First-Order Logic of Order and Metric (FO[<, +1]) when interpreted over timed words; this…
O-Minimal Invariants for Discrete-Time Dynamical Systems
Shaull Almagor, Dmitry Chistikov, Joël Ouaknine +1
Termination analysis of linear loops plays a key rôle in several areas of computer science, including program verification and abstract interpretation. Already for the simplest var…
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…