Publication details

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

Investor logo

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

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.

More info