Computing the Expected Accumulated Reward and Gain for a Subclass of Infinite Markov Chains

BRÁZDIL, Tomáš a Antonín KUČERA. Computing the Expected Accumulated Reward and Gain for a Subclass of Infinite Markov Chains. In 25th International Conference on Foundations of Software Technology and Theoretical Computer Science. Berlin Heidelberg New York: Springer, 2005, s. 372-383. ISBN 3-540-30495-9.

Základní údaje

Originální název

Computing the Expected Accumulated Reward and Gain for a Subclass of Infinite Markov Chains

Název česky

Výpočet středních hodnot vybraných náhodných proměnných pro Markovovy řetězce s nekonečně mnoha stavy

Autoři

BRÁZDIL, Tomáš a Antonín KUČERA

Vydání

Berlin Heidelberg New York, 25th International Conference on Foundations of Software Technology and Theoretical Computer Science, od s. 372-383, 12 s. 2005

Nakladatel

Springer

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.402

Kód RIV

RIV/00216224:14330/05:00012779

Organizační jednotka

Fakulta informatiky

ISBN

3-540-30495-9

ISSN

UT WoS

000234885800030

Klíčová slova anglicky

Infinite Markov Chains; Expected Reward

Štítky

Expected Reward, Infinite Markov Chains

---

Anotace

V originále

We consider the problem of computing the expected accumulated reward and the average gain per transition in a subclass of Markov chains with countable state spaces where all states are assigned a non-negative reward. We state several abstract conditions that guarantee computability of the above properties up to an arbitrarily small (but non-zero) given error. Finally, we show that our results can be applied to probabilistic lossy channel systems, a well-known model of processes communicating through faulty channels.

Česky

Článek se zabývá problematikou výpočtu středních hodnot pro vybrané náhodné proměnné definované na bězích nekonečně-stavových Markovových řetězců. Jsou definovány abstraktní podmínky, za kterých je možno uvedené hodnoty vypočítat s libovolnou přesností. Je také ukázáno, že navržená technika je aplikovatelná na pravděpodobnostní systémy s nespolehlivými komunikačnímy kanály.

---

Návaznosti

GA201/03/1161, projekt VaV	Název: Verifikace nekonečně stavových systémů Investor: Grantová agentura ČR, Verifikace nekonečně stavových systémů
MSM0021622419, záměr	Název: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy
1M0545, projekt VaV	Název: Institut Teoretické Informatiky Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky