Search

• < Previous
• 1
• Next >

---

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 that the induced labelled Markov chains are trace-equivalent. We show that this problem is decidable in polynomial time if&nbsp;[&hellip;]

---

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;]

---

The Theory of Universal Graphs for Infinite Duration Games

Thomas Colcombet ; Nathanaël Fijalkow ; Paweł Gawrychowski ; Pierre Ohlmann.

We introduce the notion of universal graphs as a tool for constructing algorithms solving games of infinite duration such as parity games and mean payoff games. In the first part we develop the theory of universal graphs, with two goals: showing an equivalence and normalisation result between&nbsp;[&hellip;]

---