What Makes Petri Nets Harder to Verify: Stack or Data?

Lazić, Ranko and Totzke, Patrick ORCID: 0000-0001-5274-8190 (2017) What Makes Petri Nets Harder to Verify: Stack or Data? .

Access the full-text of this item by clicking on the Open Access link.

Official URL: http://dx.doi.org/10.1007/978-3-319-51046-0_8

Abstract

We show how the yardstick construction of Stockmeyer, also developed as counter bootstrapping by Lipton, can be adapted and extended to obtain new lower bounds for the coverability problem for two prominent classes of systems based on Petri nets: Ackermann-hardness for unordered data Petri nets, and Tower-hardness for pushdown vector addition systems.

Item Type:	Conference or Workshop Item (Unspecified)
Additional Information:	timestamp: Mon, 06 Nov 2017 12:14:22 +0100 biburl: https://dblp.org/rec/bib/conf/birthday/LazicT17 bibsource: dblp computer science bibliography, https://dblp.org
Depositing User:	Symplectic Admin
Date Deposited:	08 Jul 2020 10:02
Last Modified:	28 Oct 2023 10:01
DOI:	10.1007/978-3-319-51046-0_8
Open Access URL:	https://arxiv.org/abs/1404.5157
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3093261