Profinite techniques for probabilistic automata and the Markov monoid algorithm

DOI10.1016/J.TCS.2017.04.006MaRDI QIDQ529062zbMATH OpenOpenAlexFDO

Authors Nathanaël Fijalkow

Publication date 18 May 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.02997, http://wrap.warwick.ac.uk/87907/7/WRAP-profinite-techniques-probabilistic-automata-Fijalkow-2017.pdf

zbMATH Keywords

topologyprobabilistic automataprofinite theory

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

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.

Recommendations

• Characterisation of an algebraic algorithm for probabilistic automata
• Profinite techniques for probabilistic automata
• Deciding the value 1 problem for probabilistic leaktight automata
• Probabilistic automata on finite words: decidable and undecidable problems
• Deciding the value 1 problem for probabilistic leaktight automata

Cites work

• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• A topological approach to recognition
• Characterisation of an algebraic algorithm for probabilistic automata
• Decidable problems for probabilistic automata on infinite words
• Deciding the value 1 problem for probabilistic leaktight automata
• Deciding the value 1 problem for probabilistic leaktight automata
• Languages of profinite words and the limitedness problem
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Probabilistic automata
• Probabilistic automata on finite words: decidable and undecidable problems
• Profinite Methods in Automata Theory
• Profinite semigroups and applications.

Cited in

(8)

• scientific article; zbMATH DE number 5734241 (Why is no real title available?)
• Profinite techniques for probabilistic automata
• NON-CONSTRUCTIVE METHODS FOR FINITE PROBABILISTIC AUTOMATA
• Characterisation of an algebraic algorithm for probabilistic automata
• Profinite Methods in Automata Theory
• The quest for minimal quotients for probabilistic and Markov automata
• Deciding the value 1 problem for probabilistic leaktight automata
• Deciding the value 1 problem for probabilistic leaktight automata

This page was built for publication: Profinite techniques for probabilistic automata and the Markov monoid algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q529062)