uu.seUppsala universitets publikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Eager Markov Chains: Eager Markov Chains
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. DoCS.
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. DoCS.
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. Datalogi.
2006 (engelsk)Inngår i: Proceedings of the fourth international symposium on Automated Technology for Verification and Analysis (ATVA), 2006, s. 24-38Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

sted, utgiver, år, opplag, sider
2006. s. 24-38
HSV kategori
Identifikatorer
URN: urn:nbn:se:uu:diva-19030ISBN: LNCS, Volume 4218 (tryckt)OAI: oai:DiVA.org:uu-19030DiVA, id: diva2:46802
Tilgjengelig fra: 2006-12-07 Laget: 2006-12-07 Sist oppdatert: 2018-01-12

Open Access i DiVA

Fulltekst mangler i DiVA

Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric

isbn
urn-nbn
Totalt: 697 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf