Evènement pour le groupe Séminaire Méthodes Formelles
|Date|| 2017-01-10 11:00-12:00|
|Titre||Why 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. |
|Orateur||B Srivathsan |
|Url||CMI Chennai |
Aucun document lié à cet événement.RetourRetour à l'index