J 2002

Weak Bisimilarity between Finite-State Systems and BPA or normed BPP is Decidable in Polynomial Time

KUČERA, Antonín a Richard MAYR

Základní údaje

Originální název

Weak Bisimilarity between Finite-State Systems and BPA or normed BPP is Decidable in Polynomial Time

Autoři

KUČERA, Antonín (203 Česká republika, garant) a Richard MAYR (276 Německo)

Vydání

Theoretical Computer Science, Amsterdam, Nizozemí, 2002, 0304-3975

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

20206 Computer hardware and architecture

Stát vydavatele

Nizozemské království

Utajení

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

Impakt faktor

Impact factor: 0.417

Kód RIV

RIV/00216224:14330/02:00004665

Organizační jednotka

Fakulta informatiky

UT WoS

000173012000025

Klíčová slova anglicky

concurrency; infinite-state systems; 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 prove that weak bisimilarity is decidable in polynomial time between finite-state systems and several classes of infinite-state systems: context-free processes (BPA) and normed Basic Parallel Processes (normed BPP). To the best of our knowledge, these are the first polynomial algorithms for weak bisimilarity problems involving infinite-state systems.

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
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ů