52 citations · 146 across the 41 of their papers we have counts for
25 papers · 1 filter
Approximate Bisimulation Minimisation
Stefan Kiefer, Qiyi Tang
We propose polynomial-time algorithms to minimise labelled Markov chains whose transition probabilities are not known exactly, have been perturbed, or can only be obtained by sampl…
Lower Bounds for Unambiguous Automata via Communication Complexity
Mika Göös, Stefan Kiefer, Weiqiang Yuan
We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. The…
Image-Binary Automata
Stefan Kiefer, Cas Widdershoven
We introduce a certain restriction of weighted automata over the rationals, called image-binary automata. We show that such automata accept the regular languages, can be exponentia…
On Complementing Unambiguous Automata and Graphs With Many Cliques and Cocliques
Emil Indzhev, Stefan Kiefer
We show that for any unambiguous finite automaton with states there exists an unambiguous finite automaton with states that recognizes the complement…
Online Monitoring -Regular Properties in Unknown Markov Chains
Javier Esparza, Stefan Kiefer, Jan Kretinsky +1
We study runtime monitoring of -regular properties. We consider a simple setting in which a run of an unknown finite-state Markov chain is monitored against a fixed…
Comparing Labelled Markov Decision Processes
Stefan Kiefer, Qiyi Tang
A labelled Markov decision process is a labelled Markov chain with nondeterminism, i.e., together with a strategy a labelled MDP induces a labelled Markov chain. The model is relat…