On Petri Nets with Hierarchical Special Arcs

DOI10.4230/LIPICS.CONCUR.2017.40zbMATH Open1442.68122arXiv1707.01157OpenAlexW2962843301MaRDI QIDQ5111656FDOQ5111656

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

Publication date: 27 May 2020

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Well-structured transition systems everywhere!
• Positivity Problems for Low-Order Linear Recurrence Sequences
• The Reachability Problem for Vector Addition System with One Zero-Test
• Mixing Coverability and Reachability to Analyze VASS with One Zero-Test
• An Algorithm for the General Petri Net Reachability Problem
• Reachability in Petri Nets with Inhibitor Arcs
• Complexity results for 1-safe nets
• Approximating Petri net reachability along context-free traces
• On the Termination of Integer Loops
• On Petri Nets with Hierarchical Special Arcs
• Model checking vector addition systems with one zero-test
• Place-boundedness for vector addition systems with one zero-test

Cited In (5)

• Title not available (Why is that?)
• A lazy query scheme for reachability analysis in Petri nets
• Synthesis of inhibitor-reset Petri nets: algorithmic and complexity issues
• Arc-typed Petri Nets
• 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)