The Library
The complexity of coverability in ν-Petri nets
Tools
Lazic, Ranko and Schmitz, Sylvain (2016) The complexity of coverability in ν-Petri nets. In: 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), New York City, USA, 5–8 Jul 2016. Published in: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) pp. 467-476. ISBN 9781450343916. doi:10.1145/2933575.2933593
|
PDF
WRAP_0070379-cs-170516-sigplanconf (1).pdf - Accepted Version - Requires a PDF viewer. Download (808Kb) | Preview |
Official URL: https://doi.org/10.1145/2933575.2933593
Abstract
We show that the coverability problem in ν-Petri nets is complete for ‘double Ackermann’ time, thus closing an open complexity gap between an Ackermann lower bound and a hyper-Ackermann upper bound. The coverability problem captures the verification of safety properties in this nominal extension of Petri nets with name management and fresh name creation. Our completeness result establishes ν-Petri nets as a model of intermediate power among the formalisms of nets enriched with data, and relies on new algorithmic insights brought by the use of well-quasi-order ideals.
Item Type: | Conference Item (Paper) | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||
Library of Congress Subject Headings (LCSH): | Petri nets -- Research | ||||||||||||
Series Name: | LICS: Logic in Computer Science | ||||||||||||
Journal or Publication Title: | Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) | ||||||||||||
Publisher: | ACM | ||||||||||||
ISBN: | 9781450343916 | ||||||||||||
Official Date: | 5 July 2016 | ||||||||||||
Dates: |
|
||||||||||||
Page Range: | pp. 467-476 | ||||||||||||
DOI: | 10.1145/2933575.2933593 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
Date of first compliant deposit: | 18 May 2016 | ||||||||||||
Date of first compliant Open Access: | 20 May 2016 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Conference Paper Type: | Paper | ||||||||||||
Title of Event: | 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) | ||||||||||||
Type of Event: | Conference | ||||||||||||
Location of Event: | New York City, USA | ||||||||||||
Date(s) of Event: | 5–8 Jul 2016 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year