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, 24-38 p.Conference 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. 24-38 p.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-19030ISBN: LNCS, Volume 4218 (print)OAI: oai:DiVA.org:uu-19030DiVA: diva2:46802
Available from: 2006-12-07 Created: 2006-12-07

Open Access in DiVA

No full text

By organisation
Department of Information TechnologyComputer Systems
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 499 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