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

---

Game Characterization of Probabilistic Bisimilarity, and Applications to Pushdown Automata

Vojtěch Forejt ; Petr Jančar ; Stefan Kiefer ; James Worrell.

We study the bisimilarity problem for probabilistic pushdown automata (pPDA) and subclasses thereof. Our definition of pPDA allows both probabilistic and non-deterministic branching, generalising the classical notion of pushdown automata (without epsilon-transitions). We first show a general&nbsp;[&hellip;]

---

The Big-O Problem

Dmitry Chistikov ; Stefan Kiefer ; Andrzej S. Murawski ; David Purser.

Given two weighted automata, we consider the problem of whether one is big-O of the other, i.e., if the weight of every finite word in the first is not greater than some constant multiple of the weight in the second. We show that the problem is undecidable, even for the instantiation of weighted&nbsp;[&hellip;]

---