Other formats:
BibTeX
LaTeX
RIS
@article{376211,
author = {Kučera, Antonín and Mayr, Richard},
article_location = {Amsterdam, Nizozemí},
article_number = {1-2},
keywords = {concurrency; infinite-state systems; bisimilarity},
language = {eng},
issn = {0304-3975},
journal = {Theoretical Computer Science},
title = {Weak Bisimilarity between Finite-State Systems and BPA or normed BPP is Decidable in Polynomial Time},
volume = {270},
year = {2002}
}
TY - JOUR
ID - 376211
AU - Kučera, Antonín - Mayr, Richard
PY - 2002
TI - Weak Bisimilarity between Finite-State Systems and BPA or normed BPP is Decidable in Polynomial Time
JF - Theoretical Computer Science
VL - 270
IS - 1-2
SP - 677
EP - 677
SN - 03043975
KW - concurrency
KW - infinite-state systems
KW - bisimilarity
N2 - 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.
ER -
KUČERA, Antonín and Richard MAYR. Weak Bisimilarity between Finite-State Systems and BPA or normed BPP is Decidable in Polynomial Time. \textit{Theoretical Computer Science}. Amsterdam, Nizozemí, vol.~270, 1-2, p.~677-700. ISSN~0304-3975. 2002.
|
