Benutzer: Gast  Login
Titel:

Simulation Preorder on Simple Process Algebras

Dokumenttyp:
Technical Report
Autor(en):
Antonin Kucera; Richard Mayr
Abstract:
We consider the problem of simulation preorder/equivalence between infinite-state processes and finite-state ones. We prove that simulation preorder (in both directions) and simulation equivalence are intractable between all major classes of infinite-state systems and finite-state ones. This result is obtained by showing that the problem whether a BPA (or BPP) process simulates a finite-state one is PSPACE-hard, and the other direction is coNP-hard; consequently, simulation equivalence between...     »
Stichworte:
concurrency; infinite-state systems; process algebras; verification; simulation
Jahr:
1999
Jahr / Monat:
1999-01-01 00:00:00
Seiten/Umfang:
25
 BibTeX