JANČAR, Petr, Antonín KUČERA, Faron MOLLER a Zdeněk SAWA. DP lower bounds for equivalence-checking and model-checking of one-counter automata. Information and Computation, Academic Press, 2004, roč. 188, č. 1, s. 1-19. ISSN 0890-5401.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název 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 (203 Česko), Antonín KUČERA (203 Česko, garant), Faron MOLLER (826 Velká Británie) a Zdeněk SAWA (203 Česko).
Vydání Information and Computation, Academic Press, 2004, 0890-5401.
Další údaje
Originální jazyk angličtina
Typ výsledku Článek v odborném periodiku
Obor 10201 Computer sciences, information science, bioinformatics
Stát vydavatele Spojené státy
Utajení není předmětem státního či obchodního tajemství
Impakt faktor Impact factor: 0.920
Kód RIV RIV/00216224:14330/04:00009891
Organizační jednotka Fakulta informatiky
UT WoS 000187574200001
Klíčová slova anglicky one-counter automata; equivalence-checking; bisimilarity
Štítky bisimilarity, Equivalence-Checking, one-counter automata
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: prof. RNDr. Antonín Kučera, Ph.D., učo 2508. Změněno: 22. 11. 2006 18:22.
Anotace
We present a general method for proving DP-hardness of problems related to formal verification of one-counter automata. For this we show a reduction of the SAT-UNSAT problem to the truth problem for a fragment of (Presburger) arithmetic. The fragment contains only special formulas with one free variable, and is particularly apt for transforming to simulation-like equivalences on one-counter automata. In this way we show that the membership problem for any relation subsuming bisimilarity and subsumed by simulation preorder is DP-hard (even) for one-counter nets (where the counter cannot be tested for zero). We also show DP-hardness for deciding simulation between one-counter automata and finite-state systems (in both directions), and for the model-checking problem with one-counter nets and the branching-time temporal logic EF.
Anotace česky
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.
Návaznosti
GA201/00/0400, projekt VaVNázev: Nekonečně stavové souběžné systémy - modely a verifikace
Investor: Grantová agentura ČR, Standardní projekty
GA201/03/1161, projekt VaVNázev: Verifikace nekonečně stavových systémů
Investor: Grantová agentura ČR, Standardní projekty
MSM 143300001, záměrNázev: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumné záměry
VytisknoutZobrazeno: 3. 7. 2020 17:02