On the Complexity of Synthesis of nop-Free Boolean Petri Nets
From International Center for Computational Logic
On the Complexity of Synthesis of nop-Free Boolean Petri Nets
Talk by Evgeny Erofeev
- Location: Online
- Start: 24. July 2020 at 1:00 pm
- End: 24. July 2020 at 2:30 pm
- Research group: Computational Logic
- Research group: Knowledge-Based Systems
- Event series: KBS Seminar
- iCal
In a Boolean Petri net, the interaction nop allows places and transitions to be independent, so that the firing of a transition does not affect the marking of a place, and vice versa. Recently, the complexity of synthesis of nets equipped with nop has been investigated thoroughly, while the question for the rest 128 types of nets remains open. This work tackles the case of nop-free nets synthesis, that is, the Boolean nets where places and transitions are always related via interactions that are able to modify the marking of a place. In this paper, we show that, for nop-free nets, the absence of swap leads always to a polynomial time synthesis procedure. Moreover, we give a first hint, that the presence of swap might make the synthesis for these types NP-complete.
