J 2002

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

KUČERA, Antonín and Richard MAYR

Basic information

Original name

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

Authors

KUČERA, Antonín (203 Czech Republic, guarantor) and Richard MAYR (276 Germany)

Edition

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

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

20206 Computer hardware and architecture

Country of publisher

Netherlands

Confidentiality degree

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

Impact factor

Impact factor: 0.417

RIV identification code

RIV/00216224:14330/02:00004665

Organization unit

Faculty of Informatics

UT WoS

000173012000025

Keywords in English

concurrency; infinite-state systems; bisimilarity

Tags

Tags

International impact, Reviewed
Změněno: 22/11/2006 18:15, prof. RNDr. Antonín Kučera, Ph.D.

Abstract

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.

Links

GA201/00/0400, research and development project
Name: Nekonečně stavové souběžné systémy - modely a verifikace
Investor: Czech Science Foundation, Infinite state concurrent systems - models and verification
MSM 143300001, plan (intention)
Name: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů
Investor: Ministry of Education, Youth and Sports of the CR, Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing