Quelle semifp.gi Sprache: unbekannt

Spracherkennung für: .gi vermutete Sprache: Unknown {[0] [0] [0]} [Methode: Schwerpunktbildung, einfache Gewichte, sechs Dimensionen]

#############################################################################
##
##  semigroups/semifp.gi
##  Copyright (C) 2015-2022                              James D. Mitchell
##
##  Licensing information can be found in the README file of this package.
##
#############################################################################
##

# Many of the methods in this file should probably have the filter
# HasRelationsOfFpMonoid/Semigroup added to their requirements, but for some
# reason fp semigroups and monoids don't known their relations at creation.

# All methods for fp semigroups and monoids go via the underlying congruence on
# the free semigroup and free monoid.

# TODO methods for submonoids of fp monoids and subsemigroups of fp semigroups
InstallImmediateMethod(CanUseGapFroidurePin,
IsSubsemigroupOfFpMonoid and HasGeneratorsOfSemigroup, 0,
function(T)
  local x;
  x := Representative(GeneratorsOfSemigroup(T));
  return CanUseFroidurePin(FpMonoidOfElementOfFpMonoid(x));
end);

InstallMethod(UnderlyingCongruence, "for an fp semigroup",
[IsFpSemigroup],
function(S)
  local F, R;
  F := FreeSemigroupOfFpSemigroup(S);
  R := RelationsOfFpSemigroup(S);
  return SemigroupCongruenceByGeneratingPairs(F, R);
end);

InstallMethod(UnderlyingCongruence, "for an fp monoid",
[IsFpMonoid],
function(S)
  local F, R;
  F := FreeMonoidOfFpMonoid(S);
  R := RelationsOfFpMonoid(S);
  return SemigroupCongruenceByGeneratingPairs(F, R);
end);

InstallMethod(ElementOfFpSemigroup,
"for an fp semigroup and an associative word",
[IsFpSemigroup, IsAssocWord],
{S, w} -> ElementOfFpSemigroup(FamilyObj(Representative(S)), w));

InstallMethod(ElementOfFpMonoid,
"for an fp monoid and an associative word",
[IsFpMonoid, IsAssocWord],
{M, w} -> ElementOfFpMonoid(FamilyObj(Representative(M)), w));

InstallMethod(Size, "for an fp semigroup", [IsFpSemigroup],
S -> NrEquivalenceClasses(UnderlyingCongruence(S)));

# TODO(later) more of these

InstallMethod(Size, "for an fp semigroup with nice monomorphism",
[IsFpSemigroup and HasNiceMonomorphism],
S -> Size(Range(NiceMonomorphism(S))));

InstallMethod(AsList, "for an fp semigroup with nice monomorphism",
[IsFpSemigroup and HasNiceMonomorphism],
function(S)
  local map;
  map := InverseGeneralMapping(NiceMonomorphism(S));
  return List(Enumerator(Source(map)), x -> x ^ map);
end);

InstallMethod(Enumerator, "for an fp semigroup with nice monomorphism",
[IsFpSemigroup and HasNiceMonomorphism], 100,
function(S)
  local enum;
  enum := rec();

  enum.map := NiceMonomorphism(S);

  enum.NumberElement := {enum, x} ->
    PositionCanonical(Range(enum!.map), x ^ enum!.map);

  enum.ElementNumber := function(enum, nr)
    return EnumeratorCanonical(Range(enum!.map))[nr]
      ^ InverseGeneralMapping(enum!.map);
  end;

  enum.Length := enum -> Size(S);

  enum.Membership := {x, enum} -> x ^ enum!.map in Range(enum!.map);

  enum.IsBound\[\] := {enum, nr} -> nr <= Size(S);

  return EnumeratorByFunctions(S, enum);
end);

# TODO(later) EnumeratorSorted

InstallMethod(AsSSortedList, "for an fp semigroup with nice monomorphism",
[IsFpSemigroup and HasNiceMonomorphism],
22,
function(S)
  local map;
  map := InverseGeneralMapping(NiceMonomorphism(S));
  # EnumeratorCanonical returns the elements of the Range(NiceMonomorphism(S))
  # in short-lex order, which is sorted.
  return List(EnumeratorCanonical(Source(map)), x -> x ^ map);
end);

InstallMethod(Size, "for an fp monoid", [IsFpMonoid],
S -> NrEquivalenceClasses(UnderlyingCongruence(S)));

InstallMethod(\=, "for elements of an f.p. semigroup",
IsIdenticalObj, [IsElementOfFpSemigroup, IsElementOfFpSemigroup],
function(x, y)
  local C;
  C := UnderlyingCongruence(FpSemigroupOfElementOfFpSemigroup(x));
  return CongruenceTestMembershipNC(C,
                                    UnderlyingElement(x),
                                    UnderlyingElement(y));
end);

InstallMethod(\=, "for two elements of an f.p. monoid",
IsIdenticalObj, [IsElementOfFpMonoid, IsElementOfFpMonoid],
function(x, y)
  local C;
  C := UnderlyingCongruence(FpMonoidOfElementOfFpMonoid(x));
  return CongruenceTestMembershipNC(C,
                                    UnderlyingElement(x),
                                    UnderlyingElement(y));
end);

InstallMethod(\<, "for elements of an f.p. semigroup",
IsIdenticalObj, [IsElementOfFpSemigroup, IsElementOfFpSemigroup],
function(x, y)
  local S, map, C;
  S := FpSemigroupOfElementOfFpSemigroup(x);
  if HasNiceMonomorphism(S) then
    map := NiceMonomorphism(S);
    return PositionCanonical(Range(map), x ^ map)
      < PositionCanonical(Range(map), y ^ map);
  fi;
  C := UnderlyingCongruence(S);
  return CongruenceLessNC(C, UnderlyingElement(x), UnderlyingElement(y));
end);

InstallMethod(\<, "for two elements of an f.p. monoid",
IsIdenticalObj, [IsElementOfFpMonoid, IsElementOfFpMonoid],
function(x, y)
  local C;
  C := UnderlyingCongruence(FpMonoidOfElementOfFpMonoid(x));
  return CongruenceLessNC(C, UnderlyingElement(x), UnderlyingElement(y));
end);

#############################################################################
# Methods not using the underlying congruence directly
#############################################################################

InstallMethod(ExtRepOfObj, "for an element of an fp semigroup",
[IsElementOfFpSemigroup], x -> ExtRepOfObj(UnderlyingElement(x)));

InstallMethod(ExtRepOfObj, "for an element of an fp monoid",
[IsElementOfFpMonoid], x -> ExtRepOfObj(UnderlyingElement(x)));

# TODO(later) AsSSortedList, RightCayleyDigraph, any more?
# - for both IsFpSemigroup/Monoid and IsFpSemigroup/Monoid +
# HasNiceMonomorphism

#############################################################################
# Viewing and printing - elements
#############################################################################

InstallMethod(ViewString, "for an f.p. semigroup element",
[IsElementOfFpSemigroup], String);

InstallMethod(ViewString, "for an f.p. monoid element",
[IsElementOfFpMonoid], String);

#############################################################################
# Viewing and printing - free monoids and semigroups
#############################################################################

InstallMethod(String, "for a free monoid with known generators",
[IsFreeMonoid and HasGeneratorsOfMonoid],
function(M)

  if UserPreference("semigroups", "ViewObj") <> "semigroups-pkg" then
    TryNextMethod();
  fi;

  return StringFormatted("FreeMonoidAndAssignGeneratorVars({})",
                         List(GeneratorsOfMonoid(M), String));
end);

InstallMethod(PrintString, "for a free monoid with known generators",
[IsFreeMonoid and HasGeneratorsOfMonoid], String);

BindGlobal("SEMIGROUPS_FreeSemigroupMonoidPrintObj",
function(M)

  if UserPreference("semigroups", "ViewObj") <> "semigroups-pkg" then
    TryNextMethod();
  fi;

  Print(PrintString(M));
  return;
end);

BindGlobal("SEMIGROUPS_FreeSemigroupMonoidString",
function(M)
  if UserPreference("semigroups", "ViewObj") <> "semigroups-pkg" then
    TryNextMethod();
  fi;
  return String(M);
end);

InstallMethod(PrintObj, "for a free monoid with known generators",
[IsFreeMonoid and HasGeneratorsOfMonoid],
SEMIGROUPS_FreeSemigroupMonoidPrintObj);

InstallMethod(String, "for a free semigroup with known generators",
[IsFreeSemigroup and HasGeneratorsOfSemigroup],
function(M)

  if UserPreference("semigroups", "ViewObj") <> "semigroups-pkg" then
    TryNextMethod();
  fi;

  return StringFormatted("FreeSemigroupAndAssignGeneratorVars({})",
                         List(GeneratorsOfSemigroup(M), String));
end);

InstallMethod(PrintString, "for a free semigroup with known generators",
[IsFreeSemigroup and HasGeneratorsOfSemigroup], String);

InstallMethod(PrintObj, "for a free semigroup with known generators",
[IsFreeSemigroup and HasGeneratorsOfSemigroup],
SEMIGROUPS_FreeSemigroupMonoidPrintObj);

#############################################################################
# Viewing and printing - free monoids and semigroups
#############################################################################

InstallMethod(String, "for an f.p. monoid with known generators",
[IsFpMonoid and HasGeneratorsOfMonoid],
function(M)
  local result, fam, id;

  if UserPreference("semigroups", "ViewObj") <> "semigroups-pkg" then
    TryNextMethod();
  fi;

  result := PRINT_STRINGIFY(FreeMonoidOfFpMonoid(M),
                            " / ",
                            RelationsOfFpMonoid(M));

  fam := ElementsFamily(FamilyObj(FreeMonoidOfFpMonoid(M)));

  if IsEmpty(fam!.names) then
    return result;
  fi;
  id := StringFormatted("One({})", fam!.names[1]);
  return ReplacedString(result, "<identity ...>", id);
end);

InstallMethod(PrintString, "for an f.p. monoid with known generators",
[IsFpMonoid and HasGeneratorsOfMonoid],
SEMIGROUPS_FreeSemigroupMonoidString);

InstallMethod(PrintObj, "for an f.p. monoid with known generators",
[IsFpMonoid and HasGeneratorsOfMonoid],
4,  # to beat the library method
SEMIGROUPS_FreeSemigroupMonoidPrintObj);

InstallMethod(ViewString, "for an f.p. monoid with known generators",
[IsFpMonoid and HasGeneratorsOfMonoid],
function(M)

  if UserPreference("semigroups", "ViewObj") <> "semigroups-pkg" then
    TryNextMethod();
  fi;

  return PRINT_STRINGIFY(
    StringFormatted("\>\><fp monoid with {} and {} of length {}>\<\<",
                    Pluralize(Length(GeneratorsOfMonoid(M)), "generator"),
                    Pluralize(Length(RelationsOfFpMonoid(M)), "relation"),
                    Length(M)));
end);

InstallMethod(ViewObj, "for an f.p. monoid with known generators",
[IsFpMonoid and HasGeneratorsOfMonoid],
4,  # to beat the library method
function(M)
  if UserPreference("semigroups", "ViewObj") <> "semigroups-pkg" then
    TryNextMethod();
  fi;
  Print(ViewString(M));
end);

InstallMethod(String, "for an f.p. semigroup with known generators",
[IsFpSemigroup and HasGeneratorsOfSemigroup],
function(M)

  if UserPreference("semigroups", "ViewObj") <> "semigroups-pkg" then
    TryNextMethod();
  fi;

  return PRINT_STRINGIFY(FreeSemigroupOfFpSemigroup(M),
                        " / ",
                         RelationsOfFpSemigroup(M));
end);

InstallMethod(PrintString, "for an f.p. semigroup with known generators",
[IsFpSemigroup and HasGeneratorsOfSemigroup],
SEMIGROUPS_FreeSemigroupMonoidString);

InstallMethod(PrintObj, "for an f.p. semigroup with known generators",
[IsFpSemigroup and HasGeneratorsOfSemigroup],
4,  # to beat the library method
SEMIGROUPS_FreeSemigroupMonoidPrintObj);

InstallMethod(ViewString, "for an f.p. semigroup with known generators",
[IsFpSemigroup and HasGeneratorsOfSemigroup],
function(S)
  if UserPreference("semigroups", "ViewObj") <> "semigroups-pkg" then
    TryNextMethod();
  fi;

  return PRINT_STRINGIFY(
    StringFormatted("\>\><fp semigroup with {} and {} of length {}>\<\<",
                    Pluralize(Length(GeneratorsOfSemigroup(S)), "generator"),
                    Pluralize(Length(RelationsOfFpSemigroup(S)), "relation"),
                    Length(S)));
end);

InstallMethod(ViewObj,
"for an f.p. semigroup with known generators",
[IsFpSemigroup and HasGeneratorsOfSemigroup],
4,  # to beat the library method
function(S)
  if UserPreference("semigroups", "ViewObj") <> "semigroups-pkg" then
    TryNextMethod();
  fi;
  Print(ViewString(S));
end);

InstallGlobalFunction(FreeMonoidAndAssignGeneratorVars,
function(arg...)
  local F;
  F := CallFuncList(FreeMonoid, arg);
  AssignGeneratorVariables(F);
  return F;
end);

InstallGlobalFunction(FreeSemigroupAndAssignGeneratorVars,
function(arg...)
  local F;
  F := CallFuncList(FreeSemigroup, arg);
  AssignGeneratorVariables(F);
  return F;
end);

########################################################################
# Random
########################################################################

InstallMethod(SEMIGROUPS_ProcessRandomArgsCons,
[IsFpSemigroup, IsList],
function(_, params)
  if Length(params) < 1 then  # nr gens
    params[1] := Random(1, 20);
    params[2] := Random(1, 8);
  elif Length(params) < 2 then  # degree
    params[2] := Random(1, 8);
  fi;
  if not ForAll(params, IsPosInt) then
    ErrorNoReturn("the arguments must be positive integers");
  fi;
  return params;
end);

InstallMethod(SEMIGROUPS_ProcessRandomArgsCons,
[IsFpMonoid, IsList],
{filt, params} -> SEMIGROUPS_ProcessRandomArgsCons(IsFpSemigroup, params));

# this doesn't work very well

InstallMethod(RandomSemigroupCons, "for IsFpSemigroup and a list",
[IsFpSemigroup, IsList],
function(filt, params)
  return AsSemigroup(filt,
                     CallFuncList(RandomSemigroup,
                                  Concatenation([IsTransformationSemigroup],
                                                 params)));
end);

# this doesn't work very well

InstallMethod(RandomMonoidCons, "for IsFpMonoid and a list",
[IsFpMonoid, IsList],
function(filt, params)
  return AsMonoid(filt,
                  CallFuncList(RandomMonoid,
                               Concatenation([IsTransformationMonoid],
                                              params)));
end);

# this doesn't work very well

InstallMethod(RandomInverseSemigroupCons, "for IsFpSemigroup and a list",
[IsFpSemigroup, IsList],
function(filt, params)
  return AsSemigroup(filt,
                     CallFuncList(RandomInverseSemigroup,
                                  Concatenation([IsPartialPermSemigroup],
                                                params)));
end);

# this doesn't work very well

InstallMethod(RandomInverseMonoidCons, "for IsFpMonoid and a list",
[IsFpMonoid, IsList],
function(filt, params)
  return AsMonoid(filt,
                  CallFuncList(RandomInverseMonoid,
                               Concatenation([IsPartialPermMonoid],
                                              params)));
end);

InstallMethod(IsomorphismSemigroup, "for IsFpSemigroup and a semigroup",
[IsFpSemigroup, IsSemigroup],
{filt, S} -> IsomorphismFpSemigroup(S));

InstallMethod(AsMonoid, "for an fp semigroup",
[IsFpSemigroup],
function(S)
  if MultiplicativeNeutralElement(S) = fail then
    return fail;  # so that we do the same as the GAP/ref manual says
  fi;
  return Range(IsomorphismMonoid(IsFpMonoid, S));
end);

InstallMethod(IsomorphismMonoid, "for IsFpMonoid and a semigroup",
[IsFpMonoid, IsSemigroup],
{filt, S} -> IsomorphismFpMonoid(S));

# same method for ideals

InstallMethod(IsomorphismFpSemigroup,
"for a semigroup with CanUseFroidurePin",
[CanUseFroidurePin],
function(S)
  local rules, F, A, rels, Q, B, map, inv, result;

  if not IsFinite(S) or not CanUseFroidurePin(S) then
    TryNextMethod();
  fi;

  rules := RulesOfSemigroup(S);

  F := FreeSemigroup(Length(GeneratorsOfSemigroup(S)));
  A := GeneratorsOfSemigroup(F);
  rels := List(rules, x -> [EvaluateWord(A, x[1]), EvaluateWord(A, x[2])]);

  Q := F / rels;
  B := GeneratorsOfSemigroup(Q);

  map := x -> EvaluateWord(B, Factorization(S, x));
  inv := x -> MappedWord(UnderlyingElement(x), A, GeneratorsOfSemigroup(S));
  result := SemigroupIsomorphismByFunctionNC(S, Q, map, inv);
  if IsTransformationSemigroup(S) or IsPartialPermSemigroup(S)
      or IsBipartitionSemigroup(S) then
    SetNiceMonomorphism(Q, InverseGeneralMapping(result));
  fi;
  if IsTransformationSemigroup(S) then
    SetIsomorphismTransformationSemigroup(Q, InverseGeneralMapping(result));
  elif IsPartialPermSemigroup(S) then
    SetIsomorphismPartialPermSemigroup(Q, InverseGeneralMapping(result));
  fi;
  return result;
end);

# same method for ideals

InstallMethod(IsomorphismFpMonoid, "for a semigroup with CanUseFroidurePin",
[CanUseFroidurePin],
function(S)
  local sgens, mgens, F, A, start, lookup, spos, mpos, pos, rules, rels,
  convert, word, is_redundant, Q, map, inv, i, rule;

  if not IsMonoidAsSemigroup(S) then
    ErrorNoReturn("the 1st argument (a semigroup) must ",
                  "satisfy `IsMonoidAsSemigroup`");
  elif not IsFinite(S) then
    TryNextMethod();
  fi;

  sgens := GeneratorsOfSemigroup(S);
  mgens := Filtered(sgens,
                    x -> x <> MultiplicativeNeutralElement(S));

  F := FreeMonoid(Length(mgens));
  A := GeneratorsOfMonoid(F);
  start := [1 .. Length(sgens)] * 0;
  lookup := [];
  # make sure we map duplicate generators to the correct values
  for i in [1 .. Length(sgens)] do
    spos := Position(sgens, sgens[i]);
    mpos := Position(mgens, sgens[i], start[spos]);
    lookup[i] := mpos;
    if mpos <> fail then
      start[spos] := mpos;
    fi;
  od;

  pos := Position(lookup, fail);

  rules := RulesOfSemigroup(S);
  rels := [];

  # convert a word in GeneratorsOfSemigroup to a word in GeneratorsOfMonoid
  convert := function(word)
    local out, i;
    out := One(F);
    for i in word do
      if lookup[i] <> fail then
        out := out * A[lookup[i]];
      fi;
    od;
    return out;
  end;

  if mgens = sgens then
    # the identity is not a generator, so to avoid adjoining an additional
    # identity in the output, we must add a relation equating the identity with
    # a word in the generators.
    word := Factorization(S, MultiplicativeNeutralElement(S));
    Add(rels, [convert(word), One(F)]);
    # Note that the previously line depends on Factorization always giving a
    # factorization in the GeneratorsOfSemigroup(S), and not in
    # GeneratorsOfMonoid(S) if S happens to be a monoid.
  fi;

  # check if a rule is a consequence of the relation (word = one)
  is_redundant := function(rule)
    local prefix, suffix, i;
    if not IsBound(word) or Length(rule[1]) < Length(word) then
      return false;
    fi;

    # check if <word> is a prefix
    prefix := true;
    for i in [1 .. Length(word)] do
      if word[i] <> rule[1][i] then
        prefix := false;
        break;
      fi;
    od;
    if prefix then
      return rule[1]{[Length(word) + 1 .. Length(rule[1])]} = rule[2];
    fi;

    # check if <word> is a suffix
    suffix := true;
    for i in [1 .. Length(word)] do
      if word[i] <> rule[1][i] then
        suffix := false;
        break;
      fi;
    od;
    if suffix then
      return rule[1]{[1 .. Length(rule[1]) - Length(word)]} = rule[2];
    fi;
    return false;
  end;

  for rule in rules do
    # only include non-redundant rules
    if (Length(rule[1]) <> 2
        or (rule[1][1] <> pos and rule[1][Length(rule[1])] <> pos))
        and (not is_redundant(rule)) then
      Add(rels, [convert(rule[1]), convert(rule[2])]);
    fi;
  od;

  Q := F / rels;

  if sgens = mgens then
    map := x -> EvaluateWord(GeneratorsOfMonoid(Q),
                             Factorization(S, x));
  else
    map := x -> EvaluateWord(GeneratorsOfSemigroup(Q),
                             Factorization(S, x));
  fi;

  inv := function(x)
    if not IsOne(UnderlyingElement(x)) then
      return MappedWord(UnderlyingElement(x), A, mgens);
    fi;
    return MultiplicativeNeutralElement(S);
  end;

  return SemigroupIsomorphismByFunctionNC(S, Q, map, inv);
end);

InstallMethod(AssignGeneratorVariables, "for a free semigroup",
[IsFreeSemigroup],
function(S)
  DoAssignGenVars(GeneratorsOfSemigroup(S));
end);

InstallMethod(AssignGeneratorVariables, "for an free monoid",
[IsFreeMonoid],
function(S)
  DoAssignGenVars(GeneratorsOfMonoid(S));
end);

InstallMethod(AssignGeneratorVariables, "for an fp semigroup",
[IsFpSemigroup],
function(S)
  DoAssignGenVars(GeneratorsOfSemigroup(S));
end);

InstallMethod(AssignGeneratorVariables, "for an fp monoid",
[IsFpMonoid],
function(S)
  DoAssignGenVars(GeneratorsOfMonoid(S));
end);

InstallMethod(IsomorphismFpSemigroup, "for a group",
[IsGroup],
function(G)
  local iso1, inv1, iso2, inv2;
  # The next clause shouldn't be required, but for some reason in GAP 4.10 the
  # rank of the method for IsomorphismFpMonoid for IsFpGroup is lower than this
  # methods rank.
  if IsFpGroup(G) then
    TryNextMethod();
  fi;

  iso1 := IsomorphismFpGroup(G);
  inv1 := InverseGeneralMapping(iso1);
  # TODO(later) the method for IsomorphismFpSemigroup uses the generators of G
  # and their inverses, since we know that G is finite this could be avoided.
  iso2 := IsomorphismFpSemigroup(Range(iso1));
  inv2 := InverseGeneralMapping(iso2);

  return SemigroupIsomorphismByFunctionNC(G,
                                          Range(iso2),
                                          x -> (x ^ iso1) ^ iso2,
                                          x -> (x ^ inv2) ^ inv1);
end);

InstallMethod(IsomorphismFpSemigroup, "for a free semigroup",
[IsFreeSemigroup],
function(S)
  local T;
  T := S / [];
  return SemigroupIsomorphismByImagesNC(S,
                                        T,
                                        GeneratorsOfSemigroup(S),
                                        GeneratorsOfSemigroup(T));
end);

InstallMethod(IsomorphismFpMonoid, "for a free monoid",
[IsFreeMonoid],
function(S)
  local T;
  T := S / [];
  return SemigroupIsomorphismByImagesNC(S,
                                        T,
                                        GeneratorsOfMonoid(S),
                                        GeneratorsOfMonoid(T));
end);

InstallMethod(IsomorphismFpSemigroup, "for a free monoid",
[IsFreeMonoid],
function(S)
  local map1, map2;
  map1 := IsomorphismFpMonoid(S);
  map2 := IsomorphismFpSemigroup(Range(map1));
  return CompositionMapping(map2, map1);
end);

InstallMethod(IsomorphismFpSemigroup, "for an fp semigroup",
[IsFpSemigroup],
function(S)
  return SemigroupIsomorphismByImagesNC(S,
                                        S,
                                        GeneratorsOfSemigroup(S),
                                        GeneratorsOfSemigroup(S));
end);

InstallMethod(IsomorphismFpMonoid, "for an fp monoid",
[IsFpMonoid],
function(M)
  return SemigroupIsomorphismByImagesNC(M,
                                        M,
                                        GeneratorsOfSemigroup(M),
                                        GeneratorsOfSemigroup(M));
end);

# The next method is copied directly from the GAP library the only change is
# the return value which uses SemigroupIsomorphismByFunctionNC here but
# MagmaIsomorphismByFunctionsNC in the GAP library; comments are also removed
# and other superficial changes to adhere to Semigroups package conventions.

InstallMethod(IsomorphismFpSemigroup, "for an fp group", [IsFpGroup],
function(G)
  local freegp, gensfreegp, freesmg, gensfreesmg, idgen, newrels, rels, smgrel,
  semi, gens, isomfun, id, invfun, i, rel;

  freegp := FreeGroupOfFpGroup(G);

  gensfreegp := List(GeneratorsOfSemigroup(freegp), String);
  freesmg := FreeSemigroup(gensfreegp{[1 .. Length(gensfreegp)]});

  gensfreesmg := GeneratorsOfSemigroup(freesmg);
  idgen := gensfreesmg[1];

  newrels := [[idgen * idgen, idgen]];
  for i in [2 .. Length(gensfreesmg)] do
    Add(newrels, [idgen * gensfreesmg[i], gensfreesmg[i]]);
    Add(newrels, [gensfreesmg[i] * idgen, gensfreesmg[i]]);
  od;

  # then relations gens * gens ^ -1 = idgen (and the other way around)
  for i in [2 .. Length(gensfreesmg)] do
    if IsOddInt(i) then
      Add(newrels, [gensfreesmg[i] * gensfreesmg[i - 1], idgen]);
    else
      Add(newrels, [gensfreesmg[i] * gensfreesmg[i + 1], idgen]);
    fi;
  od;

  rels := RelatorsOfFpGroup(G);
  for rel in rels do
     smgrel := [Gpword2MSword(idgen, rel, 1), idgen];
     Add(newrels, smgrel);
  od;

  # finally create the fp semigroup
  semi := FactorFreeSemigroupByRelations(freesmg, newrels);
  gens := GeneratorsOfSemigroup(semi);

  isomfun := x -> ElementOfFpSemigroup(FamilyObj(gens[1]),
                  Gpword2MSword(idgen, UnderlyingElement(x), 1));

  id := One(freegp);
  invfun := x -> ElementOfFpGroup(FamilyObj(One(G)),
              MSword2gpword(id, UnderlyingElement(x), 1));

  return SemigroupIsomorphismByFunctionNC(G, semi, isomfun, invfun);
end);

# The next method is copied directly from the GAP library the only change is
# the return value which uses SemigroupIsomorphismByFunctionNC here but
# MagmaIsomorphismByFunctionsNC in the GAP library; comments are also removed
# and other superficial changes to adhere to Semigroups package conventions.

InstallMethod(IsomorphismFpMonoid, "for an fp group", [IsFpGroup],
function(G)
  local freegp, gens, mongens, s, t, p, freemon, gensmon, id, newrels, rels, w,
  monrel, mon, monfam, isomfun, idg, invfun, hom, i, j, rel;

  freegp := FreeGroupOfFpGroup(G);
  gens := GeneratorsOfGroup(G);

  mongens := [];
  for i in gens do
    s := String(i);
    Add(mongens, s);
    if ForAll(s, x -> x in CHARS_UALPHA or x in CHARS_LALPHA) then
      # inverse: change casification
      t := "";
      for j in [1 .. Length(s)] do
        p := Position(CHARS_LALPHA, s[j]);
        if p <> fail then
          Add(t, CHARS_UALPHA[p]);
        else
          p := Position(CHARS_UALPHA, s[j]);
          Add(t, CHARS_LALPHA[p]);
        fi;
      od;
      s := t;
    else
      s := Concatenation(s, "^-1");
    fi;
    Add(mongens, s);
  od;

  freemon := FreeMonoid(mongens);
  gensmon := GeneratorsOfMonoid(freemon);
  id := Identity(freemon);
  newrels := [];
  # inverse relators
  for i in [1 .. Length(gens)] do
    Add(newrels, [gensmon[2 * i - 1] * gensmon[2 * i], id]);
    Add(newrels, [gensmon[2 * i] * gensmon[2 * i - 1], id]);
  od;

  rels := ValueOption("relations");
  if rels = fail then
    rels := RelatorsOfFpGroup(G);
    for rel in rels do
      w := rel;
      w := GroupwordToMonword(id, w);
      monrel := [w, id];
      Add(newrels, monrel);
    od;
  else
    if not ForAll(Flat(rels), x -> x in FreeGroupOfFpGroup(G)) then
      Info(InfoFpGroup, 1, "Converting relation words into free group");
      rels := List(rels, i -> List(i, UnderlyingElement));
    fi;
    for rel in rels do
      Add(newrels, List(rel, x -> GroupwordToMonword(id, x)));
    od;
  fi;

  mon := FactorFreeMonoidByRelations(freemon, newrels);
  gens := GeneratorsOfMonoid(mon);
  monfam := FamilyObj(Representative(mon));

  isomfun := x -> ElementOfFpMonoid(monfam,
                  GroupwordToMonword(id, UnderlyingElement(x)));

  idg := One(freegp);
  invfun := x -> ElementOfFpGroup(FamilyObj(One(G)),
     MonwordToGroupword(idg, UnderlyingElement(x)));
  hom := SemigroupIsomorphismByFunctionNC(G, mon, isomfun, invfun);
  hom!.type := 1;
  if not HasIsomorphismFpMonoid(G) then
    SetIsomorphismFpMonoid(G, hom);
  fi;
  return hom;
end);

# The next method is copied directly from the GAP library the only change is
# the return value which uses SemigroupIsomorphismByFunctionNC here but
# MagmaIsomorphismByFunctionsNC in the GAP library; comments are also removed
# and other superficial changes to adhere to Semigroups package conventions.

InstallMethod(IsomorphismFpSemigroup, "for an fp monoid", [IsFpMonoid],
function(M)
  local AddToExtRep, FMtoFS, FStoFM, FM, FS, id, rels, next, S, map, inv, x,
  rel;

  AddToExtRep := function(w, id, val)
    local wlist, i;

    wlist := ExtRepOfObj(w);
    wlist := ShallowCopy(wlist);
    for i in [1 .. 1 / 2 * (Length(wlist))] do
      wlist[2 * i - 1] := wlist[2 * i - 1] + val;
    od;

    return ObjByExtRep(FamilyObj(id), wlist);
  end;

  FMtoFS := function(id, w)
    if IsOne(w) then
      return id;
    fi;
    return AddToExtRep(w, id, 1);
  end;

  FStoFM := function(id, w)
    if ExtRepOfObj(w) = [1, 1] then
      return id;
    fi;
    return AddToExtRep(w, id, -1);
  end;

  FM := FreeMonoidOfFpMonoid(M);
  FS := FreeSemigroup(List(GeneratorsOfSemigroup(FM), String));

  id := FS.(Position(GeneratorsOfSemigroup(FM), One(FM)));

  rels := [[id * id, id]];
  for x in GeneratorsOfSemigroup(FS) do
    if x <> id then
      Add(rels, [id * x, x]);
      Add(rels, [x * id, x]);
    fi;
  od;

  for rel in RelationsOfFpMonoid(M) do
    next := [FMtoFS(id, rel[1]), FMtoFS(id, rel[2])];
    Add(rels, next);
  od;

  S := FS / rels;

  map := x -> ElementOfFpSemigroup(FamilyObj(S.1),
                                   FMtoFS(id, UnderlyingElement(x)));

  inv := x -> Image(NaturalHomomorphismByGenerators(FM, M),
                    FStoFM(One(FM), UnderlyingElement(x)));

  return SemigroupIsomorphismByFunctionNC(M, S, map, inv);
end);

InstallMethod(IsomorphismFpMonoid, "for a group", [IsGroup],
function(G)
  local iso1, inv1, iso2, inv2;
  # The next clause shouldn't be required, but for some reason in GAP 4.10 the
  # rank of the method for IsomorphismFpMonoid for IsFpGroup is lower than this
  # methods rank.
  if IsFpGroup(G) then
    TryNextMethod();
  fi;
  iso1 := IsomorphismFpGroup(G);
  inv1 := InverseGeneralMapping(iso1);
  # TODO(later) the method for IsomorphismFpMonoid uses the generators of G and
  # their inverses, since we know that G is finite this could be avoided.
  iso2 := IsomorphismFpMonoid(Range(iso1));
  inv2 := InverseGeneralMapping(iso2);

  return SemigroupIsomorphismByFunctionNC(G,
                                          Range(iso2),
                                          x -> (x ^ iso1) ^ iso2,
                                          x -> (x ^ inv2) ^ inv1);
end);

SEMIGROUPS.ExtRepObjToWord := function(ext_rep_obj)
  local n, word, val, pow, i;
  n    := Length(ext_rep_obj);
  word := [];
  for i in [1, 3 .. n - 1] do
    val := ext_rep_obj[i];
    pow := ext_rep_obj[i + 1];
    while pow > 0 do
      Add(word, val);
      pow := pow - 1;
    od;
  od;
  return word;
end;

SEMIGROUPS.WordToExtRepObj := function(word)
  local ext_rep_obj, i, j;
  ext_rep_obj := [];
  i           := 1;
  j           := 1;

  while i <= Length(word) do
    Add(ext_rep_obj, word[i]);
    Add(ext_rep_obj, 1);
    i := i + 1;
    while i <= Length(word) and word[i] = ext_rep_obj[j] do
      ext_rep_obj[j + 1] := ext_rep_obj[j + 1] + 1;
      i := i + 1;
    od;
    j := j + 2;
  od;
  return ext_rep_obj;
end;

SEMIGROUPS.ExtRepObjToString := function(ext_rep_obj)
  local alphabet, out, i;
  alphabet := "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  out := "";
  for i in [1, 3 .. Length(ext_rep_obj) - 1] do
    if ext_rep_obj[i] > Length(alphabet) then
      ErrorNoReturn("the maximum value in an odd position of the ",
                    "argument must be at most ", Length(alphabet));
    fi;
    Add(out, alphabet[ext_rep_obj[i]]);
    if ext_rep_obj[i + 1] > 1 then
      Append(out, " ^ ");
      Append(out, String(ext_rep_obj[i + 1]));
    fi;
  od;
  return out;
end;

SEMIGROUPS.WordToString := function(word)
  local alphabet, out, letter;
  alphabet := "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  out := "";
  for letter in word do
    if letter > Length(alphabet) then
      ErrorNoReturn("the argument be at most ", Length(alphabet));
    fi;
    Add(out, alphabet[letter]);
  od;
  return out;
end;

# This method is based on the following paper
# Presentations of Factorizable Inverse Monoids
# David Easdown, James East, and D. G. FitzGerald
# July 19, 2004
InstallMethod(IsomorphismFpSemigroup,
"for an inverse partial perm semigroup",
[IsPartialPermSemigroup and IsInverseActingSemigroupRep],
function(M)
  local add_to_odd_positions, S, SS, G, GG, s, g, F, rels, fam, alpha,
  beta, lhs, rhs, map, H, o, comp, U, rhs_list, conj, MF, T, inv, rel, x, y, m,
  i;

  if not IsFactorisableInverseMonoid(M) then
    TryNextMethod();
  fi;

  add_to_odd_positions := function(list, s)
    list{[1, 3 .. Length(list) - 1]} := list{[1, 3 .. Length(list) - 1]} + s;
    return list;
  end;

  S := Semigroup(IdempotentGeneratedSubsemigroup(M));
  SS := GeneratorsOfSemigroup(S);
  G := GroupOfUnits(M);
  GG := GeneratorsOfSemigroup(G);
  s := Length(GeneratorsOfSemigroup(S));
  g := Length(GeneratorsOfSemigroup(G));

  F := FreeSemigroup(s + g);
  rels := [];
  fam := ElementsFamily(FamilyObj(F));

  # R_S - semigroup relations for the idempotent generated subsemigroup
  alpha := IsomorphismFpSemigroup(S);
  for rel in RelationsOfFpSemigroup(Image(alpha)) do
    Add(rels, [ObjByExtRep(fam, ExtRepOfObj(rel[1])),
               ObjByExtRep(fam, ExtRepOfObj(rel[2]))]);
  od;

  # R_G - semigroup relations for the group of units
  beta  := IsomorphismFpSemigroup(G);
  for rel in RelationsOfFpSemigroup(Image(beta)) do
    lhs := add_to_odd_positions(ShallowCopy(ExtRepOfObj(rel[1])), s);
    rhs := add_to_odd_positions(ShallowCopy(ExtRepOfObj(rel[2])), s);
    Add(rels, [ObjByExtRep(fam, lhs), ObjByExtRep(fam, rhs)]);
  od;

  # R_product - see page 4 of the paper
  for x in [1 .. s] do
    for y in [1 .. g] do
      rhs := Factorization(S, SS[x] ^ (GG[y] ^ -1));
      Add(rels, [F.(s + y) * F.(x),
                 EvaluateWord(GeneratorsOfSemigroup(F), rhs) * F.(s + y)]);
    od;
  od;

  map := InverseGeneralMapping(IsomorphismPermGroup(G));
  H   := Source(map);
  o   := Enumerate(LambdaOrb(M));
  # R_tilde - see page 4 of the paper
  for m in [2 .. Length(OrbSCC(o))] do
    comp := OrbSCC(o)[m];
    U := SmallGeneratingSet(Stabilizer(H,
                                       PartialPerm(o[comp[1]], o[comp[1]]),
                                       OnRight));

    for i in comp do
      rhs_list := Factorization(S, PartialPerm(o[i], o[i]));
      rhs := EvaluateWord(GeneratorsOfSemigroup(F), rhs_list);
      conj := MappingPermListList(o[comp[1]], o[i]);
      for x in List(U, x -> x ^ conj) do
        lhs := ShallowCopy(rhs_list);
        Append(lhs, Factorization(G, x ^ map) + s);
        Add(rels, [EvaluateWord(GeneratorsOfSemigroup(F), lhs), rhs]);
      od;
    od;
  od;

  # Relation to identify One(G) and One(S)
  Add(rels, [EvaluateWord(GeneratorsOfSemigroup(F),
                          Factorization(G, One(G)) + s),
             EvaluateWord(GeneratorsOfSemigroup(F),
                          Factorization(S, One(S)))]);

  MF := F / rels;  # FpSemigroup which is isomorphic to M, with different gens.
  fam := ElementsFamily(FamilyObj(MF));
  T := Semigroup(Concatenation(SS, GG));  # M with isomorphic generators to MF
  map := x -> ElementOfFpSemigroup(fam, EvaluateWord(GeneratorsOfSemigroup(F),
                                                     Factorization(T, x)));
  inv := x -> EvaluateWord(GeneratorsOfSemigroup(T),
                           SEMIGROUPS.ExtRepObjToWord(ExtRepOfObj(x)));

  return SemigroupIsomorphismByFunctionNC(M, MF, map, inv);
end);

InstallMethod(ParseRelations,
"for a list of free generators and a string",
[IsDenseList, IsString],
function(gens, inputstring)
    local newinputstring, g, chartoel, RemoveBrackets, ParseRelation, output,
    chars;

    for g in gens do
      g := String(g);
      if Size(g) <> 1 or not IsAlphaChar(g[1]) then
        ErrorNoReturn(
        "expected the 1st argument to be a list of a free semigroup or monoid ",
        "generators represented by a single alphabet letter but found ",
        String(g));
      fi;
    od;

    newinputstring := Filtered(inputstring, x -> x <> ' ');
    chars := List(gens, x -> String(x)[1]);
    if PositionSublist(newinputstring, "=1") <> fail then
      Add(chars, '1');
    fi;

    for g in chars do
      newinputstring := ReplacedString(newinputstring,
                                       [g, '^'],
                                       ['(', g, ')', '^']);
      newinputstring := ReplacedString(newinputstring,
                                       Concatenation(['(', g, ')'], "^1="),
                                       ['(', g, ')', '=']);
      newinputstring := ReplacedString(newinputstring,
                                       Concatenation(['(', g, ')'], "^1)"),
                                       ['(', g, ')', ')']);
      newinputstring := ReplacedString(newinputstring,
                                       Concatenation(['(', g, ')'], "^1("),
                                       ['(', g, ')', '(']);

    od;

    RemoveBrackets := function(word)
        local i, product, lbracket, rbracket, nestcount, index, p, chartoel;
        if word = "" then
            ErrorNoReturn("expected the 2nd argument to be",
                          " a string listing the relations of a semigroup",
                          " but found an = symbol which isn't pairing two",
                          " words");
        fi;

        # if the number of left brackets is different from the number of right
        # brackets they can't possibly pair up
        if Number(word, x -> x = '(') <> Number(word, x -> x = ')') then
            ErrorNoReturn("expected the number of open brackets",
                          " to match the number of closed brackets");
        fi;

        # if the ^ is at the end of the string there is no exponent.
        # if the ^ is at the start of the string there is no base.
        if word[1] = '^' then
            ErrorNoReturn("expected ^ to be preceded by a ) or",
                          " a generator but found beginning of string");
        elif word[Size(word)] = '^' then
            ErrorNoReturn("expected ^ to be followed by a ",
                          "positive integer but found end of string");
        fi;
        # checks that all ^s have an exponent.
        for index in [1 .. Size(word)] do
            if word[index] = '^' then
                if not word[index + 1] in "0123456789" then
                  ErrorNoReturn("expected ^ to be followed by",
                  " a positive integer but found ", [word[index + 1]]);
                fi;
                if word[index - 1] in "0123456789^(" then
                  ErrorNoReturn(
                  "expected ^ to be preceded by a ) or a generator",
                  " but found ", [word[index - 1]]);
                fi;
            fi;
        od;

        # converts a character to the element it represents
        chartoel := function(char)
            local i;
            for i in [1 .. Size(gens)] do
                if char = String(gens[i])[1] then
                    return gens[i];
                fi;
            od;
            if char = '1' and IsAssocWordWithOne(gens[1]) then
              return One(gens);
            fi;
            ErrorNoReturn("expected a free semigroup generator",
                          " but found ", [char]);
        end;

        # i acts as a pointer to positions in the string.
        product := "";
        i := 1;
        while i <= Size(word) do
            # if there are no brackets the character is left as it is.
            if word[i] <> '(' then
                if product = "" then
                  product := chartoel(word[i]);
                else
                  product := product * chartoel(word[i]);
                fi;
            else
                lbracket := i;
                rbracket := -1;
                # tracks how 'deep' the position of i is in terms of nested
                # brackets
                nestcount := 0;
                i := i + 1;
                while i <= Size(word) do
                    if word[i] = '(' then
                        nestcount := nestcount + 1;
                    elif word[i] = ')' then
                        if nestcount = 0 then
                            rbracket := i;
                            break;
                        else
                            nestcount := nestcount - 1;
                        fi;
                    fi;
                    i := i + 1;
                od;
                # if rbracket is not followed by ^ then the value inside the
                # bracket is appended (recursion is used to remove any brackets
                # in this value)
                if rbracket = Size(word) or (not word[rbracket + 1] = '^') then
                    if product = "" then
                      product := RemoveBrackets(
                                 word{[lbracket + 1 .. rbracket - 1]});
                    else
                      product := product *
                                 RemoveBrackets(
                                 word{[lbracket + 1 .. rbracket - 1]});
                    fi;
                # if rbracket is followed by ^ then the value inside the
                # bracket is appended the given number of time
                else
                    i := i + 2;
                    while i <= Size(word) do
                        if word[i] in "0123456789" then
                            i := i + 1;
                        else
                            break;
                        fi;
                    od;

                    p := Int(word{[rbracket + 2 .. i - 1]});
                    if p = 0 then
                      ErrorNoReturn("expected ^ to be followed",
                                    " by a positive integer but found 0");
                    fi;
                    if product = "" then
                       product := RemoveBrackets(word{[lbracket + 1 ..
                                                       rbracket - 1]}) ^ p;
                    else
                       product := product *
                                  RemoveBrackets(word{[lbracket + 1 ..
                                                       rbracket - 1]}) ^ p;
                    fi;
                    i := i - 1;
                fi;
            fi;
            i := i + 1;
        od;
        return product;
    end;

    ParseRelation := x -> List(SplitString(x, "="), RemoveBrackets);
    output := List(SplitString(newinputstring, ","), ParseRelation);
    if ForAny(output, x -> Size(x) = 1) then
      ErrorNoReturn("expected the 2nd argument to be",
                    " a string listing the relations of a semigroup",
                    " but found an = symbol which isn't pairing two",
                    " words");
    fi;
    output := Filtered(output, x -> Size(x) >= 2);
    output := List(output,
                   x -> List([1 .. Size(x) - 1], y -> [x[y], x[y + 1]]));
    return Concatenation(output);
end);

InstallMethod(Factorization, "for an fp semigroup and element",
IsCollsElms, [IsFpSemigroup, IsElementOfFpSemigroup],
{S, x} -> SEMIGROUPS.ExtRepObjToWord(ExtRepOfObj(x)));

# Returns a factorization of the semigroup generators of S, not the monoid
# generators !!!
InstallMethod(Factorization, "for an fp monoid and element",
IsCollsElms, [IsFpMonoid, IsElementOfFpMonoid],
function(_, x)
  local y;
  y := ExtRepOfObj(x);
  if IsEmpty(y) then
    return [1];
  else
    return SEMIGROUPS.ExtRepObjToWord(y) + 1;
  fi;
end);

InstallMethod(Factorization, "for a free semigroup and word",
[IsFreeSemigroup, IsWord],
{S, x} -> SEMIGROUPS.ExtRepObjToWord(ExtRepOfObj(x)));

InstallMethod(MinimalFactorization, "for a free semigroup and word",
[IsFreeSemigroup, IsWord], Factorization);

# Returns a factorization of the semigroup generators of S, not the monoid
# generators !!!
InstallMethod(Factorization, "for a free monoid and word",
[IsFreeMonoid, IsWord],
function(_, x)
  if IsOne(x) then
    return [1];
  else
    return SEMIGROUPS.ExtRepObjToWord(ExtRepOfObj(x)) + 1;
  fi;
end);

InstallMethod(MinimalFactorization, "for a free monoid and word",
[IsFreeMonoid, IsWord], Factorization);

InstallMethod(Length, "for an fp semigroup", [IsFpSemigroup],
function(S)
  return Length(GeneratorsOfSemigroup(S))
    + Sum(RelationsOfFpSemigroup(S), x -> Length(x[1]) + Length(x[2]));
end);

InstallMethod(Length, "for an fp monoid", [IsFpMonoid],
function(S)
  return Length(GeneratorsOfMonoid(S))
    + Sum(RelationsOfFpMonoid(S), x -> Length(x[1]) + Length(x[2]));
end);

InstallMethod(ReversedOp, "for an element of an fp semigroup",
[IsElementOfFpSemigroup],
function(word)
  local rev;
  rev := Reversed(UnderlyingElement(word));
  return ElementOfFpSemigroup(FamilyObj(word), rev);
end);

InstallMethod(ReversedOp, "for an element of an fp monoid",
[IsElementOfFpMonoid],
function(word)
  local rev;
  rev := Reversed(UnderlyingElement(word));
  return ElementOfFpMonoid(FamilyObj(word), rev);
end);

InstallMethod(EmbeddingFpMonoid, "for an fp semigroup",
[IsFpSemigroup],
function(S)
  local F, R, map, T, hom, rel;

  if HasIsMonoidAsSemigroup(S) and IsMonoidAsSemigroup(S) then
    return IsomorphismFpMonoid(S);
  fi;

  F := FreeSemigroupOfFpSemigroup(S);
  F := FreeMonoid(List(GeneratorsOfSemigroup(F), String));
  R := [];

  map := x -> ObjByExtRep(ElementsFamily(FamilyObj(F)), ExtRepOfObj(x));

  for rel in RelationsOfFpSemigroup(S) do
    Add(R, [map(rel[1]), map(rel[2])]);
  od;

  T := F / R;
  hom := SemigroupHomomorphismByImages_NC(S,
                                          T,
                                          GeneratorsOfSemigroup(S),
                                          GeneratorsOfMonoid(T));
  SetIsInjective(hom, true);
  return hom;
end);

Quelle semifp.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.134 Sekunden ]