Implemented O(N^2) max chain of essential dependency.

[thomasgaozx]

Sample Input A:

alpha:=   Transformation([2,2,4,4,5,2]);;  #NAD
beta:=     Transformation([1,3,3,4,5,6]);;  #NADP
gamma:=Transformation([1,2,3,5,5,6]);;  #GDP
delta:=    Transformation([1,2,3,4,6,6]);;  #NADP
KrebsK2:=Semigroup(alpha,beta, gamma,delta);;;
skel:=Skeleton(KrebsK2);
MaxChainOfEssentialDependency(skel);

Output A:

[ 5, 6 ]

which imples level 5 and level 6 has essential dependency.

---

Sample Input B:

S := FullTransformationSemigroup(6);
sk := Skeleton(S);
MaxChainOfEssentialDependency(sk);

Output B (after ~10s of runtime)

[ 1, 2, 3, 4, 5 ]

[thomasgaozx]

Just fixed, thanks for the improvements!

[egri-nagy]

The checks were failing for a completely different reason (name clash with another package). Will recheck here when that fix is done.

[thomasgaozx]

The algorithm assumes transitivity of weak control which is provably false (with this example). So need to fix (check R-Equivalence) in a separate PR.

[Transformation ([1, 2, 3, 1, 1, 1]),
Transformation ([4, 4, 4, 5, 4]),
Transformation ([4, 4, 4, 5, 6, 4]),
Transformation ([4, 4, 4, 4, 5, 5]),
Transformation ([4, 4, 4, 1, 2, 3]),
Transformation ([2, 3, 1, 4, 4, 4])]

[nehaniv]

More precisely, the theorem being used (Rhodes, Applications of Automata Theory & Algebra, Sec 4.11, pp. 49-50, Theorem 4.11a) needs a chain of subsets under inclusion as the image sets in the chain.
It should be sufficient to add a test that one has a subset chain (then one can prove that's equivalent to having an idempotent chain e_1 > e_2 > ... > e_n with the subsets as their images).

[thomasgaozx]

Error:

gap> gen := [Transformation ([1, 2, 3, 1, 1, 1]),
> Transformation ([4, 4, 4, 5, 4]),
> Transformation ([4, 4, 4, 5, 6, 4]),
> Transformation ([4, 4, 4, 4, 5, 5]),
> Transformation ([4, 4, 4, 1, 2, 3]),
> Transformation ([2, 3, 1, 4, 4, 4])];
[ Transformation( [ 1, 2, 3, 1, 1, 1 ] ), Transformation( [ 4, 4, 4, 5, 4 ] ), Transformation( [ 4, 4, 4, 5, 6, 4 ] ),
  Transformation( [ 4, 4, 4, 4, 5, 5 ] ), Transformation( [ 4, 4, 4, 1, 2, 3 ] ),
  Transformation( [ 2, 3, 1, 4, 4, 4 ] ) ]
gap> becks := Semigroup(gen);
<transformation semigroup of degree 6 with 6 generators>
gap> skel := Skeleton(becks);
<skeleton of Semigroup( [ Transformation( [ 1, 2, 3, 1, 1, 1 ] ), Transformation( [ 4, 4, 4, 5, 4 ] ), Transformation(\
 [ 4, 4, 4, 5, 6, 4 ] ), Transformation( [ 4, 4, 4, 4, 5, 5 ] ), Transformation( [ 4, 4, 4, 1, 2, 3 ] ), Transformatio\
n( [ 2, 3, 1, 4, 4, 4 ] ) ] )>
gap> MaxChainOfEssentialDependency(skel);
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `SchutzenbergerGroup' on 1 arguments at /opt/gap-v4.12.2/.libs/../lib/methsel2.g:249 called from
SchutzenbergerGroup( HClass( S, e1 ) ) at /opt/gap-v4.12.2/.libs/../pkg/sgpdec//lib/lowerbound.gi:28 called from
CheckEssentialDependency( sk, levels[i], levels[j] ) at /opt/gap-v4.12.2/.libs/../pkg/sgpdec//lib/lowerbound.gi:86 called from
<function "MaxChainOfEssentialDependency">( <arguments> )
 called from read-eval loop at *stdin*:11
type 'quit;' to quit to outer loop

gap> CheckEssentialDependency(skel,2,3);
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `SchutzenbergerGroup' on 1 arguments at /opt/gap-v4.12.2/.libs/../lib/methsel2.g:249 called from
SchutzenbergerGroup( HClass( S, e1 ) ) at /opt/gap-v4.12.2/.libs/../pkg/sgpdec//lib/lowerbound.gi:28 called from
<function "CheckEssentialDependency">( <arguments> )
 called from read-eval loop at *stdin*:23
type 'quit;' to quit to outer loop