Introduction to Elementary Net Synthesis

This chapter aims at giving, for the particular class of elementary net systems, a first account of the principles of region-based net synthesis. The next section introduces elementary nets in an informal way. Section 1.2 recalls the corresponding formal definitions needed in this book. Section 1.3 presents the construction of the saturated net version of a transition system, as proposed by Ehrenfeucht and Rozenberg, while Section 1.4 recalls their characterization of net realizable transition systems by the regional axioms. Sections 1.5 and 1.6 focus on admissible sets of regions, namely sets of regions which are sufficient to solve the synthesis problem. The interest is to reduce significantly the search space for admissible sets of regions, which has a direct impact on the efficiency of net synthesis algorithms. Section 1.7 explores the relation between regional partitions of a transition system and sequential components of elementary net systems. We finally explain in Section 1.8 the context of Labelled Partial 2-Structures in which regions were discovered and first applied to elementary net synthesis. The chapter is completed by a series of exercises.