52 citations · 146 across the 41 of their papers we have counts for
6 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…
Linear-Time Model Checking Branching Processes
Stefan Kiefer, Pavel Semukhin, Cas Widdershoven
(Multi-type) branching processes are a natural and well-studied model for generating random infinite trees. Branching processes feature both nondeterministic and probabilistic bran…
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…
Responsibility and verification: Importance value in temporal logics
Corto Mascle, Christel Baier, Florian Funke +2
We aim at measuring the influence of the nondeterministic choices of a part of a system on its ability to satisfy a specification. For this purpose, we apply the concept of Shapley…