Search: onr:"swepub:oai:DiVA.org:uu-19030" >
Eager Markov Chains :
Eager Markov Chains : Eager Markov Chains
-
- Abdulla, Parosh (author)
- Uppsala universitet,Institutionen för informationsteknologi,Datorteknik,DoCS
-
- Ben Henda, Noomene (author)
- Uppsala universitet,Institutionen för informationsteknologi,Datorteknik,DoCS
-
Mayr, Richard (author)
-
show more...
-
- Sandberg, Sven (author)
- Uppsala universitet,Institutionen för informationsteknologi,Datorteknik,Datalogi
-
show less...
-
(creator_code:org_t)
- 2006
- 2006
- English.
-
In: Proceedings of the fourth international symposium on Automated Technology for Verification and Analysis (ATVA). ; , s. 24-38
- Related links:
-
https://urn.kb.se/re...
Abstract
Subject headings
Close
- We consider infinite-state discrete Markov chains which are eager:the probability of avoiding a defined set of final states for more than n steps is bounded by some exponentially decreasing function f(n).We prove that eager Markov chains include those induced by Probabilistic Lossy Channel Systems, Probabilistic Vector Addition Systems with States, and Noisy Turing Machines, and that the bounding function f(n) can be effectively constructed for them.Furthermore, we study the problem of computing the expected reward (or cost) of runs until reaching the final states, where rewards are assigned to individual runs by computable reward functions.For eager Markov chains, an effective path exploration scheme,based on forward reachability analysis, can be used to approximate the expected reward up-to an arbitrarily small error.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- Computer science
- Datavetenskap
Publication and Content Type
- ref (subject category)
- kon (subject category)
To the university's database