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, roč. 45, č. 2, s. 131-154. ISSN 0001-5903. 2008.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Deciding probabilistic bisimilarity over infinite-state probabilistic systems
Název česky Rozhodnutelnost pravděpodobnostní bisimulační ekvivalence pro systémy s nekonečně mnoha stavy
Autoři BRÁZDIL, Tomáš (203 Česká republika), Antonín KUČERA (203 Česká republika, garant) a Oldřich STRAŽOVSKÝ (203 Česká republika).
Vydání Acta informatica, Berlin, Springer-Verlag, 2008, 0001-5903.
Další údaje
Originální jazyk angličtina
Typ výsledku Článek v odborném periodiku
Obor 10201 Computer sciences, information science, bioinformatics
Stát vydavatele Německo
Utajení není předmětem státního či obchodního tajemství
Impakt faktor Impact factor: 0.789
Kód RIV RIV/00216224:14330/08:00025864
Organizační jednotka Fakulta informatiky
UT WoS 000254400600003
Klíčová slova anglicky probabilistic bisimilarity; infinite-state systems
Štítky infinite-state systems, probabilistic bisimilarity
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: prof. RNDr. Antonín Kučera, Ph.D., učo 2508. Změněno: 22. 5. 2009 15:10.
Anotace
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.
Anotace česky
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.
Návaznosti
MSM0021622419, záměrNázev: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy
1M0545, projekt VaVNázev: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky
VytisknoutZobrazeno: 28. 3. 2024 16:34