Raymond Devillers

Eike Best, Raymond Devillers

Persistence is a strong, global, behavioural property of a Petri net, meaning that no activity can disable a different activity. Persistent permutability is a weaker property, pertaining to individual interleavings of a Petri net and stating that a non-persistent sequence can be permuted into a persistent one. We identify Petri net classes for which persistent permutability already suffices to imply overall persistence. These classes generalise free-choice nets and are related to Petri's concept of ``confusion'', while they are distinguished from each other by diverse restrictions on the choice structure of a net. We prove Ochmanski's conjecture to be correct for these classes.

Raymond Devillers, Ronny Tredup

Synthesis consists in deciding whether a given labeled transition system (TS) $A$ can be implemented by a net $N$ of type $τ$. In case of a negative decision, it may be possible to convert $A$ into an implementable TS $B$ by applying various modification techniques, like relabeling edges that previously had the same label, suppressing edges/states/events, etc. It may however be useful to limit the number of such modifications to stay close to the original problem, or optimize the technique. In this paper, we show that most of the corresponding problems are NP-complete if $τ$ corresponds to the type of flip-flop nets or some flip-flop net derivatives.

Johan Arcile, Jean-Yves Didier, Hanna Klaudel et al.

MIRELA is a high-level language and a rapid prototyping framework dedicated to systems where virtual and digital objects coexist in the same environment and interact in real time. Its semantics is given in the form of networks of timed automata, which can be checked using symbolic methods. This paper shows how to detect various kinds of indefinite waitings in the components of such systems. The method is experimented using the PRISM model checker.