Structural liveness of Petri nets is \textsc{ExpSpace}-hard and decidable

DOI10.1007/S00236-019-00338-6MaRDI QIDQ2317836zbMATH OpenOpenAlexWikidataFDO

Authors Petr Jančar, David Purser

Publication date 13 August 2019

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00236-019-00338-6

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Deciding Structural Liveness of Petri Nets
• scientific article; zbMATH DE number 1354143
• Complexity results for 1-safe nets
• Decidability of the Petri net reachability problem
• The complexity of problems involving structurally bounded and conservative Petri nets

Cites work

• Algorithmic analysis of programs with well quasi-ordered domains.
• An Algorithm for the General Petri Net Reachability Problem
• Deciding Structural Liveness of Petri Nets
• Existence of home states in Petri nets is decidable
• Forward analysis for WSTS. II: Complete WSTS
• Free Choice Petri Nets
• scientific article; zbMATH DE number 3582425 (Why is no real title available?)
• scientific article; zbMATH DE number 1302047 (Why is no real title available?)
• Marked directed graphs
• On liveness and controlled siphons in Petri nets
• Petri Nets and Marked Graphs--Mathematical Models of Concurrent Computation
• Presburger vector addition systems
• Semigroups, Presburger formulas, and languages
• Some complexity results for polynomial ideals
• The complexity of the word problems for commutative semigroups and polynomial ideals
• The covering and boundedness problems for vector addition systems
• The reachability problem for Petri nets is not elementary
• Understanding Petri Nets
• Well-structured transition systems everywhere!

Cited in

(9)

• Population protocols: beyond runtime analysis
• Deciding Structural Liveness of Petri Nets
• Liveness of safe object nets
• Structurally cyclic Petri nets
• Co-finiteness and co-emptiness of reachability sets in vector addition systems with states
• Necessary and sufficient liveness condition of GS³PR Petri nets
• Structural Liveness of Immediate Observation Petri Nets
• Structural liveness of conservative Petri nets
• Macro liveness graph and liveness of -independent unbounded nets

Describes a project that uses

Uses Software

• Easychair

This page was built for publication: Structural liveness of Petri nets is \textsc{ExpSpace}-hard and decidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2317836)