The Library
Profinite techniques for probabilistic automata and the Markov Monoid algorithm
Tools
Fijalkow, Nathanael (2017) Profinite techniques for probabilistic automata and the Markov Monoid algorithm. Theoretical Computer Science, 680 . pp. 1-14. doi:10.1016/j.tcs.2017.04.006 ISSN 0304-3975.
|
PDF
WRAP-profinite-techniques-probabilistic-automata-Fijalkow-2017.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (623Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.tcs.2017.04.006
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.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Probabilistic automata, Algorithms, Markov processes | ||||||||
Journal or Publication Title: | Theoretical Computer Science | ||||||||
Publisher: | Elsevier Science BV | ||||||||
ISSN: | 0304-3975 | ||||||||
Official Date: | 5 June 2017 | ||||||||
Dates: |
|
||||||||
Volume: | 680 | ||||||||
Page Range: | pp. 1-14 | ||||||||
DOI: | 10.1016/j.tcs.2017.04.006 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 25 April 2017 | ||||||||
Date of first compliant Open Access: | 25 April 2017 | ||||||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC), Alan Turing Institute (London, England) | ||||||||
Grant number: | EP/N510129/1 (EPSRC) |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year