Quellcode-Bibliothek semicons.gi Sprache: unbekannt

Untersuchungsergebnis.gi Download desUnknown {[0] [0] [0]}zum Wurzelverzeichnis wechseln

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

# Trivial semigroup: main method

InstallGlobalFunction(TrivialSemigroup,
function(arg...)
  local S;

  if IsEmpty(arg) then
    S := TrivialSemigroupCons(IsTransformationSemigroup, 0);
  elif Length(arg) = 1 and IsInt(arg[1]) and arg[1] >= 0 then
    S := TrivialSemigroupCons(IsTransformationSemigroup, arg[1]);
  elif Length(arg) = 1 and IsOperation(arg[1]) then
    S := TrivialSemigroupCons(arg[1], 0);
  elif Length(arg) = 2 and IsOperation(arg[1]) and IsInt(arg[2])
      and arg[2] >= 0 then
    S := TrivialSemigroupCons(arg[1], arg[2]);
  else
    ErrorNoReturn("the arguments must be a non-negative integer or ",
                  "a filter and a non-negative integer");
  fi;
  SetIsTrivial(S, true);
  return S;
end);

# Trivial semigroup: constructors

InstallMethod(TrivialSemigroupCons,
"for IsTransformationSemigroup and an integer",
[IsTransformationSemigroup, IsInt],
function(_, deg)
  if deg = 0 then
    return Semigroup(IdentityTransformation);
  fi;
  return Semigroup(ConstantTransformation(deg, 1));
end);

InstallMethod(TrivialSemigroupCons,
"for IsPartialPermSemigroup and an integer",
[IsPartialPermSemigroup, IsInt],
{filt, n} -> Semigroup(PartialPerm([1 .. n])));

InstallMethod(TrivialSemigroupCons,
"for IsBipartitionSemigroup and an integer",
[IsBipartitionSemigroup, IsInt],
function(_, deg)
  local n;
  n := Maximum(deg, 1);
  return Semigroup(Bipartition([Concatenation(List([1 .. n], x -> [-x, x]))]));
end);

InstallMethod(TrivialSemigroupCons,
"for IsBlockBijectionSemigroup and an integer",
[IsBlockBijectionSemigroup, IsInt],
function(_, deg)
  local n;
  n := Maximum(deg, 1);
  return TrivialSemigroupCons(IsBipartitionSemigroup, n);
end);

InstallMethod(TrivialSemigroupCons,
"for IsPBRSemigroup and an integer",
[IsPBRSemigroup, IsInt],
function(_, deg)
  local n;
  n := Maximum(deg, 1);
  return Semigroup(IdentityPBR(n));
end);

InstallMethod(TrivialSemigroupCons,
"for IsBooleanMatSemigroup and an integer",
[IsBooleanMatSemigroup, IsInt],
function(_, deg)
  local n;
  n := Maximum(deg, 1);
  return Semigroup(BooleanMat(List([1 .. n], x -> BlistList([1 .. n], [x]))));
end);

# Trivial semigroup: other constructors

for _IsXSemigroup in ["IsFpSemigroup",
                      "IsFpMonoid",
                      "IsNTPMatrixSemigroup",
                      "IsMaxPlusMatrixSemigroup",
                      "IsMinPlusMatrixSemigroup",
                      "IsTropicalMaxPlusMatrixSemigroup",
                      "IsTropicalMinPlusMatrixSemigroup",
                      "IsProjectiveMaxPlusMatrixSemigroup",
                      "IsIntegerMatrixSemigroup",
                      "IsReesMatrixSemigroup",
                      "IsReesZeroMatrixSemigroup"] do
  InstallMethod(TrivialSemigroupCons,
  Concatenation("for ", _IsXSemigroup, " and an integer"),
  [ValueGlobal(_IsXSemigroup), IsInt],
  function(filter, deg)
    return AsSemigroup(filter,
                       TrivialSemigroupCons(IsTransformationSemigroup, deg));
  end);
od;

Unbind(_IsXSemigroup);

# Monogenic semigroup: main method

InstallGlobalFunction(MonogenicSemigroup,
function(arg...)
  local filter, m, r, S;

  if Length(arg) = 2  then
    filter := IsTransformationSemigroup;
    m := arg[1];
    r := arg[2];
  elif Length(arg) = 3 then
    filter := arg[1];
    m := arg[2];
    r := arg[3];
  fi;

  if not IsBound(m) or not IsPosInt(m) or not IsPosInt(r)
      or not IsOperation(filter) then
    ErrorNoReturn("the arguments must be 2 positive integers or a filter ",
                  "and a 2 positive integers");
  fi;

  S := MonogenicSemigroupCons(filter, m, r);

  SetSize(S, m + r - 1);
  SetIsMonogenicSemigroup(S, true);
  if m = 1 then
    SetIsGroupAsSemigroup(S, true);
  else
    SetIsGroupAsSemigroup(S, false);
    SetIsRegularSemigroup(S, false);
  fi;

  SetIsZeroSemigroup(S, r = 1 and m < 3);
  SetMinimalSemigroupGeneratingSet(S, GeneratorsOfSemigroup(S));

  return S;
end);

# Monogenic semigroup: constructors

InstallMethod(MonogenicSemigroupCons,
"for a IsTransformationSemigroup and two positive integers",
[IsTransformationSemigroup, IsPosInt, IsPosInt],
function(_, m, r)
  local t;

  t := [1 .. r] + 1;
  t[r] := 1;

  if m <> 1 then  # m = 1 specifies a cyclic group
    Append(t, [1 .. m] + r - 1);
  fi;

  return Semigroup(Transformation(t));
end);

InstallMethod(MonogenicSemigroupCons,
"for a IsPartialPermSemigroup and two positive integers",
[IsPartialPermSemigroup, IsPosInt, IsPosInt],
function(_, m, r)
  local cyclic_group, nilpotent_offset, nilpotent, im;

  if m = 1 and r = 1 then
    return Semigroup(PartialPerm([], []));
  elif r = 1 then
    cyclic_group := [];
    nilpotent_offset := 0;
  else
    cyclic_group := [1 .. r] + 1;
    cyclic_group[r] := 1;
    nilpotent_offset := r;
  fi;
  nilpotent := [1 .. m - 1] + nilpotent_offset;
  im := Concatenation(cyclic_group, [0], nilpotent);

  return Semigroup(PartialPerm(im));
end);

InstallMethod(MonogenicSemigroupCons,
"for a IsBipartitionSemigroup and two positive integers",
[IsBipartitionSemigroup, IsPosInt, IsPosInt],
{filter, m, r} -> MonogenicSemigroupCons(IsBlockBijectionSemigroup, m, r));

InstallMethod(MonogenicSemigroupCons,
"for IsBlockBijectionSemigroup and two positive integers",
[IsBlockBijectionSemigroup, IsPosInt, IsPosInt],
function(_, m, r)
  local out, offset, i;

  if m = 1 and r = 1 then
    return Semigroup(Bipartition([[1, -1]]));
  fi;

  out := [];
  if r = 1 then
    offset := 1;
  else
    for i in [1 .. r - 1] do
      Add(out, [i, -i - 1]);
    od;
    Add(out, [r, -1]);
    offset := r + 1;
  fi;

  if m <> 1 then
    Add(out, [offset, -offset, offset + 1, -(offset + m)]);
    for i in [offset + 2 .. offset + m] do
      Add(out, [i, -i + 1]);
    od;
  fi;

  return Semigroup(Bipartition(out));
end);

# Monogenic semigroup: other constructors

for _IsXSemigroup in ["IsPBRSemigroup",
                      "IsBooleanMatSemigroup",
                      "IsNTPMatrixSemigroup",
                      "IsMaxPlusMatrixSemigroup",
                      "IsMinPlusMatrixSemigroup",
                      "IsTropicalMaxPlusMatrixSemigroup",
                      "IsTropicalMinPlusMatrixSemigroup",
                      "IsProjectiveMaxPlusMatrixSemigroup",
                      "IsIntegerMatrixSemigroup",
                      "IsReesMatrixSemigroup",
                      "IsReesZeroMatrixSemigroup"] do
  InstallMethod(MonogenicSemigroupCons,
  Concatenation("for ", _IsXSemigroup, " and two positive integers"),
  [ValueGlobal(_IsXSemigroup), IsPosInt, IsPosInt],
  function(filter, m, r)
    return AsSemigroup(filter,
                       MonogenicSemigroupCons(IsTransformationSemigroup, m, r));
  end);
od;
Unbind(_IsXSemigroup);

# Rectangular band: main method

InstallGlobalFunction(RectangularBand,
function(arg...)
  local filter, m, n, S;

  if Length(arg) = 2  then
    filter := IsTransformationSemigroup;
    m := arg[1];
    n := arg[2];
  elif Length(arg) = 3 then
    filter := arg[1];
    m := arg[2];
    n := arg[3];
  fi;

  if not IsBound(m) or not IsPosInt(m) or not IsPosInt(n)
      or not IsOperation(filter) then
    ErrorNoReturn("the arguments must be 2 positive integers or a filter ",
                  "and a 2 positive integers");
  fi;

  S := RectangularBandCons(filter, m, n);

  SetSize(S, m * n);
  SetIsRectangularBand(S, true);
  SetNrRClasses(S, m);
  SetNrLClasses(S, n);
  if m <> 1 or n <> 1 then
    SetIsGroupAsSemigroup(S, false);
    SetIsZeroSemigroup(S, false);
    SetIsTrivial(S, false);
  fi;
  SetIsRightZeroSemigroup(S, m = 1);
  SetIsLeftZeroSemigroup(S, n = 1);

  return S;
end);

# Rectangular band: constructors

InstallMethod(RectangularBandCons,
"for a filter and a positive integer and positive integer",
[IsTransformationSemigroup, IsPosInt, IsPosInt],
function(filter, m, n)
  local L, R, div, gen, gens, min, out, i;

  if m = 1 then
    return RightZeroSemigroup(filter, n);
  elif n = 1 then
    return LeftZeroSemigroup(filter, m);
  fi;

  # don't do:
  # DirectProduct(LeftZeroSemigroup(m), RightZeroSemigroup(n));
  # because we know a generating set.

  L := LeftZeroSemigroup(filter, m);
  R := RightZeroSemigroup(filter, n);
  div := DegreeOfTransformationSemigroup(L);

  gen := function(l, r)
    return Transformation(Concatenation(ListTransformation(L.(l), div),
                                        ListTransformation(R.(r)) + div));
  end;

  gens := [];
  min := Minimum(m, n);

  for i in [1 .. min] do  # 'diagonal' generators
    Add(gens, gen(i, i));
  od;

  for i in [min + 1 .. n] do  # additional generators when n > m
    Add(gens, gen(1, i));
  od;

  for i in [min + 1 .. m] do  # additional generators when n < m
    Add(gens, gen(i, 1));
  od;

  out := Semigroup(gens);
  SetMinimalSemigroupGeneratingSet(out, GeneratorsOfSemigroup(out));
  return out;
end);

InstallMethod(RectangularBandCons,
"for a filter and two positive integers",
[IsBipartitionSemigroup, IsPosInt, IsPosInt],
function(_, m, n)
  local max, min, out, nrpoints, partitions, neg, i;

  max := Maximum(m, n);
  min := Minimum(m, n);
  out := EmptyPlist(max);

  # Find a small degree of partition monoid in which to embed rectangular band
  nrpoints := 1;
  while NrPartitionsSet([1 .. nrpoints]) < max do
    nrpoints := nrpoints + 1;
  od;

  partitions := PartitionsSet([1 .. nrpoints]);

  for i in [1 .. min] do
    Add(out, Bipartition(Concatenation(partitions[i], -1 * partitions[i])));
  od;

  neg := -1 * partitions[1];
  for i in [min + 1 .. m] do
    Add(out, Bipartition(Concatenation(partitions[i], neg)));
  od;

  for i in [min + 1 .. n] do
    Add(out, Bipartition(Concatenation(partitions[1], -1 * partitions[i])));
  od;

  return Semigroup(out);
end);

InstallMethod(RectangularBandCons,
"for a filter and a positive integer and positive integer",
[IsReesMatrixSemigroup, IsPosInt, IsPosInt],
function(_, m, n)
  local id, mat;

  id := ();
  mat := List([1 .. n], x -> List([1 .. m], y -> id));
  return ReesMatrixSemigroup(Group(id), mat);
end);

InstallMethod(RectangularBandCons,
"for IsPBRSemigroup and a pos int, and pos int",
[IsPBRSemigroup, IsPosInt, IsPosInt],
function(filter, m, n)
  return AsSemigroup(filter,
                     RectangularBandCons(IsBipartitionSemigroup, m, n));
end);

# Rectangular band: other constructors

for _IsXSemigroup in ["IsBooleanMatSemigroup",
                      "IsNTPMatrixSemigroup",
                      "IsMaxPlusMatrixSemigroup",
                      "IsMinPlusMatrixSemigroup",
                      "IsTropicalMaxPlusMatrixSemigroup",
                      "IsTropicalMinPlusMatrixSemigroup",
                      "IsProjectiveMaxPlusMatrixSemigroup",
                      "IsIntegerMatrixSemigroup"] do
  InstallMethod(RectangularBandCons,
  Concatenation("for ", _IsXSemigroup, ", pos int, and pos int"),
  [ValueGlobal(_IsXSemigroup), IsPosInt, IsPosInt],
  function(filter, m, n)
    return AsSemigroup(filter,
                       RectangularBandCons(IsTransformationSemigroup, m, n));
  end);
od;
Unbind(_IsXSemigroup);

# Free semilattice: main method

InstallGlobalFunction(FreeSemilattice,
function(arg...)
  local filter, n, S;

  if Length(arg) = 1  then
    filter := IsTransformationSemigroup;
    n := arg[1];
  elif Length(arg) = 2 then
    filter := arg[1];
    n := arg[2];
  else
    ErrorNoReturn("expected 2 arguments found ", Length(arg));
  fi;

  if not IsPosInt(n) or not IsOperation(filter) then
    ErrorNoReturn("the arguments must be a positive integer or a filter ",
                  "and a positive integer");
  fi;

  S := FreeSemilatticeCons(filter, n);

  if "IsMagmaWithOne" in NamesFilter(filter) then
    SetSize(S, 2 ^ n);
  else
    SetSize(S, 2 ^ n - 1);
  fi;

  SetIsSemilattice(S, true);

  return S;
end);

# Free semilattice: constructors

InstallMethod(FreeSemilatticeCons,
"for IsFpSemigroup and a pos int",
[IsFpSemigroup, IsPosInt],
function(_, n)
    local F, gen, l, i, j, commR, idemR;
    F := FreeSemigroup(n);
    gen := GeneratorsOfSemigroup(F);
    l := Length(gen);

    commR := [];
    for i in [1 .. l - 1] do
        for j in [i + 1 .. l] do
            Add(commR, [gen[i] * gen[j], gen[j] * gen[i]]);
        od;
    od;

    idemR := List(gen, x -> [x * x, x]);
    return F / Concatenation(commR, idemR);
end);

InstallMethod(FreeSemilatticeCons,
"for IsFpSemigroup and a pos int",
[IsFpMonoid, IsPosInt],
function(_, n)
    local F, gen, l, i, j, commR, idemR;
    F := FreeMonoid(n);
    gen := GeneratorsOfSemigroup(F);
    l := Length(gen);

    commR := [];
    for i in [1 .. l - 1] do
        for j in [i + 1 .. l] do
            Add(commR, [gen[i] * gen[j], gen[j] * gen[i]]);
        od;
    od;

    idemR := List(gen, x -> [x * x, x]);
    return F / Concatenation(commR, idemR);
end);

InstallMethod(FreeSemilatticeCons,
"for IsTransformationSemigroup and a pos int",
[IsTransformationSemigroup, IsPosInt],
function(_, n)
    local gen, i, L;
    gen := [];
    for i in [1 .. n] do
        L := [1 .. n + 1];
        L[i] := n + 1;
        Add(gen, Transformation(L));
    od;
    return Semigroup(gen);
end);

InstallMethod(FreeSemilatticeCons,
"for IsTransformationSemigroup and a pos int",
[IsTransformationMonoid, IsPosInt],
function(_, n)
    local gen, i, L;
    gen := [];
    for i in [1 .. n] do
        L := [1 .. n + 1];
        L[i] := n + 1;
        Add(gen, Transformation(L));
    od;
    return Monoid(gen);
end);

InstallMethod(FreeSemilatticeCons,
"for IsPartialPermSemigroup and a pos int",
[IsPartialPermSemigroup, IsPosInt],
function(_, n)
    local gen, i, L;
    gen := [];
    for i in [1 .. n] do
        L := [1 .. n];
        Remove(L, i);
        Add(gen, PartialPerm(L, L));
    od;
    return Semigroup(gen);
end);

InstallMethod(FreeSemilatticeCons,
"for IsPartialPermSemigroup and a pos int",
[IsPartialPermMonoid, IsPosInt],
function(_, n)
    local gen, i, L;
    gen := [];
    for i in [1 .. n] do
        L := [1 .. n];
        Remove(L, i);
        Add(gen, PartialPerm(L, L));
    od;
    return Monoid(gen);
end);

# Free semilattice: other constructors

for _IsXSemigroup in ["IsBipartitionSemigroup",
                      "IsPBRSemigroup",
                      "IsBooleanMatSemigroup",
                      "IsNTPMatrixSemigroup",
                      "IsMaxPlusMatrixSemigroup",
                      "IsMinPlusMatrixSemigroup",
                      "IsTropicalMaxPlusMatrixSemigroup",
                      "IsTropicalMinPlusMatrixSemigroup",
                      "IsProjectiveMaxPlusMatrixSemigroup",
                      "IsIntegerMatrixSemigroup"] do
  InstallMethod(FreeSemilatticeCons,
  Concatenation("for ", _IsXSemigroup, ", and pos int"),
  [ValueGlobal(_IsXSemigroup), IsPosInt],
  function(filter, n)
    return AsSemigroup(filter,
                       FreeSemilatticeCons(IsTransformationSemigroup, n));
  end);
od;

for _IsXMonoid in ["IsBipartitionMonoid",
                    "IsPBRMonoid",
                    "IsBooleanMatMonoid",
                    "IsNTPMatrixMonoid",
                    "IsMaxPlusMatrixMonoid",
                    "IsMinPlusMatrixMonoid",
                    "IsTropicalMaxPlusMatrixMonoid",
                    "IsTropicalMinPlusMatrixMonoid",
                    "IsProjectiveMaxPlusMatrixMonoid",
                    "IsIntegerMatrixMonoid"] do
  InstallMethod(FreeSemilatticeCons,
  Concatenation("for ", _IsXMonoid, ", and pos int"),
  [ValueGlobal(_IsXMonoid), IsPosInt],
  function(filter, n)
    return AsMonoid(filter,
                    FreeSemilatticeCons(IsTransformationMonoid, n));
  end);
od;

Unbind(_IsXSemigroup);
Unbind(_IsXMonoid);

# Zero semigroup: main method

InstallGlobalFunction(ZeroSemigroup,
function(arg...)
  local filter, n, S;

  if Length(arg) = 1  then
    filter := IsTransformationSemigroup;
    n := arg[1];
  elif Length(arg) = 2 then
    filter := arg[1];
    n := arg[2];
  fi;

  if not IsBound(n) or not IsPosInt(n) or not IsOperation(filter) then
    ErrorNoReturn("the arguments must be a positive integer or a filter ",
                  "and a positive integer");
  fi;

  S := ZeroSemigroupCons(filter, n);

  SetSize(S, n);
  SetIsZeroSemigroup(S, true);
  SetMultiplicativeZero(S, S.1 ^ 2);
  SetIsGroupAsSemigroup(S, IsTrivial(S));
  SetIsRegularSemigroup(S, IsTrivial(S));
  SetIsMonogenicSemigroup(S, n <= 2);
  SetMinimalSemigroupGeneratingSet(S, GeneratorsOfSemigroup(S));
  return S;
end);

# Zero semigroup: constructors

InstallMethod(ZeroSemigroupCons,
"for IsTransformationSemigroup and a positive integer",
[IsTransformationSemigroup, IsPosInt],
function(_, n)
  local out, max, deg, N, R, gens, im, iter, r, i;

  if n = 1 then
    out := Semigroup(Transformation([1]));
    SetMultiplicativeZero(out, out.1);
    return out;
  fi;

  # calculate the minimal possible degree
  max := 0;
  deg := 0;
  while max < n do
    deg := deg + 1;
    for r in [1 .. deg - 1] do
      N := r ^ (deg - r);
      if N > max then
        max := N;
        R := r;
      fi;
    od;
  od;

  gens := [];
  im   := [1 .. R] * 0 + 1;
  iter := IteratorOfTuples([1 .. R], deg - R);
  NextIterator(iter);  # skip the zero

  for i in [1 .. n - 1] do
    Add(gens, Transformation(Concatenation(im, NextIterator(iter))));
  od;

  out := Semigroup(gens, rec(acting := false));
  SetMultiplicativeZero(out, ConstantTransformation(deg, 1));

  return out;
end);

InstallMethod(ZeroSemigroupCons,
"for IsPartialPermSemigroup and a positive integer",
[IsPartialPermSemigroup, IsPosInt],
function(_, n)
  local zero, gens, out, i;

  zero := PartialPerm([], []);
  if n = 1 then
    gens := [zero];
  else
    gens := EmptyPlist(n - 1);
    for i in [1 .. n - 1] do
      gens[i] := PartialPerm([2 * i - 1], [2 * i]);
    od;
  fi;
  out := Semigroup(gens);
  SetMultiplicativeZero(out, zero);
  return out;
end);

InstallMethod(ZeroSemigroupCons,
"for a filter and a positive integer",
[IsBlockBijectionSemigroup, IsPosInt],
function(_, n)
  local zero, gens, points, pair, out, i;

  if n = 1 then
    zero := Bipartition([[1, -1]]);
    gens := [zero];
  elif n = 2 then
    points := Concatenation([1 .. 3], [-3 .. -1]);
    zero := Bipartition([points]);
    gens := [Bipartition([[1, -2], [-1, 2, 3, -3]])];
  else
    points := Concatenation([1 .. 2 * (n - 1)], -[1 .. 2 * (n - 1)]);
    zero := Bipartition([points]);
    gens := EmptyPlist(n - 1);
    for i in [1 .. n - 1] do
      pair := [2 * i - 1, -(2 * i)];
      gens[i] := Bipartition([pair, Difference(points, pair)]);
    od;
  fi;
  out := Semigroup(gens);
  SetMultiplicativeZero(out, zero);
  return out;
end);

InstallMethod(ZeroSemigroupCons,
"for a filter and a positive integer",
[IsBipartitionSemigroup, IsPosInt],
function(_, n)
  local zero, out;

  if n = 2 then
    zero := Bipartition([[1], [2], [-1], [-2]]);
    out := Semigroup(Bipartition([[1, -2], [2], [-1]]));
    SetMultiplicativeZero(out, zero);
    return out;
  fi;

  return AsSemigroup(IsBipartitionSemigroup,
                     ZeroSemigroupCons(IsTransformationSemigroup, n));
end);

InstallMethod(ZeroSemigroupCons,
"for a IsReesZeroMatrixSemigroup and a positive integer",
[IsReesZeroMatrixSemigroup, IsPosInt],
function(_, n)
  local mat;

  if n = 1 then
    ErrorNoReturn("there is no Rees 0-matrix semigroup of order 1");
  fi;
  mat := [[1 .. n - 1] * 0];
  return ReesZeroMatrixSemigroup(Group(()), mat);
end);

# Zero semigroup: other constructors

for _IsXSemigroup in ["IsPBRSemigroup",
                      "IsBooleanMatSemigroup",
                      "IsNTPMatrixSemigroup",
                      "IsMaxPlusMatrixSemigroup",
                      "IsMinPlusMatrixSemigroup",
                      "IsTropicalMaxPlusMatrixSemigroup",
                      "IsTropicalMinPlusMatrixSemigroup",
                      "IsProjectiveMaxPlusMatrixSemigroup",
                      "IsIntegerMatrixSemigroup"] do
  InstallMethod(ZeroSemigroupCons,
  Concatenation("for ", _IsXSemigroup, " and a positive integer"),
  [ValueGlobal(_IsXSemigroup), IsPosInt],
  function(filter, n)
    return AsSemigroup(filter,
                       ZeroSemigroupCons(IsTransformationSemigroup, n));
  end);
od;
Unbind(_IsXSemigroup);

# Left zero semigroup: main method

InstallGlobalFunction(LeftZeroSemigroup,
function(arg...)
  local filt, n, S, max, deg, N, R, gens, im, iter, r, i;

  if Length(arg) = 1 then
    filt := IsTransformationSemigroup;
    n    := arg[1];
  elif Length(arg) = 2 then
    filt := arg[1];
    n    := arg[2];
  fi;

  if not IsBound(filt) or not IsFilter(filt) or not IsPosInt(n) then
    ErrorNoReturn("the arguments must be a positive integer or ",
                  "a filter and a positive integer");
  elif n = 1 then
    return TrivialSemigroup(filt);
  elif filt <> IsTransformationSemigroup then
    S := RectangularBand(filt, n, 1);
    SetIsLeftZeroSemigroup(S, true);
    return S;
  fi;

  # calculate the minimal possible degree
  max := 0;
  deg := 0;
  while max < n do
    deg := deg + 1;
    for r in [1 .. deg - 1] do
      N := r ^ (deg - r);
      if N > max then
        max := N;
        R := r;
      fi;
    od;
  od;

  gens := [];
  im   := [1 .. R];
  iter := IteratorOfTuples([1 .. R], deg - R);

  for i in [1 .. n] do
    Add(gens, Transformation(Concatenation(im, NextIterator(iter))));
  od;

  S := Semigroup(gens, rec(acting := false));
  SetIsLeftZeroSemigroup(S, true);
  return S;
end);

# Right zero semigroup: main method

InstallGlobalFunction(RightZeroSemigroup,
function(arg...)
  local filt, n, S, max, deg, ker, add, iter, gens, i;

  if Length(arg) = 1 then
    filt := IsTransformationSemigroup;
    n    := arg[1];
  elif Length(arg) = 2 then
    filt := arg[1];
    n    := arg[2];
  fi;

  if not IsBound(filt) or not IsFilter(filt) or not IsPosInt(n) then
    ErrorNoReturn("the arguments must be a positive integer or ",
                  "a filter and a positive integer");
  elif n = 1 then
    return TrivialSemigroup(filt);
  elif filt <> IsTransformationSemigroup then
    S := RectangularBand(filt, 1, n);
    SetIsRightZeroSemigroup(S, true);
    return S;
  fi;

  # calculate the minimal possible degree
  max := 0;
  deg := 0;
  while max < n 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;

  # make the first class of the kernel
  if (deg mod 3) = 0 then
    ker := [[1 .. 3]];
    add := 3;
  elif (deg mod 3) = 1 then
    ker := [[1 .. 4]];
    add := 4;
  else
    ker := [[1 .. 2]];
    add := 2;
  fi;

  # add remaining classes in kernel (all of size 3)
  while add < deg do
    Add(ker, [1 .. 3] + add);
    add := add + 3;
  od;

  iter := IteratorOfCartesianProduct(ker);

  gens := [];
  for i in [1 .. n] do
    Add(gens, TransformationByImageAndKernel(NextIterator(iter), ker));
  od;

  S := Semigroup(gens, rec(acting := false));
  SetIsRightZeroSemigroup(S, true);
  return S;
end);

InstallGlobalFunction(BrandtSemigroup,
function(arg...)
  local S;

  if Length(arg) = 1 and IsPosInt(arg[1]) then
    S := BrandtSemigroupCons(IsPartialPermSemigroup, Group(()), arg[1]);
  elif Length(arg) = 2 and IsOperation(arg[1]) and IsPosInt(arg[2]) then
    S := BrandtSemigroupCons(arg[1], Group(()), arg[2]);
  elif Length(arg) = 2 and IsGroup(arg[1]) and IsPosInt(arg[2]) then
    S := BrandtSemigroupCons(IsPartialPermSemigroup, arg[1], arg[2]);
  elif Length(arg) = 3 and IsOperation(arg[1]) and IsGroup(arg[2])
      and IsPosInt(arg[3]) then
    S := BrandtSemigroupCons(arg[1], arg[2], arg[3]);
  else
    ErrorNoReturn("the arguments must be a positive integer or a filter and",
                   " a positive integer, or  a perm group and positive ",
                   "integer, or a filter, perm group, and positive ",
                   "integer");
  fi;
  SetIsZeroSimpleSemigroup(S, true);
  SetIsBrandtSemigroup(S, true);
  return S;
end);

InstallMethod(BrandtSemigroupCons,
"for IsPartialPermSemigroup, a perm group, and a positive integer",
[IsPartialPermSemigroup, IsPermGroup, IsPosInt],
function(_, G, n)
  local gens, one, m, i, x;

  gens := [];

  if IsTrivial(G) then
    if n = 1 then
      Add(gens, PartialPerm([1], [1]));
      Add(gens, EmptyPartialPerm());
    else
      for i in [2 .. n] do
        Add(gens, PartialPerm([1], [i]));
      od;
    fi;
  else
    one := PartialPerm(MovedPoints(G), MovedPoints(G));
    for x in GeneratorsOfGroup(G) do
      Add(gens, one * x);
    od;
    m := LargestMovedPoint(G) - SmallestMovedPoint(G) + 1;
    for i in [1 .. n - 1] do
      Add(gens, PartialPerm(MovedPoints(G), MovedPoints(G) + m * i));
    od;
    if n = 1 then
      Add(gens, EmptyPartialPerm());
    fi;
  fi;

  return InverseSemigroup(gens);
end);

InstallMethod(BrandtSemigroupCons,
"for IsReesZeroMatrixSemigroup, a finite group, and a positive integer",
[IsReesZeroMatrixSemigroup, IsGroup and IsFinite, IsPosInt],
function(_, G, n)
  local mat, i;
  mat := [];
  for i in [1 .. n] do
    Add(mat, ListWithIdenticalEntries(n, 0));
    mat[i][i] := One(G);
  od;

  return ReesZeroMatrixSemigroup(G, mat);
end);

for _IsXSemigroup in ["IsTransformationSemigroup",
                      "IsBipartitionSemigroup",
                      "IsPBRSemigroup",
                      "IsBooleanMatSemigroup",
                      "IsNTPMatrixSemigroup",
                      "IsMaxPlusMatrixSemigroup",
                      "IsMinPlusMatrixSemigroup",
                      "IsTropicalMaxPlusMatrixSemigroup",
                      "IsTropicalMinPlusMatrixSemigroup",
                      "IsProjectiveMaxPlusMatrixSemigroup",
                      "IsIntegerMatrixSemigroup"] do
  InstallMethod(BrandtSemigroupCons,
  Concatenation("for ", _IsXSemigroup, " and a positive integer"),
  [ValueGlobal(_IsXSemigroup), IsPermGroup, IsPosInt],
  function(filter, G, n)
    return AsSemigroup(filter,
                       BrandtSemigroupCons(IsPartialPermSemigroup, G, n));
  end);
od;
Unbind(_IsXSemigroup);

InstallMethod(StrongSemilatticeOfSemigroups,
"for a digraph, a list, and a list",
[IsDigraph, IsList, IsList],
function(D, semigroups, homomorphisms)
  local out, pos, err, efam, etype, type, maps, n, rtclosure, paths, path, len,
   tobecomposed, firsthom, gens, i, j;

  if not IsMeetSemilatticeDigraph(DigraphReflexiveTransitiveClosure(D)) then
    ErrorNoReturn("the reflexive transitive closure of the 1st argument ",
                  "(a digraph) must be a meet semilattice");
  fi;
  pos := PositionProperty(semigroups, x -> not IsSemigroup(x));
  if pos <> fail then
    ErrorNoReturn("the 2nd argument (a list) must consist of semigroups, ",
                  "but found ", TNAM_OBJ(semigroups[pos]), " in position ",
                  pos);
  elif DigraphNrVertices(D) <> Length(semigroups) then
    err := Concatenation(
             "the 2nd argument (a list) must have length {}, ",
             "the number of vertices of the 1st argument (a digraph)",
             ", but found length {}");
    ErrorNoReturn(StringFormatted(err,
                                  DigraphNrVertices(D),
                                  Length(semigroups)));
  fi;
  pos := PositionProperty(homomorphisms, x -> not IsList(x));
  if pos <> fail then
    ErrorNoReturn("the 3rd argument (a list) must consist of lists, ",
                  "but found ",
                  TNAM_OBJ(homomorphisms[pos]),
                  " in position ",
                  pos);
  elif DigraphNrVertices(D) <> Length(homomorphisms) then
    err := Concatenation(
             "the 3rd argument (a list) must have length {}, ",
             "the number of vertices of the 1st argument (a digraph)",
             ", but found length {}");
    ErrorNoReturn(StringFormatted(err,
                  DigraphNrVertices(D),
                  Length(homomorphisms)));
  fi;

  out := OutNeighbours(D);
  for i in [1 .. DigraphNrVertices(D)] do
    if Length(homomorphisms[i]) <> Length(out[i]) then
      err := Concatenation(
               "the 3rd argument (a list) must have the same shape ",
               "as the out-neighbours of the 1st argument (a digraph), ",
               "expected shape {} but found {}");
      ErrorNoReturn(StringFormatted(err,
                                    List(out, Length),
                                    List(homomorphisms, Length)));
    fi;
    pos := PositionProperty(homomorphisms[i],
                            x -> not IsSemigroupHomomorphism(x));
    if pos <> fail then
        ErrorNoReturn("the 3rd argument (a list) must consist ",
                      "of lists of homomorphisms, but position ",
                      StringFormatted("[{}, {}]", i, pos),
                      " is not a homomorphism");
    fi;

    for j in [1 .. Length(homomorphisms[i])] do
      if Source(homomorphisms[i][j]) <> semigroups[out[i][j]] then
        err := Concatenation("expected the homomorphism in position {} of the ",
                             "3rd argument to have source equal to position {}",
                             " in the 2nd argument");
        ErrorNoReturn(StringFormatted(err, [i, j], out[i][j]));
      elif Range(homomorphisms[i][j]) <> semigroups[i] then
        err := Concatenation("expected the homomorphism in position {} of the ",
                             "3rd argument to have range equal to position {} ",
                             "in the 2nd argument");
        ErrorNoReturn(StringFormatted(err, [i, j], i));
      fi;
    od;
  od;

  efam := NewFamily("StrongSemilatticeOfSemigroupsElementsFamily", IsSSSE);
  etype := NewType(efam, IsSSSERep);

  type := NewType(CollectionsFamily(efam),
                  IsStrongSemilatticeOfSemigroups
                    and IsComponentObjectRep
                    and IsAttributeStoringRep);

  # the next section converts the list of homomorphisms into a matrix,
  # composing when necessary.
  maps := [];
  n := Length(semigroups);
  rtclosure := DigraphReflexiveTransitiveClosure(D);
  for i in [1 .. n] do
    Add(maps, []);
    for j in [1 .. n] do
      if i = j then
        # First check that if a homomorphism from i to i was defined, it
        # is the identity
        if IsDigraphEdge(D, [i, i]) then
          if homomorphisms[i][Position(OutNeighboursOfVertex(D, i), i)]
              <> IdentityMapping(semigroups[i]) then
             ErrorNoReturn("Expected homomorphism from ",
                           i, " to ", i,
                           " to be the identity");
           fi;
        fi;
        Add(maps[i], IdentityMapping(semigroups[i]));
      elif IsDigraphEdge(rtclosure, [i, j]) then
        paths        := IteratorOfPaths(D, i, j);
        path         := NextIterator(paths);
        len          := Length(path[2]);
        tobecomposed := List([1 .. len],
                              x -> homomorphisms[path[1][x]][path[2][x]]);
        firsthom     := CompositionMapping(tobecomposed);

        # now check the first composition is the same as the composition along
        # all other paths from i to j
        while not IsDoneIterator(paths) do
          path         := NextIterator(paths);
          len          := Length(path[2]);
          tobecomposed := List([1 .. len],
                                x -> homomorphisms[path[1][x]][path[2][x]]);
          if CompositionMapping(tobecomposed) <> firsthom then
            ErrorNoReturn("Composing homomorphisms along different paths from ",
                          i,
                          " to ",
                          j,
                          " does not produce the same result. The ",
                          "homomorphisms must commute");
          fi;
        od;
        # If no errors so far, then all paths commute and we can add the comp.
        Add(maps[i], firsthom);
        # TODO(later) for larger digraphs, the current method will compute some
        # compositions of homomorphisms several times.  For example, take
        # Digraph([[], [1], [1], [2, 3], [4]]). It defines a meet-semilattice
        # and the SSS initialisation will check that composing the
        # homomorphisms 1->3->4 and 1->2->4 give the same result. Later on in
        # the initialisation, it will also check equivalence of the paths
        # 1->2->4->5 and 1->3->4->5, but will not be reusing previously

        # computed information on what the composition 1->3->4 equals, say.
        # Saving the homomorphsisms already computed using some sort of dynamic
        # programming approach may improve the speed (at the cost of memory).
      else
        Add(maps[i], fail);
      fi;
    od;
  od;

  out := rec();

  gens := [];
  for i in [1 .. Length(semigroups)] do
    Append(gens, List(GeneratorsOfSemigroup(semigroups[i]),
                      x -> Objectify(etype, [out, i, x])));
  od;

  ObjectifyWithAttributes(out,
                          type,
                          SemilatticeOfStrongSemilatticeOfSemigroups,
                          rtclosure,
                          SemigroupsOfStrongSemilatticeOfSemigroups,
                          semigroups,
                          HomomorphismsOfStrongSemilatticeOfSemigroups,
                          maps,
                          ElementTypeOfStrongSemilatticeOfSemigroups,
                          etype,
                          GeneratorsOfMagma,
                          gens);
  return out;
end);

InstallMethod(Size, "for a strong semilattice of semigroups",
[IsStrongSemilatticeOfSemigroups],
{S} -> Sum(SemigroupsOfStrongSemilatticeOfSemigroups(S), Size));

InstallMethod(ViewString, "for a strong semilattice of semigroups",
[IsStrongSemilatticeOfSemigroups],
function(S)
  local size;
  size := Size(SemigroupsOfStrongSemilatticeOfSemigroups(S));
  return Concatenation("<strong semilattice of ",
                       String(size),
                       " semigroups>");
end);

InstallMethod(SSSE,
"for a strong semilattice of semigroups, a pos int, and an associative elt",
[IsStrongSemilatticeOfSemigroups, IsPosInt, IsAssociativeElement],
function(S, n, x)
  if n > Size(SemigroupsOfStrongSemilatticeOfSemigroups(S)) then
    ErrorNoReturn("expected 2nd argument to be an integer between 1 and ",
                  "the size of the semilattice, i.e. ",
                  Size(SemigroupsOfStrongSemilatticeOfSemigroups(S)));
  elif not x in SemigroupsOfStrongSemilatticeOfSemigroups(S)[n] then
    ErrorNoReturn("where S, n and x are the 1st, 2nd and 3rd arguments ",
                  "respectively, expected x to be an element of ",
                  "SemigroupsOfStrongSemilatticeOfSemigroups(S)[n]");
  fi;
  return Objectify(ElementTypeOfStrongSemilatticeOfSemigroups(S), [S, n, x]);
end);

InstallMethod(\=, "for SSSEs", IsIdenticalObj,
[IsSSSERep, IsSSSERep],
{x, y} -> x![1] = y![1] and x![2] = y![2] and x![3] = y![3]);

InstallMethod(\<, "for SSSEs", IsIdenticalObj, [IsSSSERep, IsSSSERep],
{x, y} -> (x![2] < y![2]) or (x![2] = y![2] and x![3] < y![3]));

InstallMethod(\*, "for SSSEs", IsIdenticalObj,
[IsSSSERep, IsSSSERep],
function(x, y)
  local D, meet, maps;
  D    := SemilatticeOfStrongSemilatticeOfSemigroups(x![1]);
  meet := PartialOrderDigraphMeetOfVertices(D, x![2], y![2]);
  maps := HomomorphismsOfStrongSemilatticeOfSemigroups(x![1]);
  return SSSE(x![1],
              meet,
              (x![3] ^ (maps[meet][x![2]])) * (y![3] ^ (maps[meet][y![2]])));
end);

InstallMethod(ViewString, "for a SSSE", [IsSSSERep],
x -> Concatenation("SSSE(", ViewString(x![2]), ", ", ViewString(x![3]), ")"));

InstallMethod(UnderlyingSemilatticeOfSemigroups, "for a SSSE",
[IsSSSERep], x -> x![1]);

Quellcode-Bibliothek semicons.gi Sprache: unbekannt

[ 0.84Quellennavigators ]