6 papers
Reachability in Fixed-Dimensional Continuous VASS
Michal Ajdarów, A. R. Balasubramanian, Łukasz Orlikowski
Vector Addition System with States (VASS) are a ubiquitous model of infinite-state systems consisting of a set of non-negative counters which can be incremented and decremented. It…
Taming Infinity one Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs
Michal Ajdarów, James C. A. Main, Petr Novotný +1
Markov decision processes (MDPs) are a canonical model to reason about decision making within a stochastic environment. We study a fundamental class of infinite MDPs: one-counter M…
Efficient Analysis of Polynomial Asymptotic Estimates for VASS MDPs
Michal Ajdarów
Markov decision process over vector addition system with states (VASS MDP) is a finite state model combining non-deterministic and probabilistic behavior, augmented with non-negati…
Asymptotic Complexity Estimates for Probabilistic Programs and their VASS Abstractions
Michal Ajdarów, Antonín Kučera
The standard approach to analyzing the asymptotic complexity of probabilistic programs is based on studying the asymptotic growth of certain expected values (such as the expected t…
Shielding in Resource-Constrained Goal POMDPs
Michal Ajdarów, Šimon Brlej, Petr Novotný
We consider partially observable Markov decision processes (POMDPs) modeling an agent that needs a supply of a certain resource (e.g., electricity stored in batteries) to operate c…
Deciding Polynomial Termination Complexity for VASS Programs
Michal Ajdarów, Antonín Kučera
We show that for every fixed , the problem whether the termination/counter complexity of a given demonic VASS is , , and is coNP-com…