History Monoid Article Index for
History 		Website Links For
History 		 

Information About

History Monoid
  CATEGORIES ABOUT HISTORY MONOID
   
concurrency
   
semigroup theory
   
formal languages
   
free algebraic structures
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



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. ShieldsM.W. Shields "Concurrent Machines", ''Computer Journal'', (1985) 28 pp.449-465.

History monoids are isomorphic to Trace Monoid s (free partially commutative monoids) and to the Monoid of Dependency Graph s. As such, they are Free Object s and are Universal . The history monoid is a type of semi-abelian Categorical Product in the Category of monoids.


PRODUCT MONOIDS AND PROJECTION

Let
:A=(\Sigma_1,\Sigma_2,\cdots,\Sigma_n)

denote an ''n''-tuple of Alphabets \Sigma_k, and let P(A) denote the Cartesian Product of Free Monoid s

  • imes \Sigma_2^--- imes \cdots imes \Sigma_n^---


  • is the free monoid for the alphabet \Sigma_k. That is, it is the collection of all finite-length strings formed from the letters of \Sigma_k; the superscript symbol --- is the Kleene Star . Composition in the product monoid is component-wise, so that, for


:\bold{u}=(u_1,u_2,\cdots,u_n)

and

:\bold{v}=(v_1,v_2,\cdots,v_n)

then

:\bold{uv}=(u_1v_1,u_2v_2,\cdots,u_nv_n)

for all \bold{u}, \bold{v} in P(A). Define the union alphabet to be

:\Sigma=\Sigma_1 \cup \Sigma_2 \cup \cdots \cup \Sigma_n

Here, the union should be understood to be the Set Union and should ''not'' be confused with the Disjoint Union . A distribution is the projection mapping

  • o P(A)


  • to


:\pi(w)\mapsto (\pi_1(w), \pi_2(w), \cdots , \pi_n(w))

  • o\Sigma_k^--- are to be understood to be String Projection s. That is, \pi_k(w) is the string where all letters not in \Sigma_k have been removed.



HISTORIES

For every a\in\Sigma, the tuple \pi(a) is called the elementary history of ''a''. It serves as an Indicator Function for the inclusion of a letter ''a'' in an alphabet \Sigma_k. That is,

:\pi(a)=(a_1,a_2,\cdots,a_n)

where

:a_i=\begin{cases}
a \mbox{ if } a\in \Sigma_k \
arepsilon \mbox { otherwise }
\end{cases}

Here, arepsilon denotes the Empty String . The history monoid H(A) is the Free Monoid generated by elementary histories. It is clearly a submonoid of the product monoid P(A). The elements of H(A) are called '''global histories''', and the projections of a global history are called '''individual histories'''.


CONNECTION TO COMPUTER SCIENCE

The use of the word ''history'' in this context, and the connection to concurrent computing, can be understood as follows. An individual history is a record of the sequence of States of a process (or Thread or Machine ); the alphabet \Sigma_k is the set of states of the process.

A letter that occurs in two or more alphabets serves as a Synchronization Primitive between the various individual histories. That is, if such a letter occurs in one individual history, it must also occur in another history, and serves to "tie" or "rendez-vous" them together.

Consider, for example, \Sigma_1=\{a,b,c\} and \Sigma_2=\{a,d,e\}. The union alphabet is of course \Sigma=\{a,b,c,d,e\}. The elementary histories are (a,a), (b, arepsilon), (c, arepsilon), ( arepsilon,d) and ( arepsilon,e). In this example, an individual history of the first process might be "bcbcc" while the individual history of the second machine might be "ddded". Both of these individual histories are represented by the global history "bcbdddcced", since the projection of this string onto the individual alphabets yields the individual histories. In the global history, the letter ''b'' can be considered to commute with the letters ''d'' and ''e'', in that these can be rearranged without changing the individual histories. Such commutation is simply a statement that the first and second processes are running concurrently, and are unordered with respect to each other; they have not (yet) exchanged any messages or performed any synchronization.

The letter ''a'' serves as a synchronization primitive, as its occurrence marks a spot in both the global and individual histories, that cannot be commuted across. Thus, while the letters ''b'' and ''c'' can be re-ordered past ''d'' and ''e'', they cannot be reordered past ''a''. Thus, the global history "bcdabe" and the global history "bdcaeb" both have as individual histories "bcab" and "dae", indicating that the execution of ''d'' may happen before or after ''c''. However, the letter ''a'' is synchronizing, so that ''e'' is guaranteed to happen after ''c'', even though ''e'' is in a different Process than ''c''.


PROPERTIES

The history monoid is isomorphic to the Trace Monoid , and as such, is a type of semi-abelian Categorical Product in the Category of monoids. In particular, the history monoid H(\Sigma_1,\Sigma_2,\cdots,\Sigma_n) is isomorphic to the trace monoid \mathbb{M}(D) with the Dependency Relation given by

:D=\left(\Sigma_1 imes\Sigma_1 ight)\cup
\left(\Sigma_2 imes\Sigma_2 ight)\cup \cdots \cup
\left(\Sigma_n imes\Sigma_n ight)

In simple terms, this is just the formal statement of the informal discussion given above: the letters in an alphabet \Sigma_k can be commutatively re-ordered past the letters in an alphabet \Sigma_j, unless they are letters that occur in both alphabets. Thus, traces are exactly global histories, and vice-versa.


REFERENCES


  • Antoni Mazurkiewicz, "Introduction to Trace Theory", pp 3-41, in ''The Book of Traces'', V. Diekert, G. Rozenberg, eds. (1995) World Scientific, Singapore ISBN 9810220588

  • Volker Diekert, Yves Métivier, " Partial Commutation and Traces ", In G. Rozenberg and A. Salomaa, editors, ''Handbook of Formal Languages'', Vol. 3, Beyond Words, pages 457--534. Springer-Verlag, Berlin, 1997.