2008
Deciding probabilistic bisimilarity over infinite-state probabilistic systems
BRÁZDIL, Tomáš; Antonín KUČERA and Oldřich STRAŽOVSKÝBasic information
Original name
Deciding probabilistic bisimilarity over infinite-state probabilistic systems
Name in Czech
Rozhodnutelnost pravděpodobnostní bisimulační ekvivalence pro systémy s nekonečně mnoha stavy
Authors
BRÁZDIL, Tomáš (203 Czech Republic); Antonín KUČERA (203 Czech Republic, guarantor) and Oldřich STRAŽOVSKÝ (203 Czech Republic)
Edition
Acta informatica, Berlin, Springer-Verlag, 2008, 0001-5903
Other information
Language
English
Type of outcome
Article in a journal
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Germany
Confidentiality degree
is not subject to a state or trade secret
Impact factor
Impact factor: 0.789
RIV identification code
RIV/00216224:14330/08:00025864
Organization unit
Faculty of Informatics
UT WoS
000254400600003
Keywords in English
probabilistic bisimilarity; infinite-state systems
Tags
International impact, Reviewed
Changed: 22/5/2009 15:10, prof. RNDr. Antonín Kučera, Ph.D.
In the original language
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.
In Czech
V článku je dokázáno, že pravděpodobnostní bisimulační ekvivalence je algoritmicky rozhodnutelná pro pravěpodobnostní rozšíření BPA a BPP procesů. Pro normované podtřídy těchto procesů dokonce existuje algoritmus s polynomiální časovou složitostí. Dále je dokázáno, že pravěpodobnostní bisimulační ekvivalence je rozhodnutelná v exponenciálním čase i mezi procesy pravděpodobnostních zásobníkových automatů a procesy s konečně mnoha stavy.
Links
| MSM0021622419, plan (intention) |
| ||
| 1M0545, research and development project |
|