Tracking Down the Bad Guys: Reset and Set Make Feasibility for Flip-Flop Net Derivatives NP-complete

Ronny Tredup
(Universität Rostock)

Boolean Petri nets are differentiated by types of nets τ based on which of the interactions nop, inp, out, set, res, swap, used, and free they apply or spare. The synthesis problem relative to a specific type of nets τ is to find a boolean τ-net N whose reachability graph is isomorphic to a given transition system A. The corresponding decision version of this search problem is called feasibility. Feasibility is known to be polynomial for all types of flip flop derivates that contain at least the interactions nop, swap and an arbitrary selection of inp, out, used, free. In this paper, we replace inp and out by res and set, respectively, and show that feasibility becomes NP-complete for the types that contain nop, swap and a non empty selection of res, set and a non empty selection of used, free. The reduction guarantees a low degree for A's states and, thus, preserves hardness of feasibility even for considerable input restrictions.

In Massimo Bartoletti, Ludovic Henrio, Anastasia Mavridou and Alceste Scalas: Proceedings 12th Interaction and Concurrency Experience (ICE 2019), Copenhagen, Denmark, 20-21 June 2019, Electronic Proceedings in Theoretical Computer Science 304, pp. 20–37.
Published: 12th September 2019.

ArXived at: https://dx.doi.org/10.4204/EPTCS.304.2 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org