J 2004

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

JANČAR, Petr, Antonín KUČERA, Faron MOLLER a Zdeněk SAWA

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 Česká republika), Antonín KUČERA (203 Česká republika, garant), Faron MOLLER (826 Velká Británie a Severní Irsko) a Zdeněk SAWA (203 Česká republika)

Vydání

Information and Computation, Academic Press, 2004, 0890-5401

Další údaje

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

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 22. 11. 2006 18:22, prof. RNDr. Antonín Kučera, Ph.D.

Anotace

ORIG CZ

V originále

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.

Č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 VaV
Název: Nekonečně stavové souběžné systémy - modely a verifikace
Investor: Grantová agentura ČR, Nekonečně stavové souběžné systémy - modely a verifikace
GA201/03/1161, projekt VaV
Název: Verifikace nekonečně stavových systémů
Investor: Grantová agentura ČR, Verifikace nekonečně stavových systémů
MSM 143300001, záměr
Ná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, Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů