| BRÁZDIL, Tomáš, Antonín KUČERA and Oldřich STRAŽOVSKÝ. Deciding Probabilistic Bisimilarity Over Infinite-State Probabilistic Systems. P. Gardner, N. Yoshida (Eds.). In Proceedings of 15th International Conference on Concurrency Theory (CONCUR 2004). Berlin: Springer, 2004, p. 193-208. ISBN 3-540-22940-X. |
Other formats:
BibTeX
LaTeX
RIS
@inproceedings{557410,
author = {Brázdil, Tomáš and Kučera, Antonín and Stražovský, Oldřich},
address = {Berlin},
booktitle = {Proceedings of 15th International Conference on Concurrency Theory (CONCUR 2004)},
keywords = {probabilistic bisimilarity; probabilistic systems},
language = {eng},
location = {Berlin},
isbn = {3-540-22940-X},
pages = {193-208},
publisher = {Springer},
title = {Deciding Probabilistic Bisimilarity Over Infinite-State Probabilistic Systems},
year = {2004}
}
TY - JOUR
ID - 557410
AU - Brázdil, Tomáš - Kučera, Antonín - Stražovský, Oldřich
PY - 2004
TI - Deciding Probabilistic Bisimilarity Over Infinite-State Probabilistic Systems
PB - Springer
CY - Berlin
SN - 354022940X
KW - probabilistic bisimilarity
KW - probabilistic systems
N2 - 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.
ER -
BRÁZDIL, Tomáš, Antonín KUČERA and Oldřich STRAŽOVSKÝ. Deciding Probabilistic Bisimilarity Over Infinite-State Probabilistic Systems. P. Gardner, N. Yoshida (Eds.). In \textit{Proceedings of 15th International Conference on Concurrency Theory (CONCUR 2004)}. Berlin: Springer, 2004, p.~193-208. ISBN~3-540-22940-X.
|
