The complexity of coverability in -Petri nets

DOI10.1145/2933575.2933593MaRDI QIDQ4635904zbMATH OpenOpenAlexWikidataFDO

Authors Ranko Lazić, Sylvain Schmitz

Publication date 23 April 2018

Published in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL http://wrap.warwick.ac.uk/79162/8/WRAP_0070379-cs-170516-sigplanconf%20%281%29.pdf

zbMATH Keywords

formal verificationorder idealwell-quasi-orderwell-structured transition systemfast-growing complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Accelerations for the coverability set of Petri nets with names
• Approaching the coverability problem continuously
• Decidability and complexity of Petri nets with unordered data
• On the coverability and reachability languages of monotonic extensions of Petri nets

Cited in

(12)

• The ideal view on Rackoff's coverability technique
• The Parametric Complexity of Lossy Counter Machines
• Coverability and Termination in Recursive Petri Nets
• Extending the Rackoff technique to affine nets
• Coverability trees for Petri nets with unordered data
• Accelerations for the coverability set of Petri nets with names
• Model checking Petri nets with names using data-centric dynamic systems
• WQO dichotomy for 3-graphs
• Handling infinitely branching well-structured transition systems
• The ideal approach to computing closed subsets in well-quasi-orderings
• Coverability, termination, and finiteness in recursive Petri nets
• Ordinal recursive complexity of unordered data nets

This page was built for publication: The complexity of coverability in \(\nu\)-Petri nets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635904)