@article{FIJALKOW20171,
    Abstract = {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 us to give a simple and modular proof.},
    Author = {Fijalkow, Nathana{\"e}l},
    File = {Profinite techniques for probabilistic automata and the Markov Monoid algorithm - fijalkow2017 - a - t.pdf},
    ISSN = {0304-3975},
    Journal = {Theoretical Computer Science},
    Keywords = {Probabilistic automata, Profinite theory, Topology},
    Pages = {1 - 14},
    Title = {Profinite techniques for probabilistic automata and the Markov Monoid algorithm},
    URL = {http://www.sciencedirect.com/science/article/pii/S030439751730316X},
    Volume = {680},
    Year = {2017},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S030439751730316X},
    bdsk-url-2 = {https://doi.org/10.1016/j.tcs.2017.04.006},
    date-added = {2020-10-16 17:08:22 +0200},
    date-modified = {2020-10-16 17:08:22 +0200},
    doi = {10.1016/j.tcs.2017.04.006}
}

@article{FIJALKOW20171, Abstract = {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 us to give a simple and modular proof.}, Author = {Fijalkow, Nathana{\"e}l}, File = {Profinite techniques for probabilistic automata and the Markov Monoid algorithm - fijalkow2017 - a - t.pdf}, ISSN = {0304-3975}, Journal = {Theoretical Computer Science}, Keywords = {Probabilistic automata, Profinite theory, Topology}, Pages = {1 - 14}, Title = {Profinite techniques for probabilistic automata and the Markov Monoid algorithm}, URL = {http://www.sciencedirect.com/science/article/pii/S030439751730316X}, Volume = {680}, Year = {2017}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S030439751730316X}, bdsk-url-2 = {https://doi.org/10.1016/j.tcs.2017.04.006}, date-added = {2020-10-16 17:08:22 +0200}, date-modified = {2020-10-16 17:08:22 +0200}, doi = {10.1016/j.tcs.2017.04.006} }