Deciding probabilistic bisimilarity over infinite-state probabilistic systems |
| |
Authors: | Tomá? Brázdil Antonín Ku?era Old?ich Stra?ovský |
| |
Affiliation: | (1) Faculty of Informatics, Masaryk University, Botanická 68a, Brno, 60200, Czech Republic |
| |
Abstract: | We prove that probabilistic bisimilarity is decidable over probabilistic extensions of BPA and BPP processes. For normed subclasses
of probabilistic BPA and BPP processes we obtain polynomial-time algorithms. 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.
The work has been supported by the research centre Institute for Theoretical Computer Science (ITI), project No. 1M0545. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|