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
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.


This talk will be held online. If there is any interest in attending, please send an e-mail to thomas.feller@tu-dresden.de.