Evènement pour le groupe Séminaire Méthodes Formelles

Date 2017-01-10  11:00-12:00
TitreWhy liveness for timed automata is hard, and what we can do about it 
RésuméThe liveness problem for timed automata asks if a given automaton has an infinite run visiting an accepting state infinitely often. In this talk, we will show that if P is not equal to NP, the liveness problem is "more difficult" than the reachability problem - more precisely, we will exhibit a family of automata for which reachability is in P whereas liveness is NP-hard. We will then present a new algorithm to solve the liveness problem, and compare it with existing solutions. Joint work with F. Herbreteau, T.T. Tran and I. Walukiewicz. 
OrateurB Srivathsan 
UrlCMI Chennai 

Aucun document lié à cet événement.

Retour à l'index