On the complexity of the linear-time μ-calculus for Petri Nets

DOI10.1007/3-540-63139-9_32zbMath1523.68041MaRDI QIDQ6487371

Peter Habermehl

Publication date: 9 December 2022

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Temporal logic (03B44)

Related Items (9)

Equivalence Between Model-Checking Flat Counter Systems and Presburger Arithmetic ⋮ Equivalence between model-checking flat counter systems and Presburger arithmetic ⋮ Reasoning about equilibria in game-like concurrent systems ⋮ On selective unboundedness of VASS ⋮ Strategic reasoning with a bounded number of resources: the quest for tractability ⋮ On the complexity of resource-bounded logics ⋮ Model checking for process rewrite systems and a class of action-based regular properties ⋮ EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The covering and boundedness problems for vector addition systems
• Reasoning about infinite computations
• A multiparameter analysis of the boundedness problem for vector addition systems
• Verifying programs with unreliable channels
• Relationships between nondeterministic and deterministic tape complexities
• Temporal logic can be more expressive
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Infinite results

This page was built for publication: On the complexity of the linear-time μ-calculus for Petri Nets