28 citations · 43 across the 11 of their papers we have counts for
14 papers
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…
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…
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…
Computing the Density of the Positivity Set for Linear Recurrence Sequences
Edon Kelmendi
The set of indices that correspond to the positive entries of a sequence of numbers is called its positivity set. In this paper, we study the density of the positivity set of a giv…
Deciding -Regular Properties on Linear Recurrence Sequences
Shaull Almagor, Toghrul Karimov, Edon Kelmendi +2
We consider the problem of deciding -regular properties on infinite traces produced by linear loops. Here we think of a given loop as producing a single infinite trace that enco…
Invariants for Continuous Linear Dynamical Systems
Shaull Almagor, Edon Kelmendi, Joël Ouaknine +1
Continuous linear dynamical systems are used extensively in mathematics, computer science, physics, and engineering to model the evolution of a system over time. A central techniqu…
Extensions of -Regular Languages
Mikołaj Bojańczyk, Edon Kelmendi, Rafał Stefański +1
We consider extensions of monadic second order logic over -words, which are obtained by adding one language that is not -regular. We show that if the added language has a…
MSO+nabla is undecidable
Mikołaj Bojańczyk, Edon Kelmendi, Michał Skrzypczak
This paper is about an extension of monadic second-order logic over the full binary tree, which has a quantifier saying ``almost surely a branch π \in {0, 1}^w satisfies a formula…
Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm
Edon Kelmendi, Julia Krämer, Jan Kretinsky +1
Simple stochastic games can be solved by value iteration (VI), which yields a sequence of under-approximations of the value of the game. This sequence is guaranteed to converge to…
Emptiness of zero automata is decidable
Mikolaj Bojańczyk, Hugo Gimbert, Edon Kelmendi
Zero automata are a probabilistic extension of parity automata on infinite trees. The satisfiability of a certain probabilistic variant of mso, called tmso + zero, reduces to the e…
Deciding Maxmin Reachability in Half-Blind Stochastic Games
Edon Kelmendi, Hugo Gimbert
Two-player, turn-based, stochastic games with reachability conditions are considered, where the maximizer has no information (he is blind) and is restricted to deterministic strate…
Deciding the value 1 problem for probabilistic leaktight automata
Nathanaël Fijalkow, Hugo Gimbert, Edon Kelmendi +1
The value 1 problem is a decision problem for probabilistic automata over finite words: given a probabilistic automaton, are there words accepted with probability arbitrarily close…
Submixing and Shift-invariant Stochastic Games
Hugo Gimbert, Edon Kelmendi
We consider zero-sum stochastic games with perfect information and finitely many states and actions. The payoff is computed by a function which associates to each infinite sequence…
Deciding the Value 1 Problem of Probabilistic Leaktight Automata
Nathanaël Fijalkow, Hugo Gimbert, Youssouf Oualhadj
The value 1 problem is a decision problem for probabilistic automata over finite words: given a probabilistic automaton A, are there words accepted by A with probability arbitraril…