Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
A Class of Probabilistic Automata with a Decidable Value 1 Problem
du 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 
Emailhugo.gimbert@labri.fr 
UrlCNRS, LaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index