EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system
We investigate the simulation preorder between finite-state systems and a simple subclass of BPP-nets (communication-free nets). We show EXPSPACE lower bounds for the simulation problems, in both directions, as well as for the simulation equivalence. Our results improve PSPACE and co-NP lower bounds for the simulation between finite-state systems and BPP-nets, given by Kucera and Mayr in [A. Kucera, R. Mayr, Simulation preorder over simple process algebras, Information and Computation 173 (2) (2002) 184-198]. (C) 2009 Elsevier B.V. All rights reserved.
petri net bpp-net simulation preorder and equivalence trace preorder and equivalence concurrency