|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc010303,
author = {Jonathan S. Golan and Alexandru Mateescu and Dragos Vaida},
title = {Semirings and Parallel Composition of Processes},
journal = jalc,
year = 1996,
volume = 1,
number = 3,
pages = {199--217},
keywords = {concurrency, parallel computation, semirings},
abstract = {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''.\par
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.\par
Also we consider some models for re-entrant routines.}
}