集合S (台集合と呼ぶ) と二項演算 • : S → S を与えられたとき、
- 任意の a, b, c ∈ S に対して、 (a • b) • c = a • (b • c) [結合法則]
- ある元 e ∈ S が存在し、任意の a ∈ S に対して e • a = a • e = a [単位元の存在]
を満たすとき モノイド という。 （文脈におおじて二項演算の記号は省略される）
また、任意の元 a, b ∈ S に対し、a • b = b • a を満たすならば 可換モノイド (commutative monoid) という。
上のモノイドの規則から導かれるもの以外に等式関係が存在しないならば、自由モノイド (Free monoid)と呼ばれる。 例えば、「文字列とその結合」は自由モノイドであるが、「非負整数と加法」は自由モノイドではない。(1 + 5 = 3 + 3 等が成り立つ)
単純なプログラムにおいて、「プログラムの文やブロックとその連接」はモノイドを成す。 （このとき単位元はいわゆるNOPである）
Trace Monoid は 別名 free partially commutative monoidである。 つまり、一部の元同士が可換な自由モノイドである。
例：台集合 S = {a,b,c} とし、bc=cb となるTrace Monoidにおいて abbca = abcba = acbba となる。
台集合として「プログラムのブロック＝ジョブ」を取る。また、二項演算として「ジョブの結合」を取る。 このとき、可換な元同士は「独立して実行できるジョブ」、非可換な元同士は「同期的なジョブ/排他処理が必要なジョブ」という意味になる。 つまり、Trace Monoidで並行処理を表現できる。
また、Trace MonoidはDependency Graph（依存関係を表現するグラフ）と同相なので、グラフ理論の手法が利用できる。（逆も然り）
理解したら書きます。（書かないかもね）