On the Complexity of Checking Semantic Equivalences between Pushdown Processes and Finite-state Processes
| Autoři | |
|---|---|
| Rok publikování | 2010 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Information and Computation |
| Fakulta / Pracoviště MU | |
| Citace | |
| Obor | Informatika |
| Klíčová slova | pushdown automata; verification; simulation; bisimulation |
| Popis | Simulační preorder/ekvivalence a bisimulační ekvivalence jsou hojně využívány v teorii souběžnosti. Ve své standardní podobě jsou obvykle označovány jako "silná" simulační resp. bisimulační ekvivalence, zatímco ve své "slabé" podobě tyto relace abstrahují od interních tau-akcí. V článku je studována výpočetní složitost problému simulační a bisimulační ekvivalence mezi procesy zásobníkových automatů a procesy s konečně mnoha stavy. |
| Související projekty: |