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

---

Parity and Streett Games with Costs

Nathanaël Fijalkow ; Martin Zimmermann.

We consider two-player games played on finite graphs equipped with costs on edges and introduce two winning conditions, cost-parity and cost-Streett, which require bounds on the cost between requests and their responses. Both conditions generalize the corresponding classical omega-regular conditions&nbsp;[&hellip;]

---

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

---