![Jak na přijímačky](https://cdn.muni.cz/media/3633702/image_1.jpg?mode=crop¢er=0.5,0.5&rnd=133572412150000000&heightratio=0.5&width=278)
Informace o publikaci
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 | |
Rok publikování | 2004 |
Druh | Článek v odborném periodiku |
Časopis / Zdroj | Information and Computation |
Fakulta / Pracoviště MU | |
Citace | |
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: |