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é:   
Equivalence Checking of Pushdown Automata and One-Counter Automata
du groupe Modélisation et Verification

Date 2013-02-21  11:30-12:30
TitreEquivalence Checking of Pushdown Automata and One-Counter Automata 
RésuméThe first part of my talk will be about bisimilarity of one-counter automata (which are pushdown automata over a singleton stack symbol with a bottom-of-stack symbol). I will show that this problem is PSPACE-complete, improving the previously best-known 3-EXPSPACE upper bound by Yen (joint work with Stanislav Böhm and Petr Jancar). The second part of the talk will be about the complexity of bisimilarity checking of pushdown automata. While decidability of this problem has been shown by Sénizergues, no complexity-theoretic upper bound of this problem is known to date. I will present a recent nonelementary lower bound for this problem, improving the previously best-known EXPTIME-hardness result of Kucera and Mayr (joint work with Michael Benedikt, Stefan Kiefer and Andrzej Murawski). 
Lieu076 
OrateurStefan Göller 
Emailgoeller@informatik.uni-bremen.de 
UrlUniv. Bremen 



Aucun document lié à cet événement.

Retour
Retour à l'index