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

Kód výsledku v IS VaVaI

RIV/00216224:14330/02:00004665 - isvavai.cz

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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, theseare the first polynomial algorithms for weak bisimilarity problems involving infinite-state systems.

Název v anglickém jazyce

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

Popis výsledku anglicky

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, theseare the first polynomial algorithms for weak bisimilarity problems involving infinite-state systems.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

JC - Počítačový hardware a software

OECD FORD obor

—

Projekt

GA201/00/0400: Nekonečně stavové souběžné systémy - modely a verifikace

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2002

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

270

Číslo periodika v rámci svazku

1-2

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

24

Strana od-do

677

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—