Bisimulations and abstraction homomorphisms. (English) Zbl 0563.68028

Mathematical foundations of software development, Proc. Int. Conf., Berlin 1985, Vol. 1: Colloq. Trees in algebra and programming, Lect. Notes Comput. Sci. 185, 223-238 (1985).
[For the entire collection see Zbl 0561.00021.]
In this paper we show that the notion of bisimulation for a class of labelled transition systems (the class of nondeterministic processes) may be restated as one of ”reducibility to a same system” via a simple reduction relation. The reduction relation is proven to enjoy some desirable properties, notably a Church-Rosser property. We also show that, when restricted to finite nondeterministic processes, the relation yields unique minimal forms for processes and can be characterized algebraically by a set of reduction rules.


68N25 Theory of operating systems


Zbl 0561.00021