Monoids
The performance of a sequence of several actions is itself the performance of an action; a more complex action, but an action nonetheless.
A monoid can be construed as a set of actions together with a formula that encodes how a sequence of actions is itself considered an action.
A monoid packages a set M, an element e in M, and an operator ⋆: (M, M) => M which takes two elements in M and returns an element in M, such that three rules hold:
-
⋆(m, e) = m(unit identity) -
⋆(e, m) = m(unit identity) -
⋆(⋆(m, n), p)) = ⋆(m, ⋆(n, p))(associativity)
Example:
The monoid (natural numbers, 0, +) works the way we expect addition to work on the natural numbers.
First, a list based on the set X plucks out elements of X and assigns them an index, effectively placing them in a structure that resembles our intuitive notion of a list of things.
The free monoid generated by a set X is the sequence (package):
Where the set M is all lists of X (e.g., [a, b, b, c, a, b, c] if X := {a, b, c} is one such list of X), the concatenation operator, and the unit element which is the obvious empty set. Concatenating nothing to a list leaves a list unchanged, whether it is prepended or appended.
The set X is the set of generators for the free monoid F. The set of generators for the monoid can be thought of as the set of buttons which can be pressed, one after another in a list of button presses.
A congruence on a monoid is an equivalence relation which gives us:
whenever
m ~ m' and n ~ n'
Congruences on monoids can be used to put buttons in the same class, and therefore characterize sets of actions which do the same thing.
- Let a finite set G.
- Take a relation R ⊆ List(G) × List(G).
- Create the free monoid FG = (List(G), [ ], ++) generated from G.
- Create the congruence relation ~ on the free monoid by minimally augmenting the relation R so that it actually forms an equivalence relation.
- Define the presented monoid as the free monoid "modded" by the equivalence classes established from the congruence relation ~.
A presented monoid is a set of buttons you can press and some facts about when different button sequences have the same results.
Note: We assume G is a set that can have more than one element. Therefore, the classes of equivalent strings of button presses can be complex in the reductions they permit. Something interesting happens when the set G only has one element.
A monoid is cyclic if its presentation only has one generator: G is a set like {potato} or {alpha} or {☺}. When only one generator is involved, interesting things happen. Actually, when only one generator is involved and a relation is established for the monoid, then interesting things happen...
When a monoid has a generator set with one element and no relation R ⊆ List(G) × List(G), the list of "button presses" looks like:
{[ ], [☺], [☺, ☺], [☺, ☺, ☺], …}
But when there is a relation with one "rule", say:
where ☺^12 indicates 12 applications of the button press ☺, we have that the presented monoid would allow any number of button presses from 0 to 11. Pressing the button twelve times is the same as not pressing it at all!
If one were to draw a diagram depicting the action sequences for this monoid with 12 elements, one might draw a circle connecting each ☺^k to the next, with ☺^0 connected to ☺^1, ☺^1 connected to ☺^2, and ☺^11 connecting to ☺^0. A loop.
If we admit the rule:
then one would draw a loop that looks like the previous monoid, except instead of forming one loop, one would connect ☺^6 to ☺^4, leaving a diagram that looks like a lollipop. There is a cycle, but the cycle doesn't start until one gets to the seventh button press, at which point continued presses will follow the "four presses, five presses, six presses, four presses loop" of behavior. The rule ☺ ~ ☺^12 left no prefixed tail (stem?) of behavior, but the rule ☺^7 ~ ☺^4 does leave a prefix of behavior which eventually turns into a cycle. Both rules give rise to cyclic behavior.
Cyclic monoids are either infinite or finite. If one does not admit a relation, then the monoid is infinite just like the additive monoid (ℕ, 0, +). One just keeps pressing buttons however many times they wish. If one does admit a relation R ⊆ List(G) × List(G) (remember G has one element), then the monoid is finite, with cycles that loop back according to the behavior discussed in the preceding examples.
The verbiage: an M action on S, where M is a set used by a monoid and S is a set.
An M action on S, is a function α(m: M, s: S): S such that:
α(e, s) yields sα(m, α(n, s)) yields the same as α(⋆(m, n), s)
Let M act on S. Okay. Let a monoid M generated by a set of movements { up, down, right } act on a set of action positions S, perhaps a game world's grid.
The presented monoid may be subject to relations like [up, down] ~ [do nothing]. [up, down, up, down, up] is equivalent to simply [up], for example...
Then we get the neat diagram:
- Take the free monoid M created from a list of inputs to a finite state machine (the buttons).
- Let the states of the finite state machine be S.
An action of the free monoid M on the states S of the FSM is equivalent to specifying a state-transition function Σ.