Other formats:
BibTeX
LaTeX
RIS
@article{763242,
author = {Brázdil, Tomáš and Kučera, Antonín and Stražovský, Oldřich},
article_location = {Berlin},
article_number = {2},
keywords = {probabilistic bisimilarity; infinite-state systems},
language = {eng},
issn = {0001-5903},
journal = {Acta informatica},
title = {Deciding probabilistic bisimilarity over infinite-state probabilistic systems},
volume = {45},
year = {2008}
}
TY - JOUR
ID - 763242
AU - Brázdil, Tomáš - Kučera, Antonín - Stražovský, Oldřich
PY - 2008
TI - Deciding probabilistic bisimilarity over infinite-state probabilistic systems
JF - Acta informatica
VL - 45
IS - 2
SP - 131-154
EP - 131-154
PB - Springer-Verlag
SN - 00015903
KW - probabilistic bisimilarity
KW - infinite-state 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. \textit{Acta informatica}. Berlin: Springer-Verlag, vol.~45, No~2, p.~131-154. ISSN~0001-5903. 2008.
|
