SSL attr.gi   Sprache: unbekannt

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

# This file contains methods for finding various attributes of finite
# semigroups, which satisfy CanUseFroidurePin or where no better method is
# known.

# Note about the difference between One and MultiplicativeNeutralElement
# (the same goes for Zero and MultplicativeZero):
#
# One(s) returns One(Representative(s)) if it belongs to s, so that
# One(s) = Transformation([1 .. DegreeOfTransformationSemigroup(s)]) if s is a
# transformation semigroup and it returns fail otherwise, or it returns
# PartialPerm([1 .. DegreeOfPartialPermSemigroup]) if this belongs to s.
#
# MultiplicativeNeutralElement on the other hand returns the element of s that
# acts as the identity, note that this can be equal to One(s) but it can also
# not be equal to One(s).
#
# A semigroup satisfies IsMonoidAsSemigroup(s) if
# MultiplicativeNeutralElement(x) <> fail, so it could be that One(s) returns
# fail but IsMonoidAsSemigroup is still true.

SEMIGROUPS.InjectionPrincipalFactor := function(D, constructor)
  local map, inv, G, mat, rep, R, L, x, RR, LL, rms, iso, hom, i, j;

  map := IsomorphismPermGroup(GroupHClass(D));
  inv := InverseGeneralMapping(map);

  G := Range(map);
  mat := [];
  rep := MultiplicativeNeutralElement(GroupHClass(D));
  R := HClassReps(LClass(D, rep));
  L := HClassReps(RClass(D, rep));

  for i in [1 .. Length(L)] do
    mat[i] := [];
    for j in [1 .. Length(R)] do
      x := L[i] * R[j];
      if x in D then
        mat[i][j] := x ^ map;
      else
        mat[i][j] := 0;
      fi;
    od;
  od;

  RR := EmptyPlist(Length(R));
  LL := EmptyPlist(Length(L));

  for j in [1 .. Length(R)] do
    for i in [1 .. Length(L)] do
      if mat[i][j] <> 0 then
        RR[j] := ((mat[i][j] ^ -1) ^ inv) * L[i];
        break;
      fi;
    od;
  od;

  for i in [1 .. Length(L)] do
    for j in [1 .. Length(R)] do
      if mat[i][j] <> 0 then
        LL[i] := R[j] * (mat[i][j] ^ -1) ^ inv;
        break;
      fi;
    od;
  od;

  rms := constructor(G, mat);

  iso := function(x)
    local i, j;

    if not x in D then
      return fail;
    fi;

    i := PositionProperty(R, y -> y in RClass(D, x));
    j := PositionProperty(L, y -> y in LClass(D, x));

    return Objectify(TypeReesMatrixSemigroupElements(rms),
                     [i, (rep * RR[i] * x * LL[j]) ^ map, j, mat]);
  end;

  inv := function(x)
    if x![1] = 0 then
      return fail;
    fi;
    return R[x![1]] * (x![2] ^ InverseGeneralMapping(map)) * L[x![3]];
  end;
  hom := MappingByFunction(D, rms, iso, inv);
  SetIsInjective(hom, true);
  SetIsTotal(hom, true);
  return hom;
end;

#############################################################################
## 1. Default methods, for which there are currently no better methods.
#############################################################################

# Don't use ClosureSemigroup here since the order of the generators matters
# and ClosureSemigroup shuffles the generators.

InstallMethod(GeneratorsSmallest,
"for a semigroup with CanUseFroidurePin",
[CanUseFroidurePin],
function(S)
  local iter, gens, T, closure, x;

  iter := IteratorSorted(S);
  gens := [NextIterator(iter)];
  T    := Semigroup(gens);

  if CanUseLibsemigroupsFroidurePin(S) then
    closure := {S, coll, opts} ->
               ClosureSemigroupOrMonoidNC(Semigroup, S, coll, opts);
  else
    closure := ClosureSemigroup;
  fi;

  for x in iter do
    if not x in T then
      T := closure(T, [x], SEMIGROUPS.OptionsRec(T));
      Add(gens, x);
      if T = S then
        break;
      fi;
    fi;
  od;
  return gens;
end);

InstallMethod(SmallestElementSemigroup, "for a semigroup",
[IsSemigroup],
function(S)
  if not IsFinite(S) then
    TryNextMethod();
  fi;
  return NextIterator(IteratorSorted(S));
end);

InstallMethod(LargestElementSemigroup, "for a semigroup",
[IsSemigroup],
function(S)
  if not IsFinite(S) then
    TryNextMethod();
  fi;
  return EnumeratorSorted(S)[Size(S)];
end);

InstallMethod(NrIdempotents, "for a semigroup", [IsSemigroup],
S -> Length(Idempotents(S)));

InstallMethod(GroupOfUnits, "for a semigroup", [IsSemigroup],
function(S)
  local H, map, U, iso;

  if not IsFinite(S) then
    TryNextMethod();
  elif MultiplicativeNeutralElement(S) = fail then
    return fail;
  fi;

  H := GreensHClassOfElementNC(S, MultiplicativeNeutralElement(S));
  map := IsomorphismPermGroup(H);

  U := Semigroup(List(GeneratorsOfGroup(Range(map)),
                      x -> x ^ InverseGeneralMapping(map)));

  iso := SemigroupIsomorphismByFunctionNC(U,
                                          Range(map),
                                          x -> x ^ map,
                                          x -> x ^ InverseGeneralMapping(map));
  SetIsomorphismPermGroup(U, iso);
  SetIsGroupAsSemigroup(U, true);
  UseIsomorphismRelation(U, Range(iso));
  return U;
end);

# same method for ideals

InstallMethod(IsomorphismReesMatrixSemigroup, "for a D-class",
[IsGreensDClass],
function(D)
  if NrIdempotents(D) <> NrHClasses(D) then
    ErrorNoReturn("the argument (a Green's D-class) is not a semigroup");
  fi;

  return InjectionPrincipalFactor(D);
end);

# same method for ideal

InstallMethod(IrredundantGeneratingSubset,
"for a multiplicative element collection",
[IsMultiplicativeElementCollection],
function(coll)
  local gens, nrgens, deg, out, redund, i, x;

  if (IsSemigroup(coll) and HasGeneratorsOfSemigroup(coll))
      or (HasIsSemigroupIdeal(coll) and IsSemigroupIdeal(coll)) then
    coll := ShallowCopy(GeneratorsOfSemigroup(coll));
  elif not IsMutable(coll) then
    coll := ShallowCopy(coll);
  fi;

  if Size(coll) = 1 then
    return coll;
  fi;

  gens := Set(coll);
  nrgens := Length(gens);

  if nrgens = 1 then
    return gens;
  elif IsGeneratorsOfActingSemigroup(coll) then
    deg := ActionDegree(coll);
    Shuffle(coll);
    Sort(coll, {x, y} -> ActionRank(x, deg) > ActionRank(y, deg));
  fi;

  out := EmptyPlist(Length(coll));
  redund := EmptyPlist(Length(coll));
  i := 0;

  repeat
    i := i + 1;
    x := coll[i];
    if InfoLevel(InfoSemigroups) >= 3 then
      PrintFormatted(
        "at \t{} of \t{} with \t{} redundant, \t{} non-redundant\n",
        i,
        Length(coll),
        Length(redund),
        Length(out));
    fi;

    if not x in redund and not x in out then
      if Length(gens) > 1 and x in Semigroup(Difference(gens, [x])) then
        AddSet(redund, x);
        gens := Difference(gens, [x]);
      else
        AddSet(out, x);
      fi;
    fi;
  until Length(redund) + Length(out) = nrgens;

  if InfoLevel(InfoSemigroups) >= 3 then
    Print("\n");
  fi;

  return out;
end);

# same method for ideals

InstallMethod(MinimalIdeal, "for a semigroup",
[IsSemigroup],
function(S)
  local I;
  if not IsFinite(S) then
    TryNextMethod();
  fi;
  I := SemigroupIdealByGeneratorsNC(S,
                                    [RepresentativeOfMinimalIdeal(S)],
                                    SEMIGROUPS.OptionsRec(S));
  SetIsSimpleSemigroup(I, true);
  return I;
end);

InstallMethod(PrincipalFactor, "for a Green's D-class",
[IsGreensDClass], D -> Range(InjectionPrincipalFactor(D)));

InstallMethod(NormalizedPrincipalFactor, "for a Green's D-class",
[IsGreensDClass], D -> Range(InjectionNormalizedPrincipalFactor(D)));

# different method for ideals, not yet implemented

InstallMethod(SmallSemigroupGeneratingSet, "for a list or collection",
[IsListOrCollection],
function(coll)
  if Length(coll) < 2 then
    return coll;
  fi;
  return GeneratorsOfSemigroup(Semigroup(coll, rec(small := true)));
end);

# different method for ideals, not yet implemented

InstallMethod(SmallSemigroupGeneratingSet,
"for a finite semigroup", [IsSemigroup and IsFinite],
S -> SmallSemigroupGeneratingSet(GeneratorsOfSemigroup(S)));

InstallMethod(SmallMonoidGeneratingSet,
"for a multiplicative element with one collection",
[IsMultiplicativeElementWithOneCollection],
function(coll)
  if Length(coll) < 2 then
    return coll;
  fi;
  return GeneratorsOfMonoid(Monoid(coll, rec(small := true)));
end);

# same method for ideals

InstallMethod(SmallMonoidGeneratingSet, "for a finite monoid",
[IsFinite and IsMonoid],
function(S)
  if Length(GeneratorsOfMonoid(S)) < 2 then
    return GeneratorsOfMonoid(S);
  fi;
  return SmallMonoidGeneratingSet(GeneratorsOfMonoid(S));
end);

InstallMethod(SmallInverseSemigroupGeneratingSet,
"for a multiplicative element coll",
[IsMultiplicativeElementCollection],
function(coll)
  if not IsGeneratorsOfInverseSemigroup(coll) then
    ErrorNoReturn("the argument (a mult. elt. coll.) does not ",
                  "satisfy IsGeneratorsOfInverseSemigroup");
  fi;
  if Length(coll) < 2 then
    return coll;
  fi;
  return GeneratorsOfInverseSemigroup(InverseSemigroup(coll,
                                                       rec(small := true)));
end);

InstallMethod(SmallInverseSemigroupGeneratingSet,
"for an inverse semigroup with inverse op",
[IsInverseSemigroup and IsGeneratorsOfInverseSemigroup],
S -> SmallSemigroupGeneratingSet(GeneratorsOfInverseSemigroup(S)));

InstallMethod(SmallInverseMonoidGeneratingSet,
"for generators of an inverse monoid",
[IsMultiplicativeElementWithOneCollection],
function(coll)
  if not IsGeneratorsOfInverseSemigroup(coll) then
    ErrorNoReturn("the argument (a mult. elt. coll.) do not satisfy ",
                  "IsGeneratorsOfInverseSemigroup");
  fi;
  # The empty list does not satisfy IsGeneratorsOfInverseSemigroup
  Assert(1, not IsEmpty(coll));
  if Length(coll) = 1 then
    if coll[1] = One(coll) then
      return [];
    fi;
    return coll;
  fi;
  return GeneratorsOfInverseMonoid(InverseMonoid(coll, rec(small := true)));
end);

InstallMethod(SmallInverseMonoidGeneratingSet,
"for an inverse monoid with inverse op",
[IsInverseMonoid and IsGeneratorsOfInverseSemigroup],
function(S)
  if IsEmpty(GeneratorsOfInverseMonoid(S)) then
    return GeneratorsOfInverseMonoid(S);
  fi;
  return SmallMonoidGeneratingSet(GeneratorsOfInverseMonoid(S));
end);

InstallMethod(SmallGeneratingSet, "for a semigroup",
[IsSemigroup],
function(S)

  if HasGeneratorsOfSemigroupIdeal(S) then
    return MinimalIdealGeneratingSet(S);
  elif HasGeneratorsOfInverseMonoid(S) then
    return SmallInverseMonoidGeneratingSet(S);
  elif HasGeneratorsOfInverseSemigroup(S) then
    return SmallInverseSemigroupGeneratingSet(S);
  elif HasGeneratorsOfMonoid(S) then
    return SmallMonoidGeneratingSet(S);
  fi;

  return SmallSemigroupGeneratingSet(S);
end);

InstallMethod(StructureDescription, "for a Brandt semigroup",
[IsBrandtSemigroup],
function(S)
  local D;
  D := MaximalDClasses(S)[1];
  return Concatenation("B(", StructureDescription(GroupHClass(D)), ", ",
                       String(NrRClasses(D)), ")");
end);

# same method for ideals

InstallMethod(StructureDescription, "for a group as semigroup",
[IsGroupAsSemigroup],
function(S)
  if IsGroup(S) then
    TryNextMethod();
  fi;
  return StructureDescription(Range(IsomorphismPermGroup(S)));
end);

# same method for ideals

InstallMethod(MultiplicativeZero, "for a semigroup",
[IsSemigroup],
function(S)
  local gens, D, rep;

  if IsSemigroupIdeal(S)
      and HasMultiplicativeZero(SupersemigroupOfIdeal(S)) then
    return MultiplicativeZero(SupersemigroupOfIdeal(S));
  elif HasMinimalDClass(S) then
    D := MinimalDClass(S);
    if HasSize(D) then
      if IsTrivial(D) then
        return Representative(D);
      fi;
      return fail;
    fi;
  elif IsSemigroupIdeal(S) then
    return MultiplicativeZero(SupersemigroupOfIdeal(S));
  elif not IsFinite(S) then
    Info(InfoWarning,
         1,
         "may not be able to find the multiplicative zero, ",
         "the semigroup is infinite");
    # Cannot currently test this line, because the next method runs forever
    TryNextMethod();
  fi;

  rep := RepresentativeOfMinimalIdeal(S);
  gens := GeneratorsOfSemigroup(S);

  if ForAll(gens, x -> x * rep = rep and rep * x = rep) then
    return rep;
  fi;

  return fail;
end);

InstallMethod(MultiplicativeZero, "for a free semigroup",
[IsFreeSemigroup], ReturnFail);

InstallMethod(MultiplicativeZero, "for a free inverse semigroup",
[IsFreeInverseSemigroup], ReturnFail);

InstallMethod(LengthOfLongestDClassChain, "for a semigroup",
[IsSemigroup],
function(S)
  local D, min;

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

  D := DigraphReverse(PartialOrderOfDClasses(S));
  Assert(1, Length(DigraphSources(D)) = 1);
  min := DigraphSources(D)[1];  # minimal D-class
  SetMinimalDClass(S, GreensDClasses(S)[min]);
  SetRepresentativeOfMinimalIdeal(S, Representative(
                                     GreensDClasses(S)[min]));

  return DigraphLongestDistanceFromVertex(D, min);
end);

InstallMethod(NilpotencyDegree, "for a finite semigroup",
[IsSemigroup and IsFinite],
function(S)
  if not IsNilpotentSemigroup(S) then
    return fail;
  fi;
  return LengthOfLongestDClassChain(S) + 1;
end);

InstallMethod(MinimalDClass, "for a semigroup", [IsSemigroup],
S -> GreensDClassOfElementNC(S, RepresentativeOfMinimalIdeal(S)));

#############################################################################
## 2. Methods for attributes where there are known better methods for acting
##    semigroups.
#############################################################################

InstallMethod(IsGreensDGreaterThanFunc,
"for a semigroup with CanUseFroidurePin",
[IsSemigroup and CanUseFroidurePin],
function(S)
  local D, id;

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

  D := PartialOrderOfDClasses(S);
  id := GreensDRelation(S)!.data.id;

  return function(x, y)
    local u, v;
    if x = y then
      return false;
    fi;
    u := id[PositionCanonical(S, x)];
    v := id[PositionCanonical(S, y)];
    return u <> v and IsReachable(D, u, v);
  end;
end);

InstallMethod(MaximalDClasses,
"for a semigroup with CanUseFroidurePin",
[IsSemigroup and CanUseFroidurePin],
function(S)
  local D;
  if NrDClasses(S) = 1 then
    return DClasses(S);
  fi;
  D := PartialOrderOfDClasses(S);
  return DClasses(S){DigraphSources(D)};
end);

InstallMethod(MaximalDClasses,
"for a finite monoid as semigroup with mult. neutral elt",
[IsFinite and IsMonoidAsSemigroup and HasMultiplicativeNeutralElement],
S -> [DClass(S, MultiplicativeNeutralElement(S))]);

InstallMethod(MaximalLClasses,
"for a semigroup that CanUseFroidurePin",
[IsSemigroup and CanUseFroidurePin],
function(S)

  if NrLClasses(S) = 1 then
    return LClasses(S);
  fi;

  return LClasses(S){DigraphSources(PartialOrderOfLClasses(S))};
end);

InstallMethod(MaximalRClasses,
"for a semigroup that CanUseFroidurePin",
[IsSemigroup and CanUseFroidurePin],
function(S)

  if NrRClasses(S) = 1 then
    return RClasses(S);
  fi;

  return RClasses(S){DigraphSources(PartialOrderOfRClasses(S))};
end);

# same method for ideals

InstallMethod(StructureDescriptionMaximalSubgroups,
"for a semigroup", [IsSemigroup],
function(S)
  local out, D;

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

  out := [];
  for D in RegularDClasses(S) do
    AddSet(out, StructureDescription(GroupHClass(D)));
  od;

  return out;
end);

InstallMethod(IdempotentGeneratedSubsemigroup, "for a semigroup",
[IsSemigroup],
function(S)
  local out;
  if not IsFinite(S) then
    TryNextMethod();
  fi;
  out := Semigroup(Idempotents(S), rec(small := true));
  SetIsIdempotentGenerated(out, true);
  if HasIsSemigroupWithCommutingIdempotents(S)
      and IsSemigroupWithCommutingIdempotents(S) then
    SetIsSemigroupWithCommutingIdempotents(out, true);
  fi;
  return out;
end);

InstallMethod(IdempotentGeneratedSubsemigroup,
"for a Rees matrix subsemigroup",
[IsReesMatrixSubsemigroup],
function(R)
  local mat, I, J, nrrows, nrcols, min, max, gens, out, i;

  if not IsFinite(R) or not IsReesMatrixSemigroup(R)
      or not IsGroup(UnderlyingSemigroup(R)) then
    TryNextMethod();
  fi;

  mat := Matrix(R);
  I := Rows(R);
  J := Columns(R);
  nrrows := Length(I);
  nrcols := Length(J);

  min := Minimum(nrrows, nrcols);
  max := Maximum(nrrows, nrcols);
  gens := EmptyPlist(max);
  for i in [1 .. min] do
    Add(gens, RMSElement(R, I[i], mat[J[i]][I[i]] ^ -1, J[i]));
  od;
  for i in [min + 1 .. nrrows] do
    Add(gens, RMSElement(R, I[i], mat[J[1]][I[i]] ^ -1, J[1]));
  od;
  for i in [min + 1 .. nrcols] do
    Add(gens, RMSElement(R, I[1], mat[J[i]][I[1]] ^ -1, J[i]));
  od;
  out := Semigroup(gens);
  SetIsRegularSemigroup(out, true);
  SetIsIdempotentGenerated(out, true);
  SetIsSimpleSemigroup(out, true);
  return out;
end);

InstallMethod(IdempotentGeneratedSubsemigroup,
"for a Rees 0-matrix subsemigroup",
[IsReesZeroMatrixSubsemigroup],
function(R)
  local mat, gr, gens, I, J, nrrows, k, out, i, j;

  if not IsFinite(R) or not IsReesZeroMatrixSemigroup(R)
      or not IsGroup(UnderlyingSemigroup(R)) then
    TryNextMethod();
  fi;

  mat := Matrix(R);
  gr := RZMSDigraph(R);
  gens := [];

  if IsCompleteBipartiteDigraph(ReducedDigraph(gr)) or IsEmptyDigraph(gr) then
    Add(gens, MultiplicativeZero(R));
  fi;

  gr := OutNeighbours(UndirectedSpanningForest(gr));
  I := Rows(R);
  J := Columns(R);
  nrrows := Length(I);

  for i in [1 .. nrrows] do
    for j in gr[i] do
      k := J[j - nrrows];
      Add(gens, RMSElement(R, I[i], mat[k][I[i]] ^ -1, k));
    od;
  od;

  out := Semigroup(gens);
  SetIsRegularSemigroup(out, true);
  SetIsIdempotentGenerated(out, true);
  return out;
end);

InstallMethod(InjectionPrincipalFactor, "for a Green's D-class (Semigroups)",
[IsGreensDClass],
function(D)
  if not IsRegularDClass(D) then
    ErrorNoReturn("the argument (a Green's D-class) is not regular");
  elif NrHClasses(D) = NrIdempotents(D) then
    return SEMIGROUPS.InjectionPrincipalFactor(D, ReesMatrixSemigroup);
  fi;
  return SEMIGROUPS.InjectionPrincipalFactor(D, ReesZeroMatrixSemigroup);
end);

InstallMethod(InjectionNormalizedPrincipalFactor,
"for a Green's D-class (Semigroups)",
[IsGreensDClass],
function(D)
  local iso1, iso2, rms, inv1, inv2, iso, inv, hom;

  if not IsRegularDClass(D) then
    ErrorNoReturn("the argument (a Green's D-class) is not regular");
  elif NrHClasses(D) = NrIdempotents(D) then
    iso1 := SEMIGROUPS.InjectionPrincipalFactor(D, ReesMatrixSemigroup);
    iso2 := RMSNormalization(Range(iso1));
  else
    iso1 := SEMIGROUPS.InjectionPrincipalFactor(D, ReesZeroMatrixSemigroup);
    iso2 := RZMSNormalization(Range(iso1));
  fi;

  rms := Range(iso2);
  inv1 := InverseGeneralMapping(iso1);
  inv2 := InverseGeneralMapping(iso2);
  iso := x -> (x ^ iso1) ^ iso2;
  inv := x -> (x ^ inv2) ^ inv1;
  hom := MappingByFunction(D, rms, iso, inv);
  SetIsInjective(hom, true);
  SetIsTotal(hom, true);
  return hom;
end);

InstallMethod(MultiplicativeNeutralElement,
"for a semigroup with CanUseFroidurePin + generators",
[IsSemigroup and CanUseFroidurePin and HasGeneratorsOfSemigroup],
function(S)
  local D, e;

  if not IsFinite(S) then
    TryNextMethod();
  elif IsMultiplicativeElementWithOneCollection(S) and One(S) in S then
    return One(S);
  elif Length(MaximalDClasses(S)) > 1 then
    return fail;
  fi;

  D := MaximalDClasses(S)[1];

  if NrHClasses(D) <> 1 or not IsRegularDClass(D) then
    return fail;
  fi;

  e := Idempotents(D)[1];

  if ForAll(GeneratorsOfSemigroup(S), x -> e * x = x and x * e = x) then
    return e;
  fi;
  return fail;
end);

# same method for inverse/ideals

InstallMethod(RepresentativeOfMinimalIdeal, "for a semigroup",
[IsSemigroup],
function(S)

  if HasMultiplicativeZero(S) and MultiplicativeZero(S) <> fail then
    return MultiplicativeZero(S);
  elif HasIsSimpleSemigroup(S) and IsSimpleSemigroup(S) then
    # This catches known trivial semigroups
    return Representative(S);
  elif IsSemigroupIdeal(S) and
      (HasRepresentativeOfMinimalIdeal(SupersemigroupOfIdeal(S))
       or not HasGeneratorsOfSemigroup(S)) then
    return RepresentativeOfMinimalIdeal(SupersemigroupOfIdeal(S));
  elif not IsFinite(S) then
    TryNextMethod();
  fi;

  return RepresentativeOfMinimalIdealNC(S);
end);

InstallMethod(RepresentativeOfMinimalIdealNC, "for a finite semigroup",
[IsSemigroup and IsFinite],
function(S)
  local D, pos;
  D   := PartialOrderOfDClasses(S);
  pos := DigraphSinks(D)[1];
  Assert(1, Length(DigraphSinks(D)) = 1);
  return Representative(DClasses(S)[pos]);
end);

InstallMethod(InversesOfSemigroupElementNC,
"for a group as semigroup and a multiplicative element",
[IsGroupAsSemigroup and CanUseFroidurePin, IsMultiplicativeElement],
function(G, x)
  local i, iso, inv;
  if IsMultiplicativeElementWithInverse(x) then
    i := InverseOp(x);
    if i <> fail then
      return [i];
    fi;
  fi;
  iso := IsomorphismPermGroup(G);
  inv := InverseGeneralMapping(iso);
  return [((x ^ iso) ^ -1) ^ inv];
end);

InstallMethod(InversesOfSemigroupElementNC,
"for a semigroup that can use froidure-pin and a multiplicative element",
[CanUseFroidurePin, IsMultiplicativeElement],
function(S, a)
  local R, L, inverses, e, f, s;
  R := RClass(S, a);
  L := LClass(S, a);
  inverses := EmptyPlist(NrIdempotents(R) * NrIdempotents(L));

  for e in Idempotents(R) do
    s := RightGreensMultiplierNC(S, a, e) * e;
    for f in Idempotents(L) do
      Add(inverses, f * s);
    od;
  od;
  return inverses;
end);

InstallMethod(InversesOfSemigroupElement,
"for a semigroup that can use froidure-pin and a multiplicative element",
[CanUseFroidurePin, IsMultiplicativeElement],  # to beat the library method
function(S, x)
  if not IsFinite(S) then
    TryNextMethod();
  elif not x in S then
    ErrorNoReturn("the 2nd argument (a mult. element) must belong to the 1st ",
                  "argument (a semigroup)");
  fi;
  return InversesOfSemigroupElementNC(S, x);
end);

InstallMethod(OneInverseOfSemigroupElementNC,
"for a semigroup and a multiplicative element",
[IsSemigroup, IsMultiplicativeElement],
function(S, x)
    if not IsFinite(S) then
        TryNextMethod();
    fi;
    return First(EnumeratorSorted(S),
    y -> x * y * x = x and y * x * y = y);
end);

InstallMethod(OneInverseOfSemigroupElementNC,
"for CanUseFroidurePin and a multiplicative element",
[CanUseFroidurePin, IsMultiplicativeElement],
function(S, a)
  local R, L, e, f, s;
  R := RClass(S, a);
  L := LClass(S, a);
  e := Idempotents(R);
  if IsEmpty(e) then
    return fail;
  fi;
  e := e[1];
  f := Idempotents(L);
  if IsEmpty(f) then
    return fail;
  fi;
  f := f[1];
  s := RightGreensMultiplierNC(S, a, e);
  return  f * s * e;
end);

InstallMethod(OneInverseOfSemigroupElement,
"for a semigroup and a multiplicative element",
[IsSemigroup, IsMultiplicativeElement],
function(S, x)
  if not IsFinite(S) then
    ErrorNoReturn("the semigroup is not finite");
  elif not x in S then
    ErrorNoReturn("the 2nd argument (a mult. element) must belong to the 1st ",
                  "argument (a semigroup)");
  fi;
  return OneInverseOfSemigroupElementNC(S, x);
end);

InstallMethod(UnderlyingSemigroupOfSemigroupWithAdjoinedZero,
"for a semigroup",
[IsSemigroup],
function(S)
  local zero, gens, T;

  if HasIsSemigroupWithAdjoinedZero(S)
      and not IsSemigroupWithAdjoinedZero(S) then
    return fail;
  fi;

  zero := MultiplicativeZero(S);
  if zero = fail then
    return fail;
  fi;

  gens := GeneratorsOfSemigroup(S);
  if Length(gens) = 1 then
    return fail;
  elif not zero in gens then
    return fail;
  fi;

  T := Semigroup(Difference(gens, [zero]));

  if zero in T then
    return fail;
  fi;
  return T;
end);

BindGlobal("_SemigroupSizeByIndexPeriod",
function(S)
  local gen, ind;
  gen := MinimalSemigroupGeneratingSet(S)[1];
  ind := IndexPeriodOfSemigroupElement(gen);
  if ind[1] = 1 then
    SetIsGroupAsSemigroup(S, true);
  fi;
  return Sum(ind) - 1;
end);

InstallMethod(Size,
"for a monogenic transformation semigroup with minimal generating set",
[IsMonogenicSemigroup and HasMinimalSemigroupGeneratingSet and
 IsTransformationSemigroup],
10,  # to beat IsActingSemigroup
_SemigroupSizeByIndexPeriod);

InstallMethod(Size,
"for a monogenic partial perm semigroup with minimal generating set",
[IsMonogenicSemigroup and HasMinimalSemigroupGeneratingSet and
 IsPartialPermSemigroup],
10,  # to beat IsActingSemigroup
_SemigroupSizeByIndexPeriod);

InstallMethod(Size,
"for a monogenic bipartition semigroup with minimal generating set",
[IsMonogenicSemigroup and HasMinimalSemigroupGeneratingSet and
 IsBipartitionSemigroup],
10,  # to beat IsActingSemigroup
_SemigroupSizeByIndexPeriod);

InstallMethod(Size,
"for a monogenic semigroup of matrices over finite field with minimal gen set",
[IsMonogenicSemigroup and HasMinimalSemigroupGeneratingSet and
 IsMatrixOverFiniteFieldSemigroup],
_SemigroupSizeByIndexPeriod);

MakeReadWriteGlobal("_SemigroupSizeByIndexPeriod");
Unbind(_SemigroupSizeByIndexPeriod);

InstallMethod(IndecomposableElements, "for a semigroup", [IsSemigroup],
function(S)
  local out, D;

  if HasIsSurjectiveSemigroup(S) and IsSurjectiveSemigroup(S) then
    return [];
  fi;
  out := [];
  for D in MaximalDClasses(S) do
    if not IsRegularDClass(D) then
      AddSet(out, Representative(D));
    fi;
  od;
  return out;
end);

InstallMethod(MinimalSemigroupGeneratingSet, "for a free semigroup",
[IsFreeSemigroup], GeneratorsOfSemigroup);

InstallMethod(MinimalSemigroupGeneratingSet, "for a semigroup",
[IsSemigroup],
function(S)
  local gens, indecomp, id, T, zero, iso, inv, G, x, D, non_unit_gens, classes,
  po, nbs;

  if IsTrivial(S) then
    return [Representative(S)];
  elif IsGroupAsSemigroup(S) then
    iso := IsomorphismPermGroup(S);
    inv := InverseGeneralMapping(iso);
    G := Range(iso);
    return Images(inv, MinimalGeneratingSet(G));
  elif IsMonogenicSemigroup(S) then
    return [Representative(MaximalDClasses(S)[1])];
  fi;

  gens := IrredundantGeneratingSubset(S);

  # A semigroup that has a 2-generating set but is not monogenic has rank 2.
  if Length(gens) = 2 then
    return gens;
  fi;

  # A generating set for a semigroup that has either a one/zero adjoined is
  # minimal if and only if it contains that one/zero, and is minimal for the
  # semigroup without the one/zero.
  if IsMonoidAsSemigroup(S) and IsTrivial(GroupOfUnits(S)) then
    id := MultiplicativeNeutralElement(S);
    T := Semigroup(Filtered(gens, x -> x <> id));
    return Concatenation([id], MinimalSemigroupGeneratingSet(T));
  elif IsSemigroupWithAdjoinedZero(S) then
    zero := MultiplicativeZero(S);
    T := Semigroup(Filtered(gens, x -> x <> zero));
    return Concatenation([zero], MinimalSemigroupGeneratingSet(T));
  fi;

  # The indecomposable elements are contains in any generating set. If the
  # indecomposable elements (or if not, the indecomposable elements plus a
  # single element) generate the semigroup, then you have a minimal generating
  # set.
  indecomp := IndecomposableElements(S);
  if Length(gens) = Length(indecomp) then
    return indecomp;
  elif not IsEmpty(indecomp) then
    x := Difference(gens, Semigroup(indecomp));
    if Length(x) = 1 then
      return Concatenation(x, indecomp);
    fi;
  fi;

  # A generating set for a monoid that consists of a minimal generating set for
  # the group of units and exactly one generator in each D-class immediately
  # below the group of units is minimal.
  if IsMonoidAsSemigroup(S) then
    D := DClass(S, MultiplicativeNeutralElement(S));
    non_unit_gens := Filtered(gens, x -> not x in D);
    classes := List(non_unit_gens, x -> Position(DClasses(S), DClass(S, x)));
    if IsDuplicateFreeList(classes) then
      po := PartialOrderOfDClasses(S);
      po := DigraphReflexiveTransitiveReduction(po);
      nbs := OutNeighboursOfVertex(po, Position(DClasses(S), D));
      if ForAll(classes, x -> x in nbs) then
        iso := IsomorphismPermGroup(GroupOfUnits(S));
        inv := InverseGeneralMapping(iso);
        G := Range(iso);
        return Concatenation(Images(inv, MinimalGeneratingSet(G)),
                             non_unit_gens);
      fi;
    fi;
  fi;

  # An irredundant generating set of a finite semigroup that contains at most
  # one generator per D-class is minimal.
  if IsFinite(S) and (IsDTrivial(S) or
      Length(Set(gens, x -> DClass(S, x))) = Length(gens)) then
    return gens;
  fi;

  ErrorNoReturn("no further methods for computing minimal generating sets ",
                "are implemented");
end);

InstallMethod(MinimalMonoidGeneratingSet, "for a free monoid",
[IsFreeMonoid], GeneratorsOfMonoid);

InstallMethod(MinimalMonoidGeneratingSet, "for a monoid",
[IsMonoid],
function(S)
  local one, gens, new;

  one := One(S);
  if IsTrivial(S) then
    return [one];
  fi;

  gens := MinimalSemigroupGeneratingSet(S);
  if not IsTrivial(GroupOfUnits(S)) then
    return gens;
  fi;
  new := Difference(gens, [one]);
  if One(new) = one then
    # The One of the non-identity generators is the One, so One is not needed.
    return new;
  fi;

  # This currently applies to only partial perm monoids: sometimes, the One
  # of the non-One generators is not the One of the monoid. Therefore the One
  # has to be included in the GeneratorsOfMonoid. WARNING: therefore
  # MinimalMonoidGeneratingSet may include the One even though, mathematically,
  # it shouldn't be needed. For example, see symmetric inverse monoid on 1 pt.
  return gens;
end);

InstallMethod(NambooripadPartialOrder, "for a semigroup",
[IsSemigroup],
function(S)
  local elts, p, func, out, i, j;

  if not IsFinite(S) then
    ErrorNoReturn("the argument (a semigroup) is not finite");
  elif not IsRegularSemigroup(S) then
    ErrorNoReturn("the argument (a semigroup) is not regular");
  elif IsInverseSemigroup(S) then
    return NaturalPartialOrder(S);
  fi;

  Info(InfoWarning, 2, "NambooripadPartialOrder: this method ",
                       "fully enumerates its argument!");

  elts := ShallowCopy(Elements(S));
  p    := Sortex(elts, {x, y} -> IsGreensDGreaterThanFunc(S)(y, x)) ^ -1;
  func := NambooripadLeqRegularSemigroup(S);
  out  := List([1 .. Size(S)], x -> []);

  for i in [1 .. Size(S)] do
    for j in [i + 1 .. Size(S)] do
      if func(elts[i], elts[j]) then
        AddSet(out[j ^ p], i ^ p);
      fi;
    od;
  od;
  return out;
end);

InstallMethod(NambooripadLeqRegularSemigroup, "for a semigroup",
[IsSemigroup],
function(S)
  if not IsFinite(S) then
    ErrorNoReturn("the argument (a semigroup) is not finite");
  elif not IsRegularSemigroup(S) then
    ErrorNoReturn("the argument (a semigroup) is not regular");
  elif IsInverseSemigroup(S) then
    return NaturalLeqInverseSemigroup(S);
  fi;

  return
    function(x, y)
      local E;
      E := Idempotents(S);
      return ForAny(E, e -> e * y = x)
        and ForAny(E, f -> y * f = x);
    end;
end);

InstallMethod(LeftIdentity,
"for semigroup with CanUseFroidurePin and mult. elt.",
[IsSemigroup and CanUseFroidurePin, IsMultiplicativeElement],
function(S, x)
  local i, p, result;
  if not x in S then
    Error("the 2nd argument (a mult. elt.) does not belong to the 1st ",
          "argument (a semigroup)");
  elif IsMonoid(S) then
    return One(S);
  elif IsMonoidAsSemigroup(S) then
    return MultiplicativeNeutralElement(S);
  elif IsIdempotent(x) then
    return x;
  fi;

  i := PositionCanonical(S, x);
  p := DigraphPath(LeftCayleyDigraph(S), i, i);
  if p = fail then
    return fail;
  fi;
  result := EvaluateWord(GeneratorsOfSemigroup(S), Reversed(p[2]));
  return result ^ SmallestIdempotentPower(result);
end);

InstallMethod(RightIdentity,
"for semgroup with CanUseFroidurePin and mult. elt.",
[IsSemigroup and CanUseFroidurePin, IsMultiplicativeElement],
function(S, x)
  local i, p, result;
  if not x in S then
    Error("the 2nd argument (a mult. elt.) does not belong to the 1st ",
          "argument (a semigroup)");
  elif IsMonoid(S) then
    return One(S);
  elif IsMonoidAsSemigroup(S) then
    return MultiplicativeNeutralElement(S);
  elif IsIdempotent(x) then
    return x;
  fi;

  i := PositionCanonical(S, x);
  p := DigraphPath(RightCayleyDigraph(S), i, i);
  if p = fail then
    return fail;
  fi;
  result := EvaluateWord(GeneratorsOfSemigroup(S), p[2]);
  return result ^ SmallestIdempotentPower(result);
end);

InstallMethod(MultiplicationTableWithCanonicalPositions,
"for a semigroup with CanUseFroidurePin",
[IsSemigroup and CanUseFroidurePin],
function(S)
  local n, sortedlist, t, tinv, M;
  n          := Size(S);
  sortedlist := AsSortedList(S);

  t    := PermList(List([1 .. n], i -> PositionCanonical(S, sortedlist[i])));
  tinv := t ^ -1;
  M    := MultiplicationTable(S);

  return List([1 .. n], i -> List([1 .. n], j -> M[i ^ tinv][j ^ tinv] ^ t));
end);

InstallMethod(TransposedMultiplicationTableWithCanonicalPositions,
"for a semigroup with CanUseFroidurePin",
[IsSemigroup and CanUseFroidurePin],
S -> TransposedMat(MultiplicationTableWithCanonicalPositions(S)));

InstallMethod(MinimalFaithfulTransformationDegree, "for a right zero semigroup",
[IsRightZeroSemigroup],
function(S)
  local max, deg;

  max := 0;
  deg := 0;
  while max < Size(S) do
    deg := deg + 1;
    if (deg mod 3) = 0 then
      max := 3 ^ (deg / 3);
    elif (deg mod 3) = 1 then
      max := 4 * 3 ^ ((deg - 4) / 3);
    else
      max := 2 * 3 ^ ((deg - 2) / 3);
    fi;
  od;
  return deg;
end);

InstallMethod(MinimalFaithfulTransformationDegree, "for a left zero semigroup",
[IsLeftZeroSemigroup],
function(S)
  local max, deg, N, r;
  max := 0;
  deg := 0;
  while max < Size(S) do
    deg := deg + 1;
    for r in [1 .. deg - 1] do
      N := r ^ (deg - r);
      if N > max then
        max := N;
      fi;
    od;
  od;
  return deg;
end);

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