Petri Nets Properties, Analysis and Applications：Petri网的性质，分析和应用.ppt

COMP290-084 Graphical Representation of Asynchronous Systems Jan 15, 2004 Graphical Representation Petri Nets Asynchronous State Graphs Burst-Mode Representation Timed Automata Petri Nets Reference: Tadao Murata. “Petri nets: Properties, Analysis and Applications.” Proc. of the IEEE, 77(4), 1989. available on class website Credits Lecture Notes by: Gabriel Eirea UC Berkeley Petri Nets: Properties, Analysis and Applications Gabriel Eirea UC Berkeley 10/8/02 Based on paper by T. Murata Outline Introduction/History Transition enabling firing Modeling examples Behavioral properties Analysis methods Liveness, safeness reachability Analysis synthesis of Marked Graphs Structural properties Modified Petri Nets Introduction Petri Nets concurrent, asynchronous, distributed, parallel, nondeterministic and/or stochastic systems graphical tool visual communication aid mathematical tool state equations, algebraic equations, etc communication between theoreticians and practitioners History 1962: C.A. Petri’s dissertation (U. Darmstadt, W. Germany) 1970: Project MAC Conf. on Concurrent Systems and Parallel Computation (MIT, USA) 1975: Conf. on Petri Nets and related Methods (MIT, USA) 1979: Course on General Net Theory of Processes and Systems (Hamburg, W. Germany) 1980: First European Workshop on Applications and Theory of Petri Nets (Strasbourg, France) 1985: First International Workshop on Timed Petri Nets (Torino, Italy) Applications performance evaluation communication protocols distributed-software systems distributed-database systems concurrent and parallel programs industrial control systems discrete-events systems multiprocessor memory systems dataflow-computing systems fault-tolerant systems etc, etc, etc Definition Directed, weighted, bipartite graph places transitions arcs (places to transitions or transitions to places) weights associated with each arc Initial marking assigns a non-negative integer to each place Transition (firing) rule A transition t is e