52 citations · 146 across the 41 of their papers we have counts for
6 papers · 1 filter
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…
Distinguishing Hidden Markov Chains
Stefan Kiefer, A. Prasad Sistla
Hidden Markov Chains (HMCs) are commonly used mathematical models of probabilistic systems. They are employed in various fields such as speech recognition, signal processing, and b…
Long-Run Average Behaviour of Probabilistic Vector Addition Systems
Tomas Brazdil, Stefan Kiefer, Antonin Kucera +1
We study the pattern frequency vector for runs in probabilistic Vector Addition Systems with States (pVASS). Intuitively, each configuration of a given pVASS is assigned one of fin…
Tree Buffers
Radu Grigore, Stefan Kiefer
In runtime verification, the central problem is to decide if a given program execution violates a given property. In online runtime verification, a monitor observes a program's exe…
Proving the Herman-Protocol Conjecture
Maria Bruna, Radu Grigore, Stefan Kiefer +2
Herman's self-stabilisation algorithm, introduced 25 years ago, is a well-studied synchronous randomised protocol for enabling a ring of processes collectively holding any odd…
The Complexity of the Kth Largest Subset Problem and Related Problems
Christoph Haase, Stefan Kiefer
We show that the Kth largest subset problem and the Kth largest m-tuple problem are in PP and hard for PP under polynomial-time Turing reductions. Several problems from the literat…