Další formáty:
BibTeX
LaTeX
RIS
@book{345554,
author = {Černá, Ivana and Stříbrná, Jitka},
address = {Brno},
language = {eng},
location = {Brno},
publisher = {FI MU Brno},
title = {Some Remarks on Weak Bisimilarity of BPA-Processes},
url = {http://www.fi.muni.cz/informatics/reports/},
year = {2000}
}
TY - BOOK
ID - 345554
AU - Černá, Ivana - Stříbrná, Jitka
PY - 2000
TI - Some Remarks on Weak Bisimilarity of BPA-Processes
VL - FIMU-RS-2000-09
PB - FI MU Brno
CY - Brno
UR - http://www.fi.muni.cz/informatics/reports/
N2 - The purpose of this work is to examine the decidability problem of weak bisimilarity for BPA-processes. It has been known that strong bisimilarity, which may be considered a special case of weak bisimilarity, where the internal (silent) action tau is treated equally to observable actions, is decidable for BPA-processes. For strong bisimilarity, these processes are finitely branching and so for two non-bisimilar processes there exists a level n that distinguishes the two processes. Additionally, from the decidability of whether two processes are equivalent at a given level n, semidecidability of strong non-bisimilarity directly follows. We examine the following two closely related approaches to semidecidability of strong equivalence: 1.construction of a (finite) bisimulation or expansion tree, 2.construction of a finite Caucal base. We have attempted to find out if any of the above mentioned approaches could be generalized to (semi)decide weak bisimilarity. Our findings indicate that a direct generalization is not sufficient and an efficient (semi)decision procedure cannot be obtained in this way.
ER -
ČERNÁ, Ivana a Jitka STŘÍBRNÁ. \textit{Some Remarks on Weak Bisimilarity of BPA-Processes}. Brno: FI MU Brno, 2000, 26 s. FIMU-RS-2000-09.
|
