2026-07-20T05:38:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2335 2024-03-06T10:33:19Z ddc:004 open_access

Recurrence and Transience for Probabilistic Automata Tracol, Mathieu Baier, Christel Grösser, Marcus Markov Chains Probabilistic Automata Buchi Automata Recurrence Omega-Regular Properties In a context of $\omega$-regular specifications for infinite execution sequences, the classical B\"uchi condition, or repeated liveness condition, asks that an accepting state is visited infinitely often. In this paper, we show that in a probabilistic context it is relevant to strengthen this infinitely often condition. An execution path is now accepting if the \emph{proportion} of time spent on an accepting state does not go to zero as the length of the path goes to infinity. We introduce associated notions of recurrence and transience for non-homogeneous finite Markov chains and study the computational complexity of the associated problems. As Probabilistic B\"uchi Automata (PBA) have been an attempt to generalize B\"uchi automata to a probabilistic context, we define a class of Constrained Probabilistic Automata with our new accepting condition on runs. The accepted language is defined by the requirement that the measure of the set of accepting runs is positive (probable semantics) or equals 1 (almost-sure semantics). In contrast to the PBA case, we prove that the emptiness problem for the language of a constrained probabilistic B\"uchi automaton with the probable semantics is decidable. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mathieu Tracol and Christel Baier and Marcus Grösser 2009 Is Part Of LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2009.2335 urn:nbn:de:0030-drops-23357 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2335 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode