| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428075 | Information Processing Letters | 2009 | 6 Pages |
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].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
