Evènement pour le groupe Graphes et Logique

Date 2011-09-27  11:00-12:00
TitreA Class of Probabilistic Automata with a Decidable Value 1 Problem  
RésuméThe value 1 problem is a decision problem for probabilistic automata over finite words: given a probabilistic automaton A, are there words accepted by A with probability arbitrarily close to 1? This problem was proved undecidable recently, even in restricted cases. We introduce a new class of probabilistic automata, called *leak-tight automata*, for which the value 1 problem is shown decidable (and PSPACE-complete). We construct an algorithm based on the computation of a monoid abstracting the behaviours of the automaton. The correctness proof on this algorithm relies on algebraic techniques developed by Simon. 
Lieusalle 76 
OrateurHugo Gimbert 

Aucun document lié à cet événement.

Retour à l'index