4 citations · 20 across the 27 of their papers we have counts for
13 papers · 1 filter
Memoryless Strategies in Stochastic Reachability Games
Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi +1
We study concurrent stochastic reachability games played on finite graphs. Two players, Max and Min, seek respectively to maximize and minimize the probability of reaching a set of…
On Learning Polynomial Recursive Programs
Alex Buna-Marginean, Vincent Cheval, Mahsa Shirmohammadi +1
We introduce the class of P-finite automata. These are a generalisation of weighted automata, in which the weights of transitions can depend polynomially on the length of the input…
The Membership Problem for Hypergeometric Sequences with Quadratic Parameters
George Kenison, Klara Nosan, Mahsa Shirmohammadi +1
Hypergeometric sequences are rational-valued sequences that satisfy first-order linear recurrence relations with polynomial coefficients; that is, a hypergeometric sequence $\langl…
The Membership Problem for Hypergeometric Sequences with Rational Parameters
Klara Nosan, Amaury Pouly, Mahsa Shirmohammadi +1
We investigate the Membership Problem for hypergeometric sequences: given a hypergeometric sequence of rational numbers and a target $t \in \math…
Strategy Complexity of Parity Objectives in Countable MDPs
Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi +1
We study countably infinite MDPs with parity objectives. Unlike in finite MDPs, optimal strategies need not exist, and may require infinite memory if they do. We provide a complete…
Controlling a Random Population is EXPTIME-hard
Corto Mascle, Mahsa Shirmohammadi, Patrick Totzke
Bertrand et al. [1] (LMCS 2019) describe two-player zero-sum games in which one player tries to achieve a reachability objective in games (on the same finite arena) simultaneou…
Coverability in 1-VASS with Disequality Tests
Shaull Almagor, Nathann Cohen, Guillermo A. Pérez +2
We study a class of reachability problems in weighted graphs with constraints on the accumulated weight of paths. The problems we study can equivalently be formulated in the model…
Costs and Rewards in Priced Timed Automata
Martin Fränzle, Mahsa Shirmohammadi, Mani Swaminathan +1
We consider Pareto analysis of reachable states of multi-priced timed automata (MPTA): timed automata equipped with multiple observers that keep track of costs (to be minimised) an…
Parity Objectives in Countable MDPs
Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi +1
We study countably infinite MDPs with parity objectives, and special cases with a bounded number of colors in the Mostowski hierarchy (including reachability, safety, Buchi and co-…
Revisiting Reachability in Timed Automata
Karin Quaas, Mahsa Shirmohammadi, James Worrell
We revisit a fundamental result in real-time verification, namely that the binary reachability relation between configurations of a given timed automaton is definable in linear ari…
Trace Refinement in Labelled Markov Decision Processes
Nathanaël Fijalkow, Stefan Kiefer, Mahsa Shirmohammadi
Given two labelled Markov decision processes (MDPs), the trace-refinement problem asks whether for all strategies of the first MDP there exists a strategy of the second MDP such th…
Robust Synchronization in Markov Decision Processes
Laurent Doyen, Thierry Massart, Mahsa Shirmohammadi
We consider synchronizing properties of Markov decision processes (MDP), viewed as generators of sequences of probability distributions over states. A probability distribution is p…
Synchronizing Objectives for Markov Decision Processes
Laurent Doyen, Thierry Massart, Mahsa Shirmohammadi
We introduce synchronizing objectives for Markov decision processes (MDP). Intuitively, a synchronizing objective requires that eventually, at every step there is a state which con…