Profinite techniques for probabilistic automata and the Markov monoid algorithm

DOI10.1016/J.TCS.2017.04.006zbMATH Open1370.68168arXiv1501.02997OpenAlexW2605631145MaRDI QIDQ529062FDOQ529062

Nathanaël Fijalkow

Publication date: 18 May 2017

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

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.

Full work available at URL: https://arxiv.org/abs/1501.02997

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

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)

Cites Work

• Probabilistic automata
• Title not available (Why is that?)
• Probabilistic Automata on Finite Words: Decidable and Undecidable Problems
• Profinite Methods in Automata Theory
• Profinite semigroups and applications.
• A Topological Approach to Recognition
• Deciding the value 1 problem for probabilistic leaktight automata
• Decidable Problems for Probabilistic Automata on Infinite Words
• Deciding the Value 1 Problem for Probabilistic Leaktight Automata
• Languages of Profinite Words and the Limitedness Problem
• Title not available (Why is that?)
• Characterisation of an Algebraic Algorithm for Probabilistic Automata

Cited In (4)

• Title not available (Why is that?)
• NON-CONSTRUCTIVE METHODS FOR FINITE PROBABILISTIC AUTOMATA
• Profinite Methods in Automata Theory
• The quest for minimal quotients for probabilistic and Markov 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)