KUČERA, Antonín and Richard MAYR. Weak Bisimilarity between Finite-State Systems and BPA or normed BPP is Decidable in Polynomial Time. Theoretical Computer Science, Amsterdam, Nizozemí, 2002, vol. 270, 1-2, p. 677-700. ISSN 0304-3975.
Other formats:   BibTeX LaTeX RIS
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
Original language English
Type of outcome article in a journal
Field of Study 20206 Computer hardware and architecture
Country of publisher Netherlands
Confidentiality degree is not subject to a state or trade secret
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 bisimilarity, concurrency, infinite-state systems
Tags International impact, Reviewed
Changed by Changed by: prof. RNDr. Antonín Kučera, Ph.D., učo 2508. Changed: 22/11/2006 18:15.
Abstract
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 projectName: Nekonečně stavové souběžné systémy - modely a verifikace
Investor: Czech Science Foundation, Standard Projects
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, Research Intents
PrintDisplayed: 7/4/2020 15:03