1 Search Results for "Rosenke, Christian"

Document
DOI: 10.4230/LIPIcs.CONCUR.2018.16
Narrowing down the Hardness Barrier of Synthesizing Elementary Net Systems

Authors: Ronny Tredup and Christian Rosenke

Published in: LIPIcs, Volume 118, 29th International Conference on Concurrency Theory (CONCUR 2018)

Abstract
Elementary net system feasibility is the problem to decide for a given automaton A if there is a certain boolean Petri net with a state graph isomorphic to A. This is equivalent to the conjunction of the state separation property (SSP) and the event state separation property (ESSP). Since feasibility, SSP and ESSP are known to be NP-complete in general, there was hope that the restriction of graph parameters for A can lead to tractable and practically relevant subclasses. In this paper, we analyze event manifoldness, the amount of occurrences that an event can have in A, and state degree, the number of allowed successors and predecessors of states in A, as natural input restrictions. Recently, it has been shown that all three decision problems, feasibility, SSP and ESSP, remain NP-complete for linear A where every event occurs at most three times. Here, we show that these problems remain hard even if every event occurs at most twice. Nevertheless, this has to be paid by relaxing the restriction on state degree, allowing every state to have two successor and two predecessor states. As we also show that SSP becomes tractable for linear A where every event occurs at most twice the only open cases left are ESSP and feasibilty for the same input restriction.
Cite as

Ronny Tredup and Christian Rosenke. Narrowing down the Hardness Barrier of Synthesizing Elementary Net Systems. In 29th International Conference on Concurrency Theory (CONCUR 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 118, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{tredup_et_al:LIPIcs.CONCUR.2018.16,
  author =	{Tredup, Ronny and Rosenke, Christian},
  title =	{{Narrowing down the Hardness Barrier of Synthesizing Elementary Net Systems}},
  booktitle =	{29th International Conference on Concurrency Theory (CONCUR 2018)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-087-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{118},
  editor =	{Schewe, Sven and Zhang, Lijun},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2018.16},
  URN =		{urn:nbn:de:0030-drops-95546},
  doi =		{10.4230/LIPIcs.CONCUR.2018.16},
  annote =	{Keywords: Elementary net systems, Petri net synthesis, NP-completeness, Parameterized Complexity}
}
  • Refine by Author
  • 1 Rosenke, Christian
  • 1 Tredup, Ronny

  • Refine by Classification
  • 1 Software and its engineering → Petri nets
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Elementary net systems
  • 1 NP-completeness
  • 1 Parameterized Complexity
  • 1 Petri net synthesis

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact