Petri nets have been widely used to design and modeling concurrent systems, as well as certain kinds of time-dependent systems. This is due not only to their neat graphical representation but also to the fact that a great quantity of theoretical studies have been done on their mathematical properties. In this paper, in order to capture some interesting structural properties of conflict-free Petri nets we consider directed hypergraph. This representation allows us to obtain very efficient algorithms and data structures to handle conflict-free Petri nets. More precisely, we propose linear time Mgorithms for determining potentially firable and live transitions and boundedness of the net. Moreover, we mantain the set of potentially firable transitions on-line, that is, while the net is modified: an important feature when we speak about interactive design of a system. In other words, our algorithms and data structures allow us to decide if a transition is potentially firable while the net is been built, with no additional cost.

Linear time algorithms for liveness and boundedness in conflict-free Petri nets / Alimonti, Paola; Feuerstein, ESTEBAN ZINDEL; Nanni, Umberto. - 583:(1992), pp. 1-14. (Intervento presentato al convegno 1st International Symposium on Latin American Theoretical Informatics, LATIN 1992 tenutosi a São Paulo; Brazil) [10.1007/BFb0023812].

Linear time algorithms for liveness and boundedness in conflict-free Petri nets

FEUERSTEIN, ESTEBAN ZINDEL;Nanni, Umberto
1992

Abstract

Petri nets have been widely used to design and modeling concurrent systems, as well as certain kinds of time-dependent systems. This is due not only to their neat graphical representation but also to the fact that a great quantity of theoretical studies have been done on their mathematical properties. In this paper, in order to capture some interesting structural properties of conflict-free Petri nets we consider directed hypergraph. This representation allows us to obtain very efficient algorithms and data structures to handle conflict-free Petri nets. More precisely, we propose linear time Mgorithms for determining potentially firable and live transitions and boundedness of the net. Moreover, we mantain the set of potentially firable transitions on-line, that is, while the net is modified: an important feature when we speak about interactive design of a system. In other words, our algorithms and data structures allow us to decide if a transition is potentially firable while the net is been built, with no additional cost.
1992
1st International Symposium on Latin American Theoretical Informatics, LATIN 1992
Theoretical Computer Science; Computer Science (all)
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Linear time algorithms for liveness and boundedness in conflict-free Petri nets / Alimonti, Paola; Feuerstein, ESTEBAN ZINDEL; Nanni, Umberto. - 583:(1992), pp. 1-14. (Intervento presentato al convegno 1st International Symposium on Latin American Theoretical Informatics, LATIN 1992 tenutosi a São Paulo; Brazil) [10.1007/BFb0023812].
File allegati a questo prodotto
File Dimensione Formato  
Alimonti_linear-time-algorithms_1992.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 741.92 kB
Formato Adobe PDF
741.92 kB Adobe PDF   Contatta l'autore

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/11573/1205038
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 8
social impact