ESPARZA, Javier, Antonín KUČERA a Richard MAYR. Model Checking Probabilistic Pushdown Automata. In Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science (LICS 2004). Los Alamitos (California): IEEE Computer Society. s. 12-21. ISBN 0-7695-2192-4. 2004.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Model Checking Probabilistic Pushdown Automata
Název česky Ověřování platnosti formulí temporálních logik pro procesy zásobníkových automatů
Autoři ESPARZA, Javier (724 Španělsko), Antonín KUČERA (203 Česká republika, garant) a Richard MAYR (276 Německo).
Vydání Los Alamitos (California), Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science (LICS 2004), od s. 12-21, 10 s. 2004.
Nakladatel IEEE Computer Society
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 10201 Computer sciences, information science, bioinformatics
Stát vydavatele Spojené státy
Utajení není předmětem státního či obchodního tajemství
Kód RIV RIV/00216224:14330/04:00010191
Organizační jednotka Fakulta informatiky
ISBN 0-7695-2192-4
UT WoS 000223180900002
Klíčová slova anglicky Probabilistic Pushdown Automata; Model Checking
Štítky Model checking, Probabilistic Pushdown Automata
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. 11. 2006 17:28.
Anotace
We consider the model checking problem for probabilistic pushdown automata (pPDA) and properties expressible in various probabilistic logics. We start with properties that can be formulated as instances of a generalized random walk problem. We prove that both qualitative and quantitative model checking for this class of properties and pPDA is decidable. Then we show that model checking for the qualitative fragment of the logic PCTL and pPDA is also decidable. Moreover, we develop an error-tolerant model checking algorithm for general PCTL and the subclass of stateless pPDA. Finally, we consider the class of properties definable by deterministic Buchi automata, and show that both qualitative and quantitative model checking for pPDA is decidable.
Anotace česky
V práci je rozebrána problematika automatického ověřování platnosti formulí temporálních logik pro procesy pravděpodobnostních zásobníkových automatů. Nejprve je uvažována třída vlastností, která je formulovatelná jako zobecněný problém náhodné procházky. Je dokázáno, že kvalitativní i kvantitativní varianta tohoto problému je rozhodnutelná. Pak je dokázána rozhodnutelnost problému platnosti dané formule kvalitativního fragmentu logiky PCTL pro daný zásobníkový proces. Jsou také uvažovány vlastnosti popsatelné pomocí deterministických Buchiho automatů a ukázána rozhodnutelnost příslušných problémů.
Návaznosti
GA201/03/1161, projekt VaVNázev: Verifikace nekonečně stavových systémů
Investor: Grantová agentura ČR, Verifikace nekonečně stavových systémů
MSM 143300001, záměrNázev: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů
VytisknoutZobrazeno: 28. 3. 2024 20:41