DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2017.40

On Petri Nets with Hierarchical Special Arcs

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

Published in: LIPIcs, Volume 85, 28th International Conference on Concurrency Theory (CONCUR 2017)

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.

Cite as

S. Akshay, Supratik Chakraborty, Ankush Das, Vishal Jagannath, and Sai Sandeep. On Petri Nets with Hierarchical Special Arcs. In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{akshay_et_al:LIPIcs.CONCUR.2017.40,
  author =	{Akshay, S. and Chakraborty, Supratik and Das, Ankush and Jagannath, Vishal and Sandeep, Sai},
  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 =	{Meyer, Roland and Nestmann, Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2017.40},
  URN =		{urn:nbn:de:0030-drops-78026},
  doi =		{10.4230/LIPIcs.CONCUR.2017.40},
  annote =	{Keywords: Petri Nets, Hierarchy, Reachability, Coverability, Termination, Positivity}
}

Search Results

Documents authored by Jagannath, Vishal

On Petri Nets with Hierarchical Special Arcs

Abstract

Cite as

Thanks for your feedback!

Could not send message