On the Complexity of Checking Semantic Equivalences between Pushdown Processes and Finite-state Processes
| Authors | |
|---|---|
| Year of publication | 2010 |
| Type | Article in Periodical |
| Magazine / Source | Information and Computation |
| MU Faculty or unit | |
| 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: |