Monoid

From TCS Wiki
Jump to navigation Jump to search

In abstract algebra, a monoid is a set of elements with two key properties

  1. It can be combined associatively; e.g. [math]\displaystyle{ (A + B) + C = A + (B + C) }[/math]
  2. There exists an identity element; e.g. [math]\displaystyle{ 1 \times X = X }[/math], or [math]\displaystyle{ 0 + X = X }[/math]

In computing science common monoids include addition, multiplication, or, and. These properties are useful for various problems e.g. they allow a large set of data to be divided, processed in parallel and combined. As each part produces a Monoid, the final combined result will be the same. This also works with more complex Monoids e.g. a map of word counts.

Other websites

Template:Wikibooks-inline


Template:Math-stub