Add an interface to Jean-Eric Pin's Semigroupe package

[nthiery]

Add an interface to Jean-Eric Pin's Semigroupe package

http://www.liafa.jussieu.fr/~jep/semigroupes.html

An experimental spkg is now on trac; here is the patch taken from the old Sage-Combinat patch server:

:attachment:trac_8360_semigroupe-interface-nt.patch

Status: advanced proof of concept, with interactions in both directions (building a semigroup in Semigroupe from Sage data). Main show stopper: one can only manipulate one semigroup at a time.

The following should hopefully get you started:

   sage -f https://github.com/sagemath/sage-prod/files/10648262/semigroupe-2.0-2.spkg.gz
   sage -combinat update
   sage -br

   sage: semigroupe?
   sage: semigroupe.tutorial?

Beware 'sage -f an_url' does not redownload the package if sage
already has a copy of it. So you may have to first do:

        rm <SAGE_ROOT>/spkg/optional/semigroupe-2.0.spkg

Update 2016-12-05: James Mitchel is reimplementing Semigroupe in C++, which will lift the main limitation (a single semigroup at a time):
https://james-d-mitchell.github.io/semigroupsplusplus/

This could be the occasion to revive this old code.

CC: @sagetrac-sage-combinat Jean-Eric.Pin@liafa.jussieu.fr @sagetrac-abmasse @tscrim

Component: algebra

Keywords: Semigroupes

Author: Florent Hivert, Jean-Eric Pin, Nicolas M. Thiéry

Issue created by migration from https://trac.sagemath.org/ticket/8360

[nthiery]

comment:1

Attachment: Semigroupe-2.0.spkg.gz

[nthiery]

Superceedes the previous spkg

[nthiery]

comment:2

Attachment: semigroupe-2.0.spkg.gz

[saliola]

comment:5

There seems to be a problem on a 64bit machine. After installing the spkg, the following commands will cause Sage to segfault:

sage: W = CoxeterGroup(["H",4])
sage: S = semigroupe.AutomaticSemigroup(W.semigroup_generators(), W.one(), category = FiniteCoxeterGroups())
sage: S.cardinality()
------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occured in Sage.
...

The problem seems to be with compiling Semigroupe on a 64bit machine. After installing the package, the following segfaults:

karkwa: cd $SAGE_ROOT/local/bin
karkwa: Semigroupe
karkwa: ./Semigroupe
Segmentation fault
karkwa: ./SelfContainedTest 
Toto
a | 2  3  1 
b | 2  1  3 
c | 1  2  1 

Segmentation fault
karkwa: ./SemigroupeModuleTest 

a | 2  1 
b | 1  1 

Segmentation fault 

I think that the two test suites (I think they are test suites...) should be run by the spkg-check script.

[anneschilling]

comment:6

On a 32-bit machine, I obtain the following error:

sage: S = semigroupe.AutomaticSemigroup(W.semigroup_generators(), W.one(), category = FiniteCoxeterGroups())
sage: S.cardinality()
python(24860) malloc: *** vm_allocate(size=262144) failed (error code=3)
python(24860) malloc: *** error: can't allocate region
python(24860) malloc: *** set a breakpoint in szone_error to debug
memory allocation failed
memory usage :

size : 2^ used/allocated
0 310/312
1 21/22
2 109/109
3 73/73
4 49/50
5 5/6
6 9/9
7 3/3
8 1/1
9 1/1
10 1/2
11 0/1
12 0/0
13 0/1
14 1/1
15 25959/25959
16 0/0
17 0/0
18 0/0
19 0/0
20 0/0
21 0/0
22 0/0
23 0/0
24 0/0
25 0/0
26 0/0
27 0/0
28 0/0
29 0/0
30 0/0
31 0/0

total : 850645964/850657280 4-byte units used/allocated
.../Applications/sage-4.4/devel/sage-combinat/sage/combinat/crystals$

Anne

[saliola]

comment:7

In case this helps track down the issue: things seem to be working correctly in a 32bit virtual machine. I created a 32bit VirtualBox virtual machine, installed Ubuntu 10.04, then I installed the sage-4.4.1 binary, the gap3 spkg from #8906, and the semigroupe spkg here.

[nthiery]

Changed author from Florent Hivert, Jean-Eric Pin Nicolas M. Thiéry to Florent Hivert, Jean-Eric Pin, Nicolas M. Thiéry

[nthiery]

comment:8

I think that the two test suites (I think they are test suites...) should be run by the spkg-check script.

Those are little self contained test programs we had written with Florent to understand how semigroupe was working. Yes, they eventually should be turned into test suites, and run from spkg-check.

[nthiery]

Attachment: semigroupe-2.0-2.spkg.gz

Same as previous one, working on both 32bits and 64bits, but managing the patches on the semigroupe sources in a mercurial queue

[seblabbe]

comment:11

Note that semigroupe is now part of the experimental packages:

http://www.sagemath.org/packages/experimental/

One can install it with the usual sage -i semigroupe-2.0-2.spkg.

next step is to make the code in sage-combinat go into sage...

[nthiery]

comment:12

Great, thanks Sébastien for taking care of this!

The next step is actually just to make a branch out of the patch. I am not sure about actually getting this branch into Sage until Semigroupe will be fixed one way or the other to support several semigroups simultaneously.

Cheers,
Nicolas

[seblabbe]

comment:13

Replying to @nthiery:

Great, thanks Sébastien for taking care of this!

The next step is actually just to make a branch out of the patch.

you mean a git branch?

which patch? is it finite_semigroup-nt.patch ?

I don't see how this patch uses semigroupe.

I am not sure about actually getting this branch into Sage until
Semigroupe will be fixed one way or the other to support several
semigroups simultaneously.

I think I don't agree. I think the goal of the actual ticket #8360 is to make the actual semigroup into sage as it is. semigroupe was written for something no? Let's first make this available!

Then I suggest to open a ticket showing with sage command line code illustrating how the bug for creating two semigroup simultaneously is obtained. The new ticket would ask for an upstream fix.

Sébastien

[nthiery]

comment:14

Replying to @seblabbe:

Replying to @nthiery:

The next step is actually just to make a branch out of the patch.

you mean a git branch?

Yup.

which patch? is it finite_semigroup-nt.patch ?
I don't see how this patch uses semigroupe.

trac_8360_semigroupe-interface-nt.patch

I am not sure about actually getting this branch into Sage until
Semigroupe will be fixed one way or the other to support several
semigroups simultaneously.

I think I don't agree. I think the goal of the actual ticket #8360
is to make the actual semigroup into sage as it is. semigroupe was
written for something no? Let's first make this available!

Indeed, the interface was written for something. But in practice, even
if I spent quite some time on it, I am actually seldom using it
because that misfeature is making it relatively unusable (at least in
my use-cases).

Then I suggest to open a ticket showing with sage command line code
illustrating how the bug for creating two semigroup simultaneously
is obtained. The new ticket would ask for an upstream fix.

That's an option. If you are convinced that:

• At some point not to far in the future the bug will be fixed upstream (upstream meaning possibly us taking the time to do the fix).

• The current code won't need serious interface change then.

Then let's go ahead. I'd love to have this code always under my fingertips. Otherwise I am a bit reluctant to put in Sage some code that we might need to remove (because unused) or change a
lot later on.

At the end of the day, this would actually be best handled by putting
the interface code in the spkg and not in the Sage library. I haven't
checked how hard/easy it would be to handle.

Cheers,
Nicolas

[nthiery]

comment:15

Attachment: trac_8360_semigroupe-interface-nt.patch.gz