SmallGenerating set returns incorrect output for trivial monoid

Issue #64 duplicate
Attila Egri-Nagy
created an issue
gap> gens := SmallGeneratingSet(Semigroup(IdentityTransformation));
[  ]
gap> Semigroup(gens);
Error, usage: cannot create a semigroup with no generators, called from
<function "Semigroup">( <arguments> )
 called from read-eval loop at line 2 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue

Comments (7)

  1. James Mitchell repo owner

    This isn't a bug, but I might be willing to consider it as a feature request.

    Here's why: SmallGeneratingSet returns the value of Generators when applied to a semigroup created using a set of generators (found from the generators of the original semigroup). In this case what happens is that you are getting the result of Generators(Semigroup(IdentityTransformation)). Since Semigroup(IdentityTransformation) is a monoid, Generators returns GeneratorsOfMonoid for it, which in this case is empty.

    Note that you can happily do:

    gap> S:=Semigroup(IdentityTransformation);                            
    <trivial transformation group>
    gap> GeneratorsOfSemigroup(S);
    [ IdentityTransformation ]
    gap> GeneratorsOfMonoid(S);
    [  ]
    gap> GeneratorsOfGroup(S);
    [  ]

    It could be that SmallGeneratingSet always returns the value of GeneratorsOfSemigroup but then in some cases, like inverse semigroups, this would return more generators than GeneratorsOfInverseSemigroup. I'm not really sure how to proceed.

  2. Attila Egri-Nagy reporter

    If I knew nothing about implementational details, I would ask for mathematical correctness over efficiency. The problem here is that a set is returned as a generating set, but it is not.

    Probably, one solution would be to have SmallSemigroupGeneratingSet and SmallMonoidGeneratingSet, since you already distinguish between these generating sets. Monoid([]) also does not work.

    I bump into this problem when processing a set of millions of semigroups that may contain the trivial monoid. Now I have to search for the trivial monoid beforehand.

  3. Attila Egri-Nagy reporter

    Bit offtopic, but speaking of mathematical consistency, I would very much like to have the empty semigroup as a completely valid semigroup, since the empty set is a semigroup. Though I can imagine this would mess up the code with checks for emptiness everywhere...

  4. Attila Egri-Nagy reporter

    Yes, if S = Semigroup(SmallSemigroupGeneratingSet(S)) is always true, and in most cases SmallSemigroupGeneratingSet(S) < |S|, as the semigroups I need to process are often generated by the whole set of elements.

  5. Log in to comment