On Petri nets with hierarchical special arcs

DOI10.4230/LIPICS.CONCUR.2017.40MaRDI QIDQ5111656zbMATH OpenOpenAlexFDO

Authors S. Akshay, Supratik Chakraborty, Ankush Das, Vishal Jagannath, Sai Sandeep

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1707.01157

zbMATH Keywords

hierarchyreachabilityPetri netspositivityterminationcoverability

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: We investigate the decidability of termination, reachability, coverability and deadlock-freeness of Petri nets endowed with a hierarchy on places, and with inhibitor arcs, reset arcs and transfer arcs that respect this hierarchy. We also investigate what happens when we have a mix of these special arcs, some of which respect the hierarchy, while others do not. We settle the decidability status of the above four problems for all combinations of hierarchy, inhibitor, reset and transfer arcs, except the termination problem for two combinations. For both these combinations, we show that the termination problem is as hard as deciding positivity for linear recurrent sequences -- a long-standing open problem.

Recommendations

• scientific article; zbMATH DE number 1223710
• Reachability in Petri nets with inhibitor arcs
• scientific article; zbMATH DE number 1522994
• Analysis issues in Petri nets with inhibitor arcs
• \(\omega\)-Petri nets: algorithms and complexity

Cites work

• scientific article; zbMATH DE number 1223710 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• An Algorithm for the General Petri Net Reachability Problem
• Approximating Petri net reachability along context-free traces
• Complexity results for 1-safe nets
• Mixing coverability and reachability to analyze VASS with one zero-test
• Model checking vector addition systems with one zero-test
• On Petri nets with hierarchical special arcs
• On the termination of integer loops
• Place-boundedness for vector addition systems with one zero-test
• Positivity problems for low-order linear recurrence sequences
• Reachability in Petri nets with inhibitor arcs
• The Reachability Problem for Vector Addition System with One Zero-Test
• Well-structured transition systems everywhere!

Cited in

(6)

• Synthesis of inhibitor-reset Petri nets: algorithmic and complexity issues
• A lazy query scheme for reachability analysis in Petri nets
• Arc-typed Petri Nets
• Reachability in Petri nets with inhibitor arcs
• scientific article; zbMATH DE number 7561336 (Why is no real title available?)
• On Petri nets with hierarchical special arcs

This page was built for publication: On Petri nets with hierarchical special arcs

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