PartialOrderOfDClasses inconsistent output

Issue #99 resolved
Attila Egri-Nagy
created an issue

The documentation says that the partial order of D-classes can be obtained by the transitive closure of the output relations. However, it seems that the reflexive closure is also need. For manual example

gap> S:=Semigroup( Transformation( [ 2, 4, 1, 2 ] ), 
> Transformation( [ 3, 3, 4, 1 ] ) );;
gap> PartialOrderOfDClasses(S);
[ [ 3 ], [ 2, 3 ], [ 3, 4 ], [ 4 ] ]

(1,1) is missing, while the (3,3) explicitly appears in the output. This also contradicts the documentation saying that only the immediately below relations are returned, hinting that basically the Hasse diagram of the partial order is meant to be returned. From random examples it seems that PartialOrderOfDClasses misses some maximal elements.

So it is not clear what is returned exactly.

Comments (11)

  1. James Mitchell repo owner

    This is a bug in the documentation, not in the code. If l is the returned list, then it is guaranteed that in l[i] are all the indices of D-classes which are immediately below the ith D-class. There might be other indices there too, and this may or may not include i.

    So, you are correct, the documentation is wrong, I will amend it as described above, and add that it is the reflexive transitive closure which is the partial order of the D-classes.

  2. Attila Egri-Nagy reporter

    I see, and the documentation fix would solve the issue.

    However, I was trying to use PartialOrderOfDClasses as a possible invariant for deciding isomorphism (e.g. the number of arrows in the Hasse-diagram), and the fact that "There might be other indices there too, and this may or may not include i." makes it unusable for that purpose. So I wonder whether it would be possible to get the Hasse-diagram cheaply (i.e. without constructing the closures and then calculating the cover relations). Maybe this is feature request.

  3. Attila Egri-Nagy reporter

    Oh, yes, I was not precise. I would like to use the invariant for excluding the possibility of isomorphism. If the number of edges in the Hasse diagrams are different, then the semigroups are not isomorphic so we don't need to run the expensive backtrack search on their multiplication tables (in SubSemi).

  4. Attila Egri-Nagy reporter

    Just the code that I use for getting some complexity measure of the partial order by counting the edges in the Hasse diagram - as a temporary solution.

    NrEdgesInHasseDiagramOfDClasses := function(sgp)
      local hd;
      #producing the Hasse diagram of DClasses (in a roundabout way)
      hd := HasseDiagramBinaryRelation(
                    ReflexiveClosureBinaryRelation(
                            TransitiveClosureBinaryRelation(
                                    BinaryRelationByListOfImages(
                                            PartialOrderOfDClasses(sgp)))));
      #calculating the number of edges (summing the sizes of the image sets)
      return Sum(List(Source(hd), x-> Size(Images(hd,x))));;
    end;
    
  5. James Mitchell repo owner

    In changeset de5d3efdc5b5, I introduced some functions for digraphs in the Semigroups package. In there you can find the function, DigraphTransitiveClosure which has complexity O(n+m+nm) where n is the number of vertices and m is the number of edges in the digraph. I think this is best possible. So, you can do:

    gap> S:=Semigroup( Transformation( [ 2, 4, 1, 2 ] ), 
    > Transformation( [ 3, 3, 4, 1 ] ) );;
    gap> PartialOrderOfDClasses(S);
    [ [ 3 ], [ 2, 3 ], [ 3, 4 ], [ 4 ] ]
    gap> DigraphTransitiveClosure(last);
    [ [ 3, 4 ], [ 2, 3, 4 ], [ 3, 4 ], [ 4 ] ]
    

    Feedback welcome as always!

  6. Log in to comment