Mixed Relations as Enriched Semiringal Categories

This paper is included in a series aiming to contribute to the algebraic theory of distributed computation. The key problem in understanding Multi-Agent Systems is to find a theory which integrates the reactive part and the control part of such systems. The claim of this series of papers is that the mixture of the additive and multiplicative network algebras (MixNA) will contribute to the understanding of distributed computation.

A study of the classes of finite relations as enriched strict monoidal categories is presented in \cite{ca-st91}. The relations there are interpreted as connections in flowchart schemes, hence an “angelic” theory of relations is used. Finite relations may be used to model the connections between the components of dataflow networks \cite{be-st95b,br-st96}, as well. The corresponding algebras are slightly different enriched strict monoidal categories modelling a “forward-demonic” theory of relations.

In order to obtain a full model for parallel programs one needs to mix control and reactive parts, hence a richer theory of finite relations is needed. Here we present results of the second part of the series, which is devoted to algebraic presentations for such mixed finite relations. We introduced enriched (weak) semiringal categories as an algebraic model for relations in this setting.