×

Semirings and parallel composition of processes. (English) Zbl 0867.68050

Summary: We introduce a family of partially-ordered (po) semirings aiming at applying these structures to parallel processes. We develop the properties related to formalizing a specific delimited feature of these processes, namely interleaving, by linking our modeling with an enough studied domain of algebra not yet considered in this context and by suggesting a new area for applying formal languages to concurrent programming abstraction dealing with such interleaved sequences of “atomic instructions”. These semirings are obtained by combining the well-known operations of catenation, anti-catenation, and shuffle, and, by considering that the set of elementary actions is decomposed in two subsets – critical (protected) and noncritical (ordinary) actions. Whereas the catenation (anti-catenation) corresponds to sequential composition of processes with the priority of the first (second) process, the shuffle operation defines free or pure parallel composition of concurrent processes. The need of the intermediate operations is strongly motivated by the theory of concurrent processes and by the practice of concurrent programming. Indeed critical sections frequently exist inside concurrent processes and, moreover, the priority of processes can be modified during the execution, using a pre-defined strategy. The proposed modeling results in two fundamental principles in explaining the semantics of parallelism, independently of some technical implementation. Also we consider some models for re-entrant routines.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite