On the Complexity of Synthesis of nop-Free Boolean Petri Nets
Aus International Center for Computational Logic
On the Complexity of Synthesis of nop-Free Boolean Petri Nets
Vortrag von Evgeny Erofeev
- Veranstaltungsort: online
- Beginn: 24. Juli 2020 um 13:00
- Ende: 24. Juli 2020 um 14:30
- Forschungsgruppe: Computational Logic
- Forschungsgruppe: Wissensbasierte Systeme
- 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.
