Petri net synthesis

Foreword by Grzegorz Rozenberg.

A Petri net synthesis problem can be seen as a model transformation from a behavioural to a structural description of a concurrent system. In its original version formulated by Andrzej Ehrenfeucht and myself, the behavioural description was given by transition systems and the structural description was given by elementary net systems. The solution we provided was based on the theory of regions of transition systems which also yielded an automatic synthesis of an elementary net system whose behaviour was captured by a given transition system.

Since then (1989) Petri net synthesis has become a very vivid and successful research area. The original approach was extended at both ends: the behavioural and the structural descriptions. The acceptable behavioural specifications were extended to, for example, formal languages and execution traces. The structural descriptions were extended first to Place/Transition nets and then to, for example, Petri Nets augmented with priorities or inhibitor arcs. Also, the types of operational semantics were extended to, for example, step sequence semantics (where several actions can be executed simultaneously) which can be constrained by various firing policies (such as maximal parallelism). The notion of a region (suitably adapted) proved to be robust in all these extensions - as a matter of fact it became a basic/central notion of the framework of Petri nets and beyond. All these research efforts were accompanied by the development of suitable algorithms for net synthesis.

Application areas of net synthesis currently cover, among others, the construction of distributed systems, supervisory control, process discovery, and the design of asynchronous circuits. One can already identify the influence of net synthesis research on the design of asynchronous circuits operating under relative timing, and process mining technologies aimed at understanding causal relationships in the behaviour of complex business systems.

Altogether Petri net synthesis has become a full-fledged, relevant, and exciting research area. This book provides an impressive in-depth account of a wide range of the existing results and techniques. It extensively covers the theory and the algorithms and it also provides a good insight into applications. The book is an impressive achievement that will be very valuable for both novices entering this research field and for researchers in this area as a rich and reliable reference as well as a source of relevant research problems.

The very high technical and presentation quality of the book is certainly due to the fact that all three authors made fundamental contributions to this research area. Unfortunately, Philippe Darondeau passed away much too early, so that he could not see the final product of this project. The book is a tribute to this outstanding and inspiring researcher.

Grzegorz Rozenberg
Leiden, The Netherlands 2015