free submonoid

Let A be an arbitrary set, let A be the free monoid on A, and let e be the identity elementMathworldPlanetmath (empty wordPlanetmathPlanetmath) of A.

Let M be a submonoid of A. The minimal generating set of M is

mgs(M)=(M{e})(M{e})2. (1)

Shortly, mgs(M) is the set of all the nontrivial elements of M that cannot be “reconstructed” as products of elements of M. It is straightforward that

  1. 1.

    (mgs(M))=M, and

  2. 2.

    if SA and MS, then mgs(M)S.

We say that M is a free submonoid of A if it is isomorphicPlanetmathPlanetmathPlanetmath (as a monoid) to a free monoid B for some set B. A set KA such that K=mgs(M) for some free submonoid M of A is also called a code.

Title free submonoid
Canonical name FreeSubmonoid
Date of creation 2013-03-22 18:21:36
Last modified on 2013-03-22 18:21:36
Owner Ziosilvio (18733)
Last modified by Ziosilvio (18733)
Numerical id 5
Author Ziosilvio (18733)
Entry type Definition
Classification msc 20M10
Classification msc 20M05
Defines minimal generating set of a submonoid