Author name cluster

Edon Kelmendi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

1 author row

Highlights Conference 2024 Conference Abstract

Multiple Reachability for Linear Dynamical Systems

Edon Kelmendi

A linear dynamical system is a pair: a point $\mathbf x \in\mathbb Q^d$, a $d\times d$ matrix $M$, where the positive integer $d$ is called the ambient dimension. The orbit of the system is defined as the infinite sequence of points in $\mathbb Q^d$ $$ \mathbf x, M\mathbf x, M^2 \mathbf x, \ldots $$ that we obtain by repeatedly applying the linear function which is given in the form of the matrix $M$. We are interested in designing algorithms for deciding whether the orbit of a given system intersects some given target. The latter may be a hyperplane (i. e. the set of points that is a solution to a linear equation), a halfspace (i. e. the set of points that is a solution to a linear inequality), or a more general set of points given via polynomial (in)equalities. It is still unknown whether there exist a procedure for deciding even hyperplane reachability. The short talk will be based on a recent paper, joint work with Toghrul Karimov, Joel Ouaknine, and James Worrell. In that paper we considered the slightly more general question of multiple reachability, namely not merely reaching the target, but reaching it at least $k$ times; where $k$ is given as input. This problem is surprisingly difficult. We prove that it is undecidable in ambient dimension $d=10$, even when $k$ is fixed to $k=9$. The main theorem however is about solving this problem on the plane, $d=2$, which seems to be the only reasonable subclass to treat. For this we use some new techniques based on intersections of varieties with all algebraic subgroups of certain dimension. Notably, the main tool of this area, Baker's lower bounds on linear combinations of logarithms, does not seem to work. In the talk I will present the problem and sketch the solution in case $d=2$, using those new techniques. The problem and solution lend themselves to a nice visual illustration which is appropriate for a short talk.

Details

Highlights Conference 2022 Conference Abstract

Computing the Density of the Positivity Set for Linear Recurrence Sequences

Edon Kelmendi

The set of indices that correspond to the positivie entries of a sequence of numbers is called its positivity set. In this talk, we present a couple of results regarding the density of the positivity set of a given linear recurrence sequence. We show that one can compute this density to arbitrary precision, and decide whether it is equal to 1.

Details

Highlights Conference 2020 Conference Abstract

Asymptotic omega-Regular Properties of Linear Recurrence Sequences

Edon Kelmendi

We consider the sign descriptions of linear recurrence sequences. This is the infinite word that results by replacing positive elements with the letter +, negative elements with the letter −, and leaving 0 as is. We prove that it is decidable whether the sign description of a simple linear recurrence sequence has a given prefix-independent omega-regular property. This is achieved by showing that such sequences are almost-periodic. To complement this result, we prove that sign descriptions of general linear recurrence sequences need not be almost-periodic.

Details

Highlights Conference 2018 Conference Abstract

Expressing Unboudedness in MSO + nabla

Edon Kelmendi

ABSTRACT. We consider an extension of MSO on the infinite binary tree. The extensions adds a probabilistic path quantifier that says that with probability 1 a branch is chosen such that the formula holds in this branch. The probability measure that is used is the coin-flipping measure. This added quantifier properly extends MSO, but we do not know whether this logic has decidable satisfiability problem. Here we make progress into showing that the satisfiability problem is undecidable by proving that the logic is powerful enough to be able to express unboundedness of counters.

Details

Highlights Conference 2016 Conference Abstract

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 strategies whereas the minimizer is perfectly informed. We ask the question of whether the game has maxmin, in other words we ask whether for all 0" title="Rendered by QuickLaTeX. com" height="12" width="40" style="vertical-align: 0px" /> there exists a deterministic strategy for the (blind) maximizer such that against all the strategies of the minimizer, it is possible to reach the set of final states with probability larger than. This problem is undecidable in general, but we define a class of games, called leaktight half-blind games where the problem becomes decidable. We also show that mixed strategies in general are stronger for both players and that optimal strategies for the minimizer might require infinite-memory.

Details

Highlights Conference 2014 Conference Abstract

Two-Player Perfect-Information Shift-Invariant Submixing Stochastic Games are Half-Positional

Edon Kelmendi

The object of study are two-player stochastic games with perfect information and infinite duration, the property of these games that we study is positionality, namely the question: when can one player play optimally without memory and without a source of random bits? We give a sufficient condition on the payoff function to achieve half-positionality (Player 1 can play optimally with a positional strategy). The condition is that the payoff function should be shift-invariant and submixing. In [2] it is shown that one-player stochastic games with shift-invariant and submixing payoff functions are positional, and in [3] the half-positionality of deterministic two-player games with shift-invariant and submixing payoff functions is demonstrated. We extend these two results to half-positionality of two -player stochastic games. In the way of proving our main result we also show that for all ε > 0, given that the payoff function is shift-invariant, both players have ε -subgame perfect strategies, i. e. strategies that are ε -optimal not only from the beginning of the game but also for any finite play already played. The submixing and shift-invariant payoff functions form a class that is large enough to have the half-positionality of games equipped the following well-known payoff functions follow easily from our main result: mean-payoff: each state is labeled by some reward, and the payoff function computes the average accumulated reward. discounted payoff: each state is labeled by some immediate reward and a discount factor and the payoff function measures the long-term performance with an inflation rate parity condition: states are labeled by integers, Player 1 wins if the largest integer seen infinitely often is odd limsup (liminf) payoff: states are labeled by rewards, and the payoff function computes the limsup (liminf) of the rewards. The (half)-positionality of games equipped with the payoff functions above have been shown by numerous authors, using different techniques. A unified proof is a consequence of our main result. Given a payoff function such that every one-player stochastic game equipped with it is positional does not imply that the two-player game is half-positional. We provide an example that proves this. Gimbert, Hugo, and Edon Kelmendi. "Two-Player Perfect-Information Shift-Invariant Submixing Stochastic Games Are Half-Positional. " arXiv preprint arXiv: 1401. 6575 (2014). Gimbert, Hugo. "Pure stationary optimal strategies in Markov decision processes. " STACS 2007. Springer Berlin Heidelberg, 2007. 200-211. Kopczyński, Eryk. "Half-positional determinacy of infinite games. " Automata, Languages and Programming. Springer Berlin Heidelberg, 2006. 336-347.

PDF Details