Characterisation of an Algebraic Algorithm for Probabilistic Automata Characterisation of an Algebraic Algorithm for Probabilistic Automata - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Characterisation of an Algebraic Algorithm for Probabilistic Automata Characterisation of an Algebraic Algorithm for Probabilistic Automata

Résumé

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.
Fichier principal
Vignette du fichier
main.pdf (192.75 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01102610 , version 1 (13-01-2015)
hal-01102610 , version 2 (29-01-2015)
hal-01102610 , version 3 (12-02-2016)

Identifiants

Citer

Nathanaël Fijalkow. Characterisation of an Algebraic Algorithm for Probabilistic Automata Characterisation of an Algebraic Algorithm for Probabilistic Automata. STACS, Symposium on Theoretical Aspects of Computer Science, Feb 2016, Orléans, France. ⟨hal-01102610v3⟩
84 Consultations
85 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More