EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system

DOI10.1016/j.ipl.2009.04.003zbMath1205.68246OpenAlexW2029953169MaRDI QIDQ989507

Sławomir Lasota

Publication date: 20 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.04.003

zbMATH Keywords

Petri netconcurrencyBPP-netsimulation preorder and equivalencetrace preorder and equivalence

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (1)

Flatness and Complexity of Immediate Observation Petri Nets

Cites Work

• The covering and boundedness problems for vector addition systems
• Complexity of equivalence problems for concurrent systems of finite agents
• Strong bisimilarity of simple process algebras: Complexity lower bounds
• Simulation preorder over simple process algebras
• A lower bound on web services composition
• High undecidability of weak bisimilarity for Petri nets
• CONCUR 2003 - Concurrency Theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system