PETRI NETS 2011
ACSD 2011

Half Day Tutorial: Elementary Net Synthesis

Authors: Eric Badouel and Philippe Darondeau
INRIA Rennes-Bretagne Atlantique, Rennes, France
Eric.Badouel@inria.fr Philippe.Darondeau@inria.fr

Objective: Elementary Nets are a basic framework in which one can study the fundamental concepts of net theory, and for this reason, they are often the topic of introductory tutorials to Petri Nets. This tutorial has a different goal, which is to present the fundamentals of Petri net synthesis in the simplified setting of Elementary Nets. By Petri net synthesis, we mean the problem to decide from behavioural specifications, including transition systems and regular languages, whether they may be realized by a Petri net, and to produce such a net. Elementary Net synthesis is the root of all other forms of Petri net synthesis. Petri net synthesis has been succesfully applied in many areas, including asynchronous circuits, deadlock avoidance, supervisory control, process mining, representation of services and service compositions... The tutorial aims at providing a unified view of Elementary Net synthesis, covering and connecting different forms of this problem (e.g. synthesis from a transition system or from a regular language) and different aspects of this problem (e.g. the logical, algebraic, combinatorial and algorithmic aspects). The material presented covers the literature but it contains also several recent developments by the authors, who worked together on Petri net synthesis since about twenty years.

Tutorial Outline: The program of this half-day tutorial is organized as follows.

1. Introduction to Elementary Net Synthesis
• Elementary Net Systems : definition and firing rule.
• Regions and Elementary Transition Systems: Ehrenfeucht and Rozenberg's seminal theory.
• Admissible sets of regions and the separation axioms: Ehrenfeucht and Rozenberg's axioms and Desel and Reisig's results.
• Galois connection between initialized transition systems and reduced net systems : new.
• Net synthesis up to a quotient: Inspired from work by Cortadella and co.
• Net synthesis from languages : new.
2. Algorithms of Net Synthesis
• Minimal regions and state machine decompositions: Bernardinello's results.
• Sufficient completeness of minimal regions for exact or approximated synthesis: existing + new results.
• Minimal admissible sets of regions and minimal regions: existing + new results.
• NP-completeness of synthesis: Hiraishi's result and Bernardinello and the authors' results.
• Abstract sets of regions and refinement operations: new.
• Algorithm for constructing a small superset of minimal regions: new.
• Algorithm for constructing the set of minimal regions: new.
• Algorithm for solving synthesis problems expressed as separation goals: not new!
• Heuristic approach of Petrify: the approach by Cortadella and co.
3. Connections between Elementary Net synthesis and algebra
• Connections with 2-structures : Ehrenfeucht and Rozenbers's theory of representation of 2-structures based on regions.
• Connections with cutsets in graph theory: former work of the authors.
• Connections with orthomodular posets: Bernardinello and Pomello's results.
4. Variations on Elementary Net synthesis
• Synthesis of nets with self-loops, read arcs, inhibitor arcs: works by Winskel, Busi and Pinna, Pietkiewicz-Koutny.
• Synthesis of nets with the step firing rule: Pietkiewicz-Koutny and Koutny's results.
• Synthesis of Trace Nets: former work of the authors.
• Synthesis of Flip-Flop Nets: Schmitt's results on polynomial time synthesis.

Intended Audience: This tutorial on Elementary Net Synthesis is an autonomous lecture oriented primarily towards students or young researchers who were never taught about this topic. The tutorial may also have interest for people who worked in the area but would like to have a more general perspective.

Previous Venues: This tutorial was never presented before (nor any similar tutorial, as far as we know).

Speakers' Biographies:
Eric Badouel, born in 1959, joined INRIA in 1990. From 1999 to 2003, he was Head of the Computer Science Department of ENSP, a school of engineers in Yaounde, Cameroon. His research activities are centered on models of concurrency and the synthesis of Petri nets, on structured documents and domain specific languages, and finally on Interface Theories for components.

Philippe Darondeau, born in 1948, qualified as an engineer in applied mathematics at ENSIMAG (Grenoble) in 1970. He worked there until 1978, as a researcher at CNRS, on protection in operating systems. He then moved to Rennes and worked subsequently on concurrency. His main centers of interest in that field were process equivalences, true concurrency, fairness and computability. He left CNRS for INRIA in 1991, and then oriented his research on Petri net synthesis. His recent work bears also upon DES supervision for safety and for security objectives. Philippe Darondeau is a member of IFIP WG 2.2.

The speakers do not have webpages. Some of their publications may be found here