Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

11 Free inverse semigroups
 11.1 Free inverse semigroups
 11.2 Displaying free inverse semigroup elements
 11.3 Operators and operations for free inverse semigroup elements

11 Free inverse semigroups

This chapter describes the functions in Semigroups for dealing with free inverse semigroups and free bands. This part of the manual and the functions described herein were written by Julius JonuĊĦas.

11.1 Free inverse semigroups

An inverse semigroup \(F\) is said to be free on a non-empty set \(X\) if there is a map \(f\) from \(F\) to \(X\) such that for every inverse semigroup \(S\) and a map \(g\) from \(X\) to \(S\) there exists a unique homomorphism \(g'\) from \(F\) to \(S\) such that \(fg' = g\). Moreover, by this universal property, every inverse semigroup can be expressed as a quotient of a free inverse semigroup.

The internal representation of an element of a free inverse semigroup uses a Munn tree. A Munn tree is a directed tree with distinguished start and terminal vertices and where the edges are labeled by generators so that two edges labeled by the same generator are only incident to the same vertex if one of the edges is coming in and the other is leaving the vertex. For more information regarding free inverse semigroups and the Munn representations see Section 5.10 of [How95].

See also Reference: Inverse semigroups and monoids, Reference: Partial permutations and Reference: Free Groups, Monoids and Semigroups.

An element of a free inverse semigroup in Semigroups is displayed, by default, as a shortest word corresponding to the element. However, there might be more than one word of the minimum length. For example, if \(x\) and \(y\) are generators of a free inverse semigroups, then

\[xyy ^ {-1}xx ^ {-1}x ^ {-1} = xxx ^ {-1}yy ^ {-1}x ^ {-1}.\]

See MinimalWord (11.3-2). Therefore we provide a another method for printing elements of a free inverse semigroup: a unique canonical form. Suppose an element of a free inverse semigroup is given as a Munn tree. Let \(L\) be the set of words corresponding to the shortest paths from the start vertex to the leaves of the tree. Also let \(w\) be a word corresponding to the shortest path from start to terminal vertices. The word \(vv ^ {-1}\) is an idempotent for every \(v\) in \(L\). The canonical form is given by multiplying these idempotents, in shortlex order, and then postmultiplying by \(w\). For example, consider the word \(xyy ^ {-1}xx ^ {-1}x ^ {-1}\) again. The words corresponding to the paths to the leaves are in this case \(xx\) and \(xy\). And \(w\) is an empty word since start and terminal vertices are the same. Therefore, the canonical form is

\[xxx ^ {-1}x ^ {-1}xyy ^ {-1}x ^ {-1}.\]

See CanonicalForm (11.3-1).

11.1-1 FreeInverseSemigroup
‣ FreeInverseSemigroup( rank[, name] )( function )
‣ FreeInverseSemigroup( name1, name2, ... )( function )
‣ FreeInverseSemigroup( names )( function )

Returns: A free inverse semigroup.

Returns a free inverse semigroup on rank generators, where rank is a positive integer. If rank is not specified, the number of names is used. If S is a free inverse semigroup, then the generators can be accessed by S.1, S.2 and so on.

gap> S := FreeInverseSemigroup(7);
<free inverse semigroup on the generators 
[ x1, x2, x3, x4, x5, x6, x7 ]>
gap> S := FreeInverseSemigroup(7, "s");
<free inverse semigroup on the generators 
[ s1, s2, s3, s4, s5, s6, s7 ]>
gap> S := FreeInverseSemigroup("a", "b", "c");
<free inverse semigroup on the generators [ a, b, c ]>
gap> S := FreeInverseSemigroup(["a", "b", "c"]);
<free inverse semigroup on the generators [ a, b, c ]>
gap> S.1;
a
gap> S.2;
b

11.1-2 IsFreeInverseSemigroupCategory
‣ IsFreeInverseSemigroupCategory( obj )( category )

Every free inverse semigroup in GAP created by FreeInverseSemigroup (11.1-1) belongs to the category IsFreeInverseSemigroup. Basic operations for a free inverse semigroup are: GeneratorsOfInverseSemigroup (Reference: GeneratorsOfInverseSemigroup) and GeneratorsOfSemigroup (Reference: GeneratorsOfSemigroup). Elements of a free inverse semigroup belong to the category IsFreeInverseSemigroupElement (11.1-4).

11.1-3 IsFreeInverseSemigroup
‣ IsFreeInverseSemigroup( S )( property )

Returns: true or false

Attempts to determine whether the given semigroup S is a free inverse semigroup.

11.1-4 IsFreeInverseSemigroupElement
‣ IsFreeInverseSemigroupElement( category )

Every element of a free inverse semigroup belongs to the category IsFreeInverseSemigroupElement.

11.2 Displaying free inverse semigroup elements

There is a way to change how GAP displays free inverse semigroup elements using the user preference FreeInverseSemigroupElementDisplay. See UserPreference (Reference: UserPreference) for more information about user preferences.

There are two possible values for FreeInverseSemigroupElementDisplay:

minimal

With this option selected, GAP will display a shortest word corresponding to the free inverse semigroup element. However, this shortest word is not unique. This is a default setting.

canonical

With this option selected, GAP will display a free inverse semigroup element in the canonical form.

gap> SetUserPreference("semigroups", 
>                      "FreeInverseSemigroupElementDisplay",
>                      "minimal");
gap> S := FreeInverseSemigroup(2);
<free inverse semigroup on the generators [ x1, x2 ]>
gap> S.1 * S.2;
x1*x2
gap> SetUserPreference("semigroups", 
>                      "FreeInverseSemigroupElementDisplay", 
>                      "canonical");
gap> S.1 * S.2;
x1x2x2^-1x1^-1x1x2

11.3 Operators and operations for free inverse semigroup elements

w ^ -1

returns the semigroup inverse of the free inverse semigroup element w.

u * v

returns the product of two free inverse semigroup elements u and v.

u = v

checks if two free inverse semigroup elements are equal, by comparing their canonical forms.

11.3-1 CanonicalForm
‣ CanonicalForm( w )( attribute )

Returns: A string.

Every element of a free inverse semigroup has a unique canonical form. If w is such an element, then CanonicalForm returns the canonical form of w as a string.

gap> S := FreeInverseSemigroup(3);
<free inverse semigroup on the generators [ x1, x2, x3 ]>
gap> x := S.1; y := S.2;
x1
x2
gap> CanonicalForm(x ^ 3 * y ^ 3);
"x1x1x1x2x2x2x2^-1x2^-1x2^-1x1^-1x1^-1x1^-1x1x1x1x2x2x2"

11.3-2 MinimalWord
‣ MinimalWord( w )( attribute )

Returns: A string.

For an element w of a free inverse semigroup S, MinimalWord returns a word of minimal length equal to w in S as a string.

Note that there maybe more than one word of minimal length which is equal to w in S.

gap> S := FreeInverseSemigroup(3);
<free inverse semigroup on the generators [ x1, x2, x3 ]>
gap> x := S.1;
x1
gap> y := S.2;
x2
gap> MinimalWord(x ^ 3 * y ^ 3);
"x1*x1*x1*x2*x2*x2"
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Bib Ind

generated by GAPDoc2HTML