CONCUR 2004 START ConferenceManager    

Deciding Probabilistic Bisimilarity over Infinite-State Probabilistic Systems

T. Brazdil, A. Kucera, O. Strazovsky

Presented at Fifteenth International Conference on Concurrency Theory (CONCUR 2004), London, England, 31 August - 3 September, 2004


We prove that probabilistic bisimilarity is decidable over probabilistic extensions of BPA and BPP processes. Further, we show that probabilistic bisimilarity between probabilistic pushdown automata and finite-state systems is decidable in exponential time. If the number of control states in PDA is bounded by a fixed constant, then the algorithm needs only polynomial time.

START Conference Manager (V2.47.4)