J 2008

Deciding probabilistic bisimilarity over infinite-state probabilistic systems

BRÁZDIL, Tomáš, Antonín KUČERA a Oldřich STRAŽOVSKÝ

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

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

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 22. 5. 2009 15:10, prof. RNDr. Antonín Kučera, Ph.D.

Anotace

ORIG CZ

V originále

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.

Č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ěr
Ná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 VaV
Název: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky