×

Towards the unification of models for concurrency. (English) Zbl 0758.68027

CAAP’90, Proc. 15th Colloq., Copenhagen/Denmark 1990, Lect. Notes Comput. Sci. 431, 162-176 (1990).
Summary: [For the entire collection see Zbl 0745.00027.]
The problem of the conceptual unification of the models for concurrent and distributed systems is addressed in terms of categories of graphs with algebraic structure. We model the semantics of a concrete process description language, in both its interleaving and its true concurrency versions. As a test case, we consider Milner’s calculus of communicating systems (CCS). Instead of defining a single model for CCS, we introduce categories whose objects are models, and where morphisms represent a specification-implementation relation. We start by showing that CCS models can be viewed as ordinary graphs equipped with additional structures over nodes and transitions. Labels are defined using a comma category construction. We then define special classes of morphisms expressing a notion of simplification and we show that observational congruences can be characterized in terms of final universal properties in the sub categories induced by such morphisms. In order to model the truly concurrent aspect of CCS, we write axioms which identify computations obtained by permuting independent transitions. By unfolding the resulting transition system, we obtain the domain of configurations of an event structure.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
18A25 Functor categories, comma categories
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
18A40 Adjoint functors (universal constructions, reflective subcategories, Kan extensions, etc.)
18C10 Theories (e.g., algebraic theories), structure, and semantics

Citations:

Zbl 0745.00027
PDFBibTeX XMLCite