On the Complexity of Checking Semantic Equivalences between Pushdown Processes and Finite-state Processes

Investor logo

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 2010
Type Article in Periodical
Magazine / Source Information and Computation
MU Faculty or unit

Faculty of Informatics

Citation
Field Informatics
Keywords pushdown automata; verification; simulation; bisimulation
Description Simulation preorder/equivalence and bisimulation equivalence are the most commonly used equivalences in concurrency theory. Their standard definitions are often called strong simulation/bisimulation, while weak simulation/bisimulation abstracts from internal tau-actions. We study the computational complexity of checking these strong and weak semantic preorders/equivalences between pushdown processes and finite-state processes.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.