113 citations · 260 across the 57 of their papers we have counts for
71 papers
On Periodic and Aperiodic Optimal Strategies in Solvency Games
Quentin Guilmant, Florian Luca, Richard Mayr +2
Solvency games are a gambling problem on infinite-state Markov decision processes in which the state represents an investor's fortune. In every round, the invest…
Conjectural Decidability of the Skolem Problem
Florian Luca, Joël Ouaknine, James Worrell
The Skolem Problem asks to determine whether a given integer linear recurrence sequence (LRS) has a zero term. This problem, whose decidability has been open for many decades, aris…
On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic
Piotr Bacik, Joris Nieuwveld, Joël Ouaknine +3
We consider expansions of Presburger arithmetic with families of monadic polynomial predicates. (Examples of such predicates are the set of perfect squares, or the set of integers…
Termination Analysis of Linear-Constraint Programs
Amir M. Ben-Amram, Samir Genaim, Joël Ouaknine +1
This paper provides an overview of techniques in termination analysis for programs with numerical variables and transitions defined by linear constraints. This subarea of program a…
On the Complexity of the Skolem Problem at Low Orders
Piotr Bacik, Joël Ouaknine, James Worrell
The Skolem Problem asks to determine whether a given linear recurrence sequence (LRS) over the integers has a zero term, that is, whether there e…
(Un)Decidability of Two-Clock Weighted Timed Games
Quentin Guilmant, Joël Ouaknine, Isa Vialard +1
The Value Problem for weighted timed games consists in determining, given a two-player weighted timed game with a reachability objective and a rational threshold, whether or not th…
Computing transcendence and linear relations of 1-periods
Emre Can Sertöz, Joël Ouaknine, James Worrell
A 1-period is a complex number given by the integral of a univariate algebraic function, where all data involved -- the integrand and the domain of integration -- are defined over…
Transcendence of Hecke-Mahler Series
Florian Luca, Joel Ouaknine, James Worrell
We prove transcendence of the Hecke-Mahler series , where is a non-constant polynomial is a real numbe…
Linear dynamical systems with continuous weight functions
Rajab Aghamov, Christel Baier, Toghrul Karimov +2
In discrete-time linear dynamical systems (LDSs), a linear map is repeatedly applied to an initial vector yielding a sequence of vectors called the orbit of the system. A weight fu…
Transcendence for Pisot Morphic Words over an Algebraic Base
Pavol Kebis, Florian Luca, Joel Ouaknine +2
It is known that for a uniform morphic sequence and an algebraic number such that , the number $[\![\boldsymbol{u} ]\!]…
The 2-Dimensional Constraint Loop Problem is Decidable
Quentin Guilmant, Engel Lefaucheux, Joël Ouaknine +1
A linear constraint loop is specified by a system of linear inequalities that define the relation between the values of the program variables before and after a single execution of…
Multiple Reachability in Linear Dynamical Systems
Toghrul Karimov, Edon Kelmendi, Joël Ouaknine +1
We consider reachability decision problems for linear dynamical systems: Given a linear map on , together with source and target sets, determine whether there is a p…
On the Counting Complexity of the Skolem Problem
Gorav Jindal, Joël Ouaknine
The Skolem Problem asks, given an integer linear recurrence sequence (LRS), to determine whether the sequence contains a zero term or not. Its decidability is a longstanding open p…
Twisted rational zeros of linear recurrence sequences
Yuri Bilu, Florian Luca, Joris Nieuwveld +2
We introduce the notion of a twisted rational zero of a non-degenerate linear recurrence sequence (LRS). We show that any non-degenerate LRS has only finitely many such twisted rat…
Transcendence of Sturmian Numbers over an Algebraic Base
Florian Luca, Joel Ouaknine, James Worrell
We consider numbers of the form for a Sturmian sequence over a binary alp…
Skolem Meets Bateman-Horn
Florian Luca, James Maynard, Armand Noubissie +2
The Skolem Problem asks to determine whether a given integer linear recurrence sequence has a zero term. This problem arises across a wide range of topics in computer science, incl…
Reachability in Injective Piecewise Affine Maps
Faraz Ghahremani, Edon Kelmendi, Joël Ouaknine
One of the most basic, longstanding open problems in the theory of dynamical systems is whether reachability is decidable for one-dimensional piecewise affine maps with two interva…
Model Checking Linear Dynamical Systems under Floating-point Rounding
Engel Lefaucheux, Joël Ouaknine, David Purser +1
We consider linear dynamical systems under floating-point rounding. In these systems, a matrix is repeatedly applied to a vector, but the numbers are rounded into floating-point re…
On the -adic zeros of the Tribonacci sequence
Yuri Bilu, Florian Luca, Joris Nieuwveld +2
In this paper, we refute some conjectures of Marques and Lengyel concerning the -adic valuations of members of the Tribonacci sequence.
Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set
Julian D'Costa, Engel Lefaucheux, Eike Neumann +2
We study the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets. We establish a uniform upper bound on the number of iterations it takes for…
What's Decidable about Discrete Linear Dynamical Systems?
Toghrul Karimov, Edon Kelmendi, Joël Ouaknine +1
We survey the state of the art on the algorithmic analysis of discrete linear dynamical systems, focussing in particular on reachability, model-checking, and invariant-generation q…
The Pseudo-Reachability Problem for Diagonalisable Linear Dynamical Systems
Julian D'Costa, Toghrul Karimov, Rupak Majumdar +3
We study fundamental reachability problems on pseudo-orbits of linear dynamical systems. Pseudo-orbits can be viewed as a model of computation with limited precision and pseudo-rea…
On the transcendence of a series related to Sturmian words
Florian Luca, Joël Ouaknine, James Worrell
Let be an algebraic number with and a finite set of algebraic numbers. We study the transcendence of numbers of the form $\sum_{n=0}^\infty \frac{a_n}{b^n…
On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets
Julian D'Costa, Engel Lefaucheux, Eike Neumann +2
We study the computational complexity of the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets, or equivalently the Termination Problem for…