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:
“It is change, continuing change, inevitable change, that is the dominant factor in society today. No sensible decision can be made any longer without taking into account not only the world as it is, but the world as it will be.... This, in turn, means that our statesmen, our businessmen, our everyman must take on a science fictional way of thinking.”
—Isaac Asimov (1920–1992)