Exposés des semaines suivantes

jeudi 21 Septembre, 14h en salle Minquiers (B025)

Frédéric Herbreteau

Why Liveness for Timed Automata Is Hard, and What We Can Do About It

The liveness problem for timed automata asks if a given automaton has a run passing infinitely often through an accepting state. We show that unless P=NP, the liveness problem is more difficult than the reachability problem; more precisely, we exhibit a family of automata for which solving the reachability problem with the standard algorithm is in P but solving the liveness problem is NP-hard. This leads us to revisit the algorithmics for the liveness problem. We propose a notion of a witness for the fact that a timed automaton violates a liveness property. We give an algorithm for computing such a witness and compare it with the existing solutions.

jeudi 26 Octobre, 14h en salle Aurigny

Tali Sznajder

TBA

TBA