52 citations · 146 across the 41 of their papers we have counts for
4 papers · 2 filters
Bisimilarity of Pushdown Systems is Nonelementary
Michael Benedikt, Stefan Göller, Stefan Kiefer +1
Given two pushdown systems, the bisimilarity problem asks whether they are bisimilar. While this problem is known to be decidable our main result states that it is nonelementary, i…
Bisimilarity of Probabilistic Pushdown Automata
Vojtech Forejt, Petr Jancar, Stefan Kiefer +1
We study the bisimilarity problem for probabilistic pushdown automata (pPDA) and subclasses thereof. Our definition of pPDA allows both probabilistic and non-deterministic branchin…
BPA Bisimilarity is EXPTIME-hard
Stefan Kiefer
Given a basic process algebra (BPA) and two stack symbols, the BPA bisimilarity problem asks whether the two stack symbols are bisimilar. We show that this problem is EXPTIME-hard.
On the Complexity of the Equivalence Problem for Probabilistic Automata
Stefan Kiefer, Andrzej S. Murawski, Joël Ouaknine +2
Checking two probabilistic automata for equivalence has been shown to be a key problem for efficiently establishing various behavioural and anonymity properties of probabilistic sy…