LIPIcs.STACS.2016.34.pdf
- Filesize: 0.71 MB
- 13 pages
Document
Characterisation of an Algebraic Algorithm for Probabilistic Automata
Author
-
Part of:
Volume:
33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-02-16
Cite AsGet BibTex
Nathanaël Fijalkow. Characterisation of an Algebraic Algorithm for Probabilistic Automata. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 34:1-34:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.STACS.2016.34
https://doi.org/10.4230/LIPIcs.STACS.2016.34
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.
Keywords
- Probabilistic Automata
- Value 1 Problem
- Markov Monoid Algorithm
- Algebraic Algorithm
- Profinite Theory
- Topology in Computer Science
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Jorge Almeida. Profinite semigroups and applications. Structural Theory of Automata, Semigroups, and Universal Algebra, 207:1-45, 2005.
- Krishnendu Chatterjee and Mathieu Tracol. Decidable problems for probabilistic automata on infinite words. In LICS, pages 185-194, 2012. URL: http://dx.doi.org/10.1109/LICS.2012.29.
-
Nathanaël Fijalkow, Hugo Gimbert, Edon Kelmendi, and Youssouf Oualhadj. Deciding the value 1 problem for probabilistic leaktight automata. Logical Methods in Computer Science, 11(1), 2015.
- Nathanaël Fijalkow, Hugo Gimbert, and Youssouf Oualhadj. Deciding the value 1 problem for probabilistic leaktight automata. In LICS, pages 295-304, 2012. URL: http://dx.doi.org/10.1109/LICS.2012.40.
- Nathanaël Fijalkow and Denis Kuperberg. ACME: automata with counters, monoids and equivalence. In ATVA, pages 163-167, 2014. URL: http://dx.doi.org/10.1007/978-3-319-11936-6_12.
- Mai Gehrke, Serge Grigorieff, and Jean-Éric Pin. A topological approach to recognition. In ICALP (2), pages 151-162, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14162-1_13.
- Hugo Gimbert and Youssouf Oualhadj. Probabilistic automata on finite words: Decidable and undecidable problems. In ICALP (2), pages 527-538, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14162-1_44.
- Jean-Éric Pin. Profinite methods in automata theory. In STACS, pages 31-50, 2009. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2009.1856.
- Michael O. Rabin. Probabilistic automata. Information and Control, 6(3):230-245, 1963. URL: http://dx.doi.org/10.1016/S0019-9958(63)90290-0.
-
Szymon Toruńczyk. Languages of Profinite Words and the Limitedness Problem. PhD thesis, University of Warsaw, 2011.