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é:   
Semi-deterministic automata: How to obtain and complement them
du groupe Séminaire Méthodes Formelles

Date 2018-06-19  11:00-12:00
TitreSemi-deterministic automata: How to obtain and complement them 
RésuméSemi-deterministic Büchi automata (sDBA) are useful for example in model checking of probabilistic systems or in termination analysis. While in probabilistic model checking sDBA represent the set of behaviours of interest, in termination analysis they represent terminating behaviours of programs and are often complemented to perform a language difference. In my talk, I first introduce the class of semi-deterministic Büchi automata (sDBA). Then I will explain how can we convert nondeterministic Büchi automata (NBA) into sDBA, followed by a discussion on how to efficiently convert generalized Büchi automata into sDBA. After we learn how to build sDBA, I will introduce a complementation algorithm sDBA. The algorithm produces a complement automata with at most 4^n states while the best upper bound on complementation of NBA is O((0.76n)^n). Further, our algorithm produces automata with a very low degree of nondeterminism, indeed, the resulting automata are even unambiguous. 
Lieu178 
OrateurFrantišek Blahoudek 
Emailhttps://www.fi.muni.cz/~xblahoud/ 
UrlMasaryk University 



Aucun document lié à cet événement.

Retour
Retour à l'index