2026-07-20T05:27:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5735 2024-03-06T10:36:57Z ddc:004 open_access

Characterisation of an Algebraic Algorithm for Probabilistic Automata Fijalkow, Nathanaël Probabilistic Automata Value 1 Problem Markov Monoid Algorithm Algebraic Algorithm Profinite Theory Topology in Computer Science We consider the value 1 problem for probabilistic automata over finite words: it asks whether a given probabilistic automaton accepts words with probability arbitrarily close to 1. This problem is known to be undecidable. However, different algorithms have been proposed to partially solve it; it has been recently shown that the Markov Monoid algorithm, based on algebra, is the most correct algorithm so far. The first contribution of this paper is to give a characterisation of the Markov Monoid algorithm. The second contribution is to develop a profinite theory for probabilistic automata, called the prostochastic theory. This new framework gives a topological account of the value 1 problem, which in this context is cast as an emptiness problem. The above characterisation is reformulated using the prostochastic theory, allowing to give a modular proof. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nathanaël Fijalkow 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.34 urn:nbn:de:0030-drops-57355 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.34 eng https://creativecommons.org/licenses/by/3.0/legalcode