Universal Safety for Timed Petri Nets is PSPACE-complete.

Parosh Aziz Abdulla, Mohamed Faouzi Atig, Radu Ciobanu, Richard Mayr, Patrick Totzke

Browse the full CONCUR paper archive.