Free Generators and Rank
The members of a set A are called the free generators for A∗ and A+. The superscript * is then commonly understood to be the Kleene star. More generally, if S is an abstract free monoid (semigroup), then a set of elements which maps onto the set of single-letter words under an isomorphism to a semigroup A+ (monoid A∗) is called a set of free generators for S.
Each free semigroup (or monoid) S has exactly one set of free generators, the cardinality of which is called the rank of S.
Two free monoids or semigroups are isomorphic if and only if they have the same rank. In fact, every set of generators for a free semigroup or monoid S contains the free generators. It follows that a free semigroup or monoid is finitely generated if and only if it has finite rank.
A set of free generators for a free monoid P is referred to as a basis for P: a set of words C is a code if C* is a free monoid and C is a basis. A set X of words in A∗ is a prefix if it is closed under taking initial segments: that is, xy in X implies x in X. Every prefix in A+ is a code.
A submonoid N of A∗ is right unitary if x, xy in N implies y in N. A submonoid is generated by a prefix if and only if it is right unitary.
Read more about this topic: Free Monoid
Famous quotes containing the words free and/or rank:
“The writer, unlike his non-writing adult friend, has no predisposed outlook; he seldom observes deliberately. He sees what he did not intend to see; he remembers what does not seem wholly possible. Inattentive learner in the schoolroom of life, he keeps some faculty free to veer and wander. His is the roving eye.”
—Elizabeth Bowen (1899–1973)
“If, in looking at the lives of princes, courtiers, men of rank and fashion, we must perforce depict them as idle, profligate, and criminal, we must make allowances for the rich men’s failings, and recollect that we, too, were very likely indolent and voluptuous, had we no motive for work, a mortal’s natural taste for pleasure, and the daily temptation of a large income. What could a great peer, with a great castle and park, and a great fortune, do but be splendid and idle?”
—William Makepeace Thackeray (1811–1863)