Universal Safety for Timed Petri Nets is PSPACE-complete

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A timed network consists of an arbitrary number of initially identical 1-clock timed automata, interacting via hand-shake communication. In this setting there is no unique central controller, since all automata are initially identical. We consider the universal safety problem for such controller-less timed networks, i.e., verifying that a bad event (enabling some given transition) is impossible regardless of the size of the network.
This universal safety problem is dual to the existential coverability problem for timed-arc Petri nets, i.e., does there exist a number m of tokens, such that starting with m tokens in a given place, and none in the other places, some given transition is eventually enabled. We show that these problems are PSPACE-complete.
Original languageEnglish
Title of host publication29th International Conference on Concurrency Theory (CONCUR 2018)
EditorsSven Schewe, Lijun Zhang
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages6:1--6:15
Number of pages15
ISBN (Print)978-3-95977-087-3
DOIs
Publication statusPublished - 31 Aug 2018
Event29th International Conference on Concurrency Theory (CONCUR 2018) - Beijing, China
Duration: 4 Sep 20187 Sep 2018
http://lcs.ios.ac.cn/concur2018/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume118
ISSN (Print)1868-8969

Conference

Conference29th International Conference on Concurrency Theory (CONCUR 2018)
Abbreviated titleCONCUR 2018
CountryChina
CityBeijing
Period4/09/187/09/18
Internet address

Fingerprint

Dive into the research topics of 'Universal Safety for Timed Petri Nets is PSPACE-complete'. Together they form a unique fingerprint.

Cite this