Zero-reachability in probabilistic multi-counter automata
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F14%3A00074099" target="_blank" >RIV/00216224:14330/14:00074099 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1145/2603088.2603161" target="_blank" >http://dx.doi.org/10.1145/2603088.2603161</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/2603088.2603161" target="_blank" >10.1145/2603088.2603161</a>
Alternative languages
Result language
angličtina
Original language name
Zero-reachability in probabilistic multi-counter automata
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GPP202%2F12%2FP612" target="_blank" >GPP202/12/P612: Formal Verification of Stochastic Real-Time Systems</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
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
—
e-ISSN
—
Number of pages
10
Pages from-to
—
Publisher name
ACM
Place of publication
New York
Event location
Vídeň
Event date
Jan 1, 2014
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—