Traces, histories, graphs: instances of a process monoid. (English) Zbl 0577.68061

Mathematical foundations of computer science, Proc. 11th Symp., Praha/Czech. 1984, Lect. Notes Comput. Sci. 176, 115-133 (1984).
[For the entire collection see Zbl 0544.00022.]
Some notions of processes with partially ordered set of event occurrences have been already elaborated by different authors at different time, to enable analysis of concurrent systems and to create a solid basis for developing their theory. Such a first notion is due to Petri [C. A. Petri: ”Non-sequential processes”, ISF Rep. 77.05, Gesellschaft für Mathematik und Datenverarbeitung mbH Bonn (1977); see also W. Reisig: Petrinetze (1982; Zbl 0482.68054)], and other notions - either directly, or indirectly - have been derived from it. In this approach processes are represented by occurrence nets; their finite version is close to occurrence graphs considered below and the infinite can be obtained via the limit construction. The second was the notion of traces [the author: ”Concurrent program schemes and their interpretations”, Aarhus Univ., DAIMI Rep. PB78 (1977)] introduced to facilitate formal reasoning about concurrent program schemata; dependence graphs, also described in the present paper, have been thought as graphical representations of traces. Almost at the same time the notion of string vectors [M. W. Shields, Lect. Notes Comput. Sci. 70, 249-265 (1979; Zbl 0429.68058)], called here histories, was introduced for a formal description of the path expressions semantics, converted next to the COSY system.
The aim of this paper is to compare the above notions of processes, to find some common features of them, and if possible, to define an abstract algebra comprising features of all of them. We shall not follow the original definitions in details; we hope however, that the essential properties of the authors’ definitions as well as their intentions will be preserved. It will be shown that all these algebras are instances of one algebra: a monoid with some characteristic axioms. Since in this paper we are not interested in any concrete concurrent system, no restrictions on the sets of processes will be imposed (as conditions concerning a mutual precedence of events in processes). The intention of the author is only to characterize any possible processes in a given event domain and to leave the question of properties of their sets to more specific theories of concurrent systems.


68Q99 Theory of computing
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
20M35 Semigroups in automata theory, linguistics, etc.
68Q45 Formal languages and automata
68N25 Theory of operating systems
68Q60 Specification and verification (program logics, model checking, etc.)