Branching bisimilarity is an equivalence indeed!

被引：64

作者：

Basten, T

机构：

[1] Dept. of Math. and Computing Science, Eindhoven University of Technology, 5600 MB Eindhoven

来源：

INFORMATION PROCESSING LETTERS | 1996年 / 58卷 / 03期

关键词：

formal semantics; concurrency theory; branching bisimilarity;

D O I：

10.1016/0020-0190(96)00034-8

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This note presents a detailed proof of a result in the theory of concurrency semantics that is already considered folklore, namely that branching bisimilarity is an equivalence relation. The ''simple proof'', which in the literature is always assumed to exist, is shown to be incorrect. The proof in this note is based on the notion of a semi-branching bisimulation taken from (Van Glabbeek and Weijland, 1991). Branching bisimilarity can equivalently be defined in terms of semi-branching bisimulations; the results suggest that such a definition is more intuitive than the original definition of Van Glabbeek and Weijland (1989).

引用

页码：141 / 147

页数：7

共 13 条

[1]

[Anonymous], 1980, CALCULUS COMMUNICATI, DOI DOI 10.1007/3-540-10235-3

[2]

Baeten J.C.M., 1990, Cambridge Tracts in Theoretical Computer Science, V18

[3] STRUCTURAL OPERATIONAL SEMANTICS FOR WEAK BISIMULATIONS [J].

BLOOM, B .

THEORETICAL COMPUTER SCIENCE, 1995, 146 (1-2) :25-68

[4]

CHERIEF F, 1990, PROCESS LETT, V40, P219

[5]

Darondeau P., 1991, Fundamenta Informaticae, V14, P221

[6] 3 LOGICS FOR BRANCHING BISIMULATION [J].

DENICOLA, R ;

VAADRAGER, F .

JOURNAL OF THE ACM, 1995, 42 (02) :458-487

[7]

DENICOLA R, 1990, LECT NOTES COMPUT SC, V458, P152

[8]

Van Glabbeek R. J., 1989, Information Processing 89. Proceedings of the IFIP 11th World Computer Congress, P613

[9]

van Glabbeek R.J., 1993, Lecture Notes in Computer Science, V715, P66, DOI [10.1007/3-540-57208-26, 10.1007/3-540-57208-2_6, DOI 10.1007/3-540-57208-2_6, DOI 10.1007/3-540-57208-26]

[10]

VANGLABBEEK RJ, IN PRESS J ACM

← 1 2 →