Bisimulations and abstraction homomorphisms. (English) Zbl 0563.68028

Castellani, Ilaria

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.

MSC:

68N25

Theory of operating systems

Keywords:

abstraction homomorphisms; bisimulation; labelled transition systems; nondeterministic processes; Church-Rosser property

Citations:

Zbl 0561.00021