6 citations · 21 across the 9 of their papers we have counts for
7 papers · 1 filter
On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
Raymond Devillers, Ronny Tredup
Synthesis consists in deciding whether a given labeled transition system (TS) can be implemented by a net of type . In case of a negative decision, it may be possible to…
The Complexity of Synthesis of -Bounded Petri Nets
Ronny Tredup
For a fixed type of Petri nets , \textsc{-Synthesis} is the task of finding for a given transition system a Petri net of type (-net, for short) whose reachabil…
On the Parameterized Complexity of Synthesizing Boolean Petri Nets With Restricted Dependency
Ronny Tredup, Evgeny Erofeev
Modeling of real-world systems with Petri nets allows to benefit from their generic concepts of parallelism, synchronisation and conflict, and obtain a concise yet expressive syste…
On the Parameterized Complexity of Synthesizing Boolean Petri Nets With Restricted Dependency (Technical Report)
Ronny Tredup, Evgeny Erofeev
The problem of -synthesis consists in deciding whether a given directed labeled graph is isomorphic to the reachability graph of a Boolean Petri net of type . In case…
The Complexity of Synthesizing nop-Equipped Boolean Nets from g-Bounded Inputs (Technical Report)
Ronny Tredup
Boolean Petri nets equipped with nop allow places and transitions to be independent by being related by nop. We characterize for any fixed natural number g the computational comple…
Tracking Down the Bad Guys: Reset and Set Make Feasibility for Flip-Flop Net Derivatives NP-complete
Ronny Tredup
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 probl…
Towards Completely Characterizing the Complexity of Boolean Nets Synthesis
Ronny Tredup, Christian Rosenke
Boolean nets are Petri nets that permit at most one token per place. Research has approached this important subject in many ways which resulted in various different classes of bool…