Simulation Preorder over Simple Process Algebras

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors	KUČERA Antonín MAYR Richard
Year of publication	2002
Type	Article in Periodical
Magazine / Source	Information and Computation
MU Faculty or unit	Faculty of Informatics
Citation
Field	Computer hardware and software
Keywords	concurrency; process algebras; simulation equivalence
Description	We consider the problem of simulation preorder/equivalence between infinite-state processes and finite-state ones. First, we describe a general method how to utilize the decidability of bisimulation problems to solve (certain instances of) the corresponding simulation problems. For certain process classes, the method allows to design effective reductions of simulation problems to their bisimulation counterparts and some new decidability results for simulation have already been obtained in this way. Then we establish the decidability/tractability border for the problem of simulation preorder/equivalence between infinite-state processes and finite-state ones w.r.t. the hierarchy of process rewrite systems.
Related projects:	Infinite state concurrent systems - models and verification Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing