Synthesizing Petri nets from state-based models

ABSTRACT

This paper presents a method to synthesize labeled Petri nets from state-based models. Although state-based models (such as Finite State Machines) are a powerful formalism to describe the behavior of sequential systems, they cannot explicitly express the notions of concurrency, causality and conflict. Petri nets can naturally capture these notions. The proposed method in based on deriving an Elementary Transition System (ETS) from a specification model. Previous work has shown that for any ETS there exists a Petri net with minimum transition count (one transition for each label) with a reachability graph isomorphic to the original ETS. This paper presents the first known approach to obtain an ETS from a non-elementary TS and derive a place-irredundant Petri net. Furthermore, by imposing constraints on the synthesis method, different classes of Petri nets can be derived from the same reachability graph (pure, free choice, unique choice). This method has been implemented and efficiently applied in different frameworks: Petri net composition, synthesis of Petri nets from asynchronous circuits, and resynthesis of Petri nets.

REFERENCES

• 1: E. Badouel, L. Bernardinello, and Ph. Darondeau. Polynomial algorithms for the synthesis of bounded nets. Technical Report 2316, INRIA, RENNES Cedex, France, 1994.
• 2: K. van Berkel. Handshake circuits: an intermedia17 between communicating processes and VLSI. PhD thesis, Technical University of Eindhoven, 1992.
• 3: L. Bernardinello, G. De Michelis, K. Petruni, and S. Vigna. On synchronic structure of transition systems. Technical report, Universita di Milano, Milano, 1994.
• 4: J. Cortadella, M. Kishinevsky, L. Lavagno, and A. Yakovlev. Synthesizing Petri nets from state-based models. Technical Report RR 95/09 UPC/DAC, Universitat Politecnica de Catalunya, April 1995.
• 5: J. Cortadella, L. Lavagno, E Vanbekbergen, and A.Yakovlev. Designing asynchronous circuits from behavioural specifications with internal conflicts. In Proceedings oflnt. Conf. on Adv. Res. in Asynch. Circ. and Syst., pages 106-115, November 1994.
• 6: J. Ebergen. Personal communication. March 1995.
• 7: J. Esparza and M. Nielsen. Decidability issues for Petri nets. Petri Nets Newsletter, 94:5-23, 1994.
• 8: Michael Kishinevsky , Alex Kondratyev , Alexander Taubin , Victor Varshavsky , Alex Yakovlev , Eric Napelbaum , Olga Reva, Concurrent hardware: the theory and practice of self-timed design, John Wiley & Sons, Inc., New York, NY, 1994
• 9: Robin Milner. A calculus of communication systems. In Lecture Notes in Computer Science, volume 92, 1980.
• 10: M. Mukund. Petri nets and step transition systems. Int. Journal of Foundations of Computer Science, 3(4):443-478, 1992.
• 11: M. Nielsen , G. Rozenberg , P. S. Thiagarajan, Elementary transition systems, Theoretical Computer Science, v.96 n.1, p.3-33, 6 April 1992
• 12: C. A. Petri. Kommunikation mit Automaten. PhD thesis, Bonn, Institut fur Instrumentelle Mathematik, 1962. (technical report Schriften des IIM Nr. 3).
• 13: Robert F. Sproull , Ivan E. Sutherland , Charles E. Molnar, The Counterflow Pipeline Processor Architecture, IEEE Design & Test, v.11 n.3, p.48-59, July 1994 [doi>10.1109/MDT.1994.303847]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Theory

Keywords:
Petri nets, Transition Systems, Asynchronous Circuits, Finite State Machines, Synthesis