Enriched categorical semantics for distributed calculi
type: Item
instance of: scholarly article
title: Enriched categorical semantics for distributed calculi
zbMATH Open document ID: 0777.18007
DOI: 10.1016/0022-4049(92)90048-K
author: Stefano Kasangian
author: Anna Labella
published in: Journal of Pure and Applied Algebra
publication date: 1993-05-16T00:00:00Z
review text: The authors propose a general categorical framework in which many of the existing proposals for the mathematical semantics of the interaction between concurrent or parallel computations can be expressed and, therefore, compared. They propose a two-tier formalization of synchronization between (concurrent) computing agents. At the first level we find computations, described as labelled trees. Formally, they introduce the topos of labelled budding trees (constructed out of the topos of labelled \(A\)-trees, \({\mathbf T}/F(A)\), which is a monoidal category with respect to a notion of concatenation between trees. Since this topos, however, if not monoidal closed, its reflective subcategory \({\mathbf N}{\mathbf T}\) of nice trees is introduced, which turns out to be monoidal closed (but not biclosed, a fact which accounts for nondeterminism). Finally, an operation of synchronization is introduced on \({\mathbf N}{\mathbf T}\) and shown to be a monoidal functor. The second level of the proposed semantics aims to model processes and computations among them, described as enriched categories over \({\mathbf N}{\mathbf T}\). Synchronization among processes is obtained by lifting to the enriched structure the corresponding operation of the base monoidal category. Particular relevance assumes a notion of hereditary fullness, characterizing the ``good semantics''. With this set up, the concepts of relabelling, restrictions, insertion and deletion of idle moves are then described, with particular emphasis of the comparison with similar operations of other formal descriptions (e.g., CCS and ACP). The paper tries to motivate the formal notions through intuitive operations on computations and the analogy with regular languages and automata.
reviewed by: Simone Martini
Mathematics Subject Classification ID: 18D20
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68Q55
Mathematics Subject Classification ID: 18B25
zbMATH DE Number: 166158
zbMATH Keywords: concurrency
zbMATH Keywords: monoidal closed category
zbMATH Keywords: CCS
zbMATH Keywords: parallel computations
zbMATH Keywords: labelled trees
zbMATH Keywords: synchronization
MaRDI profile type: Publication
cites work: Algèbre de processus et synchronisation
cites work: Q3682648
cites work: Algebra of communicating processes with abstraction
cites work: Q3904750
cites work: Q3692876
cites work: A Theory of Communicating Sequential Processes
cites work: Q3956374
cites work: Q4746776
cites work: Q3677155
cites work: Extensional equivalences for transition systems
cites work: Testing equivalences for processes
cites work: Q5586461
cites work: Communicating sequential processes
cites work: Q4145861
cites work: Q3667049
cites work: Q3780423
cites work: Q3028349
cites work: Q3934579
cites work: Q4728237
cites work: Metric spaces, generalized logic, and closed categories
cites work: A calculus of communicating systems
cites work: Calculi for synchrony and asynchrony
cites work: Q3683531
full work available at URL: 0022-4049(92)90048-k
OpenAlex ID: W2086295015
description: scientific article; zbMATH DE number 166158