BRÁZDIL, Tomáš, Antonín KUČERA a Oldřich STRAŽOVSKÝ. Deciding probabilistic bisimilarity over infinite-state probabilistic systems. Acta informatica. Berlin: Springer-Verlag, 2008, roč. 45, č. 2, s. 131-154. ISSN 0001-5903. |
Další formáty:
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 a Oldřich STRAŽOVSKÝ. Deciding probabilistic bisimilarity over infinite-state probabilistic systems. \textit{Acta informatica}. Berlin: Springer-Verlag, 2008, roč.~45, č.~2, s.~131-154. ISSN~0001-5903.
|