Voltar
Artigo Acesso aberto Revisado por pares
BIBTEX RIS

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

2009; Elsevier BV; Volume: 109; Issue: 15 Linguagem: Inglês

10.1016/j.ipl.2009.04.003

ISSN

1872-6119

Autores

Sławomir Lasota,

Tópico(s)

Distributed systems and fault tolerance

Resumo

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].

Referência(s)