Complexity of Probabilistic Bisimilarity
|
Supervisor |
|
|
Suitable for |
Abstract
Probabilistic bisimilarity (also known as lumpability) is a fundamental equivalence for Markov chains. The goal of this project is to classify the complexity of computing probabilistic bisimilarity on finite-state Markov chains. The project would suit a student with interests in complexity theory and algorithms.
Reading:
C. Baier: Polynomial Time Algorithms for Testing Probabilistic Bisimulation and Simulation. Proceedings of CAV'96. LNCS 1102, Springer 1996.
Z. Sawa and P. Jancar. P-hardness of Equivalence Testing on Finite-State Processes. Proceedings of SOFSEM'01, LNCS 2234, Springer 2001.
S. Buss: Alogtime Algorithms for Tree Isomorphism, Comparison, and Canonization. Kurt Gödel Colloquium 1997: 18-33