Prioritised Petri Net¶
A Petri net whose firing rule suppresses an enabled transition while an eligible higher-priority transition exists.
Core Idea¶
A prioritised Petri net is a Petri net whose transition-firing rule consults a declared priority relation after ordinary marking-based enabling. At a given marking, determine which transitions have the required tokens. An ordinarily enabled transition cannot fire if another currently eligible transition outranks it under the chosen priority semantics. Remaining highest-priority transitions can still present a choice; priority does not necessarily choose a unique winner. Numerical levels are one way to express the order, not an all-instance requirement.[ref-0b41251b6c23][ref-eafff955bf46]
Araki and Kasami study a generalized net in which one distinguished transition has priority over others. Chiola and colleagues study generalized stochastic Petri nets (GSPNs) with immediate transitions prioritized over timed transitions and, in their revised model, multiple immediate priority levels. These are unlike formal and applied settings that share the enabled-transition filter, while their timing, weights, and decision-problem results remain variant-specific.[ref-0b41251b6c23][ref-eafff955bf46]
Scope of Application¶
Araki and Kasami's 1976 original publisher abstract supplies the formal-decision setting. It states that a generalized Petri net in which one distinguished transition has priority over the others has undecidable coverability and reachability. The abstract establishes the bounded claim; it does not expose every arc and proof detail needed to reconstruct the theorem. The priority-net identity used here is the net and its priority rule, not the undecidability consequence.[^ref-0b41251b6c23]
Chiola, Ajmone Marsan, Balbo, and Conte's 1993 original paper supplies a different setting: GSPN modeling. Timed transitions have exponentially distributed firing delays; immediate transitions fire in zero time and take priority over timed transitions when both are eligible. Their revised net-level specification assigns timed transitions the lowest level, permits higher levels among immediate transitions, and uses positive weights in defined conflict sets to select among competing immediate transitions. These clocks and weights define that GSPN variant, not the minimum identity of prioritisation.[^ref-eafff955bf46]
The paper's flexible manufacturing system (FMS) example makes the priority filter operational. In its Fig. 9 model, the authors give immediate transitions loadX1 and loadX2 priority level 2 over other transitions in subnet T1 to remove the particular confusion they analyze. Weights still govern remaining immediate choices. This example supports that one model's selection policy; it does not establish a general unload-before-load rule, universal deadlock prevention, or deterministic scheduling of every manufacturing system.[^ref-eafff955bf46]
Clarity¶
At each marking, perform the tests in order. First, apply the ordinary token enabling rule. Second, compare the enabled transitions using the declared priority order. Third, exclude any lower-priority enabled transition while an eligible higher one exists. Finally, apply the model's tie, timing, or weight rule to the survivors. Reversing the first two steps would let a disabled high-priority transition suppress an enabled low-priority one, which is not the intended firing condition.[^ref-eafff955bf46]
“Conflict” needs precision. Priority can restrict firings even if the two transitions do not share an input place, depending on the net's semantics. Conversely, equal-priority transitions can remain in conflict. Neither “has a priority label” nor “resolves all conflict” is an adequate membership test.[^ref-eafff955bf46]
Manages Complexity¶
Ordinary Petri nets express concurrent possibilities through markings and enabled firings. Priority adds a compact policy that removes some enabled choices based on rank rather than by rebuilding all token flow. In Chiola's GSPN, this distinguishes zero-time immediate events from timed ones and permits an extra priority layer inside the immediate class. The paper uses the net-level structure to reason about conflict and probabilistic selection.[^ref-eafff955bf46]
This convenience changes behavior and can alter formal decision properties in some extensions. Araki and Kasami's generalized-net result is a warning that a small-looking firing-rule addition can affect reachability analysis. It is not a complexity theorem for every priority scheme; any transfer of that theorem must preserve the exact formal variant and assumptions.[ref-0b41251b6c23][ref-eafff955bf46]
Abstract Reasoning¶
Consider two ordinarily enabled transitions at one marking, with the declared order placing High (computability) above low. The priority rule removes low from the next-firing set while High (computability) remains eligible. If High (computability) loses enabling after a marking update, low may become fireable again. This illustrates the marking-relative filter; it is not a claim about the specific arcs of Araki and Kasami's theorem net.[^ref-eafff955bf46]
If two transitions share the same maximal level, priority alone leaves both in the set. A GSPN may assign selection weights, while another priority-net variant may leave nondeterminism. Remove all priority filtering yet keep the same Petri-net graph and the result is still a Petri net, but not a prioritised one. Remove the place-transition/token carrier and the ranking becomes some other scheduling system.[^ref-eafff955bf46]
Knowledge Transfer¶
The formal and FMS/GSPN cases share the same four roles. Each has a Petri-net marking and ordinary eligible set, a priority comparison, and a restricted firing set. Araki and Kasami's abstract identifies the privileged-transition extension; Chiola's full paper shows levels, immediate/timed preemption, and a worked manufacturing model. The common identity is the filter. A detailed theorem from the generalized formal net does not transfer automatically to a stochastic GSPN, and the GSPN weights do not become mandatory in the untimed net.[ref-0b41251b6c23][ref-eafff955bf46]
The transfer extends to other discrete-event models only after verifying the token-net carrier and an actual firing-rule priority filter. Describing an emergency task as “high priority” without changing enabled-transition firing is an analogy, not an instance of this Petri-net subclass.[^ref-eafff955bf46]
Example¶
Generalized one-priority net. Carrier: the generalized Petri net in Araki and Kasami's original abstract. Priority relation: one distinguished transition outranks the others. Enabled set: transitions eligible at a marking under that generalized net's rule. Filter: when the distinguished transition is enabled, its lower-priority alternatives cannot fire. The abstract reports undecidable coverability and reachability for this class; it does not furnish a fully reproduced construction here, so no proof-step or universal zero-test mechanism is asserted.[^ref-0b41251b6c23]
FMS GSPN. Carrier: Chiola and colleagues' Fig. 9 net for pallets, part routes, and machines. Priority relation: immediate firings outrank timed firings, and loadX1/loadX2 receive priority 2 above other T1 immediate transitions. Enabled set: the transitions whose input conditions hold at a marking. Filter: eligible higher-priority loading transitions preempt eligible lower ones in the analyzed part of the model. Residual selection: weights choose among competing immediate transitions in the paper's defined extended conflict sets. The priority assignment removes a specific confusion in this model; it is not a general manufacturing liveness theorem.[^ref-eafff955bf46]
Relationships to Other Abstractions¶
Current abstraction Prioritised Petri Net Domain-specific
Parents (1) — more general patterns this builds on
-
Prioritised Petri Net is a kind of Petri net Domain-specific
Every prioritised Petri net retains a marking-based place-transition token net and adds a priority-restricted firing rule.
Hierarchy path (1) — routes to 1 parentless root
- Prioritised Petri Net → Petri net → Network → Reservoir-Flux Network → Conservation Laws → Invariance
Neighborhood in Abstraction Space¶
Prioritised Petri Net sits in a sparse region of the domain-specific corpus (92nd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2551 abstractions)
Nearest neighbors
- Petri net — 0.81
- Automaton — 0.80
- Navigation loop — 0.79
- Operator-precedence grammar — 0.79
- Logic Synthesis — 0.79
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
A bare timed stochastic net need not include priority; a coloured token net changes token types rather than ranking enabled firings. Higher-priority disabled transitions do not block merely by existing, while equal-level enabled transitions need not resolve deterministically. Araki and Kasami's priority extension and their separate reset-to-zero extension must not be conflated. Their generalized-net undecidability result does not automatically apply to Chiola's GSPN or to every priority Petri net.[ref-0b41251b6c23][ref-eafff955bf46]
References¶
[^ref-0b41251b6c23]: Toshiro Araki and Tadao Kasami, “Some Decision Problems Related to the Reachability Problem for Petri Nets”, Theoretical Computer Science 3(1), 1976, pp. 85–104, publisher abstract numbered results (4)–(5). DOI: 10.1016/0304-3975(76)90067-0. The original abstract supports the one-privileged-transition generalized-net undecidability claim and treats reset transitions separately; full proof and construction pages were not independently inspected.
[^ref-eafff955bf46]: Giovanni Chiola, Marco Ajmone Marsan, Gianfranco Balbo, and Gianni Conte, “Generalized Stochastic Petri Nets, A Definition at the Net Level and Its Implications”, original IEEE Transactions on Software Engineering 19(2), 1993, pp. 89–107, Introduction and §V on net dynamics; §VI.A–B pp. 100–102 on revised priority/weight semantics; §VII Fig. 9 and pp. 104–105 on the flexible-manufacturing example. DOI: 10.1109/32.214828. The printed original title uses a colon after “Nets”; the comma in this linked label preserves the full title in the reference binder. Author-uploaded full original article; unlike the Araki–Kasami abstract, these model details were inspected.