License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2022.8
URN: urn:nbn:de:0030-drops-170710
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17071/
Go to the corresponding LIPIcs Volume Portal

Khomenko, Victor ; Koutny, Maciej ; Yakovlev, Alex

Slimming down Petri Boxes: Compact Petri Net Models of Control Flows

pdf-format:
LIPIcs-CONCUR-2022-8.pdf (0.8 MB)

Abstract

We look at the construction of compact Petri net models corresponding to process algebra expressions supporting sequential, choice, and parallel compositions. If "silent" transitions are disallowed, a construction based on Cartesian product is traditionally used to construct places in the target Petri net, resulting in an exponential explosion in the net size. We demonstrate that this exponential explosion can be avoided, by developing a link between this construction problem and the problem of finding an edge clique cover of a graph that is guaranteed to be complement-reducible (i.e., a cograph). It turns out that the exponential number of places created by the Cartesian product construction can be reduced down to polynomial (quadratic) even in the worst case, and to logarithmic in the best (non-degraded) case. As these results affect the "core" modelling techniques based on Petri nets, eliminating a source of an exponential explosion, we hope they will have applications in Petri net modelling and translations of various formalisms to Petri nets.

BibTeX - Entry

@InProceedings{khomenko_et_al:LIPIcs.CONCUR.2022.8,
  author =	{Khomenko, Victor and Koutny, Maciej and Yakovlev, Alex},
  title =	{{Slimming down Petri Boxes: Compact Petri Net Models of Control Flows}},
  booktitle =	{33rd International Conference on Concurrency Theory (CONCUR 2022)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-246-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{243},
  editor =	{Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17071},
  URN =		{urn:nbn:de:0030-drops-170710},
  doi =		{10.4230/LIPIcs.CONCUR.2022.8},
  annote =	{Keywords: Petri net, Petri box, cograph, edge clique cover, control flow, static construction, local construction, interface graph, Burst automata, composition}
}

Keywords: Petri net, Petri box, cograph, edge clique cover, control flow, static construction, local construction, interface graph, Burst automata, composition
Collection: 33rd International Conference on Concurrency Theory (CONCUR 2022)
Issue Date: 2022
Date of publication: 06.09.2022

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