Factor Monoid and Monoid Presentations
Since is a congruence, we can define the factor monoid of the free monoid by the Thue congruence in the usual manner. If a monoid is isomorphic with, then the semi-Thue system is called a monoid presentation of .
We immediately get some very useful connections with other areas of algebra. For example, the alphabet {a, b} with the rules { ab → ε, ba → ε }, where ε is the empty string, is a presentation of the free group on one generator. If instead the rules are just { ab → ε }, then we obtain a presentation of the bicyclic monoid.
The importance of semi-Thue systems as presentation of monoids is made stronger by the following:
Theorem: Every monoid has a presentation of the form, thus it may be always be presented by a semi-Thue system, possibly over an infinite alphabet.
In this context, the set is called the set of generators of, and R is called the set of defining relations . We can immediately classify monoids based on their presentation. is called
- finitely generated if is finite.
- finitely presented if both and R are finite.
Read more about this topic: Semi-Thue System
Famous quotes containing the word factor:
“Weapons are an important factor in war, but not the decisive factor; it is people, not things, that are decisive. The contest of strength is not only a contest of military and economic power, but also a contest of human power and morale. Military and economic power is necessarily wielded by people.”
—Mao Zedong (1893–1976)