|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Robert F. Morse.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
##
## This file contains generic methods for magma congruences
##
## Maintenance and further development by:
## Robert F. Morse
## Andrew Solomon
##
##
#############################################################################
##
#M PrintObj( <S> )
## print a [left, right, two-sided] Magma Congruence
##
## left magma congruence
InstallMethod( PrintObj,
"for a left magma congruence",
true,
[ IsLeftMagmaCongruence ], 0,
function( S )
Print( "LeftMagmaCongruence( ... )" );
end );
InstallMethod( PrintObj,
"for a left magma congruence with known generating pairs",
true,
[ IsLeftMagmaCongruence and HasGeneratingPairsOfMagmaCongruence ], 0,
function( S )
Print( "LeftMagmaCongruence( ",
GeneratingPairsOfMagmaCongruence( S ), " )" );
end );
## right magma congruence
InstallMethod( PrintObj,
"for a right magma congruence",
true,
[ IsRightMagmaCongruence ], 0,
function( S )
Print( "RightMagmaCongruence( ... )" );
end );
InstallMethod( PrintObj,
"for a right magma congruence with known generating pairs",
true,
[ IsRightMagmaCongruence and HasGeneratingPairsOfMagmaCongruence ], 0,
function( S )
Print( "RightMagmaCongruence( ",
GeneratingPairsOfMagmaCongruence( S ), " )" );
end );
## two sided magma congruence
InstallMethod( PrintObj,
"for a magma congruence",
true,
[ IsMagmaCongruence ], 0,
function( S )
Print( "MagmaCongruence( ... )" );
end );
InstallMethod( PrintObj,
"for a magma Congruence with known generating pairs",
true,
[ IsMagmaCongruence and HasGeneratingPairsOfMagmaCongruence ], 0,
function( S )
Print( "MagmaCongruence( ",
GeneratingPairsOfMagmaCongruence( S ), " )" );
end );
#############################################################################
##
#M ViewObj( <S> )
##
## view a [left,right,two-sided] magma congruence
##
## left magma congruence
InstallMethod( ViewObj,
"for a LeftMagmaCongruence",
true,
[ IsLeftMagmaCongruence ], 0,
function( S )
Print( "<LeftMagmaCongruence>" );
end );
InstallMethod( ViewObj,
"for a LeftMagmaCongruence with known generating pairs",
true,
[ IsLeftMagmaCongruence and HasGeneratingPairsOfMagmaCongruence ], 0,
function( S )
Print( "<LeftMagmaCongruence with ",
Length( GeneratingPairsOfMagmaCongruence( S ) ),
" generating pairs>" );
end );
## right magma congruence
InstallMethod( ViewObj,
"for a RightMagmaCongruence",
true,
[ IsRightMagmaCongruence ], 0,
function( S )
Print( "<RightMagmaCongruence>" );
end );
InstallMethod( ViewObj,
"for a RightMagmaCongruence with generators",
true,
[ IsRightMagmaCongruence and HasGeneratingPairsOfMagmaCongruence ], 0,
function( S )
Print( "<RightMagmaCongruence with ",
Length( GeneratingPairsOfMagmaCongruence( S ) ),
" generating pairs>" );
end );
## two sided magma congruence
InstallMethod( ViewObj,
"for a magma congruence",
true,
[ IsMagmaCongruence ], 0,
function( S )
Print( "<MagmaCongruence>" );
end );
InstallMethod( ViewObj,
"for a magma congruence with generating pairs",
true,
[ IsMagmaCongruence and HasGeneratingPairsOfMagmaCongruence ], 0,
function( S )
Print( "<MagmaCongruence with ",
Length( GeneratingPairsOfMagmaCongruence( S ) ),
" generating pairs>" );
end );
#############################################################################
##
#M LR2MagmaCongruenceByGeneratingPairsCAT(<F>,<rels>,<category>)
##
## create the magma congruence with generating pairs <rels> as
## a <category> where <category> is IsLeftMagmaCongruence,
## IsRightMagmaCongruence or IsMagmaCongruence.
##
InstallGlobalFunction( LR2MagmaCongruenceByGeneratingPairsCAT,
function(F, gens, category )
local r, cong, fam;
# Check that the relations are all lists of length 2
for r in gens do
if Length(r) <> 2 then
Error("A relation should be a list of length 2");
fi;
od;
# Create the equivalence relation
fam := GeneralMappingsFamily( ElementsFamily(FamilyObj(F)),
ElementsFamily(FamilyObj(F)) );
# Create the default type for the elements.
cong := Objectify(NewType(fam,
category and IsEquivalenceRelationDefaultRep), rec());
SetSource(cong, F);
SetRange(cong, F);
# Add the generators in the appropriate attribute
# They are all set in a common place with special names
# as needed
if (category = IsMagmaCongruence) then
SetGeneratingPairsOfMagmaCongruence(cong, Immutable(gens));
elif (category = IsLeftMagmaCongruence) then
SetGeneratingPairsOfLeftMagmaCongruence(cong, Immutable(gens));
elif (category = IsRightMagmaCongruence) then
SetGeneratingPairsOfRightMagmaCongruence(cong, Immutable(gens));
else
Error("Invalid category ",category," of Magma congruence");
fi;
return cong;
end);
#############################################################################
##
#M LR2MagmaCongruenceByPartitionNCCAT(<F>,<part>,<category>)
##
## create the magma congruence with partition <part> as
## a <category> where <category> is IsLeftMagmaCongruence,
## IsRightMagmaCongruence or IsMagmaCongruence.
##
## <part> is a list of lists containing (at least) all of the non singleton
## blocks of the partition. It is not checked that <part> is actually
## a congruence in the category specified.
##
InstallGlobalFunction( LR2MagmaCongruenceByPartitionNCCAT,
function(F, part, cat)
local cong, fam;
# The only cheap check we can do:
if not IsElmsColls(FamilyObj(F), FamilyObj(part)) then
Error("<part> should be a list of lists of elements of the magma");
fi;
# Create the equivalence relation
fam := GeneralMappingsFamily( ElementsFamily(FamilyObj(F)),
ElementsFamily(FamilyObj(F)) );
# Create the default type for the elements.
cong := Objectify(NewType(fam,
cat and IsEquivalenceRelationDefaultRep), rec());
SetSource(cong, F);
SetRange(cong, F);
SetEquivalenceRelationPartition(cong, part);
return cong;
end);
#############################################################################
##
#M LeftMagmaCongruenceByGeneratingPairs( <D>, <gens> )
#M RightMagmaCongruenceByGeneratingPairs( <D>, <gens> )
#M MagmaCongruenceByGeneratingPairs( <D>, <gens> )
##
InstallMethod( LeftMagmaCongruenceByGeneratingPairs,
"for a magma and a list of pairs of its elements",
IsElmsColls,
[ IsMagma, IsList ], 0,
function( M, gens )
return LR2MagmaCongruenceByGeneratingPairsCAT(M, gens,
IsLeftMagmaCongruence);
end );
InstallMethod( LeftMagmaCongruenceByGeneratingPairs,
"for a magma and an empty list",
true,
[ IsMagma, IsList and IsEmpty ], 0,
function( M, gens )
return LR2MagmaCongruenceByGeneratingPairsCAT(M, gens,
IsLeftMagmaCongruence);
end );
InstallMethod( RightMagmaCongruenceByGeneratingPairs,
"for a magma and a list of pairs of its elements",
IsElmsColls,
[ IsMagma, IsList ], 0,
function( M, gens )
return LR2MagmaCongruenceByGeneratingPairsCAT(M, gens,
IsRightMagmaCongruence);
end );
InstallMethod( RightMagmaCongruenceByGeneratingPairs,
"for a magma and an empty list",
true,
[ IsMagma, IsList and IsEmpty ], 0,
function( M, gens )
return LR2MagmaCongruenceByGeneratingPairsCAT(M, gens,
IsRightMagmaCongruence);
end );
InstallMethod( MagmaCongruenceByGeneratingPairs,
"for a magma and a list of pairs of its elements",
IsElmsColls,
[ IsMagma, IsList ], 0,
function( M, gens )
local c;
c := LR2MagmaCongruenceByGeneratingPairsCAT(M, gens,
IsMagmaCongruence);
if HasIsSemigroup(M) and IsSemigroup(M) then
SetIsSemigroupCongruence(c,true);
fi;
return c;
end );
InstallMethod( MagmaCongruenceByGeneratingPairs,
"for a magma and an empty list",
true,
[ IsMagma, IsList and IsEmpty ], 0,
function( M, gens )
local c;
c := LR2MagmaCongruenceByGeneratingPairsCAT(M, gens,
IsMagmaCongruence);
if HasIsSemigroup(M) and IsSemigroup(M) then
SetIsSemigroupCongruence(c,true);
fi;
return c;
end );
#############################################################################
##
#M EquivalenceClasses( <E> )
##
## For a MagmaCongruence
##
InstallMethod(EquivalenceClasses,
"for magma congruences", true, [IsMagmaCongruence], 0,
function(e)
local part, # the partition of the equivalence relation
distinctreps; # the reprentatives of distinct non-trivial
# congruence classes
part := EquivalenceRelationPartition(e);
distinctreps := List(part,x->x[1]);
return List(distinctreps, x->EquivalenceClassOfElementNC(e, x));
end);
#############################################################################
##
#M \*( <x1>, <x2> )
##
## Product of congruence classes. As in fp-semigroups we just
## multiply without worrying about getting the representative right.
## Then we check equality when doing < or =.
##
InstallMethod( \*,
"for two magma congruence classes",
IsIdenticalObj,
[ IsCongruenceClass, IsCongruenceClass ],
0,
function( x1, x2 )
if EquivalenceClassRelation(x1) <> EquivalenceClassRelation(x2) then
Error("Can only multiply classes of the same congruence");
fi;
return EquivalenceClassOfElementNC(EquivalenceClassRelation(x1),
Representative(x1)*Representative(x2));
end );
############################################################################
##
#M One(<congruence class>)
##
## It is installed as
## OtherMethod to appease GAP since the selection filters
## IsCongruenceClass and IsMultiplicativeElementWithOne
## match two declarations of One - the first filter for domains,
## the second filter for IsMultiplicativeElementWithOne.
##
InstallOtherMethod(One,
"One(<congruence class>)", true,
[IsCongruenceClass and IsMultiplicativeElementWithOne], 0,
function(x)
return EquivalenceClassOfElement(EquivalenceClassRelation(x),
One(Representative(x)));
end);
######################################################################
##
#F MagmaCongruencePartition(<cong>,<partialcond>)
##
## This function sets one of the two attributes
##
## EquivalenceRelationPartition
## PartialClosureOfCongruence
##
## depending on whether full closure is found or partial closure is
## found. Both of these attributes are partitions of the magma's
## elements. If a previously computed PartialClosureOfCongruence satisfies
## the <partialcond> no computations are performed.
##
## A left magma congruence, right magma congruence, and magma congruence
## is the smallest equivalence relation containing the generating pairs
## closed under the operations of left multiplication, right
## multiplication or both respectively.
##
## If the magma is infinite (or very large) it may not be possible to compute
## the entire partition. <partialcond> allows for a stop condition (possibly)
## short of full closure. The function <partialcond> takes two parameters
## (congruence, forest). Other variables that might be needed by <partialcond>
## should be assigned to globals variables before MagmaCongruencePartition is
## called.
##
## A PartialClosureOfCongruence reflects a partial computation that can be used
## in subsequent computations. Hence it is a mutable attribute.
##
## A partial closure is also provided if either one block or the number of
## blocks exceeds 64,000 in length. The partial closure attribute is stored for
## the user to inspect.
##
## This algorithm is based on Atkinson et. al. (Group Theory on a
## Microcomputer, in Computational Group Theory, 1984).
##
## Non-trivial blocks are considered trees and the block system a forest
##
## Data representation:
## o Forest is a list of non-empty lists with no holes.
## o Each list in the forest represents a non-empty tree of depth 1
## with root the first element (hence it has at least 2 elements).
##
## If follows from the data representations that full path compression
## is used.
##
## The merging of blocks can only be done via list Append.
## This insures that the root of the left tree being merged does not change
## and hence is an invariant.
##
######################################################################
BindGlobal("MagmaCongruencePartition",
function(cong,partialcond)
local C, #Initial branches (given pairs)
forest, #Forest in which each tree is a block
i,p,g,j, #index variables
r1,r2, #roots of possible blocks to merge
p1,p2, #positions of the blocks
gens, #Required generators (in generality all the elements
maxlimit, #Maximum size for either a partition or number of
# partition;
checklimit,#Function for checking limit
equivrel; #Initial forest (if there is not partial closure)
## Set up limits on the size and number of partitions we can
## create a check function
##
maxlimit := 64000;
checklimit := function()
if Length(forest) >= maxlimit then return true; fi;
if First(forest, x->Length(x)>=maxlimit) <> fail then return true; fi;
return false;
end;
## check that we know the generators ....
##
if not HasGeneratingPairsOfMagmaCongruence(cong) then
Error("MagmaCongruencePartition requires GeneratingPairsOfMagmaCongruence");
fi;
if not ((HasGeneratorsOfMagma(Source(cong)) or
HasGeneratorsOfMagmaWithInverses(Source(cong))) or
(HasIsFinite(Source(cong)) and IsFinite(Source(cong)) )) then
Error("MagmaCongruencePartition requires generators for underlying semigroup or list of all elements");
fi;
## does the partition already exist if so return done deal
##
if HasEquivalenceRelationPartition(cong) then
return;
fi;
## check to see if we are to generate the trivial relation
##
## Filter all pairs of the form (a,a).
## if this filtered set is empty return the diagonal
## equivalence
##
C := List(Filtered(GeneratingPairsOfMagmaCongruence(cong),
x->not x[1]=x[2]), ShallowCopy);
if IsEmpty(C) then
SetEquivalenceRelationPartition(cong,[]);
return;
fi;
C := Set(C);
## Set the forest either to the partial closure from a previous
## call or find the smallest equivalence relation
## containing the filtered generators
##
if HasPartialClosureOfCongruence(cong) then
forest := ShallowCopy(PartialClosureOfCongruence(cong));
C := ShallowCopy(cong!.C);
else
equivrel := EquivalenceRelationPartition(
EquivalenceRelationByPairsNC(Source(cong),C));
forest := List(equivrel, ShallowCopy);
fi;
## Check partial closure might be fulfilled by initial closure
##
if partialcond(cong,forest) then
SetPartialClosureOfCongruence(cong,forest);
cong!.C := MakeImmutable(C);
return;
fi;
## Determine whether we can use generators or need
## all the elements
##
## If the Magma is associative then use generators
##
#T If the magam has a generating set but is not associative
#T then use an iterator. One need to be implemented
##
## else use elements of the magma
##
if HasGeneratorsOfMagmaWithInverses(Source(cong)) and
HasIsAssociative(Source(cong)) and
IsAssociative(Source(cong)) then
gens := GeneratorsOfMagmaWithInverses(Source(cong));
elif HasGeneratorsOfMagma(Source(cong)) and
HasIsAssociative(Source(cong)) and
IsAssociative(Source(cong)) then
gens := GeneratorsOfMagma(Source(cong));
elif HasGeneratorsOfMagma(Source(cong)) and
HasIsFinite(Source(cong)) and
IsFinite(Source(cong)) then
gens := AsSSortedList(Source(cong));
else
gens := AsSSortedList(Source(cong));
fi;
##
## Work through the branches in the forest above
## determining the closure wrt left and right
## translations following Atkinson et. al.
##
repeat
p := C[1];
RemoveSet(C,C[1]);
for g in gens do
p1 := Length(forest)+1;
p2 := Length(forest)+1;
if IsRightMagmaCongruence(cong) then
##
## Search the forest to see if each right translation
## is in one of the blocks (trees) in the forest
## Get out a soon as both are found
##
for i in [1..Length(forest)] do
if p1>Length(forest) and p[1]*g in forest[i] then
r1 := forest[i][1];
p1 := i;
if p2<=Length(forest) then break; fi;
fi;
if p2>Length(forest) and p[2]*g in forest[i] then
r2 := forest[i][1];
p2 := i;
if p1<=Length(forest) then break; fi;
fi;
od;
##
## If the translation is not in any of the
## blocks already defined make the element
## a root to a potential block
##
if p1=Length(forest)+1 then
r1:=p[1]*g;
fi;
if p2=Length(forest)+1 then
r2:=p[2]*g;
fi;
##
## If the roots are different
## merge the blocks they represent
##
if r1<>r2 then
##
## Merging of two existing blocks
## we must complete the Append and
## get rid of the one block without
## leaving a hole
##
if p1<=Length(forest) and p2<=Length(forest) and
not p1=p2 then
Append(forest[p1],forest[p2]);
Unbind(forest[p2]);
## No holes are left is at the end otherwise
## move the last one into the middle
if p2<Length(forest) then
forest[p2]:=Remove(forest);
fi;
## Simple cases of merging a new element with
## an existing block
elif p1<=Length(forest) and not p2<=Length(forest) then
Add(forest[p1],r2);
elif p2<=Length(forest) and not p1<=Length(forest) then
Add(forest[p2],r1);
## Add new non-trivial block made up of r1 and r2
else
Add(forest,[r1,r2]);
fi;
## Add the new branch to C
AddSet(C,[r1,r2]);
fi;
fi;
if IsLeftMagmaCongruence(cong) then
##
## Complete the left translations in an exact
## manner as above
##
p1 := Length(forest)+1;
p2 := Length(forest)+1;
for i in [1..Length(forest)] do
if p1>Length(forest) and g*p[1] in forest[i] then
r1 := forest[i][1];
p1 := i;
if p2<=Length(forest) then break; fi;
fi;
if p2>Length(forest) and g*p[2] in forest[i] then
r2 := forest[i][1];
p2 := i;
if p1<=Length(forest) then break; fi;
fi;
od;
if p1=Length(forest)+1 then
r1:=g*p[1];
fi;
if p2=Length(forest)+1 then
r2:=g*p[2];
fi;
if r1<>r2 then
if p1<=Length(forest) and p2<=Length(forest)
and not p1=p2 then
Append(forest[p1],forest[p2]);
Unbind(forest[p2]);
if p2<Length(forest) then
forest[p2]:=Remove(forest);
fi;
elif p1<=Length(forest) and not p2<=Length(forest) then
Add(forest[p1],r2);
elif p2<=Length(forest) and not p1<=Length(forest) then
Add(forest[p2],r1);
else
Add(forest,[r1,r2]);
fi;
AddSet(C,[r1,r2]);
fi;
fi;
od;
## Exit conditions are:
## full closure is complete
## we have created a partition larger than our limit
## partial closure condition is satisfied
##
until IsEmpty(C) or checklimit() or partialcond(cong,forest);
## Set the equivalence partition if we have full closure
##
if IsEmpty(C) then
SetEquivalenceRelationPartition(cong,forest);
## Set partial closure if partialcond is met or
## size limit has been reached
##
elif partialcond(cong,forest) then
SetPartialClosureOfCongruence(cong,forest);
cong!.C := MakeImmutable(C);
elif checklimit() then
Info(InfoWarning,1,
"The congruence has either over 64,000 blocks or a \n",
"#I block with over 64,000 elements. Hence only a\n",
"#I a partial closure has been completed. You may view\n",
"#I this partition using the 'PartialClosureOfCongruence'\n",
"#I attribute");
SetPartialClosureOfCongruence(cong,forest);
cong!.C := MakeImmutable(C);
else
Error("error, internal error in mgmcong.gi");
fi;
end);
######################################################################
##
## EquivalenceRelationPartition(<cong>)
## Calculate the partition attribute of a left congruence
##
######################################################################
InstallMethod(EquivalenceRelationPartition,
"for a left congruence on a magma",
true,
[IsLeftMagmaCongruence], 0,
function(cong) # cong a congruence.
# close the congruence with respect to left mult.
MagmaCongruencePartition(cong,function(x,y) return false; end);
return EquivalenceRelationPartition(cong);
end);
######################################################################
##
## EquivalenceRelationPartition(<cong>)
## Calculate the partition attribute of a right congruence
##
######################################################################
InstallMethod(EquivalenceRelationPartition,
"for a right congruence on a magma",
true,
[IsRightMagmaCongruence], 0,
function(cong) # cong a congruence.
# close the congruence with respect to right mult.
MagmaCongruencePartition(cong,function(x,y) return false; end);
return EquivalenceRelationPartition(cong);
end);
######################################################################
##
## EquivalenceRelationPartition(<cong>)
## Calculate the partition attribute of a congruence
##
######################################################################
InstallMethod(EquivalenceRelationPartition,
"for a congruence on a magma",
true,
[IsMagmaCongruence], 0,
function(cong) # cong a congruence.
# close the congruence with respect to left and right mult.
MagmaCongruencePartition(cong,function(x,y) return false; end);
return EquivalenceRelationPartition(cong);
end);
#############################################################################
##
#M JoinMagmaCongruences(<cong1>,<cong2>)
##
## Find the transitive closure of equivalence relations represented by
## cong1 and cong2
##
InstallMethod(JoinMagmaCongruences,
"for magma congruences", true,
[IsMagmaCongruence, IsMagmaCongruence],0,
function(c1,c2)
local
er, # Join is equivalence relations
cong; # Join congruence
# Check to see that the both congruences have the same
# parent magma
#
if Source(c1)<>Source(c2) then
Error("usage: the source of <cong1> and <cong2> must be the same");
fi;
# Find the join of the two congruences ar equivalence relations
#
er := JoinEquivalenceRelations(c1,c2);
# Create the congruence and set the partition to that of
# of er
#
cong := LR2MagmaCongruenceByGeneratingPairsCAT(Source(c1),
Union(GeneratingPairsOfMagmaCongruence(c1),
GeneratingPairsOfMagmaCongruence(c2)),
IsMagmaCongruence);
cong!.EquivalenceRelationPartition := EquivalenceRelationPartition(er);
if HasIsAssociative(Source(c1)) and IsAssociative(Source(c1)) then
SetIsSemigroupCongruence(cong,true);
fi;
return cong;
end);
#############################################################################
##
#M MeetMagmaCongruences(<cong1>,<cong2>)
##
## Find the meet of the equivalence relations represented by
## cong1 and cong2
##
InstallMethod(MeetMagmaCongruences,
"for magma congruences", true,
[IsMagmaCongruence, IsMagmaCongruence],0,
function(c1,c2)
local
er, # Meet os equivalence relations
cong; # Meet congruence
# Check to see that the both congruences have the same
# parent magma
#
if Source(c1)<>Source(c2) then
Error("The source of <cong1> and <cong2> must be the same");
fi;
# Find the meet of the two congruences as equivalence relations
#
er := MeetEquivalenceRelations(c1,c2);
# Create the congruence and set the partition to that of
# of er
#
cong := LR2MagmaCongruenceByGeneratingPairsCAT(Source(c1),
Intersection(GeneratingPairsOfMagmaCongruence(c1),
GeneratingPairsOfMagmaCongruence(c2)),
IsMagmaCongruence);
cong!.EquivalenceRelationPartition := EquivalenceRelationPartition(er);
if HasIsAssociative(Source(c1)) and IsAssociative(Source(c1)) then
SetIsSemigroupCongruence(cong,true);
fi;
return cong;
end);
#############################################################################
##
#M \in( <x>, <C> )
##
## Checks whether <x> is contained in the magma congruence class <C>
## If <C> is infinite, this will not necessarily terminate.
##
InstallMethod( \in, "for a magma congruence class", true,
[IsObject, IsCongruenceClass], 0,
function(x, C)
local
partialclosure, #Partial closure
part, #Partition
rep,
rel,
class,
GLOBAL_SEARCH_ELEMENT,
GLOBAL_REP;
# first ensure that <x> is in the right family
if FamilyObj(x) <>
ElementsFamily(FamilyObj(Source(EquivalenceClassRelation(C)))) then
Error("incompatible arguments for \\in");
fi;
# quick check to see if element is representative
if x=Representative(C) then return true; fi;
## If the partition has been computed let the equivalence relation
## method deal with it
if HasEquivalenceRelationPartition(EquivalenceClassRelation(C)) then
TryNextMethod();
fi;
## We have partial closure see if this is enough
##
if HasPartialClosureOfCongruence(EquivalenceClassRelation(C)) then
part := PartialClosureOfCongruence(EquivalenceClassRelation(C));
rep := Representative(C);
class := First(part,y->rep in y);
# the partial closure has the elements in the same class
# return true
if class <> fail and x in class then
return true;
fi;
fi;
## Need to see if a partial closure can give an answer
## NOT possible to give a negative solution if the number
## of blocks or the size of a block is infinite
##
GLOBAL_REP := Representative(C);
GLOBAL_SEARCH_ELEMENT := x;
rel := EquivalenceClassRelation(C);
## These global variables are constant and used
## in the following partial closure test:
## stop when the search element is found in
## a block with the class's representative
##
partialclosure :=
function(cong, forest)
local block;
block := First(forest,y-> GLOBAL_SEARCH_ELEMENT in y);
if block=fail then return false; fi;
return GLOBAL_REP in block;
end;
MagmaCongruencePartition(rel, partialclosure);
## We might have gotten a full closure from this call if so
## delegate the next method to determine if we have
## the element in the class
## Otherwise the partial condition must have been satisfied
## return true
##
if HasEquivalenceRelationPartition(rel) then
TryNextMethod();
else
return true;
fi;
end);
#############################################################################
##
#M Enumerator( <C> )
##
## Enumerator for a magma congruence class.
##
InstallMethod( Enumerator, "for a magma congruence class", true,
[IsCongruenceClass], 0,
function(class)
local cong; # the congruence of which class is a class
cong := EquivalenceClassRelation(class);
## if the partition is already known, just go through the
## generic equivalence class method else compute the partition
## then get lazy and call generic equivalence
##
if HasEquivalenceRelationPartition(EquivalenceClassRelation(class)) then
TryNextMethod();
else
MagmaCongruencePartition(cong,function(x,y) return false; end);
TryNextMethod();
fi;
end);
#############################################################################
##
#M EquivalenceClassOfElement( <C>, <rep> )
#M EquivalenceClassOfElementNC( <C>, <rep> )
##
## Returns the equivalence class of an element <rep> with respect to a
## magma congrucene <C>. No calculation is performed at this stage.
## We do not always wish to check that <rep> is in the underlying set
## of <C>, since we may wish to use equivalence relations to perform
## membership tests (for example when checking membership of a
## transformation in a monoid, we use Greens relations and classes).
##
InstallMethod(EquivalenceClassOfElementNC,
"for magma congruence with no check",
[IsMagmaCongruence, IsObject],
function(rel, rep)
local filts, new;
filts:= IsCongruenceClass and IsEquivalenceClassDefaultRep;
if IsMultiplicativeElementWithOne(rep) then
filts:=filts and IsMultiplicativeElementWithOne;
else
filts:=filts and IsMultiplicativeElement;
fi;
if IsAssociativeElement(rep) then
filts:=filts and IsAssociativeElement;
fi;
new:= Objectify(NewType(CollectionsFamily(FamilyObj(rep)), filts), rec());
SetEquivalenceClassRelation(new, rel);
SetRepresentative(new, rep);
SetParent(new, UnderlyingDomainOfBinaryRelation(rel));
return new;
end);
InstallMethod(EquivalenceClassOfElementNC,
"for magma congruence with no check", true,
[IsLeftMagmaCongruence, IsObject], 0,
function(rel, rep)
local new;
if IsMultiplicativeElementWithOne(rep) then
new:= Objectify(NewType(CollectionsFamily(FamilyObj(rep)),
IsCongruenceClass and IsEquivalenceClassDefaultRep
and IsMultiplicativeElementWithOne), rec());
else
new:= Objectify(NewType(CollectionsFamily(FamilyObj(rep)),
IsCongruenceClass and IsEquivalenceClassDefaultRep
and IsMultiplicativeElement), rec());
fi;
SetEquivalenceClassRelation(new, rel);
SetRepresentative(new, rep);
SetParent(new, UnderlyingDomainOfBinaryRelation(rel));
return new;
end);
InstallMethod(EquivalenceClassOfElementNC,
"for magma congruence with no check", true,
[IsRightMagmaCongruence, IsObject], 0,
function(rel, rep)
local new;
if IsMultiplicativeElementWithOne(rep) then
new:= Objectify(NewType(CollectionsFamily(FamilyObj(rep)),
IsCongruenceClass and IsEquivalenceClassDefaultRep
and IsMultiplicativeElementWithOne), rec());
else
new:= Objectify(NewType(CollectionsFamily(FamilyObj(rep)),
IsCongruenceClass and IsEquivalenceClassDefaultRep
and IsMultiplicativeElement), rec());
fi;
SetEquivalenceClassRelation(new, rel);
SetRepresentative(new, rep);
SetParent(new, UnderlyingDomainOfBinaryRelation(rel));
return new;
end);
InstallMethod(EquivalenceClassOfElement, "for magma congruence with checking", true,
[IsMagmaCongruence, IsObject], 0,
function(rel, rep)
if not rep in UnderlyingDomainOfBinaryRelation(rel) then
Error("Representative must lie in underlying set of the relation");
fi;
return EquivalenceClassOfElementNC(rel, rep);
end);
InstallMethod(EquivalenceClassOfElement, "for left magma congruence with checking", true,
[IsLeftMagmaCongruence, IsObject], 0,
function(rel, rep)
if not rep in UnderlyingDomainOfBinaryRelation(rel) then
Error("Representative must lie in underlying set of the relation");
fi;
return EquivalenceClassOfElementNC(rel, rep);
end);
InstallMethod(EquivalenceClassOfElement, "for right magma congruence with checking", true,
[IsRightMagmaCongruence, IsObject], 0,
function(rel, rep)
if not rep in UnderlyingDomainOfBinaryRelation(rel) then
Error("Representative must lie in underlying set of the relation");
fi;
return EquivalenceClassOfElementNC(rel, rep);
end);
#############################################################################
##
#M ImagesElm( <rel>, <elm> ) . . . for a magma congruence
## assume we can compute the partition
##
InstallMethod( ImagesElm,
"for magma congruence and element",
FamSourceEqFamElm,
[ IsMagmaCongruence, IsObject ], 0,
function( rel, elm )
return Set(Enumerator(EquivalenceClassOfElement(rel,elm)));
end);
#############################################################################
##
#M ImagesElm( <rel>, <elm> ) . . . for a left magma congruence
## assume we can compute the partition
##
InstallMethod( ImagesElm,
"for magma congruence and element",
FamSourceEqFamElm,
[ IsLeftMagmaCongruence, IsObject ], 0,
function( rel, elm )
return Set(Enumerator(EquivalenceClassOfElement(rel,elm)));
end);
#############################################################################
##
#M ImagesElm( <rel>, <elm> ) . . . for a right magma congruence
## assume we can compute the partition
##
InstallMethod( ImagesElm,
"for magma congruence and element",
FamSourceEqFamElm,
[ IsRightMagmaCongruence, IsObject ], 0,
function( rel, elm )
return Set(Enumerator(EquivalenceClassOfElement(rel,elm)));
end);
[ Dauer der Verarbeitung: 0.6 Sekunden
(vorverarbeitet)
]
|
