|
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. |
Lieu | 178 |
Orateur | B Srivathsan |
Email | http://www.cmi.ac.in/~sri/ |
Url | CMI Chennai |
Aucun document lié à cet événement. RetourRetour à l'index
| |