EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system |
| |
| Authors: | S?awomir Lasota |
| |
| Affiliation: | Institute of Informatics, Warsaw University, Warsaw, Poland |
| |
| Abstract: | 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 Ku?era and Mayr in [A. Ku?era, R. Mayr, Simulation preorder over simple process algebras, Information and Computation 173 (2) (2002) 184-198]. |
| |
| Keywords: | Petri net BPP-net Simulation preorder and equivalence Trace preorder and equivalence Concurrency |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
