Zero-reachability in probabilistic multi-counter automata (2014)výskyt výsledku
| Identifikační kód | RIV/00216224:14330/14:00074099 |
|---|---|
| Název v anglickém jazyce | Zero-reachability in probabilistic multi-counter automata |
| Druh | D - Článek ve sborníku |
| Jazyk | eng - angličtina |
| Obor - skupina | I - Informatika |
| Obor | IN - Informatika |
| Rok uplatnění | 2014 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
| Počet výskytů výsledku | 1 |
| Počet tvůrců celkem | 5 |
| Počet domácích tvůrců | 3 |
| Výčet všech uvedených jednotlivých tvůrců | Tomáš Brázdil (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 1762834) Stefan Kiefer (státní příslušnost: DE - Spolková republika Německo) Antonín Kučera (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 9872655) Petr Novotný (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 2158507) Joost-Pieter Katoen (státní příslušnost: NL - Nizozemsko) |
| Popis výsledku v anglickém jazyce | We study the qualitative and quantitative zero-reachability problem in probabilistic multi-counter systems. We identify the undecidable variants of the problems, and then we concentrate on the remaining two cases. In the first case, when we are interested in the probability of all runs that visit zero in some counter, we show that the qualitative zero-reachability is decidable in time which is polynomial in the size of a given pMC and doubly exponential in the number of counters. Further, we show that the probability of all zero-reaching runs can be effectively approximated up to an arbitrarily small given error epsilon > 0 in time which is polynomial in log(epsilon), exponential in the size of a given pMC, and doubly exponential in the number of counters. In the second case, we are interested in the probability of all runs that visit zero in some counter different from the last counter. |
| Klíčová slova oddělená středníkem | markov chains; petri nets; reachability; multicounter automata |
| Stránka www, na které se nachází výsledek | - |
| DOI výsledku | 10.1145/2603088.2603161 |
Údaje o výsledku v závislosti na druhu výsledku
| Název sborníku | Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) |
|---|---|
| ISBN | 9781450328869 |
| ISSN | - |
| Počet stran výsledku | 10 |
| Strana od-do | |
| Název nakladatele | ACM |
| Místo vydání | New York |
| Místo konání akce | Vídeň |
| Datum konání akce | 2014 |
| Typ akce podle státní příslušnosti účastníků | WRD - Celosvětová |
| Kód UT WoS článku podle Web of Science | - |
Ostatní informace o výsledku
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
|---|---|
| Dodavatel | GA0 - Grantová agentura České republiky (GA ČR) |
| Rok sběru | 2015 |
| Specifikace | RIV/00216224:14330/14:00074099!RIV15-GA0-14330___ |
| Datum poslední aktualizace výsledku | 12.05.2015 |
| Kontrolní číslo | 152518277 |
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl
| Projekt podporovaný GA ČR v programu GP | GPP202/12/P612 - Formální verifikace stochastických systémů s reálným časem (2012 - 2014) |
|---|