Software
This page describes the software I wrote for counting subsemigroups, ideals and congruences of free semigroups. For background material and a description of the algorithms used, see
this paper.
For a summary of the results of these computations see
here.
FISOFS
This is a collection of C++ files for constructing all finite (Rees) index subsemigroups of free semigroups, quite lamely called 'FISOFS'. It is recursive in nature, calculating the index n subsemigroups from
those of index n-1.
For free rank equal to 1 the number of subsemigroups grows asymptotically like the Fibonacci numbers, for free rank greater than 1, they grow superexponentially (i.e. there are a lot of them!) Therefore it was written with the intention of being run in parallel to make use of available HPC facilities.
We ran the code on the
Iridis 4
compute cluster and calculated all subsemigroups of index 9. The 9th polynomial took 2 hours 30 minutes to compute (this would have taken approximately one week on a standard desktop computer).
You can download the source code
here
or visit the GitHub repository
here.
You can also download precomputed data files up to index 8 here:
For a summary of the orbit data for each support size and the subsequent polynomials see
here.
For an HTML depiction of the subsemigroup tree of FS
2, see
here.
FIIOFS
This is almost identical to the code above except it calculates (Rees) index n ideals of free semigroups.
You can download the source code
here
or visit the GitHub repository
here.
You can download precomputed data files here:
-
For index 2 through 12 (350KB, extracted 4.1MB)
-
For index 2 through 25, just for support 1 and 2 (34MB, extracted 871MB)
For a summary of the orbit data for each support size and the subsequent polynomials see
here.
Congruences
Here
is the GAP code I used to calculate the number of 'ascendingly generated' Cayley tables which was used to
calculate
the number of n class congruences on the free semigroups, up to n=7. It makes use of the Smallsemi data library.