SSL tietze.gi   Sprache: unbekannt

############################################################################
##
##  fp/tietze.gi
##  Copyright (C) 2021-2022                               Tom Conti-Leslie
##                                                              Ben Spiers
##
##  Licensing information can be found in the README file of this package.
##
############################################################################
##

########################################################################
# This file is organised as follows:
#
# 1.  Definition of the Semigroup Tietze (IsStzPresentation) object
# 2.  Viewing methods for IsStzPresentation objects
# 3.  Internal Tietze transformation functions
# 4.  User-accessible Tietze transformation functions (wrappers)
# 5.  Internal helper functions for word/relation manipulation etc.
# 6.  Internal auto-checkers and appliers for presentation simplifying
# 7.  SimplifyPresentation etc.
# 8.  Other
########################################################################

########################################################################
# 1. Definition of the Semigroup Tietze (IsStzPresentation) object
########################################################################

InstallMethod(StzPresentation, "for a finitely presented semigroup",
[IsFpSemigroup],
function(S)
  local gens, out, rels, type;

  type := NewType(NewFamily("StzFamily", IsStzPresentation),
                  IsStzPresentation and IsComponentObjectRep);

  rels := List(RelationsOfFpSemigroup(S),
              x -> [LetterRepAssocWord(x[1]), LetterRepAssocWord(x[2])]);
  gens := List(GeneratorsOfSemigroup(S), ViewString);

  out := rec(GeneratorsOfStzPresentation := gens,
             RelationsOfStzPresentation  := rels,
             UnreducedFpSemigroup        := S,
             TietzeForwardMap            := List(
               [1 .. Length(GeneratorsOfSemigroup(S))], x -> [x]),
             TietzeBackwardMap           := List(
               [1 .. Length(GeneratorsOfSemigroup(S))], x -> [x]),
             usedGens                    := Set(gens));

  return Objectify(type, out);
end);

InstallMethod(SetRelationsOfStzPresentation,
[IsStzPresentation, IsList],
function(stz, arg)
  if not ForAll(arg, IsList) or
      not ForAll(arg, x -> Length(x) = 2 and ForAll(x, IsList)) or
      not ForAll(arg, x -> ForAll(x, y -> ForAll(y, IsPosInt))) then
        ErrorNoReturn("parameter <arg> must be a list of pairs of words in ",
                      "LetterRep format");
  fi;
  stz!.RelationsOfStzPresentation := arg;
end);

InstallMethod(RelationsOfStzPresentation, [IsStzPresentation],
stz -> stz!.RelationsOfStzPresentation);

InstallMethod(UnreducedFpSemigroup, [IsStzPresentation],
stz -> stz!.UnreducedFpSemigroup);

InstallMethod(TietzeForwardMap, [IsStzPresentation],
stz -> stz!.TietzeForwardMap);

InstallMethod(TietzeBackwardMap, [IsStzPresentation],
stz -> stz!.TietzeBackwardMap);

InstallMethod(GeneratorsOfStzPresentation, [IsStzPresentation],
stz -> stz!.GeneratorsOfStzPresentation);

InstallMethod(SetGeneratorsOfStzPresentation, [IsStzPresentation, IsList],
function(stz, newGens)
  stz!.GeneratorsOfStzPresentation := newGens;
end);

InstallMethod(StzIsomorphism,
[IsStzPresentation],
function(stz)
  local source, range, forward_dict, forward_map, backward_dict, backward_map;
  source := UnreducedFpSemigroup(stz);
  range  := SEMIGROUPS.StzConvertObjToFpSemigroup(stz);

  # build forward map
  forward_dict := TietzeForwardMap(stz);
  forward_map  := function(word)
    local new_word;
    new_word := SEMIGROUPS.StzExpandWord(
                LetterRepAssocWord(UnderlyingElement(word)), forward_dict);
    return Product(new_word, x -> GeneratorsOfSemigroup(range)[x]);
  end;

  # build backward map
  backward_dict := TietzeBackwardMap(stz);
  backward_map  := function(word)
    local new_word;
    new_word := SEMIGROUPS.StzExpandWord(
                LetterRepAssocWord(UnderlyingElement(word)), backward_dict);
    return Product(new_word, x -> GeneratorsOfSemigroup(source)[x]);
  end;

  # TODO(later) are we okay to assume this is necessarily an isomorphism?
  return SemigroupIsomorphismByFunctionNC(source,
                                          range,
                                          forward_map,
                                          backward_map);
end);

InstallMethod(SetTietzeForwardMap,
"for an stz presentation and list",
[IsStzPresentation, IsList],
function(stz, newMaps)
    if not ForAll(newMaps, x -> IsList(x) and ForAll(x, IsPosInt)) then
      ErrorNoReturn("the 2nd argument <newMaps> must ",
                    "be a list of lists of positive integers");
    fi;
    stz!.TietzeForwardMap := newMaps;
end);

InstallMethod(SetTietzeBackwardMap,
"for an stz presentation and list",
[IsStzPresentation, IsList],
function(stz, newMaps)
    if not ForAll(newMaps, x -> IsList(x) and ForAll(x, IsPosInt)) then
      ErrorNoReturn("the 2nd argument <newMaps> must ",
                    "be a list of lists of positive integers");
    fi;
    stz!.TietzeBackwardMap := newMaps;
end);

InstallMethod(TietzeForwardMapReplaceSubword,
"for an stz presentation, list, and list",
[IsStzPresentation, IsList, IsList],
function(stz, subWord, newSubWord)
    local newMaps;
    newMaps := List(stz!.TietzeForwardMap,
                    x -> SEMIGROUPS.StzReplaceSubwordRel(x,
                                                         subWord,
                                                         newSubWord));
    stz!.TietzeForwardMap := newMaps;
end);

# Length of an StzPresentation is defined as the number of generators plus the
# length of every word in the defining relations
InstallMethod(Length, "for an stz presentation", [IsStzPresentation],
function(stz)
  local out, rel;
  out := Length(stz!.GeneratorsOfStzPresentation);
  for rel in RelationsOfStzPresentation(stz) do
    out := out + Length(rel[1]) + Length(rel[2]);
  od;
  return out;
end);

InstallMethod(\<, "for stz presentations",
[IsStzPresentation, IsStzPresentation],
{stz1, stz2} -> Length(stz1) < Length(stz2));

########################################################################
# 2. Viewing methods for IsStzPresentation objects
########################################################################

InstallMethod(ViewString,
[IsStzPresentation],
function(stz)
  local num_gens, num_rels;
  num_gens := Length(stz!.GeneratorsOfStzPresentation);
  num_rels := Length(stz!.RelationsOfStzPresentation);
  return Concatenation(
    StringFormatted("<fp semigroup presentation with {} and {}",
                    Pluralize(num_gens, "generator"),
                    Pluralize(num_rels, "relation")),
    StringFormatted("\< with length {}>", Length(stz)));
end);

SEMIGROUPS.StzRelationDisplayString := function(stz, i)
  local rels, f, gens, w1, w2;
  rels := RelationsOfStzPresentation(stz);
  if i > Length(rels) then
    return fail;
  else
    # We'd like patterns to be grouped, i.e. abab=(ab)^2 when displayed. To
    # do this we sneakily piggyback off display methods for the free semigroup.
    f    := FreeSemigroup(GeneratorsOfStzPresentation(stz));
    gens := GeneratorsOfSemigroup(f);
    w1   := Product(rels[i][1], x -> gens[x]);
    w2   := Product(rels[i][2], x -> gens[x]);
    return Concatenation(PrintString(i),
                         ". ",
                         PrintString(w1),
                         " = ",
                         PrintString(w2));
  fi;
end;

InstallMethod(StzPrintRelations,
"for an stz presentation and a list of pos ints",
[IsStzPresentation, IsList],
function(stz, list)
  local i;
  # This function displays the current relations in terms of the current
  # generators for a semigroup Tietze presentation.
  if IsEmpty(RelationsOfStzPresentation(stz)) then
    Info(InfoFpSemigroup,
         1,
         "There are no relations in the presentation <stz>");
  fi;

  # Print relations at each index of the list, unless incorrect index,
  # in which case skip.
  for i in list do
    if IsPosInt(i) and i <= Length(RelationsOfStzPresentation(stz)) then
      Info(InfoFpSemigroup, 1, SEMIGROUPS.StzRelationDisplayString(stz, i));
    fi;
  od;
end);

InstallMethod(StzPrintRelations, "for an stz presentation",
[IsStzPresentation],
function(stz)
  StzPrintRelations(stz, [1 .. Length(RelationsOfStzPresentation(stz))]);
end);

InstallMethod(StzPrintRelation, "for an stz presentation and a pos int",
[IsStzPresentation, IsPosInt],
function(stz, int)
  StzPrintRelations(stz, [int]);
end);

InstallMethod(StzPrintGenerators,
"for an stz presentation and a list of pos ints",
[IsStzPresentation, IsList],
function(stz, list)
  local flat, gens, out, rel, i;
  # This function displays a list of generators and number of occurrences
  # of each

  # warn if there are no generators in the list (not sure this could happen)
  if IsEmpty(GeneratorsOfStzPresentation(stz)) then
    Info(InfoFpSemigroup, 1,
         "There are no generators in the presentation <stz>");
  fi;

  # create flat flat list of relations to count occurrences
  flat := [];
  for rel in RelationsOfStzPresentation(stz) do
    Append(flat, rel[1]);
    Append(flat, rel[2]);
  od;

  # enumerate and count generators
  gens := GeneratorsOfStzPresentation(stz);
  for i in list do
    # only print if requested index is valid
    if IsPosInt(i) and i <= Length(gens) then
      out := Concatenation(PrintString(i),
                           ".  ",
                           gens[i],
                           "  ",
                           PrintString(Number(flat, x -> x = i)),
                           " occurrences");
      Info(InfoFpSemigroup, 1, out);
    fi;
  od;
end);

InstallMethod(StzPrintGenerators, "for an stz presentation",
[IsStzPresentation],
function(stz)
  StzPrintGenerators(stz, [1 .. Length(GeneratorsOfStzPresentation(stz))]);
end);

InstallMethod(StzPrintPresentation, "for an stz presentation",
[IsStzPresentation],
function(stz)
  local status, oldgens, oldfree, oldelms, newgens, newfree, newelms, w, i;
  # prints everything that is known about the presentation.

  # current generators
  Info(InfoFpSemigroup, 1, "Current generators:");
  StzPrintGenerators(stz);

  # current relations
  Info(InfoFpSemigroup, 1, "");
  Info(InfoFpSemigroup, 1, "Current relations:");
  StzPrintRelations(stz);

  # total number and total length
  Info(InfoFpSemigroup, 1, "");
  status := "There ";
  if Length(stz!.GeneratorsOfStzPresentation) = 1 then
    status := Concatenation(status, "is 1 generator");
  else
    status := Concatenation(status,
                            "are ",
                            PrintString(
                            Length(GeneratorsOfStzPresentation(stz))),
                            " generators");
  fi;
  status := Concatenation(status, " and ");
  if Length(stz!.RelationsOfStzPresentation) = 1 then
    status := Concatenation(status, "1 relation");
  else
    status := Concatenation(status,
               PrintString(Length(stz!.RelationsOfStzPresentation)),
               " relations");
  fi;
  status := Concatenation(status,
                          " of total length ",
                          PrintString(Length(stz)),
                          ".");
  Info(InfoFpSemigroup, 1, status);

  # build free semigroup of old gens for display
  oldgens := GeneratorsOfSemigroup(UnreducedFpSemigroup(stz));
  oldgens := List(oldgens, ViewString);
  oldfree := FreeSemigroup(oldgens);
  oldelms := GeneratorsOfSemigroup(oldfree);

  # build free semigroup of new gens for display
  newgens := GeneratorsOfStzPresentation(stz);
  newfree := FreeSemigroup(newgens);
  newelms := GeneratorsOfSemigroup(newfree);

  # old generators expressed using current ones
  Info(InfoFpSemigroup, 1, "");
  Info(InfoFpSemigroup, 1, "Generators of original fp semigroup expressed as");
  Info(InfoFpSemigroup, 1,
       "combinations of generators in current presentation:");
  for i in [1 .. Length(oldgens)] do
    w := Product(TietzeForwardMap(stz)[i], x -> newelms[x]);
    Info(InfoFpSemigroup, 1, Concatenation(PrintString(i),
                                       ". ",
                                       oldgens[i],
                                       " = ",
                                       PrintString(w)));
  od;

  # new generators expressed using old ones
  Info(InfoFpSemigroup, 1, "");
  Info(InfoFpSemigroup, 1, "Generators of current presentation expressed as");
  Info(InfoFpSemigroup, 1,
       "combinations of generators of original fp semigroup:");
  for i in [1 .. Length(newgens)] do
    w := Product(TietzeBackwardMap(stz)[i], x -> oldelms[x]);
    Info(InfoFpSemigroup, 1, Concatenation(PrintString(i),
                                       ". ",
                                       newgens[i],
                                       " = ",
                                       PrintString(w)));
  od;
end);

########################################################################
# 3. Internal Tietze transformation functions
########################################################################

# TIETZE TRANSFORMATION 1: INTERNAL: ADD REDUNDANT RELATION - NO CHECK
SEMIGROUPS.TietzeTransformation1 := function(stz, pair)
  local rels_copy;
  # Arguments:
  # - <stz> should be a Semigroup Tietze (IsStzPresentation) object.
  # - <pair> should be a list containing two LetterRep words.
  #
  # This function returns nothing, and modifies <stz> in place by adding a new
  # relation given by <pair>. This relation is assumed to be redundant based
  # on the relations already present in RelationsOfStzPresentation(<stz>)
  # (although this is not checked).
  #
  # WARNING: this is an internal function and performs only minimal argument
  # checks. Entering arguments in the wrong format may result in errors that
  # are difficult to interpret. Argument checks are carried out in the
  # analogous, documented function: StzAddRelation. However, these checks
  # may not terminate in some cases.

  # Add relation
  rels_copy := ShallowCopy(RelationsOfStzPresentation(stz));
  Add(rels_copy, pair);
  stz!.RelationsOfStzPresentation := rels_copy;
  return;
end;

# TIETZE TRANSFORMATION 2: INTERNAL: REMOVE REDUNDANT RELATION - NO CHECK
SEMIGROUPS.TietzeTransformation2 := function(stz, index)
  local rels_copy;
  # Arguments:
  # - <stz> should be a Semigroup Tietze (IsStzPresentation) object.
  # - <index> should be the index of the relation in
  #   RelationsOfStzPresentation(<stz>) that needs to be removed.
  #
  # This function returns nothing, and modifies <stz> in place by removing
  # relation number <index>, assumed to be redundant (though redundancy of
  # that relation is not checked).
  #
  # WARNING: this is an internal function and performs only minimal argument
  # checks. Entering arguments in the wrong format may result in errors that
  # are difficult to interpret. Argument checks are carried out in the
  # analogous, documented function: StzRemoveRelation. However, these checks
  # may not terminate in some cases.

  # Remove relation
  rels_copy := ShallowCopy(RelationsOfStzPresentation(stz));
  Remove(rels_copy, index);
  stz!.RelationsOfStzPresentation := rels_copy;
end;

# TIETZE TRANSFORMATION 3: INTERNAL: ADD NEW GENERATOR - NO CHECK
SEMIGROUPS.TietzeTransformation3 := function(stz, word, name)
  local new_gens, new_rels, back_word, new_maps, letter;
  # Arguments:
  # - <stz> should be a Semigroup Tietze (IsStzPresentation) object.
  # - <word> should be a LetterRep word.
  # - <name> should be a string, or fail.
  #
  # This function returns nothing, and modifies <stz> in place by adding a new
  # generator and the relation gen = <word>.
  # The name for the new generator is <name>, unless this argument is fail,
  # in which case the name is automatically generated using
  # SEMIGROUPS.NewGeneratorName.
  # This function also updates the Tietze backwards map so that the new
  # generator can be expressed as a word on the generators of the original
  # semigroup.
  #
  # WARNING: this is an internal function and performs only minimal argument
  # checks. Entering arguments in the wrong format may result in errors that
  # are difficult to interpret. Argument checks are carried out in the
  # analogous, documented function: StzAddGenerator.

  # Add new generator string to the list of gens in similar format
  new_gens := ShallowCopy(stz!.GeneratorsOfStzPresentation);
  new_rels := ShallowCopy(stz!.RelationsOfStzPresentation);
  if name = fail or name in stz!.GeneratorsOfStzPresentation then
    # either name was not specified, or it was but is already a generator.
    # generate a new generator name, as of yet unused.
    Add(new_gens, SEMIGROUPS.NewGeneratorName(List(stz!.usedGens)));
  else
    # this must mean the argument is a string as of yet unused, so add that
    Add(new_gens, ShallowCopy(name));
  fi;

  # in either case we have added a new generator: for cosmetic reasons,
  # prohibit that generator name from being auto-used again (in case we delete
  # it)
  UniteSet(stz!.usedGens, new_gens);

  # Add relation setting new gen equal to <word>
  Add(new_rels, [word, [Length(stz!.GeneratorsOfStzPresentation) + 1]]);

  # Update internal representation of the stz object
  SetGeneratorsOfStzPresentation(stz, new_gens);
  SetRelationsOfStzPresentation(stz, new_rels);

  # Now we need to update the backwards map to express the new generator in
  # terms of the original generators.
  back_word := [];
  new_maps  := ShallowCopy(TietzeBackwardMap(stz));
  for letter in word do
    Append(back_word, new_maps[letter]);
  od;
  Add(new_maps, back_word);
  SetTietzeBackwardMap(stz, new_maps);
end;

# TIETZE TRANSFORMATION 4: INTERNAL: REMOVE GENERATOR - MINIMAL CHECKS
SEMIGROUPS.TietzeTransformation4 := function(stz, gen, index)
  local found_expr, expr, decrement, tempMaps, tempRels, tempGens;
  # Arguments:
  # - <stz> should be a Semigroup Tietze (IsStzPresentation) object.
  # - <gen> should be a pos int.
  # - <index> should be a pos int.
  #
  # This function returns nothing, and modifies <stz> in place by removing
  # generator number <gen> using relation number <index>.
  # If relation number <index> of <stz> is not of the form
  # [<gen>] = *some word not including <gen>* (or that relation flipped),
  # then this function throws ErrorNoReturn.
  # This function also updates the Tietze forward map, so that any generator
  # in the original semigroup expressed as a combination of generators
  # including <gen> is now represented without using <gen> (since <gen>
  # has been removed).
  #
  # WARNING: this is an internal function and performs only minimal argument
  # checks. Entering arguments in the wrong format may result in errors that
  # are difficult to interpret. Argument checks are carried out in the
  # analogous, documented function: StzRemoveGenerator.

  # check we can express <gen> using only other generators with relation
  # number <index>
  found_expr := false;
  if RelationsOfStzPresentation(stz)[index][1] = [gen] and
      not gen in RelationsOfStzPresentation(stz)[index][2] then
    expr := RelationsOfStzPresentation(stz)[index][2];
    found_expr := true;
  elif RelationsOfStzPresentation(stz)[index][2] = [gen] and
      not gen in RelationsOfStzPresentation(stz)[index][1] then
    expr := RelationsOfStzPresentation(stz)[index][1];
    found_expr := true;
  fi;

  # check we found an expression for <gen>. If not, nothing can be done.
  if not found_expr then
    ErrorNoReturn("TietzeTransformation4, internal function: third argument\n",
                  "<index> does not point to a relation expressing second\n",
                  "argument <gen> as a combination of other generators");
  fi;

  # Define decrement function to bump down generator numbers past the one
  # we're going to remove
  decrement := function(z)
    if z <= gen then  # shouldn't be equal but just in case
      return z;
    else
      return z - 1;
    fi;
  end;

  # update forward mapping component
  # TODO(later) do we really need TietzeForwardMapReplaceSubword?
  TietzeForwardMapReplaceSubword(stz, [gen], expr);
  tempMaps := ShallowCopy(TietzeForwardMap(stz));
  Apply(tempMaps, x -> List(x, decrement));
  SetTietzeForwardMap(stz, tempMaps);

  # remove generator from backward mapping component
  tempMaps := ShallowCopy(TietzeBackwardMap(stz));
  Remove(tempMaps, gen);
  SetTietzeBackwardMap(stz, tempMaps);

  # sub in expression we found and remove relation we used for gen
  tempRels := ShallowCopy(RelationsOfStzPresentation(stz));
  Remove(tempRels, index);
  tempRels := SEMIGROUPS.StzReplaceSubword(tempRels, [gen], expr);
  SetRelationsOfStzPresentation(stz, tempRels);
  Apply(stz!.RelationsOfStzPresentation, x -> List(x, y -> List(y, decrement)));

  # remove generator.
  tempGens := ShallowCopy(GeneratorsOfStzPresentation(stz));
  Remove(tempGens, gen);
  SetGeneratorsOfStzPresentation(stz, tempGens);
end;

########################################################################
# 4. User-accessible Tietze transformation functions (wrappers)
########################################################################

# Tietze Transformation 1: Add relation
InstallMethod(StzAddRelation, "for an stz presentation and a pair of words",
[IsStzPresentation, IsList],
1,  # bump ahead of next implementation and do the list size arg check here
function(stz, pair)
  local n, f, free_fam, r, s, fp_fam, w1, w2, p1, p2, word, letter;
  # <pair> should be a pair of LetterRep words.

  # argument checks:
  if Length(pair) <> 2 then
    ErrorNoReturn("StzAddRelation: second argument <pair> should be a list\n",
                  "of length 2");
  fi;
  n := Length(stz!.GeneratorsOfStzPresentation);
  for word in pair do
    if not IsList(word) then
      TryNextMethod();  # pass this on to the case where the list may be a pair
                        # of words in OG semigroup
    elif IsEmpty(word) then
      ErrorNoReturn("StzAddRelation: words in second argument <pair> should\n",
                    "be non-empty");
    else
      for letter in word do
        if not (IsPosInt(letter) and letter <= n) then
          ErrorNoReturn("StzAddRelation: words in second argument <pair>\n",
                        "should be lists of pos ints no greater than the\n",
                        "number of generators of first argument <stz>");
        fi;
      od;
    fi;
  od;

  # check that the pair can be deduced from the other relations, by
  # creating fp semigroup with current relations.

  # base free semigroup
  f        := FreeSemigroup(stz!.GeneratorsOfStzPresentation);
  free_fam := FamilyObj(f.1);            # marrow for creating free semigp words
  r        := List(stz!.RelationsOfStzPresentation,
                   x -> List(x, y -> AssocWordByLetterRep(free_fam, y)));
  s        := f / r;                    # fp semigroup
  fp_fam   := FamilyObj(s.1);           # marrow for creating fp words
  # words first in free semigroup, then map to fp semigroup:
  w1       := AssocWordByLetterRep(free_fam, pair[1]);
  w2       := AssocWordByLetterRep(free_fam, pair[2]);
  p1       := ElementOfFpSemigroup(fp_fam, w1);
  p2       := ElementOfFpSemigroup(fp_fam, w2);
  # check if words are equal in the fp semigroup
  # WARNING: may run forever if undecidable
  if p1 = p2 then
    SEMIGROUPS.TietzeTransformation1(stz, pair);
    return;
  else
    ErrorNoReturn("StzAddRelation: second argument <pair> must list two\n",
                  "words that are equal in the presentation <stz>");
  fi;
end);

InstallMethod(StzAddRelation,
"for an stz presentation and a pair of semigroup elements",
[IsStzPresentation, IsList],
function(stz, pair)
  local s, pairwords, word;
  # retrieve original semigroup
  s := UnreducedFpSemigroup(stz);
  for word in pair do
    if not word in s then
      TryNextMethod();
    fi;
  od;

  # convert into words in original semigroup
  pairwords := List(pair, UnderlyingElement);
  Apply(pairwords, LetterRepAssocWord);
  # map to words in new semigroup
  Apply(pairwords, x -> SEMIGROUPS.StzExpandWord(x, TietzeForwardMap(stz)));

  # apply tietze1, with argument checks
  StzAddRelation(stz, pairwords);
  return;
end);

# Tietze Transformation 1: Add relation (NO REDUNDANCY CHECK)
InstallMethod(StzAddRelationNC, "for an stz presentation and a pair of words",
[IsStzPresentation, IsList],
1,  # bump priority, do list size check here
function(stz, pair)
  local n, word, letter;
  # <pair> should be a pair of LetterRep words.

  # argument checks:
  if Length(pair) <> 2 then
    ErrorNoReturn("StzAddRelationNC: second argument <pair> should be a list\n",
                  "of length 2");
  fi;
  n := Length(stz!.GeneratorsOfStzPresentation);
  for word in pair do
    if not IsList(word) then
      TryNextMethod();  # pass this on to the case where the list may be a pair
                        # of words in OG semigroup
    elif IsEmpty(word) then
      ErrorNoReturn("StzAddRelationNC: words in second argument <pair>\n",
                    "should be non-empty");
    else
      for letter in word do
        if not (IsPosInt(letter) and letter <= n) then
          ErrorNoReturn("StzAddRelationNC: words in second argument <pair>\n",
                        "should be lists of pos ints no greater than the\n",
                        "number of generators of first argument <stz>");
        fi;
      od;
    fi;
  od;

  # WARNING: no checks are run to verify that the pair is redundant. This
  # may result in an output semigroup which is non-isomorphic to the
  # starting semigroup.
  SEMIGROUPS.TietzeTransformation1(stz, pair);
  return;
end);

InstallMethod(StzAddRelationNC,
"for an stz presentation and a pair of semigroup elements",
[IsStzPresentation, IsList],
function(stz, pair)
  local s, pairwords, word;
  # retrieve original semigroup
  s := UnreducedFpSemigroup(stz);
  for word in pair do
    if not word in s then
      TryNextMethod();
    fi;
  od;

  # convert into words in original semigroup
  pairwords := List(pair, UnderlyingElement);
  Apply(pairwords, LetterRepAssocWord);
  # map to words in new semigroup
  Apply(pairwords, x -> SEMIGROUPS.StzExpandWord(x, TietzeForwardMap(stz)));

  # apply tietze1, without argument checks
  # WARNING: no checks are run to verify that the pair is redundant. This
  # may result in an output semigroup which is non-isomorphic to the
  # starting semigroup.
  SEMIGROUPS.TietzeTransformation1(stz, pairwords);
  return;
end);

# Tietze Transformation 2: Remove relation
InstallMethod(StzRemoveRelation,
"for an stz presentation and a pos int",
[IsStzPresentation, IsPosInt],
function(stz, index)
  local rels, pair, new_f, new_gens, new_s, free_fam, w1, w2, fp_fam, p1, p2;
  # <index> should be the index of the relation needing removing in the
  # overall list of relations.

  # argument check: valid index
  rels := ShallowCopy(stz!.RelationsOfStzPresentation);
  if index > Length(rels) then
    ErrorNoReturn("StzRemoveRelation: second argument <index> must be less\n",
                  "than or equal to the number of relations of the first\n",
                  "argument <stz>");
  fi;

  # create hypothetical fp semigroup that would be the result of removing
  # the requested pair
  pair := rels[index];
  Remove(rels, index);
  new_f    := FreeSemigroup(stz!.GeneratorsOfStzPresentation);
  new_gens := GeneratorsOfSemigroup(new_f);
  new_s    := new_f / List(rels,
                           x -> List(x,
                                     y -> Product(List(y,
                                                       z -> new_gens[z]))));

  # create two associative words
  free_fam := FamilyObj(new_f.1);
  w1       := AssocWordByLetterRep(free_fam, pair[1]);
  w2       := AssocWordByLetterRep(free_fam, pair[2]);

  # map these words to hypothetical fp semigroup words and check equality
  fp_fam := FamilyObj(new_s.1);
  p1     := ElementOfFpSemigroup(fp_fam, w1);
  p2     := ElementOfFpSemigroup(fp_fam, w2);

  # WARNING: may run forever if undecidable
  if p1 = p2 then
    SEMIGROUPS.TietzeTransformation2(stz, index);
    return;
  else
    ErrorNoReturn("StzRemoveRelation: second argument <index> must point to\n",
                  "a relation that is redundant in the presentation <stz>");
  fi;
end);

# Tietze Transformation 2: Remove relation (NO REDUNDANCY CHECK)
InstallMethod(StzRemoveRelationNC,
"for an stz presentation and a pos int",
[IsStzPresentation, IsPosInt],
function(stz, index)
  if index > Length(RelationsOfStzPresentation(stz)) then
    ErrorNoReturn("StzRemoveRelationNC: second argument <index> must be less\n",
                  "than or equal to the number of relations of the first\n",
                  "argument <stz>");
  fi;

  # WARNING: no checks are run to verify that the pair is redundant. This
  # may result in an output semigroup which is non-isomorphic to the
  # starting semigroup.
  SEMIGROUPS.TietzeTransformation2(stz, index);
  return;
end);

# Tietze Transformation 3: Add generator
InstallMethod(StzAddGenerator,
"for an stz presentation and a LetterRep word",
[IsStzPresentation, IsList],
function(stz, word)
  local n, letter;
  # argument checks
  if IsEmpty(word) then
    ErrorNoReturn("StzAddGenerator: cannot add generator equal to the empty\n",
                  "word");
  fi;
  n := Length(GeneratorsOfStzPresentation(stz));
  for letter in word do
    if not (IsPosInt(letter) and letter <= n) then
      # the argument has not been entered as a list of pos ints. Pass off to
      # potential future methods for Tietze3, but this is likely to be a
      # mistake.
      ErrorNoReturn("StzAddGenerator: second argument <word> is not a\n",
                    "list of pos ints at most equal to the number of\n",
                    "generators of the first argument <stz>");
    fi;
  od;

  # at this point all is good, so request new generator to be added with
  # a new generator name auto-created.
  SEMIGROUPS.TietzeTransformation3(stz, word, fail);
end);

InstallMethod(StzAddGenerator,
"for an stz presentation and a fp semigroup element",
[IsStzPresentation, IsElementOfFpSemigroup],
function(stz, word)
  local letterrepword;
  # argument check: word should be an element of the unreduced semigroup
  # (that way we can express it as a word on the current tietze generators)
  if not word in UnreducedFpSemigroup(stz) then
    TryNextMethod();
  fi;

  # if we do have an element of s, use the forward map to express it as a word
  # on the current generators, then run the original implementation of Tietze 3.
  letterrepword := SEMIGROUPS.StzExpandWord(
                     LetterRepAssocWord(UnderlyingElement(word)),
                     TietzeForwardMap(stz));
  StzAddGenerator(stz, letterrepword);
end);

# Tietze Transformation 3: Add generator (with specified new generator name)
InstallMethod(StzAddGenerator,
"for an stz presentation, a LetterRep word and a string",
[IsStzPresentation, IsList, IsString],
function(stz, word, name)
  local n, letter;
  # argument check 0: new word is non-empty
  if IsEmpty(word) then
    ErrorNoReturn("StzAddGenerator: cannot add generator equal to the empty\n",
                  "word");
  fi;
  # argument check 1: word is a valid word
  n := Length(GeneratorsOfStzPresentation(stz));
  for letter in word do
    if not (IsPosInt(letter) and letter <= n) then
      # the argument has not been entered as a list of pos ints. Pass off to
      # potential future methods for Tietze3, but this is likely to be a
      # mistake.
      ErrorNoReturn("StzAddGenerator: second argument <word> is not a\n",
                    "list of pos ints at most equal to the number of\n",
                    "generators of the first argument <stz>");
    fi;
  od;

  # argument check 2: requested generator name not yet used
  if name in GeneratorsOfStzPresentation(stz) then
    ErrorNoReturn("StzAddGenerator: third argument <name> should not be the\n",
                  "name of a pre-existing generator");
  fi;

  # otherwise we are all good
  SEMIGROUPS.TietzeTransformation3(stz, word, name);
end);

InstallMethod(StzAddGenerator,
"for an stz presentation, a fp semigroup element and a string",
[IsStzPresentation, IsElementOfFpSemigroup, IsString],
function(stz, word, name)
  local letterrepword;
  # argument check: word should be an element of the unreduced semigroup
  # (that way we can express it as a word on the current tietze generators)
  if not word in UnreducedFpSemigroup(stz) then
    TryNextMethod();
  fi;

  # if we do have an element of s, use the forward map to express it as a word
  # on the current generators, then run the original implementation of Tietze 3.
  letterrepword := SEMIGROUPS.StzExpandWord(
                     LetterRepAssocWord(UnderlyingElement(word)),
                     TietzeForwardMap(stz));
  StzAddGenerator(stz, letterrepword, name);
end);

# Tietze Transformation 4: Remove generator
InstallMethod(StzRemoveGenerator,
"for an stz presentation and a positive integer",
[IsStzPresentation, IsPosInt],
function(stz, gen)
  local found, index, i, rels;
  # argument check 1: requested removal is potentially possible
  if Length(GeneratorsOfStzPresentation(stz)) = 1 then
    ErrorNoReturn("StzRemoveGenerator: cannot remove only remaining\n",
                  "generator \"",
                  GeneratorsOfStzPresentation(stz)[1],
                  "\"");
  elif gen > Length(GeneratorsOfStzPresentation(stz)) then
    ErrorNoReturn("StzRemoveGenerator: second argument <gen> must be no\n",
                  "greater than the total number of generators");
  fi;

  # argument check 2: generator can be expressed as a product of others.
  # this check has to be repeated inside Tietze4, but we include it here to
  # ensure that an incorrect input is clearly reported to the user.
  found := false;
  rels  := RelationsOfStzPresentation(stz);
  for i in [1 .. Length(rels)] do
    if  (rels[i][1] = [gen] and not gen in rels[i][2]) or
        (rels[i][2] = [gen] and not gen in rels[i][1]) then
      found := true;
      index := i;
      continue;
    fi;
  od;
  if not found then
    ErrorNoReturn("StzRemoveGenerator: there is no relation in first\n",
                  "argument <stz> expressing second argument <gen> as a\n",
                  "product of other generators");
  fi;

  # otherwise all good; apply internal Tietze 4 function (it will check
  # whether any relation can actually express that generator as a combination
  # of others)
  SEMIGROUPS.TietzeTransformation4(stz, gen, index);
end);

InstallMethod(StzRemoveGenerator,
"for an stz presentation and a generator name",
[IsStzPresentation, IsString],
function(stz, genname)
  local gen;
  # find index of genname in stz gens
  gen := Position(GeneratorsOfStzPresentation(stz), genname);
  if gen = fail then
    ErrorNoReturn("StzRemoveGenerator: second argument <gen> does not\n",
                  "correspond to a generator name in first argument <stz>");
  else
    StzRemoveGenerator(stz, gen);
  fi;
end);

# Tietze transformation 4 with specified index (e.g. if there are several
# relations allowing the generator to be removed and the user wants a specific
# one)
InstallMethod(StzRemoveGenerator,
"for an stz presentation and two pos ints",
[IsStzPresentation, IsPosInt, IsPosInt],
function(stz, gen, index)
  # first argument check: requested generator exists
  if Length(GeneratorsOfStzPresentation(stz)) = 1 then
    ErrorNoReturn("StzRemoveGenerator: cannot remove only remaining\n",
                  "generator \"",
                  GeneratorsOfStzPresentation(stz)[1],
                  "\"");
  elif gen > Length(GeneratorsOfStzPresentation(stz)) then
    ErrorNoReturn("StzRemoveGenerator: second argument <gen> must be no\n",
                  "greater than the total number of generators");
  fi;

  # second argument check: index exists
  if index > Length(RelationsOfStzPresentation(stz)) then
    ErrorNoReturn("StzRemoveGenerator: third argument <index> must be no\n",
                  "greater than the total number of relations in first\n",
                  "argument <stz>");
  fi;

  # third argument check: a reasonable relation number has been supplied
  if (RelationsOfStzPresentation(stz)[index][1] <> [gen]
      or gen in RelationsOfStzPresentation(stz)[index][2])
      and (RelationsOfStzPresentation(stz)[index][2] <> [gen]
      or gen in RelationsOfStzPresentation(stz)[index][1]) then
    ErrorNoReturn("StzRemoveGenerator: third argument <index> does not point\n",
                  "to a relation expressing second argument <gen> as a\n",
                  "combination of other generators in first argument <stz>");
  fi;

  # if we made it this far then the substitution can be made
  SEMIGROUPS.TietzeTransformation4(stz, gen, index);
end);

InstallMethod(StzRemoveGenerator,
"for an stz presentation, a generator name and a pos int",
[IsStzPresentation, IsString, IsPosInt],
function(stz, genname, index)
  local gen;
  # find index of genname in stz gens
  gen := Position(GeneratorsOfStzPresentation(stz), genname);
  if gen = fail then
    ErrorNoReturn("StzRemoveGenerator: second argument <gen> does not\n",
                  "correspond to a generator name in first argument <stz>");
  else
    StzRemoveGenerator(stz, gen, index);
  fi;
end);

# Tietze Transformation 1/2: substitute relation
InstallMethod(StzSubstituteRelation,
"for an stz presentation and two positive integers",
[IsStzPresentation, IsPosInt, IsPosInt],
function(stz, index, side)
  local oldword, newword, new_rel, i;
  # argument check
  if index > Length(RelationsOfStzPresentation(stz)) then
    ErrorNoReturn("StzSubstituteRelation: second argument <index> must be no\n",
                  "greater than the number of relations in first argument\n",
                  "<stz>");
  fi;
  if not side in [1, 2] then
    ErrorNoReturn("StzSubstituteRelation: third argument <side> must be\n",
                  "either 1 or 2");
  fi;

  oldword := ShallowCopy(RelationsOfStzPresentation(stz)[index][side]);
  newword := ShallowCopy(RelationsOfStzPresentation(stz)[index][[2, 1][side]]);

  # Push relations onto the end of the stack of relations, each time replacing
  # the relation at the front by that relation, with oldword -> newword.
  # Each time, immediately delete the replaced relation at the front of the
  # stack, and do this as many times as there are relations, so that order
  # is preserved.
  # Special case for relation number <index> itself: it should not be changed.
  for i in [1 .. Length(RelationsOfStzPresentation(stz))] do
    if i = index then
      new_rel := [oldword, newword];
    else
      new_rel := List(stz!.RelationsOfStzPresentation[1],
                      x -> SEMIGROUPS.StzReplaceSubwordRel(x,
                                                           oldword,
                                                           newword));
    fi;
    SEMIGROUPS.TietzeTransformation1(stz, new_rel);
    SEMIGROUPS.TietzeTransformation2(stz, 1);
  od;
end);

########################################################################
# 5. Internal helper functions for word/relation manipulation etc.
########################################################################

SEMIGROUPS.StzReplaceSubword := function(rels, subword, newWord)
  local newRels, rel1, rel2, i;

  newRels := List([1 .. Length(rels)], x -> []);
  for i in [1 .. Length(rels)] do
    rel1 := SEMIGROUPS.StzReplaceSubwordRel(rels[i][1], subword, newWord);
    rel2 := SEMIGROUPS.StzReplaceSubwordRel(rels[i][2], subword, newWord);
    newRels[i] := [rel1, rel2];
  od;
  return newRels;
end;

SEMIGROUPS.StzReplaceSubwordRel := function(word, subword, newWord)
  local out, k, l, i;
  # Searches a single LetterRepAssocWord list and replaces instances of
  # subword with newWord.

  # build word up as we read through the old word.
  out := [];
  k   := Length(subword);
  l   := Length(word);
  i   := 1;  # current index that we are looking at when trying to see subword
  while i <= l do
    if word{[i .. Minimum(i + k - 1, l)]} = subword then
      # in this, case the word starting at i needs to be substituted out.
      # (the minimum is there to make sure we don't fall off the end of word)
      Append(out, newWord);
      # jump to end of occurrence
      i := i + k;
    else
      # move over by one and append the original letter, since the word is not
      # seen here.
      Add(out, word[i]);
      i := i + 1;
    fi;
  od;
  return out;
end;

# takes in a letterrep word and replaces every letter with its expression in
# dict.
# NOTE: does not check arguments. Assumes in good faith that every integer
# in word has an entry in the list <dict>.
SEMIGROUPS.StzExpandWord := function(word, dict)
  local out, letter;
  out := [];
  for letter in word do
    Append(out, dict[letter]);
  od;
  return out;
end;

SEMIGROUPS.NewGeneratorName := function(names_immut)
  local alph, Alph, na, nA, names_prefx, names_suffx, int_positions, prefixes,
  prefixes_collected, p, ints, i, name, names;
  names := [];
  for name in names_immut do
    Add(names, ShallowCopy(name));
  od;

  # useful helper variables
  alph := "abcdefghijklmnopqrstuvwxyz";
  Alph := "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

  # SPECIAL CASE 0: empty list
  if IsEmpty(names) then
    return "a";
  fi;

  # SPECIAL CASE 1: only one generator
  if Length(names) = 1 then
    if Length(names[1]) = 1 then
      if names[1][1] in Alph then
        return [First(Alph, x -> not [x] in names)];
      elif names[1][1] in alph then
        return [First(alph, x -> not [x] in names)];
      else
        return "a";
      fi;
    else
      return "a";
    fi;
  fi;

  # SPECIAL CASE 2: single letter names are present. Add an unused letter
  # with the most common capitalisation
  na := Length(Filtered(names, x -> Length(x) = 1 and x[1] in alph));
  nA := Length(Filtered(names, x -> Length(x) = 1 and x[1] in Alph));
  if 2 <= na and na < 26 then
    if na <= nA and nA < 26 then
      return [First(Alph, x -> not [x] in names)];
    else
      return [First(alph, x -> not [x] in names)];
    fi;
  elif 2 <= nA and nA < 26 then
    return [First(Alph, x -> not [x] in names)];
  fi;

  # SPECIAL CASE 3: there are names like s1, s3, s23, etc or x12, etc
  names_prefx := [];
  names_suffx := [];
  for name in names do
    Add(names_prefx, [name[1]]);
    Add(names_suffx, name{[2 .. Length(name)]});
  od;
  int_positions := PositionsProperty(names_suffx, x -> Int(x) <> fail
                                              and x <> ""
                                              and x[1] <> '-');
  if Length(int_positions) >= 2 then
    prefixes           := names_prefx{int_positions};
    prefixes_collected := Collected(prefixes);
    # look for highest frequency in collected list
    p := prefixes_collected[PositionMaximum(prefixes_collected, x -> x[2])][1];
    # find maximum suffix int, even amongst those with prefix not p
    ints := List(names_suffx{int_positions}, Int);
    i    := Maximum(ints) + 1;
    return Concatenation(p, String(i));
  fi;

  # if none of the special cases are covered, just try s1, s2,... until good
  for i in [1 .. Length(names) + 1] do
    if not Concatenation("s", String(i)) in names then
      return Concatenation("s", String(i));
    fi;
  od;
end;

# Counts the number of times a subword appears in the relations of an stz
# presentation, ensuring that the subwords do not overlap
# (Eg, for relations [[1,1,1,1],[1,1]], the subword [1,1] would return 3 and not
# 4)
SEMIGROUPS.StzCountRelationSubwords := function(stz, subWord)
  local count, relSide, rel, rels, pos, len, relSideCopy;
  rels := RelationsOfStzPresentation(stz);
  len := Length(subWord);
  count := 0;
  for rel in rels do
    for relSide in rel do
      pos := PositionSublist(relSide, subWord);
      relSideCopy := ShallowCopy(relSide);
      while pos <> fail do
        count := count + 1;
        relSideCopy := List([(pos + len) .. Length(relSideCopy)],
                            x -> relSideCopy[x]);
        pos := PositionSublist(relSideCopy, subWord);
      od;
    od;
  od;
  return count;
end;

# Converts an Stz presentation into an fp semigroup.
SEMIGROUPS.StzConvertObjToFpSemigroup := function(stz)
  local F, rels, gens;
  F    := FreeSemigroup(stz!.GeneratorsOfStzPresentation);
  rels := RelationsOfStzPresentation(stz);
  gens := GeneratorsOfSemigroup(F);
  return F / List(rels, x -> List(x, y -> Product(List(y, z -> gens[z]))));
end;

########################################################################
# 6.  Internal auto-checkers and appliers for presentation simplifying
########################################################################

## Format to add a new reduction check:
## StzCheck: function that takes an stz presentation as input and checks all
##           possible instances of the desired reduction, and outputs as a
##           record the least length of the possible reductions together with
##           the arguments required to achieve that length
## StzApply: function that takes an stz presentation and the above record as
##           input and applies the arguments from the record to achieve the
##           desired reduction
## Add the above two functions to the list results in StzSimplifyOnce as the
## pair [StzApply, StzCheck(stz)]

SEMIGROUPS.StzFrequentSubwordCheck := function(stz)
  local best_gain, best_word, flat, count_occurrences, n, c, gain, word,
        pair, i, j;
  # SUPER INEFFICIENT (~n^3), do something about this eventually (@Reinis?)
  # Look at every subword, count how many times it appears, and see whether
  # introducing a new generator equal to a given subword would make the
  # whole presentation shorter
  best_gain := 0;   # best reduction seen so far
  best_word := [];  # word currently holding record

  # flat list of words (don't care about which one is related to which)
  flat := [];
  for pair in stz!.RelationsOfStzPresentation do
    Append(flat, ShallowCopy(pair));  # TODO(later) might not need shallow copy
  od;

  # function to count occurrences of subword in list of lists
  count_occurrences := function(list, subword)
    local count, k, l, i, word;
    count := 0;
    k     := Length(subword);
    for word in list do
      l := Length(word);
      i := 1;  # index at which to start counting
      while i <= l - k + 1 do
        if word{[i .. i + k - 1]} = subword then
          count := count + 1;
          # jump to end of occurrence
          i := i + k;
        else
          # move over by one
          i := i + 1;
        fi;
      od;
    od;
    return count;
  end;

  # now check for every subword, how many times it appears
  for word in flat do
    # N.B. ASSUMES WORDS NON-EMPTY
    n := Length(word);
    for i in [1 .. n - 1] do
      for j in [i + 1 .. n] do
        c := count_occurrences(flat, word{[i .. j]});
        # now calculate what a gain that would be:
        # subbing out every instance of word{[i .. j]} for a word of length 1
        # makes us gain j - i characters per substitution
        # BUT, we also have a new generator cost of 1
        # AND a new relation cost of 3 + j - i
        gain := (c - 1) * (j - i) - 3;
        if gain > best_gain then
          best_gain := gain;
          best_word := word{[i .. j]};
        fi;
      od;
    od;
  od;
  return rec(reduction := Length(stz) - best_gain,
             word := best_word);
end;

SEMIGROUPS.StzFrequentSubwordApply := function(stz, metadata)
  local word, rels, n, gens, k, shortened_rels, new_rel, i, str, f, aWord;

  # have received instruction to sub out metadata.word for something shorter.
  word := metadata.word;
  rels := ShallowCopy(RelationsOfStzPresentation(stz));
  n    := Length(rels);
  gens := ShallowCopy(GeneratorsOfStzPresentation(stz));
  k    := Length(gens);

  # Build message
  str := "<Creating new generator to replace instances of word: ";
  f := FreeSemigroup(gens);
  aWord := AssocWordByLetterRep(FamilyObj(f.1), metadata.word);
  Append(str, PrintString(aWord));
  Append(str, ">");
  Info(InfoFpSemigroup, 2, PRINT_STRINGIFY(str));

  # first, add new generator.
  SEMIGROUPS.TietzeTransformation3(stz, word, fail);

  # then, go through and add loads of relations which are the old ones but
  # with the old word subbed out.
  shortened_rels := SEMIGROUPS.StzReplaceSubword(rels, word, [k + 1]);
  for new_rel in shortened_rels do
    SEMIGROUPS.TietzeTransformation1(stz, new_rel);
  od;

  # finally, remove the original relations.
  for i in [1 .. n] do
    SEMIGROUPS.TietzeTransformation2(stz, 1);
  od;
  return;
end;

# Checks each relation in the stz presentation in turn and determines if
# replacing the longer side by the shorter side reduces the length of the
# presentation
SEMIGROUPS.StzRelsSubCheck := function(stz)
  local rels, currentMin, currentRel, tempRel, len, relLenDiff, numInstances,
        newLen, i;
  rels := RelationsOfStzPresentation(stz);
  currentMin := Length(stz);
  currentRel := 0;
  for i in [1 .. Length(rels)] do
    tempRel := ShallowCopy(rels[i]);
    SortBy(tempRel, Length);
    len := Length(stz);
    relLenDiff := Length(tempRel[2]) - Length(tempRel[1]);
    numInstances := SEMIGROUPS.StzCountRelationSubwords(stz, tempRel[2]) - 1;
    newLen := len - numInstances * relLenDiff;
    if newLen < currentMin then
      currentMin := newLen;
      currentRel := i;
    fi;
  od;
  return rec(reduction := currentMin,
              argument := currentRel);
end;

# Checks each relation of the stz presentation to see if any are of the form
# a = w, where a is a generator and w is a word not containing a, then
# determines the length if the generator and relation were removed
SEMIGROUPS.StzRedundantGeneratorCheck := function(stz)
  local rel, rels, numInstances, relPos, tempPositions, r, out, redLen,
        genToRemove, wordToReplace, foundRedundant, currentMin, currentGen,
        currentRel;
  rels := RelationsOfStzPresentation(stz);
  out := [];
  currentMin := Length(stz);
  currentGen := 0;
  currentRel := 0;
  for rel in rels do
    foundRedundant := false;
    if Length(rel[1]) = 1 and Length(rel[2]) = 1 and rel[1] <> rel[2] then
      genToRemove := rel[1][1];
      wordToReplace := rel[2];
      Append(out, [Length(stz) - 3]);
      if Length(stz) - 3 < currentMin then
        currentMin := Length(stz) - 3;
        currentGen := genToRemove;
        currentRel := Position(rels, rel);
      fi;
      continue;
    elif Length(rel[1]) = 1 and Length(rel[2]) > 1 and
          (not (rel[1][1] in rel[2])) then
      genToRemove := rel[1][1];
      wordToReplace := rel[2];
      foundRedundant := true;
    elif Length(rel[2]) = 1 and Length(rel[1]) > 1 and
          (not (rel[2][1] in rel[1])) then
      genToRemove := rel[2][1];
      wordToReplace := rel[1];
      foundRedundant := true;
    fi;
    if foundRedundant then
      relPos := Position(rels, rel);
      numInstances := 0;
      for r in Concatenation([1 .. relPos - 1], [relPos + 1 .. Length(rels)]) do
        tempPositions := Length(Positions(Concatenation(rels[r][1], rels[r][2]),
                                          genToRemove));
        numInstances  := numInstances + tempPositions;
      od;
      redLen := Length(stz) + (numInstances * (Length(wordToReplace) - 1)) -
                2 - Length(wordToReplace);
      if redLen < currentMin then
        currentMin := redLen;
        currentGen := genToRemove;
        currentRel := Position(rels, rel);
      fi;
    fi;
  od;
  return rec(reduction := currentMin,
              argument := currentGen,
              infoRel := currentRel);
end;

# Checks each relation to determine if it is a direct duplicate of another
# (ie does not check equivalence in terms of other relations, just whether they
# are literally the same relation)
SEMIGROUPS.StzDuplicateRelsCheck := function(stz)
  local rel, rels, i, tempRel, j, currentMin, currentRel, len;
  rels := RelationsOfStzPresentation(stz);
  currentMin := Length(stz);
  currentRel := 0;
  if Length(rels) < 2 then
    return rec(reduction := Length(stz),
                argument := 1);
  else
    for j in [1 .. Length(rels)] do
      rel := rels[j];
      for i in Concatenation([1 .. j - 1],
                              [j + 1 .. Length(rels)]) do
        tempRel := rels[i];
        if (tempRel[1] = rel[1] and tempRel[2] = rel[2]) or
            (tempRel[1] = rel[2] and tempRel[2] = rel[1]) then
          len := Length(stz) - Length(rel[1]) - Length(rel[2]);
          if len < currentMin then
            currentMin := len;
            currentRel := j;
          fi;
        fi;
      od;
    od;
    return rec(reduction := currentMin,
                argument := currentRel);
  fi;
end;

# Checks each relation to determine if any are of the form w = w, where w is a
# word over the generators
SEMIGROUPS.StzTrivialRelationCheck := function(stz)
  local rels, len, i, currentMin, currentRel, newLen;
  rels := RelationsOfStzPresentation(stz);
  len := Length(stz);
  currentMin := len;
  currentRel := 0;
  for i in [1 .. Length(rels)] do
    if rels[i][1] = rels[i][2] then
      newLen := len - Length(rels[i][1]) - Length(rels[i][2]);
      if newLen < currentMin then
        currentMin := newLen;
        currentRel := i;
      fi;
    fi;
  od;
  return rec(reduction := currentMin,
              argument := currentRel);
end;

# Removes a trivial relation
SEMIGROUPS.StzTrivialRelationApply := function(stz, args)
  local str;
  str := "<Removing trivial relation: ";
  Append(str, SEMIGROUPS.StzRelationDisplayString(stz, args.argument));
  Append(str, ">");
  Info(InfoFpSemigroup, 2, PRINT_STRINGIFY(str));
  SEMIGROUPS.TietzeTransformation2(stz, args.argument);
end;

# Removes a duplicated relation
SEMIGROUPS.StzDuplicateRelsApply := function(stz, args)
  local str;
  str := "<Removing duplicate relation: ";
  Append(str, SEMIGROUPS.StzRelationDisplayString(stz, args.argument));
  Append(str, ">");
  Info(InfoFpSemigroup, 2, PRINT_STRINGIFY(str));
  SEMIGROUPS.TietzeTransformation2(stz, args.argument);
end;

# Removes a redundant generator
SEMIGROUPS.StzGensRedundantApply := function(stz, args)
  local str;
  str := "<Removing redundant generator ";
  Append(str, GeneratorsOfStzPresentation(stz)[args.argument]);
  Append(str, " using relation : ");
  Append(str, SEMIGROUPS.StzRelationDisplayString(stz, args.infoRel));
  Append(str, ">");
  Info(InfoFpSemigroup, 2, PRINT_STRINGIFY(str));
  SEMIGROUPS.TietzeTransformation4(stz, args.argument, args.infoRel);
end;

# Replaces all instances of one side of a relation with the other inside each
# other relation
SEMIGROUPS.StzRelsSubApply := function(stz, args)
  local str, relIndex, rels, rel, subword, replaceWord, containsRel, newRel, i,
        j;
  str := "<Replacing all instances in other relations of relation: ";
  Append(str, SEMIGROUPS.StzRelationDisplayString(stz, args.argument));
  Append(str, ">");
  Info(InfoFpSemigroup, 2, PRINT_STRINGIFY(str));

  relIndex := args.argument;
  rels := RelationsOfStzPresentation(stz);
  rel := ShallowCopy(rels[relIndex]);
  SortBy(rel, Length);
  # TODO(later) line above: potential edge cases where we are not substituting
  # the longer for the shorter, but rather two words of equal length? I guess
  # not, since the checker function would only suggest this applier function if
  # there was an actual reduction? In that case, careful to use correctly

  # record words to sub out (one we are searching for) and to replace with
  subword := rel[2];
  replaceWord := rel[1];

  # keep track of relation indices where we substituted
  containsRel := [];
  for i in [1 .. Length(rels)] do
    if  i <> relIndex and
        (PositionSublist(rels[i][1], subword) <> fail or
         PositionSublist(rels[i][2], subword) <> fail) then
      Add(containsRel, i);
    fi;
  od;

  for i in containsRel do
    newRel := List([1 .. 2], x -> ShallowCopy(rels[i][x]));
    newRel := List(newRel, x -> SEMIGROUPS.StzReplaceSubwordRel(x, subword,
                                                                replaceWord));
    SEMIGROUPS.TietzeTransformation1(stz, newRel);
  od;
  for j in [1 .. Length(containsRel)] do
    SEMIGROUPS.TietzeTransformation2(stz, containsRel[j]);
    containsRel := containsRel - 1;
  od;
end;

########################################################################
# 7. SimplifyPresentation etc.
########################################################################

InstallMethod(StzSimplifyOnce,
[IsStzPresentation],
function(stz)
  local rels, results, len, mins, result, func, args;
  rels := RelationsOfStzPresentation(stz);
  if IsEmpty(rels) then
    return false;
  else
    results := [[SEMIGROUPS.StzGensRedundantApply,
                  SEMIGROUPS.StzRedundantGeneratorCheck(stz)],
                [SEMIGROUPS.StzDuplicateRelsApply,
                  SEMIGROUPS.StzDuplicateRelsCheck(stz)],
                [SEMIGROUPS.StzRelsSubApply,
                  SEMIGROUPS.StzRelsSubCheck(stz)],
                [SEMIGROUPS.StzFrequentSubwordApply,
                  SEMIGROUPS.StzFrequentSubwordCheck(stz)],
                [SEMIGROUPS.StzTrivialRelationApply,
                  SEMIGROUPS.StzTrivialRelationCheck(stz)]];
    len := Length(stz);
    mins := List(results, x -> x[2].reduction);
    if Minimum(mins) < len then
      result := results[Position(mins, Minimum(mins))];
      func := result[1];
      args := result[2];
      func(stz, args);
      return true;
    fi;
    return false;
  fi;
end);

InstallMethod(StzSimplifyPresentation,
[IsStzPresentation],
function(stz)
  local transformApplied;
  transformApplied := true;
  Info(InfoFpSemigroup, 2, "Applying StzSimplifyPresentation...");
  Info(InfoFpSemigroup, 2, "StzSimplifyPresentation is verbose by default. ",
                           "Use SetInfoLevel(InfoFpSemigroup, 1) to hide");
  Info(InfoFpSemigroup, 2, "output while maintaining ability to use ",
                           "StzPrintRelations, StzPrintGenerators, etc.");
  Info(InfoFpSemigroup, 2, Concatenation("Current: ", ViewString(stz)));
  while transformApplied do
    transformApplied := StzSimplifyOnce(stz);
    if transformApplied then
      Info(InfoFpSemigroup, 2, Concatenation("Current: ", ViewString(stz)));
    fi;
  od;
end);

InstallMethod(SimplifiedFpSemigroup,
[IsFpSemigroup],
function(S)
  local T, map;
  map := SimplifyFpSemigroup(S);
  T := Range(map);
  SetUnreducedFpSemigroup(T, S);
  SetFpTietzeIsomorphism(T, map);
  return T;
end);

InstallMethod(SimplifyFpSemigroup, "for an f.p. semigroup", [IsFpSemigroup],
function(S)
  local stz;
  stz := StzPresentation(S);
  StzSimplifyPresentation(stz);
  return StzIsomorphism(stz);
end);

[ Verzeichnis aufwärts0.54unsichere Verbindung  Übersetzung europäischer Sprachen durch Browser  ]