We present an algorithm which, in order to characterize the deadlock states, analyzes the invariants and the reachability graph $G$ of a Petri Net (PN). Our idea is to investigate the strong commonality between the transition invariants of the net, associated with circuits in $G$, and the concurrent processes, associated with different paths in $G$ from the initial state of the system. In particular, starting from $G$, we determine a subgraph $L$, called “restricted live reachability graph”, containing all and only the deadlock-free states of the system. Such a graph is shown to be a unique Strongly Connected Component (SCC). In this paper, the basic steps of our algorithm are presented along with an application to the performance analysis of a highly concurrent manufacturing system

Archetti, F., Messina, V., Sciomachen, A. (1994). A graph theoretical approach to the performance analysis of highly concurrent systems. JOURNAL OF COMBINATORICS, INFORMATION & SYSTEM SCIENCES, 19(1-2), 87-95.

A graph theoretical approach to the performance analysis of highly concurrent systems.

ARCHETTI, FRANCESCO ANTONIO;MESSINA, VINCENZINA;
1994

Abstract

We present an algorithm which, in order to characterize the deadlock states, analyzes the invariants and the reachability graph $G$ of a Petri Net (PN). Our idea is to investigate the strong commonality between the transition invariants of the net, associated with circuits in $G$, and the concurrent processes, associated with different paths in $G$ from the initial state of the system. In particular, starting from $G$, we determine a subgraph $L$, called “restricted live reachability graph”, containing all and only the deadlock-free states of the system. Such a graph is shown to be a unique Strongly Connected Component (SCC). In this paper, the basic steps of our algorithm are presented along with an application to the performance analysis of a highly concurrent manufacturing system
Articolo in rivista - Articolo scientifico
Petri net; restricted live reachability graph
English
87
95
9
Archetti, F., Messina, V., Sciomachen, A. (1994). A graph theoretical approach to the performance analysis of highly concurrent systems. JOURNAL OF COMBINATORICS, INFORMATION & SYSTEM SCIENCES, 19(1-2), 87-95.
Archetti, F; Messina, V; Sciomachen, A
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/42533
Citazioni
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
Social impact