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.
Free semi-group. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Free_semi-group&oldid=16067