Structural analysis of Petri nets has played an important role in the success of Petri nets for the analysis of discrete-event dynamic systems. Most structural Petri net theory has focused on P- (and T-) semiflows, the left (and right) non-negative integer annullers of the Petri net incidence matrix, which capture invariant laws for markings and cyclic behaviors, while little attention has been devoted to the general case of integer annullers, leading us to our first question: Are there useful invariant laws based on arbitrary integer flows? Moreover, the set of semiflows is typically characterized (in theory and tools) by the minimal semiflows, whose entries are relatively prime and whose support does not contain that of other semiflows. Minimal semiflows form a Q≥0-generator: any semiflow can be written as a linear combination with positive rational coefficients of minimal semiflows. Then, our second question is: Can we characterize the set of (semi)flows through anN-generating set, and do we gain better or additional insights by doing so? To answer these questions, we consider the lattice of integer flows and shed light on the role of the Hilbert and Graver bases of a lattice vs. the notion of minimal flows. Moreover, we use various examples to discuss invariant laws based on flows in the Graver basis, and the role of arbitrary integer flows.

Old and New Perspectives on Petri Nets Flows

Amparore, Elvio G.;Ciardo, Gianfranco;Donatelli, Susanna;Terracini, Lea
2026-01-01

Abstract

Structural analysis of Petri nets has played an important role in the success of Petri nets for the analysis of discrete-event dynamic systems. Most structural Petri net theory has focused on P- (and T-) semiflows, the left (and right) non-negative integer annullers of the Petri net incidence matrix, which capture invariant laws for markings and cyclic behaviors, while little attention has been devoted to the general case of integer annullers, leading us to our first question: Are there useful invariant laws based on arbitrary integer flows? Moreover, the set of semiflows is typically characterized (in theory and tools) by the minimal semiflows, whose entries are relatively prime and whose support does not contain that of other semiflows. Minimal semiflows form a Q≥0-generator: any semiflow can be written as a linear combination with positive rational coefficients of minimal semiflows. Then, our second question is: Can we characterize the set of (semi)flows through anN-generating set, and do we gain better or additional insights by doing so? To answer these questions, we consider the lattice of integer flows and shed light on the role of the Hilbert and Graver bases of a lattice vs. the notion of minimal flows. Moreover, we use various examples to discuss invariant laws based on flows in the Graver basis, and the role of arbitrary integer flows.
2026
47th International Conference on Application and Theory of Petri Nets and Concurrency, PETRI NETS 2026
deu
2026
Lecture Notes in Computer Science
Springer Science and Business Media Deutschland GmbH
16567
43
63
9783032278784
9783032278791
Flows; Graver bases; Hilbert bases; Semiflows
Amparore, Elvio G.; Ciardo, Gianfranco; Donatelli, Susanna; Terracini, Lea
File in questo prodotto:
File Dimensione Formato  
PetriNets2026.pdf

Accesso aperto con embargo fino al 30/11/2027

Tipo di file: PREPRINT (PRIMA BOZZA)
Dimensione 749.86 kB
Formato Adobe PDF
749.86 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/2318/2168551
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact