Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
History monoid
Summary
In mathematics and computer science, a history monoid is a way of representing the histories of concurrently running computer processes as a collection of strings, each string representing the individual history of a process. The history monoid provides a set of synchronization primitives (such as locks, mutexes or thread joins) for providing rendezvous points between a set of independently executing processes or threads.
History monoids occur in the theory of concurrent computation, and provide a low-level mathematical foundation for process calculi, such as CSP the language of communicating sequential processes, or CCS, the calculus of communicating systems. History monoids were first presented by M.W. Shields.
History monoids are isomorphic to trace monoids (free partially commutative monoids) and to the monoid of dependency graphs. As such, they are free objects and are universal. The history monoid is a type of semi-abelian categorical product in the of monoids.
Let
denote an n-tuple of (not necessarily pairwise disjoint) alphabets . Let denote all possible combinations of one finite-length string from each alphabet:
(In more formal language, is the Cartesian product of the free monoids of the . The superscript star is the Kleene star.) Composition in the product monoid is component-wise, so that, for
and
then
for all in . Define the union alphabet to be
(The union here is the set union, not the disjoint union.) Given any string , we can pick out just the letters in some using the corresponding string projection . A distribution is the mapping that operates on with all of the , separating it into components in each free monoid:
For every , the tuple is called the elementary history of a. It serves as an indicator function for the inclusion of a letter a in an alphabet . That is,
where
Here, denotes the empty string. The history monoid is the submonoid of the product monoid generated by the elementary histories: (where the superscript star is the Kleene star applied with a component-wise definition of composition as given above).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.