License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2017.40
URN: urn:nbn:de:0030-drops-78026
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7802/
Go to the corresponding LIPIcs Volume Portal

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

On Petri Nets with Hierarchical Special Arcs

pdf-format:
LIPIcs-CONCUR-2017-40.pdf (0.6 MB)

Abstract

We investigate the decidability of termination, reachability, coverability and deadlock-freeness of Petri nets endowed with a hierarchy of 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 deciding termination is as hard as deciding the positivity problem on linear recurrence sequences -- a long-standing open problem.

BibTeX - Entry

@InProceedings{akshay_et_al:LIPIcs:2017:7802,
  author =	{S. Akshay and Supratik Chakraborty and Ankush Das and Vishal Jagannath and Sai Sandeep},
  title =	{{On Petri Nets with Hierarchical Special Arcs}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{40:1--40:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Roland Meyer and Uwe Nestmann},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7802},
  URN =		{urn:nbn:de:0030-drops-78026},
  doi =		{10.4230/LIPIcs.CONCUR.2017.40},
  annote =	{Keywords: Petri Nets, Hierarchy, Reachability, Coverability, Termination, Positivity}
}

Keywords: Petri Nets, Hierarchy, Reachability, Coverability, Termination, Positivity
Collection: 28th International Conference on Concurrency Theory (CONCUR 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI