DP lower bounds for equivalence-checking and model-checking of one-counter automata

• Název česky: DP dolní složitostní odhady pro problémy související s formální verifikací automatů s jedním čítačem
• Autoři: JANČAR Petr; KUČERA Antonín; MOLLER Faron; SAWA Zdeněk
• Rok publikování: 2004
• Druh: Článek v odborném periodiku
• Časopis / Zdroj: Information and Computation
• Fakulta / Pracoviště MU: Fakulta informatiky
• Obor: Informatika
• Klíčová slova: one-counter automata; equivalence-checking; bisimilarity
• Popis: Je podána obecná metoda pro dokazování DP dolního složitostního odhadu pro problémy související s formální verifikací automatů s jedním čítačem. Za tímto účelem je prezentována redukce problému SAT-UNSAT na problém platnosti formulí vhodného fragmentu Presburgerovy aritmetiky. Tento fragment obsahuje pouze formule s jednou volnou proměnnou a je velmi vhodný pro redukci na problém simulačních ekvivalencí mezi procesy automatů s jedním čítačem. Tímto způsobem je prokázána DP-těžkost libovolné ekvivalence mezi simulační a bisimulační ekvivalencí. Je také dokázána DP-těžkost problému ověřování platnosti formulí temporální logiky EF.

Související projekty

• Nekonečně stavové souběžné systémy - modely a verifikace
• Verifikace nekonečně stavových systémů
• Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů