-
Notifications
You must be signed in to change notification settings - Fork 33
/
froidure-pin.gi
147 lines (124 loc) · 4.73 KB
/
froidure-pin.gi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
###########################################################################
##
## ideals/froidure-pin.gi
## Copyright (C) 2014-2022 James D. Mitchell
##
## Licensing information can be found in the README file of this package.
##
#############################################################################
##
# This file contains method specific to ideals of semigroups.
# We use the result of running the Froidure-Pin algorithm on the supersemigroup
# of an ideal to calculate elements, size, test membership, find idempotents,
# etc. We get a generating set and use that otherwise.
InstallMethod(PositionsInSupersemigroup,
"for a semigroup ideal with known generators",
[IsSemigroupIdeal and HasGeneratorsOfSemigroupIdeal and
CanUseFroidurePin],
function(I)
local S, L, R, D, result, pos, x;
S := SupersemigroupOfIdeal(I);
L := LeftCayleyDigraph(S);
R := RightCayleyDigraph(S);
D := DigraphEdgeUnion(L, R);
# This could be better, we could use the quotient of the above graph by its
# sccs.
result := [];
for x in GeneratorsOfSemigroupIdeal(I) do
pos := PositionCanonical(S, x);
if not pos in result then
AddSet(result, pos);
UniteSet(result, VerticesReachableFrom(D, pos));
fi;
od;
return result;
end);
InstallMethod(PositionsInSupersemigroup,
"for a left semigroup ideal with known generators",
[IsLeftSemigroupIdeal and HasGeneratorsOfSemigroupIdeal and
CanUseFroidurePin],
function(I)
local S, L, result, pos, x;
S := SupersemigroupOfIdeal(I);
L := LeftCayleyDigraph(S);
result := [];
for x in GeneratorsOfSemigroupIdeal(I) do
pos := PositionCanonical(S, x);
if not pos in result then
AddSet(result, pos);
UniteSet(result, VerticesReachableFrom(L, pos));
fi;
od;
return result;
end);
InstallMethod(PositionsInSupersemigroup,
"for a right semigroup ideal with known generators",
[IsRightSemigroupIdeal and HasGeneratorsOfSemigroupIdeal and
CanUseFroidurePin],
function(I)
local S, R, result, pos, x;
S := SupersemigroupOfIdeal(I);
R := RightCayleyDigraph(S);
result := [];
for x in GeneratorsOfSemigroupIdeal(I) do
pos := PositionCanonical(S, x);
if not pos in result then
AddSet(result, pos);
UniteSet(result, VerticesReachableFrom(R, pos));
fi;
od;
return result;
end);
InstallMethod(GeneratorsOfInverseSemigroup,
"for an inverse semigroup ideal with inverse op and generators",
[IsSemigroupIdeal and IsInverseSemigroup
and IsGeneratorsOfInverseSemigroup and HasGeneratorsOfSemigroupIdeal],
GeneratorsOfSemigroup);
InstallMethod(Enumerator,
"semigroup ideal with generators and CanUseFroidurePin",
[IsSemigroupIdeal and HasGeneratorsOfSemigroupIdeal and CanUseFroidurePin],
2, # To beat the method for IsSemigroup and CanUseFroidurePin
function(I)
local en, record;
en := EnumeratorCanonical(SupersemigroupOfIdeal(I));
record := rec();
# TODO store en in enum
record.NumberElement :=
{enum, elt} -> Position(PositionsInSupersemigroup(I), Position(en, elt));
record.ElementNumber := {enum, nr} -> en[PositionsInSupersemigroup(I)[nr]];
record.IsBound\[\] := {enum, nr} -> IsBound(PositionsInSupersemigroup(I)[nr]);
record.Length := enum -> Length(PositionsInSupersemigroup(I));
return EnumeratorByFunctions(I, record);
end);
InstallMethod(Size, "for a semigroup ideal with generators",
[IsSemigroupIdeal and HasGeneratorsOfSemigroupIdeal],
I -> Length(Enumerator(I)));
InstallMethod(\in,
"for a multiplicative element and semigroup ideal with generators",
[IsMultiplicativeElement,
IsSemigroup and CanUseFroidurePin and IsSemigroupIdeal
and HasGeneratorsOfSemigroupIdeal],
{x, I} -> Position(Enumerator(I), x) <> fail);
# The method for GeneratorsOfSemigroup for a semigroup ideal must
# not rely in any way on the output of the Froidure-Pin algorithm when run on
# the ideal. In order to run the Froidure-Pin algorithm requires its input
# semigroup (ideal) to have a generating set, and so if the method below
# requires the output of the F-P algorithm (Green's relations, etc), then we
# get caught in an infinite loop: finding the generating set calls the F-P
# algorithm which tries to find a generating set, and so on.
InstallMethod(GeneratorsOfSemigroup, "for a semigroup ideal with generators",
[IsSemigroupIdeal and HasGeneratorsOfSemigroupIdeal],
function(I)
local U;
U := ClosureSemigroup(Semigroup(MinimalIdealGeneratingSet(I)),
Enumerator(I));
return GeneratorsOfSemigroup(U);
end);
InstallMethod(Idempotents, "for a semigroup ideal with generators",
[IsSemigroupIdeal and HasGeneratorsOfSemigroupIdeal and CanUseFroidurePin],
function(I)
local S, en;
S := SupersemigroupOfIdeal(I);
en := EnumeratorCanonical(S);
return en{IdempotentsSubset(S, PositionsInSupersemigroup(I))};
end);