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
Basic information
Original name Deciding Probabilistic Bisimilarity Over Infinite-State Probabilistic Systems
Name in Czech Rozhodnutelnost pravděpodobnostní bisimulace pro nekonečně-stavové pravděpodobnostní systémy
Authors BRÁZDIL, Tomáš (203 Czech Republic), Antonín KUČERA (203 Czech Republic, guarantor) and Oldřich STRAŽOVSKÝ (203 Czech Republic).
P. Gardner, N. Yoshida (Eds.).
Edition Berlin, Proceedings of 15th International Conference on Concurrency Theory (CONCUR 2004), p. 193-208, 16 pp. 2004.
Publisher Springer
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
RIV identification code RIV/00216224:14330/04:00010251
Organization unit Faculty of Informatics
ISBN 3-540-22940-X
UT WoS 000223795700013
Keywords in English probabilistic bisimilarity; probabilistic systems
Tags probabilistic bisimilarity, probabilistic systems
Changed by Changed by: doc. RNDr. Tomáš Brázdil, Ph.D., učo 4074. Changed: 4/2/2005 15:02.
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.
Abstract (in Czech)
V článku je dokázáno, že pravděpodobnostní bisimulace je rozhodnutelná pro pravděpodobnostní rozšíření BPA a BPP procesů. Pro normované podtřídy pravděpodobnostních BPA a BPP procesů jsou prezentovány algoritmy, jejichž časová složitost je polynomiální. Dále je dokázáno, že pravděpodobnostní bisimulace mezi pravděpodobnostními zásobníkovými automaty a konečně-stavovými pravděpodobnostními systémy je rozhodnutelná v exponenciálním čase. Pokud je počet kontrolních stavů zásobníkového automatu omezen fixní konstantou, pak je tato časová složitost polynomiální.
Links
GA201/03/1161, research and development projectName: Verifikace nekonečně stavových systémů
Investor: Czech Science Foundation, Verification of infinite-state systems
MSM 143300001, plan (intention)Name: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů
Investor: Ministry of Education, Youth and Sports of the CR, Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing
PrintDisplayed: 25/7/2024 14:08