Package jline.api.spn

Class Spn_siphons

java.lang.Object
jline.api.spn.Spn_siphons
public class Spn_siphons extends Object
All minimal siphons of a stochastic Petri net, and Commoner's check that each one contains an initially marked trap.

A siphon is a non-empty set S of place levels with *S contained in S*: once empty it stays empty. A trap Q has Q* contained in *Q: once marked it stays marked. Commoner's property (every minimal siphon contains a marked trap) is decided per siphon by marking the largest trap inside it; for the underlying ordinary net it implies deadlock freedom, for an asymmetric-choice net liveness, and for an extended-free-choice net it is equivalent to liveness. Structural: inhibitor arcs, priorities and immediate precedence are ignored.

The enumeration is a complete, duplicate-free branch and bound over the levels forced in or out, bounded by the largest siphon inside the allowed levels. Each search node costs O(n^3 E), but the number of minimal siphons can be exponential in n and deciding whether a minimal siphon contains a given place is NP-complete, so the worst case is exponential.

References: T. Murata, Proc. IEEE 77(4) (1989), Sec. VI-B; R. Cordone, L. Ferrarini, L. Piroddi, IEEE Trans. SMC-A 35(6) (2005) 844-854.

  • Method Details

    • spn_siphons

      public static Spn_siphons.SpnSiphons spn_siphons(NetworkStruct sn)

    • spn_siphons

      public static Spn_siphons.SpnSiphons spn_siphons(NetworkStruct sn, double[] init)
      Minimal siphons and Commoner's property.
      Parameters:
      sn - a NetworkStruct of a closed model holding Places and Transitions
      init - initial tokens per place level, place-major; null reads the marking declared on the Places, and failing that the reference station populations
      Returns:
      the siphons