Search

• < Previous
• 1
• Next >

---

Deciding the value 1 problem for probabilistic leaktight automata

Nathanaël Fijalkow ; Hugo Gimbert ; Edon Kelmendi ; Youssouf Oualhadj.

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 to 1? This problem was proved undecidable recently; to overcome this, several classes of probabilistic automata of&nbsp;[&hellip;]

---

Life is Random, Time is Not: Markov Decision Processes with Window Objectives

Thomas Brihaye ; Florent Delgrange ; Youssouf Oualhadj ; Mickael Randour.

The window mechanism was introduced by Chatterjee et al. to strengthen classical game objectives with time bounds. It permits to synthesize system controllers that exhibit acceptable behaviors within a configurable time frame, all along their infinite execution, in contrast to the traditional&nbsp;[&hellip;]

---

Games Where You Can Play Optimally with Arena-Independent Finite Memory

Patricia Bouyer ; Stéphane Le Roux ; Youssouf Oualhadj ; Mickael Randour ; Pierre Vandenhove.

For decades, two-player (antagonistic) games on graphs have been a framework of choice for many important problems in theoretical computer science. A notorious one is controller synthesis, which can be rephrased through the game-theoretic metaphor as the quest for a winning strategy of the system in&nbsp;[&hellip;]

---

Arena-Independent Finite-Memory Determinacy in Stochastic Games

Patricia Bouyer ; Youssouf Oualhadj ; Mickael Randour ; Pierre Vandenhove.

We study stochastic zero-sum games on graphs, which are prevalent tools to model decision-making in presence of an antagonistic opponent in a random environment. In this setting, an important question is the one of strategy complexity: what kinds of strategies are sufficient or required to play&nbsp;[&hellip;]

---