Article2592758975: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Johannes Lehmann (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorVorname=Christel |ErsterAutorNachname=Baier |FurtherAuthors=Nathalie Bertrand; Philippe Schnoebelen}} {{Article |Journal=Information Processing Letters |Number=2 |Pages=58--63 |Title=A note on the attractor-property of infinite-state Markov chains |Volume=97 |Year=2006 }} {{Publikation Details |DOI Name=10.1016/J.IPL.2005.09.011 |Abstract=In the past 5 years, a series of verification algorithms has been…“) |
Johannes Lehmann (Diskussion | Beiträge) K (Textersetzung - „Verifikation und formale quantitative Analyse“ durch „Algebraische und logische Grundlagen der Informatik“) |
||
| Zeile 14: | Zeile 14: | ||
|DOI Name=10.1016/J.IPL.2005.09.011 | |DOI Name=10.1016/J.IPL.2005.09.011 | ||
|Abstract=In the past 5 years, a series of verification algorithms has been proposed for infinite Markov chains that have a finite attractor, i.e., a set that will be visited infinitely often almost surely starting from any state. In this paper, we establish a sufficient criterion for the existence of an attractor. We show that if the states of a Markov chain can be given levels (positive integers) such that the expected next level for states at some level n > 0 is less than n - Δ for some positive Δ, then the states at level 0 constitute an attractor for the chain. As an application, we obtain a direct proof that some probabilistic channel systems combining message losses with duplication and insertion errors have a finite attractor. | |Abstract=In the past 5 years, a series of verification algorithms has been proposed for infinite Markov chains that have a finite attractor, i.e., a set that will be visited infinitely often almost surely starting from any state. In this paper, we establish a sufficient criterion for the existence of an attractor. We show that if the states of a Markov chain can be given levels (positive integers) such that the expected next level for states at some level n > 0 is less than n - Δ for some positive Δ, then the states at level 0 constitute an attractor for the chain. As an application, we obtain a direct proof that some probabilistic channel systems combining message losses with duplication and insertion errors have a finite attractor. | ||
|Forschungsgruppe= | |Forschungsgruppe=Algebraische und logische Grundlagen der Informatik | ||
}} | }} | ||
Aktuelle Version vom 5. März 2025, 15:43 Uhr
A note on the attractor-property of infinite-state Markov chains
Christel BaierChristel Baier, Nathalie BertrandNathalie Bertrand, Philippe SchnoebelenPhilippe Schnoebelen
Christel Baier, Nathalie Bertrand, Philippe Schnoebelen
A note on the attractor-property of infinite-state Markov chains
Information Processing Letters, 97(2):58--63, 2006
A note on the attractor-property of infinite-state Markov chains
Information Processing Letters, 97(2):58--63, 2006
- KurzfassungAbstract
In the past 5 years, a series of verification algorithms has been proposed for infinite Markov chains that have a finite attractor, i.e., a set that will be visited infinitely often almost surely starting from any state. In this paper, we establish a sufficient criterion for the existence of an attractor. We show that if the states of a Markov chain can be given levels (positive integers) such that the expected next level for states at some level n > 0 is less than n - Δ for some positive Δ, then the states at level 0 constitute an attractor for the chain. As an application, we obtain a direct proof that some probabilistic channel systems combining message losses with duplication and insertion errors have a finite attractor. - Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science
@article{BBS2006,
author = {Christel Baier and Nathalie Bertrand and Philippe Schnoebelen},
title = {A note on the attractor-property of infinite-state Markov chains},
journal = {Information Processing Letters},
volume = {97},
number = {2},
year = {2006},
pages = {58--63},
doi = {10.1016/J.IPL.2005.09.011}
}
