J 2003

The Complexity of Bisimilarity-Checking for One-Counter Processes

KUČERA, Antonín

Základní údaje

Originální název

The Complexity of Bisimilarity-Checking for One-Counter Processes

Autoři

KUČERA, Antonín (203 Česká republika, garant)

Vydání

Theoretical Computer Science, Amsterdam, Nizozemí, Elsevier, 2003, 0304-3975

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.764

Kód RIV

RIV/00216224:14330/03:00008108

Organizační jednotka

Fakulta informatiky

UT WoS

000184305300007

Klíčová slova anglicky

concurrency; one-counter automata; bisimilarity

Štítky

Příznaky

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

Anotace

V originále

We study the problem of bisimilarity-checking between processes of one-counter automata and finite-state processes. We show that deciding weak bisimilarity between processes of one-counter nets and finite-state processes is DP-hard. Then we design an algorithm which decides weak bisimilarity between processes of one-counter automata and finite-state processes in time which is polynomial for a large subclass of instances, giving a kind of characterization of all hard instances as a byproduct.

Návaznosti

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ů