Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.34
URN: urn:nbn:de:0030-drops-57355
URL: https://drops.dagstuhl.de/opus/volltexte/2016/5735/
Fijalkow, Nathanaël
Characterisation of an Algebraic Algorithm for Probabilistic Automata
| pdf-format: |
|
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 to give a modular proof.
BibTeX - Entry
@InProceedings{fijalkow:LIPIcs:2016:5735,
author = {Nathana{\"e}l Fijalkow},
title = {{Characterisation of an Algebraic Algorithm for Probabilistic Automata}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {34:1--34:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-001-9},
ISSN = {1868-8969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5735},
URN = {urn:nbn:de:0030-drops-57355},
doi = {10.4230/LIPIcs.STACS.2016.34},
annote = {Keywords: Probabilistic Automata, Value 1 Problem, Markov Monoid Algorithm, Algebraic Algorithm, Profinite Theory, Topology in Computer Science}
}
| Keywords: | Probabilistic Automata, Value 1 Problem, Markov Monoid Algorithm, Algebraic Algorithm, Profinite Theory, Topology in Computer Science | |
| Seminar: | 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 16.02.2016 |
