Namespaces
Variants
Actions

Difference between revisions of "Free semi-group"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
(TeX done)
 
Line 1: Line 1:
''over an alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f0416401.png" />''
+
''over an alphabet $A$''
  
The semi-group whose elements are all possible finite sequences of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f0416402.png" /> (letters), and the operation consists of placing one sequence after another. The elements of a free semi-group are usually called words (cf. [[Word|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f0416403.png" /> for any word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f0416404.png" />; the semi-group with an identity that arises in this way is called the free monoid over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f0416405.png" />. The free semi-group (respectively, free monoid) over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f0416406.png" /> is often denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f0416407.png" /> (respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f0416408.png" />). The alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f0416409.png" /> for the free semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164010.png" /> is the unique irreducible generating set that consists of just those elements that cannot be decomposed into products. The letters of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164011.png" /> 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.
+
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|Free algebra]]) in the category of all semi-groups. For a semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164012.png" /> the following conditions are equivalent: 1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164013.png" /> is free; 2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164014.png" /> has a generating set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164015.png" /> such that any element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164016.png" /> can be uniquely represented as a product of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164017.png" />; and 3) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164018.png" /> satisfies the [[cancellation law]], does not contain idempotents, every element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164019.png" /> has a finite number of divisors, and for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164020.png" /> the equality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164021.png" /> implies that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164022.png" />, or that one of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164023.png" /> is a left divisor of the other.
+
Free semi-groups are the free objects (cf. [[Free algebra|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164024.png" /> of a free semi-group has a unique irreducible generating set, which consists of elements that cannot be decomposed into a product in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164025.png" />; however, not every sub-semi-group of a free semi-group is free. The following conditions on a sub-semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164026.png" /> of a free semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164027.png" /> are equivalent: 1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164028.png" /> is a free semi-group; 2) for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164029.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164030.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164031.png" /> imply that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164032.png" />; and 3) for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164033.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164034.png" /> implies that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164035.png" />. For arbitrary different words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164036.png" /> in a free semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164037.png" />, either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164039.png" /> are free generators of the sub-semi-group generated by them, or there is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164040.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164041.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164042.png" /> for some natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164043.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164044.png" />; the second alternative holds if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164045.png" />. 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.
+
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|Automata, algebraic theory of]], see also [[#References|[5]]], [[#References|[6]]]), the theory of coding (see [[Coding, alphabetical|Coding, alphabetical]], [[#References|[4]]]–[[#References|[6]]]), and the theory of formal languages and formal grammars (cf. [[Grammar, formal|Grammar, formal]], see also [[#References|[3]]], [[#References|[5]]], [[#References|[6]]]). Connected with these topics are the problems of solving equations in free semi-groups (see [[#References|[7]]]–[[#References|[9]]]). There are algorithms that recognize the solvability of arbitrary equations in a free semi-group.
+
Free semi-groups arise naturally in the algebraic theory of automata (cf. [[Automata, algebraic theory of]], see also [[#References|[5]]], [[#References|[6]]]), the theory of coding (see [[Coding, alphabetical]], [[#References|[4]]]–[[#References|[6]]]), and the theory of formal languages and formal grammars (cf. [[Grammar, formal]], see also [[#References|[3]]], [[#References|[5]]], [[#References|[6]]]). Connected with these topics are the problems of solving equations in free semi-groups (see [[#References|[7]]]–[[#References|[9]]]). There are algorithms that recognize the solvability of arbitrary equations in a free semi-group.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.H. Clifford,  G.B. Preston,  "Algebraic theory of semi-groups" , '''1–2''' , Amer. Math. Soc.  (1961–1967)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  E.S. Lyapin,  "Semigroups" , Amer. Math. Soc.  (1974)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  M. Gross,  A. Lentin,  "Introduction to formal grammars" , Springer  (1970)  (Translated from French)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.A. Markov,  "Introduction to coding theory" , Moscow  (1982)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  S. Eilenberg,  "Automata, languages and machines" , '''A-B''' , Acad. Press  (1974–1976)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  G. Lallement,  "Semi-groups and combinatorial applications" , Wiley  (1979)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  A. Lentin,  "Equations dans les monoids libres" , Mouton  (1972)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  Yu.I. Khmelevskii,  "Equations in free semi-groups"  ''Proc. Steklov Inst. Math.'' , '''107'''  (1976)  ''Trudy Mat. Inst. Steklov.'' , '''107'''  (1971)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  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</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  A.H. Clifford,  G.B. Preston,  "Algebraic theory of semi-groups" , '''1–2''' , Amer. Math. Soc.  (1961–1967)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  E.S. Lyapin,  "Semigroups" , Amer. Math. Soc.  (1974)  (Translated from Russian)</TD></TR>
 +
<TR><TD valign="top">[3]</TD> <TD valign="top">  M. Gross,  A. Lentin,  "Introduction to formal grammars" , Springer  (1970)  (Translated from French)</TD></TR>
 +
<TR><TD valign="top">[4]</TD> <TD valign="top">  A.A. Markov,  "Introduction to coding theory" , Moscow  (1982)  (In Russian)</TD></TR>
 +
<TR><TD valign="top">[5]</TD> <TD valign="top">  S. Eilenberg,  "Automata, languages and machines" , '''A-B''' , Acad. Press  (1974–1976)</TD></TR>
 +
<TR><TD valign="top">[6]</TD> <TD valign="top">  G. Lallement,  "Semi-groups and combinatorial applications" , Wiley  (1979)</TD></TR>
 +
<TR><TD valign="top">[7]</TD> <TD valign="top">  A. Lentin,  "Equations dans les monoids libres" , Mouton  (1972)</TD></TR>
 +
<TR><TD valign="top">[8]</TD> <TD valign="top">  Yu.I. Khmelevskii,  "Equations in free semi-groups"  ''Proc. Steklov Inst. Math.'' , '''107'''  (1976)  ''Trudy Mat. Inst. Steklov.'' , '''107'''  (1971)</TD></TR>
 +
<TR><TD valign="top">[9]</TD> <TD valign="top">  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</TD></TR>
 +
</table>
  
  
  
 
====Comments====
 
====Comments====
The (categorical) freeness property of the free semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164046.png" /> over the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164047.png" /> is the following. For every semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164048.png" /> and mapping of sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164049.png" /> there is a unique homomorphism of semi-groups <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164050.png" /> extending <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f041/f041640/f04164051.png" />. A similar property holds for the free monoid.
+
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.
 +
 
 +
{{TEX|done}}

Latest revision as of 20:17, 8 December 2015

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.

How to Cite This Entry:
Free semi-group. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Free_semi-group&oldid=36869
This article was adapted from an original article by L.N. Shevrin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article