Structural Liveness of Immediate Observation Petri Nets
From MaRDI portal
Abstract: We look in detail at the structural liveness problem (SLP) for subclasses of Petri nets, namely immediate observation nets (IO nets) and their generalized variant called branching immediate multi-observation nets (BIMO nets), that were recently introduced by Esparza, Raskin, and Weil-Kennedy. We show that SLP is PSPACE-hard for IO nets and in PSPACE for BIMO nets. In particular, we discuss the (small) bounds on the token numbers in net places that are decisive for a marking to be (non)live.
Recommendations
Cites work
- Complexity of some problems in Petri nets
- Computation in networks of passively mobile finite-state sensors
- Efficient restrictions of immediate observation Petri nets
- Existence of home states in Petri nets is decidable
- Flatness and Complexity of Immediate Observation Petri Nets
- Free Choice Petri Nets
- scientific article; zbMATH DE number 1059894 (Why is no real title available?)
- Structural liveness of Petri nets is \textsc{ExpSpace}-hard and decidable
- The computational power of population protocols
Cited in
(7)- Deciding Structural Liveness of Petri Nets
- scientific article; zbMATH DE number 5079405 (Why is no real title available?)
- Critical Observability for Automata and Petri Nets
- Liveness and boundedness analysis of Petri net synthesis
- Parameterized Analysis of Immediate Observation Petri Nets
- Structural liveness of conservative Petri nets
- Temporal hyperproperties for population protocols
This page was built for publication: Structural Liveness of Immediate Observation Petri Nets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6044494)
