A metric characterization of fair computations in CCS. (English) Zbl 0563.68024

Costa, Gerardo

Mathematical foundations of software development, Proc. Int. Conf., Berlin 1985, Vol. 1: Colloq. Trees in algebra and programming, Lect. Notes Comput. Sci. 185, 239-252 (1985).

[For the entire collection see Zbl 0561.00021.]
We address the problem of characterizing fair (infinite) behaviours of concurrent systems as limits of finite approximations. The framework chosen is Milner’s Calculus of Communicating Systems. The results can be summarized as follows. On the set FD of all finite derivations in the calculus we define three distances: da, dw, ds. Then the metric completion of (FD,da) yields the space of all derivations, while the completion of (FD,dw), resp. (FD,ds), yields the space of all finite derivations together with all - and only - the weakly, resp. strongly, fair computations (i.e. non-extendable derivations). The results concerning da and dw are a reformulation of previously known ones, while that concerning ds is - we believe - new.

MSC:

68N25

Theory of operating systems

Keywords:

concurrent systems; Calculus of Communicating Systems; fair computations

Citations:

Zbl 0561.00021