uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Eager Markov Chains: Eager Markov Chains
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. DoCS.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. DoCS.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Datalogi.
2006 (English)In: Proceedings of the fourth international symposium on Automated Technology for Verification and Analysis (ATVA), 2006, p. 24-38Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
2006. p. 24-38
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:uu:diva-19030ISBN: LNCS, Volume 4218 (print)OAI: oai:DiVA.org:uu-19030DiVA, id: diva2:46802
Available from: 2006-12-07 Created: 2006-12-07 Last updated: 2018-01-12

Open Access in DiVA

No full text in DiVA

By organisation
Department of Information TechnologyComputer Systems
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 515 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf