6 citations · 21 across the 9 of their papers we have counts for
12 papers
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…
Synthesis of Pure and Impure Petri nets With Restricted Place-environments: Complexity Issues
Raymond Devillers, Ronny Tredup
Petri net synthesis consists in deciding for a given transition system whether there exists a Petri net whose reachability graph is isomorphic to . Several works examine…
Some Basic Techniques allowing Petri Net Synthesis: Complexity and Algorithmic Issues
Raymond Devillers, Ronny Tredup
In Petri net synthesis we ask whether a given transition system can be implemented by a Petri net . Depending on the level of accuracy, there are three ways how can impl…
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…
The Complexity of Boolean State Separation (Technical Report)
Ronny Tredup, Evgeny Erofeev
For a Boolean type of nets , a transition system is synthesizeable into a -net if and only if distinct states of correspond to distinct markings of , and p…
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…
Hardness Results for the Synthesis of -bounded Petri Nets (Technical Report)
Ronny Tredup
Synthesis for a type of Petri nets is the following search problem: For a transition system , find a Petri net of type whose state graph is isomorphic to , if the…
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…
The Hardness of Synthesizing Elementary Net Systems from Highly Restricted Inputs
Christian Rosenke, Ronny Tredup
Elementary net systems (ENS) are the most fundamental class of Petri nets. Their synthesis problem has important applications in the design of digital hardware and commercial proce…