Free semi-group

over an alphabet $A$

The semi-group whose elements are all possible finite sequences of elements of $A$ (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 $w1 = w = w1$ for any word $w$; the semi-group with an identity that arises in this way is called the free monoid over $A$. The free semi-group (respectively, free monoid) over $A$ is often denoted by $A^+$ (respectively, $A^*$). The alphabet $A$ for the free semi-group $A^+$ is the unique irreducible generating set that consists of just those elements that cannot be decomposed into products. The letters of $A$ 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 $F$ the following conditions are equivalent: 1) $F$ is free; 2) $F$ has a generating set $A$ such that any element of $F$ can be uniquely represented as a product of elements of $A$; and 3) $F$ satisfies the cancellation law, does not contain idempotents, every element of $F$ has a finite number of divisors, and for any $u,v,u',v' \in F$ the equality $uv = u'v'$ implies that $u = u'$, or that one of $u,u'$ is a left divisor of the other.

Every sub-semi-group $H$ of a free semi-group has a unique irreducible generating set, which consists of elements that cannot be decomposed into a product in $H$; however, not every sub-semi-group of a free semi-group is free. The following conditions on a sub-semi-group $H$ of a free semi-group $F$ are equivalent: 1) $H$ is a free semi-group; 2) for any $w \in F$, $H \cap wH \neq \emptyset$ and $H \cap Hw \neq \emptyset$ imply that $w \in H$; and 3) for any $w \in F$, $H \cap wH \cap Hw \neq \emptyset$ implies that $w \in H$. For arbitrary different words $u,v$ in a free semi-group $F$, either $u$ and $v$ are free generators of the sub-semi-group generated by them, or there is a $w \in F$ such that $w = u^k$, $w = v^l$ for some natural numbers $k$ and $l$; the second alternative holds if and only if $uv = vu$. 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 $F$ over the set $A$ is the following. For every semi-group $S$ and mapping of sets $\alpha : A \rightarrow S$ there is a unique homomorphism of semi-groups $F \rightarrow S$ extending $\alpha$. A similar property holds for the free monoid.