In this chapter we describe the functions implemented in Semigroups that extend the features available in GAP for dealing with finitely presented semigroups and monoids.
Section 15.1 (written by Maria Tsalakou and Murray Whyte) and Section 15.2 (written by Luke Elliott) demonstrate a number of helper functions that allow the user to convert between different representations of words and relations.
In the later sections, written and implemented by Ben Spiers and Tom Conti-Leslie, we describe how to change the relations of a finitely presented semigroup either manually or automatically using Tietze transformations (which is abbreviated to Stz.
This section contains various methods for dealing with words, which for these purposes are lists of positive integers.
‣ WordToString( A, w ) | ( operation ) |
Returns: A string.
Returns the word w, in the form of a string of letters of the alphabet A. The alphabet is given as a string containing its members.
gap> WordToString("abcd", [4, 2, 3, 1, 1, 4, 2, 3]); "dbcaadbc"
‣ RandomWord( l, n ) | ( operation ) |
Returns: A word.
Returns a random word of length l over n letters.
gap> RandomWord(8, 5); [ 2, 4, 3, 4, 5, 3, 3, 2 ] gap> RandomWord(8, 5); [ 3, 3, 5, 5, 5, 4, 4, 5 ] gap> RandomWord(8, 4); [ 1, 4, 1, 1, 3, 3, 4, 4 ]
‣ StandardiseWord( w ) | ( operation ) |
‣ StandardizeWord( w ) | ( operation ) |
Returns: A list of positive integers.
This function takes a word w, consisting of n distinct positive integers and returns a word s where the characters of s correspond to those of w in order of first appearance.
The word w is changed in-place into word s.
gap> w := [3, 1, 2]; [ 3, 1, 2 ] gap> StandardiseWord(w); [ 1, 2, 3 ] gap> w; [ 1, 2, 3 ] gap> w := [4, 2, 10, 2]; [ 4, 2, 10, 2 ] gap> StandardiseWord(w); [ 1, 2, 3, 2 ]
‣ StringToWord( s ) | ( operation ) |
Returns: A list of positive integers.
This function takes a string s, consisting of n distinct positive integers and returns a word w (i.e. a list of positive integers) over the alphabet [1 .. n]. The positive integers of w correspond to the characters of s, in order of first appearance.
gap> w := "abac"; "abac" gap> StringToWord(w); [ 1, 2, 1, 3 ] gap> w := "ccala"; "ccala" gap> StringToWord(w); [ 1, 1, 2, 3, 2 ] gap> w := "a1b5"; "a1b5" gap> StringToWord(w); [ 1, 2, 3, 4 ]
This section describes operations implemented in Semigroups that are designed to interact with standard GAP methods for creating finitely presented semigroups and monoids (see Reference: Finitely Presented Semigroups and Monoids).
‣ ParseRelations( gens, rels ) | ( operation ) |
Returns: A list of pairs of semigroup or monoid elements.
ParseRelations converts a string describing relations for a semigroup or monoid to the list of pairs of semigroup or monoid elements it represents. Any white space given is ignored. The output list is then compatible with other GAP functions. In the below examples we see free semigroups and monoids being directly quotiented by the output of the ParseRelations function.
The argument gens must be a list of generators for a free semigroup, each being a single alphabet letter (in upper or lower case). The argument rels must be string that lists the equalities desired.
To take a quotient of a free monoid, it is necessary to use GeneratorsOfMonoid (Reference: GeneratorsOfMonoid) as the 1st argument to ParseRelations and the identity may appear as 1 in the specified relations.
gap> f := FreeSemigroup("x", "y", "z");; gap> AssignGeneratorVariables(f); gap> ParseRelations([x, y, z], " x=(y^2z) ^2x, y=xxx , z=y^3"); [ [ x, (y^2*z)^2*x ], [ y, x^3 ], [ z, y^3 ] ] gap> r := ParseRelations([x, y, z], " x=(y^2z)^2x, y=xxx=z , z=y^3"); [ [ x, (y^2*z)^2*x ], [ y, x^3 ], [ x^3, z ], [ z, y^3 ] ] gap> f / r; <fp semigroup with 3 generators and 4 relations of length 23> gap> f2 := FreeSemigroup("a"); <free semigroup on the generators [ a ]> gap> f2 / ParseRelations(GeneratorsOfSemigroup(f2), "a = a^2"); <fp semigroup with 1 generator and 1 relation of length 4> gap> FreeMonoidAndAssignGeneratorVars("a", "b") > / ParseRelations([a, b], "a^2=1,b^3=1,(ab)^3=1"); <fp monoid with 2 generators and 3 relations of length 13>
‣ ElementOfFpSemigroup( S, word ) | ( operation ) |
Returns: An element of the fp semigroup S.
When S is a finitely presented semigroup and word is an associative word in the associated free semigroup (see IsAssocWord (Reference: IsAssocWord)), this returns the fp semigroup element with representative word.
This function is just a short form of the GAP library implementation of ElementOfFpSemigroup (Reference: ElementOfFpSemigroup) which does not require retrieving an element family.
gap> f := FreeSemigroup("x", "y");; gap> AssignGeneratorVariables(f); gap> s := f / [[x * x, x], [y * y, y]]; <fp semigroup with 2 generators and 2 relations of length 8> gap> a := ElementOfFpSemigroup(s, x * y); x*y gap> b := ElementOfFpSemigroup(s, x * y * y); x*y^2 gap> a in s; true gap> a = b; true
‣ ElementOfFpMonoid( M, word ) | ( operation ) |
Returns: An element of the fp monoid M.
When M is a finitely presented monoid and word is an associative word in the associated free monoid (see IsAssocWord (Reference: IsAssocWord)), this returns the fp monoid element with representative word.
This is analogous to ElementOfFpSemigroup (15.2-2).
‣ FreeMonoidAndAssignGeneratorVars( arg... ) | ( function ) |
‣ FreeSemigroupAndAssignGeneratorVars( arg... ) | ( function ) |
Returns: A free semigroup or monoid.
FreeMonoidAndAssignGeneratorVars is synonym with:
FreeMonoid(arg...);
AssignGeneratorVariables(last);These functions exist so that the String method for a finitely presented semigroup or monoid to be valid GAP input which can be used to reconstruct the semigroup or monoid.
gap> F := FreeSemigroupAndAssignGeneratorVars("x", "y");; gap> IsBound(x); true gap> IsBound(y); true
‣ IsSubsemigroupOfFpMonoid( S ) | ( property ) |
Returns: true or false.
This property is true if the object S is a subsemigroup of an fp monoid, and false otherwise. This property is just a synonym for IsSemigroup (Reference: IsSemigroup) and IsElementOfFpMonoidCollection.
gap> F := FreeSemigroup("a", "b"); <free semigroup on the generators [ a, b ]> gap> AssignGeneratorVariables(F); gap> R := [[a ^ 3, a], [b ^ 2, b], [(a * b) ^ 2, a]]; [ [ a^3, a ], [ b^2, b ], [ (a*b)^2, a ] ] gap> S := F / R; <fp semigroup with 2 generators and 3 relations of length 14> gap> IsSubsemigroupOfFpMonoid(S); false gap> map := EmbeddingFpMonoid(S); <fp semigroup with 2 generators and 3 relations of length 14> -> <fp monoid with 2 generators and 3 relations of length 14> gap> IsSubsemigroupOfFpMonoid(Image(map)); true gap> IsSubsemigroupOfFpMonoid(Range(map)); true
It is possible to use GAP to create finitely presented semigroups without the Semigroups package, by creating a free semigroup, then quotienting by a list of relations. This is described in the reference manual (Reference: Finitely Presented Semigroups and Monoids).
However, finitely presented semigroups do not allow for their relations to be simplified, so in the following sections, we describe how to create and modify the semigroup Tietze (IsStzPresentation (15.3-2)) object associated with an fp semigroup. This object can be automatically simplified, or the user can manually apply Tietze transformations to add or remove relations or generators in the presentation.
This object is analogous to PresentationFpGroup (Reference: PresentationFpGroup) implemented for fp groups in the main GAP distribution (Reference: Presentations and Tietze Transformations), but its features are semigroup-specific. Most of the functions used to create, view and manipulate semigroup Tietze objects are prefixed with Stz.
‣ StzPresentation( S ) | ( operation ) |
Returns: A semigroup Tietze (Stz) object.
If s is an fp semigroup (IsFpSemigroup (Reference: IsFpSemigroup)), then this function returns a modifiable object representing the generators and relations of s.
gap> F := FreeSemigroup("a", "b", "c");; gap> AssignGeneratorVariables(F);; gap> S := F / [[a * b, c], [b * c, a], [c * a, b]]; <fp semigroup with 3 generators and 3 relations of length 12> gap> stz := StzPresentation(S); <fp semigroup presentation with 3 generators and 3 relations with length 12>
‣ IsStzPresentation( stz ) | ( filter ) |
Returns: true or false.
Every semigroup Tietze object is an element of the category IsStzPresentation. Internally, each Stz object contains a list of generators (each represented as a string) and a list of relations (each represented as a pair of LetterRep words, see LetterRepAssocWord (Reference: LetterRepAssocWord)). These generator and relation lists can be modified using Tietze transformations (15.5).
When a IsStzPresentation object stz is created from an fp semigroup s using stz := StzPresentation(s), the generators and relations of stz are initially equal to the generators and relations of s. However, as the Stz object stz is modified, these lists may change, and their current state can be viewed using GeneratorsOfStzPresentation (15.3-3) and RelationsOfStzPresentation (15.3-4).
gap> F := FreeSemigroup("a", "b", "c");; gap> AssignGeneratorVariables(F);; gap> S := F / [[a * b, c], [b * c, a], [c * a, b]]; <fp semigroup with 3 generators and 3 relations of length 12> gap> stz := StzPresentation(S); <fp semigroup presentation with 3 generators and 3 relations with length 12> gap> IsStzPresentation(stz); true
‣ GeneratorsOfStzPresentation( stz ) | ( attribute ) |
Returns: A list of strings.
If stz is an StzPresentation (15.3-1) object, then GeneratorsOfStzPresentation will return (as strings) the generators of the fp semigroup that the presentation was created from. In the StzPresentation (15.3-1) object, it is only necessary to know how many generators there are, but for the purposes of representing generators and relations of the presentation object and building a new fp semigroup from the object, the strings representing the generators are stored.
As Tietze transformations are performed on stz, the generators will change, but the labels will remain as close to the original labels as possible, so that if a generator in the fp semigroup obtained from the presentation is the same as a generator in the original fp semigroup, then they should have the same label.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3]]; <fp semigroup with 3 generators and 2 relations of length 19> gap> stz := StzPresentation(T); <fp semigroup presentation with 3 generators and 2 relations with length 19> gap> GeneratorsOfStzPresentation(stz); [ "a", "b", "c" ]
‣ RelationsOfStzPresentation( stz ) | ( attribute ) |
Returns: A list of pairs of words in LetterRep (LetterRepAssocWord (Reference: LetterRepAssocWord)) form.
If stz is an StzPresentation (15.3-1) object, then RelationsOfStzPresentation will return in letter rep form the current relations of the presentation object. When the presentation object is first created, these will be the LetterRep forms of the relations of the fp semigroup object that is used to create stz. As Tietze transformations are performed on the presentation object, the relations returned by this function will change to reflect the transformations.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3]]; <fp semigroup with 3 generators and 2 relations of length 19> gap> stz := StzPresentation(T); <fp semigroup presentation with 3 generators and 2 relations with length 19> gap> RelationsOfStzPresentation(stz); [ [ [ 1 ], [ 2, 2, 2, 2, 2, 3 ] ], [ [ 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2 ] ] ]
‣ UnreducedFpSemigroup( stz ) | ( attribute ) |
Returns: An fp semigroup.
If stz is an StzPresentation (15.3-1) object, then UnreducedFpSemigroup will return the fp semigroup that was used to create stz using StzPresentation (15.3-1).
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3]]; <fp semigroup with 3 generators and 2 relations of length 19> gap> stz := StzPresentation(T); <fp semigroup presentation with 3 generators and 2 relations with length 19> gap> UnreducedFpSemigroup(stz) = T; true
‣ Length( stz ) | ( operation ) |
Returns: A non-negative integer.
If stz is an StzPresentation (15.3-1) object, then the Length of the object is defined as the number of generators plus the lengths of each word in each relation of stz.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]]; <fp semigroup with 3 generators and 3 relations of length 22> gap> stz := StzPresentation(T); <fp semigroup presentation with 3 generators and 3 relations with length 22> gap> Length(stz); 22
Since the relations are stored as flat lists of numbers, there are several methods installed to print the presentations in more user-friendly forms.
All printing methods in this section are displayed as information (Info (Reference: Info)) in the class InfoFpSemigroup at level 1. Setting SetInfoLevevl(InfoFpSemigroup, 0) will suppress the messages, while any higher number will display them.
‣ StzPrintRelations( stz[, list] ) | ( operation ) |
If stz is an StzPresentation (15.3-1) object and list is a list of positive integers, then StzPrintRelations prints for each i in list the ith relation to the console in terms of the stored labels for the generators (that is, as words over the alphabet consisting of the generators of stz).
If list is not specified then StzPrintRelations prints all relations of stz in order.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]]; <fp semigroup with 3 generators and 3 relations of length 22> gap> stz := StzPresentation(T); <fp semigroup presentation with 3 generators and 3 relations with length 22> gap> StzPrintRelations(stz, [2, 3]); #I 2. b^6 = b^3 #I 3. b^2 = b gap> StzPrintRelations(stz); #I 1. a = b^5*c #I 2. b^6 = b^3 #I 3. b^2 = b
‣ StzPrintRelation( stz, int ) | ( operation ) |
If stz is an StzPresentation (15.3-1) object, then StzPrintRelation calls StzPrintRelations with parameters stz and [int].
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]]; <fp semigroup with 3 generators and 3 relations of length 22> gap> stz := StzPresentation(T); <fp semigroup presentation with 3 generators and 3 relations with length 22> gap> StzPrintRelation(stz, 2); #I 2. b^6 = b^3
‣ StzPrintGenerators( stz[, list] ) | ( operation ) |
If stz is an StzPresentation (15.3-1) object and list is a list of positive integers, then StzPrintGenerators for each i in list the ith generator and the number of occurrences of that generator in the relations is printed to the screen.
If list is not specified then StzPrintGenerators prints all generators of stz in order.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]]; <fp semigroup with 3 generators and 3 relations of length 22> gap> stz := StzPresentation(T); <fp semigroup presentation with 3 generators and 3 relations with length 22> gap> StzPrintGenerators(stz, [1, 2]); #I 1. a 1 occurrences #I 2. b 17 occurrences gap> StzPrintGenerators(stz); #I 1. a 1 occurrences #I 2. b 17 occurrences #I 3. c 1 occurrences
‣ StzPrintPresentation( stz ) | ( operation ) |
If stz is an StzPresentation (15.3-1) object, then StzPrintPresentation prints a comprehensive overview of stz, including the generators and number of occurrences of each generator in the relations, the relations as words over the generators, and the forward and backward maps that indicate how the unreduced semigroup maps to the semigroup currently described by stz.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]]; <fp semigroup with 3 generators and 3 relations of length 22> gap> stz := StzPresentation(T); <fp semigroup presentation with 3 generators and 3 relations with length 22> gap> StzPrintPresentation(stz); #I Current generators: #I 1. a 1 occurrences #I 2. b 17 occurrences #I 3. c 1 occurrences #I #I Current relations: #I 1. a = b^5*c #I 2. b^6 = b^3 #I 3. b^2 = b #I #I There are 3 generators and 3 relations of total length 22. #I #I Generators of original fp semigroup expressed as #I combinations of generators in current presentation: #I 1. a = a #I 2. b = b #I 3. c = c #I #I Generators of current presentation expressed as #I combinations of generators of original fp semigroup: #I 1. a = a #I 2. b = b #I 3. c = c
Fundamentally, there are four different changes that can be made to a presentation without changing the algebraic structure of the fp semigroup that can be derived from it. These four changes are called Tietze transformations, and they are primarily implemented in this section as operations on an StzPresentation object that will throw errors if the conditions have not been met to perform the Tietze transformation.
However, the checks required in order to ensure that a Tietze transformation is valid sometimes require verifying equality of two words in an fp semigroup (for example, to ensure that a relation we are adding to the list of relations can be derived from the relations already present). Since these checks sometimes do not terminate, a second implementation of Tietze transformations assumes good faith and does not perform any checks to see whether the requested Tietze transformation actually maintains the structure of the semigroup. This latter type should be used at the user's discretion. If only the first type are used, the presentation will always give a semigroup isomorphic to the one used to create the object, but if instead one is not changing the presentation with the intention of maintaining algebraic structure, these no-check functions are available for use.
The four Tietze transformations on a presentation are adding a relation, removing a relation, adding a generator, and removing a generator, with particular conditions on what can be added/removed in order to maintain structure. More details on each transformation and its arguments and conditions is given in each entry below. In addition to the four elementary transformations, there is an additional function StzSubstituteRelation which applies multiple Tietze transformations in sequence.
‣ StzAddRelation( stz, pair ) | ( operation ) |
If stz is an StzPresentation (15.3-1) object and pair is a list containing two LetterRep words over the generators of stz, then StzAddRelation will perform a Tietze transformation of the first type and add a new relation to stz. This only happens if the new relation that would be formed from pair can be constructed from the other existing relations; that is, if we can perform elementary operations using the existing relations of stz to convert pair[1] into pair[2].
If, instead, pair is a list containing two elements of the fp semigroup S that was used to create stz, and the two words are equal in that semigroup, then this function will add the LetterRep of these words as a new relation to stz.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3]]; <fp semigroup with 3 generators and 2 relations of length 19> gap> stz := StzPresentation(T); <fp semigroup presentation with 3 generators and 2 relations with length 19> gap> pair := [[2, 2, 2, 2, 2, 2, 2, 2, 2], [2, 2, 2]];; gap> StzAddRelation(stz, pair); gap> RelationsOfStzPresentation(stz); [ [ [ 1 ], [ 2, 2, 2, 2, 2, 3 ] ], [ [ 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2 ] ], [ [ 2, 2, 2, 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2 ] ] ] gap> pair2 := [[1, 1], [3]]; [ [ 1, 1 ], [ 3 ] ] gap> StzAddRelation(stz, pair2); Error, StzAddRelation: second argument <pair> must list two words that are equal in the presentation <stz>
‣ StzRemoveRelation( stz, index ) | ( operation ) |
If stz is an StzPresentation (15.3-1) object and index is a positive integer less than or equal to the number of relations of stz, then StzRemoveRelation will perform a Tietze transformation of the second type and remove the indexth relation of stz if that relation is such that one side of it can be obtained from the other by a sequence of elementary operations using only the other relations of stz.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]]; <fp semigroup with 3 generators and 3 relations of length 22> gap> stz := StzPresentation(T); <fp semigroup presentation with 3 generators and 3 relations with length 22> gap> StzRemoveRelation(stz, 2); gap> RelationsOfStzPresentation(stz); [ [ [ 1 ], [ 2, 2, 2, 2, 2, 3 ] ], [ [ 2, 2 ], [ 2 ] ] ] gap> StzRemoveRelation(stz, 2); Error, StzRemoveRelation: second argument <index> must point to a relation that is redundant in the presentation <stz>
‣ StzAddGenerator( stz, word[, name] ) | ( operation ) |
If stz is an StzPresentation (15.3-1) object and word is a LetterRep word over the generators of stz, then StzAddGenerator will perform a Tietze transformation which adds a new generator to stz and a new relation of the form newgenerator = word.
If, instead, word is a word over the fp semigroup S that was used to create stz, then this function will add the new generator and a new relation with the new generator equal to the LetterRep of this word as a new relation to stz.
A new name for the generator is chosen and added automatically based on the names of the existing generators to GeneratorsOfStzPresentation (15.3-3) if the argument name is not included. If it is, and if name is a string that is not equal to an existing generator, then the string added to the list of generators will be name instead.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]]; <fp semigroup with 3 generators and 3 relations of length 22> gap> stz := StzPresentation(T); <fp semigroup presentation with 3 generators and 3 relations with length 22> gap> StzAddGenerator(stz, [2, 2, 2]); gap> RelationsOfStzPresentation(stz); [ [ [ 1 ], [ 2, 2, 2, 2, 2, 3 ] ], [ [ 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2 ] ], [ [ 2, 2 ], [ 2 ] ], [ [ 2, 2, 2 ], [ 4 ] ] ]
‣ StzRemoveGenerator( stz, gen/genname[, index] ) | ( operation ) |
If stz is an StzPresentation (15.3-1) object and gen is a positive integer less than or equal to the number of generators of stz, then StzRemoveGenerator will perform a Tietze transformation which removes the genth generator of stz.
The argument stz must contain a relation of the form gen = word or word = gen, where word contains no occurrences of the generator gen being removed. The generator is then removed from the presentation by replacing every instance of gen with a copy of word.
If the second argument is a string genname rather than a positive integer gen, then the function searches the generators of stz for a generator with the same name and attempts to remove the generator if the same conditions as above are met.
If the argument index is included and is a positive integer less than or equal to the number of relations, then rather than searching the relations for the first to satisfy the necessary conditions, the function checks the indexth relation to see if it satisfies those conditions, and applies the Tietze transformation by removing this relation.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]]; <fp semigroup with 3 generators and 3 relations of length 22> gap> stz := StzPresentation(T); <fp semigroup presentation with 3 generators and 3 relations with length 22> gap> StzRemoveGenerator(stz, 1); gap> RelationsOfStzPresentation(stz); [ [ [ 1, 1, 1, 1, 1, 1 ], [ 1, 1, 1 ] ], [ [ 1, 1 ], [ 1 ] ] ]
‣ StzSubstituteRelation( stz, index, side ) | ( operation ) |
If stz is an StzPresentation (15.3-1) object and index is a positive integer less than or equal to the number of relations of stz and side is either 1 or 2, then StzRemoveGenerator will perform a sequence of Tietze transformations in order to replace, for the indexth relation (say [u, v]), to replace all instances of the sideth word of the relation in all other relations by the other side (so, for side=1, all instances of u in all other relations of stz are replaced by v). This requires two Tietze transformations per relation containing u, one to add a new redundant relation with each u replaced by v, and another to remove the original (now redundant) relation.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]]; <fp semigroup with 3 generators and 3 relations of length 22> gap> stz := StzPresentation(T); <fp semigroup presentation with 3 generators and 3 relations with length 22> gap> StzSubstituteRelation(stz, 3, 1); gap> RelationsOfStzPresentation(stz); [ [ [ 1 ], [ 2, 2, 2, 3 ] ], [ [ 2, 2, 2 ], [ 2, 2 ] ], [ [ 2, 2 ], [ 2 ] ] ] gap> StzSubstituteRelation(stz, 3, 1); gap> RelationsOfStzPresentation(stz); [ [ [ 1 ], [ 2, 2, 3 ] ], [ [ 2, 2 ], [ 2 ] ], [ [ 2, 2 ], [ 2 ] ] ]
Semigroup Tietze transformation objects (IsStzPresentation (15.3-2)) are not actual fp semigroups in the sense of IsFpSemigroup (Reference: IsFpSemigroup). This is because their generators and relations can be modified (see section 15.5). However, an StzPresentation (15.3-1) can be converted back into an actual finitely presented semigroup using the methods described in this section.
The intended use of semigroup Tietze objects is as follows: given an fp semigroup S, create a modifiable presentation using stz := StzPresentation(S), apply Tietze transformations to it (perhaps in order to simplify the presentation), then generate a new fp semigroup T given by stz which is isomorphic to S, but has a simpler presentation. Once T is obtained, it may be of interest to map elements of S over to T, where they may be represented by different combinations of generators. The isomorphism achieving this is described in this section (see StzIsomorphism (15.6-3)).
‣ TietzeForwardMap( stz ) | ( attribute ) |
Returns: A list of lists of positive integers.
If stz is an StzPresentation (15.3-1) object, then TietzeForwardMap returns a list of lists of positive integers. There is an element of this list for every generator of the unreduced semigroup of the presentation (see UnreducedFpSemigroup (15.3-5)) that indicates the word (in LetterRep form) in the semigroup object currently defined by the presentation that the generator maps to.
This mapping is updated as the presentation object is transformed. It begins as a list of the form [[1], [2], [3], . . ., [n]] where n is the number of generators of the unreduced semigroup.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> S := F / [[F.1, F.3 ^ 3], [F.2 ^ 2, F.3 ^ 2]]; <fp semigroup with 3 generators and 2 relations of length 11> gap> stz := StzPresentation(S); <fp semigroup presentation with 3 generators and 2 relations with length 11> gap> StzRemoveGenerator(stz, 1); gap> TietzeForwardMap(stz); [ [ 2, 2, 2 ], [ 1 ], [ 2 ] ]
‣ TietzeBackwardMap( stz ) | ( attribute ) |
Returns: A list of lists of positive integers.
If stz is an StzPresentation (15.3-1) object, then TietzeBackwardMap returns a list of lists of positive integers. There is an element of this list for every generator of the semigroup that the presentation currently defines that indicates the word (in LetterRep form) in the unreduced semigroup of the presentation (see UnreducedFpSemigroup (15.3-5)) that the generator maps to.
This mapping is updated as the presentation object is transformed. It begins as a list of the form [[1], [2], [3], . . ., [n]] where n is the number of generators of the unreduced semigroup.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> S := F / [[F.1, F.3 ^ 3], [F.2 ^ 2, F.3 ^ 2]]; <fp semigroup with 3 generators and 2 relations of length 11> gap> stz := StzPresentation(S); <fp semigroup presentation with 3 generators and 2 relations with length 11> gap> StzRemoveGenerator(stz, 1); gap> TietzeBackwardMap(stz); [ [ 2 ], [ 3 ] ]
‣ StzIsomorphism( stz ) | ( operation ) |
Returns: A mapping object.
If stz is an StzPresentation (15.3-1) object, then StzIsomorphism returns a mapping object that maps the unreduced semigroup of the presentation (see UnreducedFpSemigroup (15.3-5)) to an FpSemigroup object that is defined by the generators and relations of the semigroup presentation at the moment this function is ran.
If a StzIsomorphism is generated from stz, and the presentation stz is further modified afterwards (for example by applying more Tietze transformations or StzSimplifyOnce (15.7-1) to stz), then running StzIsomorphism(stz) a second time will produce a different result consistent with the new generators and relations of stz.
This mapping is built from the TietzeForwardMap (15.6-1) and TietzeBackwardMap (15.6-2) attributes from the presentation object, since if we know how to map the generators of the respective semigroups, then we know how to map any element of that semigroup.
This function is the primary way to obtain the simplified semigroup from the presentation object, by applying Range to the mapping that this function returns.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> S := F / [[F.1, F.3 ^ 3], [F.2 ^ 2, F.3 ^ 2]]; <fp semigroup with 3 generators and 2 relations of length 11> gap> stz := StzPresentation(S); <fp semigroup presentation with 3 generators and 2 relations with length 11> gap> StzRemoveGenerator(stz, "a"); gap> map := StzIsomorphism(stz); <fp semigroup with 3 generators and 2 relations of length 11> -> <fp semigroup with 2 generators and 1 relation of length 6> gap> S.1 ^ map; c^3
It is possible to create a presentation object from an fp semigroup object and attempt to manually reduce it by applying Tietze transformations. However, there may be many different reductions that can be applied, so StzSimplifyOnce can be used to automatically check a number of different possible reductions and apply the best one. Then, StzSimplifyPresentation repeatedly applies StzSimplifyOnce to the presentation object until it fails to reduce the presentation any further. The metric with respect to which the IsStzPresentation object is reduced is Length (15.3-6).
‣ StzSimplifyOnce( stz ) | ( operation ) |
Returns: true or false.
If stz is an StzPresentation (15.3-1) object, then StzSimplifyOnce will check the possible reductions in length for a number of different possible Tietze transformations, and apply the choice which gives the least length. If a valid transformation was found then the function returns true, and if no transformation was performed because none would lead to a reduction in length, then the function returns false.
There are four different possible transformations that StzSimplifyOnce may apply. The function searches for redundant generators and checks if removing them would reduce the overall length of the presentation, it checks whether substituting one side of each relation throughout the rest of the relations would reduce the length, it checks whether there are any trivial relations (of the form w = w for some word w) or any duplicated relations (relations which are formed from precisely the same words as another relation), and it checks whether any frequently occurring subwords in the relations can be replaced with a new generator to reduce the length. For more details, see 15.5
At InfoLevel 2 (which is the default value, and which can be set using SetInfoLevel(InfoFpSemigroup, 2)), the precise transformations performed are printed to the screen.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3]]; <fp semigroup with 3 generators and 2 relations of length 19> gap> stz := StzPresentation(T); <fp semigroup presentation with 3 generators and 2 relations with length 19> gap> StzSimplifyOnce(stz); #I <Removing redundant generator a using relation : 1. a = b^5*c> true gap> stz; <fp semigroup presentation with 2 generators and 1 relation with length 11>
‣ StzSimplifyPresentation( stz ) | ( operation ) |
If stz is an StzPresentation object, then StzSimplifyPresentation will repeatedly apply the best of a few possible reductions to stz until it can no longer reduce the length of the presentation.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3]]; <fp semigroup on the generators [ a, b, c ]> gap> stz := StzPresentation(T); <fp semigroup presentation with 3 generators and 2 relations with length 19> gap> StzSimplifyPresentation(stz); gap> RelationsOfStzPresentation(stz); [ [ [ 1, 1, 1 ], [ 3 ] ], [ [ 3, 3 ], [ 3 ] ] ]
It may be the case that, rather than working with a Tietze transformation object, we want to start with an fp semigroup object and obtain the most simplified version of that fp semigroup that StzSimplifyPresentation can produce. In this case, SimplifyFpSemigroup can be applied to obtain a mapping from its argument to a reduced fp semigroup. If the mapping is not of interest, SimplifiedFpSemigroup can be used to directly obtain a new fp semigroup isomorphic to the first with reduced relations and generators (the mapping is stored as an attribute of the output). With these functions, the user never has to consider precisely what Tietze transformations to perform, and never has to worry about using the StzPresentation object or its associated operations. They can start with an fp semigroup and obtain a simplified fp semigroup.
‣ SimplifyFpSemigroup( S ) | ( operation ) |
Returns: A mapping object.
If S is a finitely presented semigroup, then SimplifyFpSemigroup will return a mapping object which will map S to a finitely presented semigroup which has had its presentation simplified. SimplifyFpSemigroup creates an StzPresentation object stz from S, which is then reduced using Tietze transformations until the presentation cannot be reduced in length any further.
SimplifyFpSemigroup applies the function StzSimplifyPresentation (15.7-2) to stz, which repeatedly checks whether a number of different possible transformations will cause a reduction in length, and if so applies the best one. This loop continues until no transformations cause any reductions, in which case the mapping is returned. The newly reduced FpSemigroup can be accessed either by taking the range of the mapping or calling SimplifiedFpSemigroup, which first runs SimplifyFpSemigroup and then returns the range of the mapping with the mapping held as an attribute.
For more information on how the mapping is created and used, go to 15.6.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3]]; <fp semigroup on the generators [ a, b, c ]> gap> map := SimplifyFpSemigroup(T);; #I Applying StzSimplifyPresentation... #I StzSimplifyPresentation is verbose by default. Use SetInfoLevel(InfoFpSemigroup, 1) to hide #I output while maintaining ability to use StzPrintRelations, StzPrintGenerators, etc. #I Current: <fp semigroup presentation with 3 generators and 2 relations with length 19> #I <Removing redundant generator a using relation : 1. a = b^5*c> #I Current: <fp semigroup presentation with 2 generators and 1 relation with length 11> #I <Creating new generator to replace instances of word: b^3> #I Current: <fp semigroup presentation with 3 generators and 2 relations with length 10> gap> IsMapping(map); true gap> T.1; a gap> T.1 ^ map; b^5*c gap> RelationsOfFpSemigroup(Range(map)); [ [ b^3, d ], [ d^2, d ] ]
‣ SimplifiedFpSemigroup( S ) | ( operation ) |
Returns: A finitely presented semigroup.
If S is an fp semigroup object (IsFpSemigroup (Reference: IsFpSemigroup)), then SimplifiedFpSemigroup will return an FpSemigroup object T which is isomorphic to S which has been reduced to minimise its length. SimplifiedFpSemigroup applies SimplifyFpSemigroup (15.8-1) and assigns the Range of the isomorphism object which is returned to T, adding the isomorphism to T as an attribute. In this way, while T is a completely new FpSemigroup object, words in S can be mapped to T using the map obtained from the attribute FpTietzeIsomorphism (15.8-4).
For more information on the mapping between the semigroups and how it is created, see 15.6.
gap> F := FreeSemigroup("a", "b", "c");; gap> S := F / [[F.1 ^ 4, F.1], [F.1, F.1 ^ 44], [F.1 ^ 8, F.2 * F.3]];; gap> T := SimplifiedFpSemigroup(S);; #I Applying StzSimplifyPresentation... #I StzSimplifyPresentation is verbose by default. Use SetInfoLevel(InfoFpSemigroup, 1) to hide #I output while maintaining ability to use StzPrintRelations, StzPrintGenerators, etc. #I Current: <fp semigroup presentation with 3 generators and 3 relations with length 63> #I <Replacing all instances in other relations of relation: 1. a^4 = a> #I Current: <fp semigroup presentation with 3 generators and 3 relations with length 24> #I <Replacing all instances in other relations of relation: 1. a^4 = a> #I Current: <fp semigroup presentation with 3 generators and 3 relations with length 18> #I <Replacing all instances in other relations of relation: 1. a^4 = a> #I Current: <fp semigroup presentation with 3 generators and 3 relations with length 15> #I <Replacing all instances in other relations of relation: 3. a = a^2> #I Current: <fp semigroup presentation with 3 generators and 3 relations with length 12> #I <Removing duplicate relation: 1. a = a^2> #I Current: <fp semigroup presentation with 3 generators and 2 relations with length 9> #I <Removing redundant generator a using relation : 2. a = b*c> #I Current: <fp semigroup presentation with 2 generators and 1 relation with length 8> gap> map := FpTietzeIsomorphism(T);; gap> S.1 ^ map; b*c gap> S.1 ^ map = T.1 * T.2; true gap> invmap := InverseGeneralMapping(map);; gap> T.1 ^ invmap = S.2; true gap> T.1 = S.2; false
‣ UnreducedFpSemigroup( S ) | ( attribute ) |
Returns: T, an fp semigroup object.
If S is an fp semigroup object that has been obtained through calling SimplifiedFpSemigroup (15.8-2) on some fp semigroup T then UnreducedFpSemigroup returns the original semigroup object before simplification. These are unrelated semigroup objects, except that S will have a FpTietzeIsomorphism (15.8-4) attribute that returns an isomorphic mapping from T to S.
If SimplifyFpSemigroup (15.8-1) has been called on an fp semigroup T, then UnreducedFpSemigroup can be used on the Range of the resultant mapping to obtain the domain.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3]]; <fp semigroup on the generators [ a, b, c ]> gap> S := SimplifiedFpSemigroup(T); #I Applying StzSimplifyPresentation... #I StzSimplifyPresentation is verbose by default. Use SetInfoLevel(InfoFpSemigroup, 1) to hide #I output while maintaining ability to use StzPrintRelations, StzPrintGenerators, etc. #I Current: <fp semigroup presentation with 3 generators and 2 relations with length 19> #I <Removing redundant generator a using relation : 1. a = b^5*c> #I Current: <fp semigroup presentation with 2 generators and 1 relation with length 11> #I <Creating new generator to replace instances of word: b^3> #I Current: <fp semigroup presentation with 3 generators and 2 relations with length 10> <fp semigroup on the generators [ b, c, d ]> gap> UnreducedFpSemigroup(S) = T; true
‣ FpTietzeIsomorphism( S ) | ( attribute ) |
Returns: A mapping object.
If S is an fp semigroup object that has been obtained through calling SimplifiedFpSemigroup (15.8-2) on some fp semigroup T, then FpTietzeIsomorphism returns an isomorphism from T to S. Simplification produces an fp semigroup isomorphic to the original fp semigroup, and these two fp semigroup objects can interact with each other through the mapping given by this function.
gap> F := FreeSemigroup("a", "b", "c"); <free semigroup on the generators [ a, b, c ]> gap> T := F / [[F.1, F.2 ^ 5 * F.3], > [F.2 ^ 6, F.2 ^ 3]]; <fp semigroup on the generators [ a, b, c ]> gap> S := SimplifiedFpSemigroup(T); #I Applying StzSimplifyPresentation... #I StzSimplifyPresentation is verbose by default. Use SetInfoLevel(InfoFpSemigroup, 1) to hide #I output while maintaining ability to use StzPrintRelations, StzPrintGenerators, etc. #I Current: <fp semigroup presentation with 3 generators and 2 relations with length 19> #I <Removing redundant generator a using relation : 1. a = b^5*c> #I Current: <fp semigroup presentation with 2 generators and 1 relation with length 11> #I <Creating new generator to replace instances of word: b^3> #I Current: <fp semigroup presentation with 3 generators and 2 relations with length 10> <fp semigroup on the generators [ b, c, d ]> gap> T.2; b gap> S.1; b gap> T.2 = S.1; false gap> map := FpTietzeIsomorphism(S);; gap> T.2 ^ map = S.1; true
generated by GAPDoc2HTML