Detailed Information on Publication Record
2000
Some Remarks on Weak Bisimilarity of BPA-Processes
ČERNÁ, Ivana and Jitka STŘÍBRNÁBasic information
Original name
Some Remarks on Weak Bisimilarity of BPA-Processes
Authors
ČERNÁ, Ivana and Jitka STŘÍBRNÁ
Edition
Brno, 26 pp. FIMU-RS-2000-09, 2000
Publisher
FI MU Brno
Other information
Language
English
Type of outcome
Odborná kniha
Field of Study
10000 1. Natural Sciences
Country of publisher
Czech Republic
Confidentiality degree
není předmětem státního či obchodního tajemství
References:
RIV identification code
RIV/00216224:14330/00:00002688
Organization unit
Faculty of Informatics
Změněno: 26/2/2001 07:26, prof. RNDr. Ivana Černá, CSc.
Abstract
V originále
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.
Links
GA201/00/0400, research and development project |
| ||
GA201/99/D026, research and development project |
| ||
MSM 143300001, plan (intention) |
|