Free semi-group

over an alphabet

The semi-group whose elements are all possible finite sequences of elements of (letters), and the operation consists of placing one sequence after another. The elements of a free semi-group are usually called words (cf. Word), and the operation is often called concatenation. For the sake of convenience, the empty word 1 is often adjoined (its length is, by definition, zero) by setting for any word ; the semi-group with an identity that arises in this way is called the free monoid over . The free semi-group (respectively, free monoid) over is often denoted by (respectively, ). The alphabet for the free semi-group is the unique irreducible generating set that consists of just those elements that cannot be decomposed into products. The letters of are called free generators. A free semi-group is defined uniquely up to an isomorphism by the cardinality of its alphabet, called the rank of the free semi-group. The free semi-group of rank 2 has sub-semi-groups that are free of countable rank.

Free semi-groups are the free objects (cf. Free algebra) in the category of all semi-groups. For a semi-group the following conditions are equivalent: 1) is free; 2) has a generating set such that any element of can be uniquely represented as a product of elements of ; and 3) satisfies the cancellation law, does not contain idempotents, every element of has a finite number of divisors, and for any the equality implies that , or that one of is a left divisor of the other.

Every sub-semi-group of a free semi-group has a unique irreducible generating set, which consists of elements that cannot be decomposed into a product in ; however, not every sub-semi-group of a free semi-group is free. The following conditions on a sub-semi-group of a free semi-group are equivalent: 1) is a free semi-group; 2) for any , and imply that ; and 3) for any , implies that . For arbitrary different words in a free semi-group , either and are free generators of the sub-semi-group generated by them, or there is a such that , for some natural numbers and ; the second alternative holds if and only if . Every sub-semi-group with three generators in a free semi-group is finitely presented, but there are sub-semi-groups with four generators that are not.

Free semi-groups arise naturally in the algebraic theory of automata (cf. Automata, algebraic theory of, see also [5], [6]), the theory of coding (see Coding, alphabetical, [4]–[6]), and the theory of formal languages and formal grammars (cf. Grammar, formal, see also [3], [5], [6]). Connected with these topics are the problems of solving equations in free semi-groups (see [7]–[9]). There are algorithms that recognize the solvability of arbitrary equations in a free semi-group.

References

[1]	A.H. Clifford, G.B. Preston, "Algebraic theory of semi-groups" , 1–2 , Amer. Math. Soc. (1961–1967)
[2]	E.S. Lyapin, "Semigroups" , Amer. Math. Soc. (1974) (Translated from Russian)
[3]	M. Gross, A. Lentin, "Introduction to formal grammars" , Springer (1970) (Translated from French)
[4]	A.A. Markov, "Introduction to coding theory" , Moscow (1982) (In Russian)
[5]	S. Eilenberg, "Automata, languages and machines" , A-B , Acad. Press (1974–1976)
[6]	G. Lallement, "Semi-groups and combinatorial applications" , Wiley (1979)
[7]	A. Lentin, "Equations dans les monoids libres" , Mouton (1972)
[8]	Yu.I. Khmelevskii, "Equations in free semi-groups" Proc. Steklov Inst. Math. , 107 (1976) Trudy Mat. Inst. Steklov. , 107 (1971)
[9]	G.S. Makanin, "The problem of solvability of equations in a free semigroup" Math. USSR-Sb. , 32 : 2 (1977) pp. 129–198 Mat. Sb. , 103 : 2 (1977) pp. 147–236

Comments

The (categorical) freeness property of the free semi-group over the set is the following. For every semi-group and mapping of sets there is a unique homomorphism of semi-groups extending . A similar property holds for the free monoid.