Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma


products/Sources/formale Sprachen/GAP/pkg/smallsemi/doc/ (Algebra von RWTH Aachen Version 4.15.1^©) Datei vom 25.1.2025 mit Größe 27 kB

Quelle chap3.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/smallsemi/doc/chap3.html

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (Smallsemi) - Chapter 3: Extended Examples</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap3" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap2.html">[Previous Chapter]</a> <a href="chap4.html">[Next Chapter]</a> </div>

<a href="chap3_mj.html">[MathJax on]</a>
<a id="X7CDC63A27F7790AA" name="X7CDC63A27F7790AA"></a>
<div class="ChapSects"><a href="chap3.html#X7CDC63A27F7790AA">3 Extended Examples</a>
<div class="ContSect"> <a href="chap3.html#X80DFE0117B7A7C24">3.1 Lists, Enumerators and Iterators of Semigroups</a>

<div class="ContSSBlock">
 <a href="chap3.html#X790CB8D686E0A336">3.1-1 Precomputed properties</a>

 <a href="chap3.html#X804593297D7EEF68">3.1-2 User functions</a>

 <a href="chap3.html#X7E4F0756878EB958">3.1-3 Semigroups of order 8</a>

</div></div>
<div class="ContSect"> <a href="chap3.html#X8772952F7B2CFDE1">3.2 Identifying Semigroups</a>

</div>
</div>

<h3>3 Extended Examples</h3>

The main features of the library can be summarized in three points: it provides a complete set of semigroups up to isomorphism and anti-isomorphism of sizes up to 8; it carries a vast amount of precomputed information about these semigroups; and there is an identification function which takes a semigroup with at most 8 elements and returns a map to the equivalent one from the library.

These features lead to different ways of using the library. It is impossible to describe - or even to anticipate - all possible types of usage. Most problems will admit multiple solutions. We find it difficult to predict which will be most effective. The examples in this chapter should give an idea of the differences in the various functions and help you to find an alternative if a computation uses more time or memory than you have available.

Let us go step by step through some ways to use the library showing which tools are provided.

<a id="X80DFE0117B7A7C24" name="X80DFE0117B7A7C24"></a>

<h4>3.1 Lists, Enumerators and Iterators of Semigroups</h4>

At first one could want to search through the stored semigroups for one or all semigroups with a certain property. Going through all the semigroups can take a long time. Just to create all the 1.8 billion semigroups as objects in GAP takes around a day on a modern PC. Doing a simple test on all the semigroups in the library might take another day. Performing complicated tests easily takes weeks. To avoid this, many properties of the semigroups were precomputed. Semigroups with or without a precomputed property can be accessed as quickly as simply creating the same number of semigroups. (Note that timings of two calls to the same command may vary and, of course, heavily depend on your machine.)

<div class="example"><pre>
gap> # obtain a list of all semigroups with 6 elements
gap> AllSmallSemigroups(6);;
gap> time;
2636
gap> # obtain a list of all commutative semigroups with 7 elements
gap> AllSmallSemigroups(7, IsCommutative, true);;
gap> time;
2957
gap> # compare the numbers of semigroups in the two lists
gap> NrSmallSemigroups(6); NrSmallSemigroups(7, IsCommutative, true);
15973
17291
</pre></div>

(In all the examples in this section the info messages which are given by default when data is loaded are turned off via <code class="code">SetInfoLevel(InfoSmallSemi,0)</code>.)

We provide three commands that can be used if one is interested in all semigroups with some properties. These are <code class="func">AllSmallSemigroups</code> (<a href="chap4.html#X81DC0FE28043C9B0">4.5-1</a>), <code class="func">EnumeratorOfSmallSemigroups</code> (<a href="chap4.html#X831E543E83DDFDEA">4.5-2</a>), and <code class="func">IteratorOfSmallSemigroups</code> (<a href="chap4.html#X7D6BFDE17A9BEEC3">4.5-9</a>). Which one is best to use depends a lot on the situation. Here we attempt to provide some insight about the essential differences.

<a id="X790CB8D686E0A336" name="X790CB8D686E0A336"></a>

<h5>3.1-1 Precomputed properties</h5>

We start with examples using only precomputed information. In this case there is essentially no advantage of calling an iterator instead of an enumerator. Thus only <code class="func">AllSmallSemigroups</code> (<a href="chap4.html#X81DC0FE28043C9B0">4.5-1</a>) and <code class="func">EnumeratorOfSmallSemigroups</code> (<a href="chap4.html#X831E543E83DDFDEA">4.5-2</a>) will be considered.

We first compare the memory usage and the setup time. Assume we are interested in the commutative semigroups with at most 7 elements.

<div class="example"><pre>
gap> list := AllSmallSemigroups([1 .. 7], IsCommutativeSemigroup, true);;
gap> time; # the time needed will always depend on your machine
3180
gap> enum := EnumeratorOfSmallSemigroups([1 .. 7], IsCommutativeSemigroup, true);
<enumerator of semigroups of sizes [ 1 .. 7 ]>
gap> time;
8
</pre></div>

The enumerator stores the information, which semigroups it contains, but only creates the semigroups when asked for them explicitly.

<div class="example"><pre>
gap> # now the semigroups have to be created ...
gap> for sg in enum do
> # do nothing, the semigroup will be created anyway
> od;
gap> time;
3428
gap> # ... and again if you want to look through them another time ...
gap> for sg in enum do od;
gap> time;
3437
gap> # ... not so for the list of semigroups though
gap> for sg in list do od;
gap> time;
4
</pre></div>

There are several reasons why one would nevertheless prefer an enumerator, one is the smaller need for memory. While the number of semigroups in this example is rather moderate (compared with all the semigroups in the library) the difference is remarkable:

<div class="example"><pre>
gap> nr := Length(enum);
17291
gap> MemoryUsage(enum);
70507
gap> MemoryUsage(list); # this will take a while .. .
19089280
gap> # ... but you can get a close approximation much faster
gap> sg := OneSmallSemigroup(7, IsCommutativeSemigroup, true);

gap> nr * MemoryUsage(sg);
19020100
</pre></div>

As said before the advantage of the enumerator comes from the fact that the members of it are created anew every time they are called. This means on the other hand that information that is computed is not stored.

<div class="example"><pre>
gap> IsZeroSemigroup(list[3]); # a semigroup from the list .. .
false
gap> KnownPropertiesOfObject(list[3]); # .. . can store new information
[ "IsEmpty", "IsTrivial", "IsNonTrivial", "IsFinite", "IsDuplicateFree",
 "IsAssociative", "IsCommutativeSemigroup", "IsZeroSemigroup" ]
gap> IsZeroSemigroup(enum[3]); # semigroups in the enumerator .. .
false
gap> KnownPropertiesOfObject(enum[3]); # .. . are created anew in every call
[ "IsEmpty", "IsTrivial", "IsNonTrivial", "IsFinite", "IsDuplicateFree",
 "IsAssociative", "IsCommutativeSemigroup" ]
gap> # but if it turns out this is the semigroup you want to analyse, just do
gap> sg := enum[3];
</pre></div>

Observe that in the last example the semigroup from the enumerator knew about the property that was used to create the enumerator. The enumerator stores this knowledge and passes it on whenever a member is called.

Another reason to prefer an enumerator is that one might only be interested in some of the elements it contains. This could become clear after analysing some of the elements and then there is no time wasted in creating all semigroups in the enumerator. Or possibly creating the enumerator involving precomputed properties was just the first step. As described in Section <a href="chap4.html#X82F9C36C86006857">4.5</a> enumerators themselves can be given as argument to get to a more restricted class of semigroups. This leads us to the next part of this section.

<a id="X804593297D7EEF68" name="X804593297D7EEF68"></a>

<h5>3.1-2 User functions</h5>

We now come to examples dealing with properties that are not precomputed - including user defined functions. This makes <code class="func">IteratorOfSmallSemigroups</code> (<a href="chap4.html#X7D6BFDE17A9BEEC3">4.5-9</a>) interesting again. Assume you want to work with bands (<code class="func">IsBand</code> (<a href="chap4.html#X7C8DB14587D1B55A">4.2-5</a>)) of order 8 having 1 Green's D-class (see Reference: Green's Relations</a>). You might feel tempted to implement a function testing a semigroup for this combination of properties.

<div class="example"><pre>
gap> isFascinatingSemigroup := function(sgrp)
local dclasses;
dclasses := GreensDClasses(sgrp);
return IsBand(sgrp) and Length(dclasses) = 1;
end;
</pre></div>

But then the precomputed property <code class="func">IsBand</code> (<a href="chap4.html#X7C8DB14587D1B55A">4.2-5</a>) is hidden inside your function and a call like <code class="code">AllSmallSemigroups(8,isFascinatingSemigroup,true)</code> would take days to complete.

The following finds the same semigroups more efficiently:

<div class="example"><pre>
gap> list := AllSmallSemigroups(8, IsBand, true,
> x -> Size(GreensDClasses(x)), 1);
[ , ]
gap> time;
49211
gap> enum := EnumeratorOfSmallSemigroups(8, IsBand, true,
> x -> Size(GreensDClasses(x)), 1);
<enumerator of semigroups of size 8>
gap> time;
48723
</pre></div>

Observe that the enumerator lost its advantage of returning the answer faster because not all properties are precomputed. Thus all bands have to be constructed to test their number of D-classes. As the number of such semigroups is small, <code class="func">AllSmallSemigroups</code> (<a href="chap4.html#X81DC0FE28043C9B0">4.5-1</a>) is the better choice in this example - remember that the semigroups from the enumerator have to be recreated in every call. Often one does not have this kind of knowledge beforehand. Even for a large number of semigroups the enumerator still has the advantage of using far less memory as it stores only the IDs of the semigroups. Before explaining more about this let us for a moment go back to the semigroups from the previous example. It turns out they are the 2 non-equivalent rectangular bands (<code class="func">IsRectangularBand</code> (<a href="chap4.html#X7E9B674D781B072C">4.2-22</a>)) with 8 elements.

<div class="example"><pre>
gap> ForAll(list, IsRectangularBand);
true
</pre></div>

As a last example in this subsection we look at semigroups from the library that are not nilpotent. As there are quite some of these we will first try an enumerator. The obvious call seems to be

<div class="example"><pre>
gap> enum1 := EnumeratorOfSmallSemigroups([1 .. 7], IsNilpotentSemigroup, false);
<enumerator of semigroups of sizes [ 2, 3, 4, 5, 6, 7 ]>
gap> time;
103403
</pre></div>

However, we would like to include the semigroups of order 8 as well. As <code class="func">IsNilpotentSemigroup</code> (<a href="chap4.html#X780ADE31828F0848">4.2-20</a>) is not a precomputed property in the current version of Smallsemi this would take a long time. Here, additional knowledge, about the way the semigroups are stored in the library, is helpful. The description of <code class="func">NilpotencyDegree</code> (<a href="chap4.html#X7D1C336E7B0A059C">4.2-34</a>) contains information on the IDs of all 3-nilpotent semigroups of order 8. We can create an enumerator without those semigroups doing the following:

<div class="example"><pre>
gap> # all 8 element semigroups that are not 3-nilpotent
gap> enum2 := EnumeratorOfSmallSemigroupsByIds([8], [[1 .. 11433106]]);
<enumerator of semigroups of size 8>
</pre></div>

Out of this enumerator the subclass of not nilpotent semigroups can be extracted.

<div class="example"><pre>
gap> enum3 := EnumeratorOfSmallSemigroups(enum2, IsNilpotentSemigroup, false);
gap> # This still takes quite a while though
gap> time;
1931140
</pre></div>

You can avoid the waiting time at setup by using an iterator instead of an enumerator. An iterator does not know how many elements it contains, one can always just access the next element - if such exists - and one cannot go back. (Making copies of an iterator can help to circumvent this problem.) On the other hand one could in the above example start investigating the first couple of elements right away.

<div class="example"><pre>
gap> iter := IteratorOfSmallSemigroups(enum2, IsNilpotentSemigroup, false);
gap> for i in [1 .. 100000] do
> NextIterator(iter);
> od;
gap> time;
30785
</pre></div>

But even if you know you want to inspect all the semigroups having a property which is not precomputed, an iterator has the advantage that it does not create the semigroups before you can actually work with them. To create an enumerator all semigroups in question will be created and - as said before - every element is created anew when it is accessed. An iterator on the other hand creates the semigroups in question one-by-one and returns the next one having the property. This makes a big difference if the number of semigroups one is interested in is big like in the example of not nilpotent semigroups of size 8. In the former example with the rectangular bands it would not play a role and the disadvantages of an iterator would prevail.

As you can see the number of semigroups you are interested in is even more important in the case of user defined functions than it was in the previous section about precomputed properties. Sometimes you might have a rough idea about the numbers - or even a very good one - to base your choice on. Otherwise the best approach seems to consist of two steps. First, create an enumerator involving all precomputed properties (try to find as many implied properties as possible). Then work with an iterator, call the semigroups one-by-one and store them in a separate list if you think you might want to look at them again at a later stage.

<a id="X7E4F0756878EB958" name="X7E4F0756878EB958"></a>

<h5>3.1-3 Semigroups of order 8</h5>

When using enumerators and iterators of semigroups of order 8 there are some limitations. In a 32-bit system the number of semigroups of order 8 exceeds the maximal length of a list in GAP. The following will work in a 64-bit system, but not on a 32-bit system.

<div class="example"><pre>
gap> EnumeratorOfSmallSemigroups(8);
</pre></div>

In all other cases there is currently no difference between 32-bit and 64-bit systems. Hence the following will fail in any case.

<div class="example"><pre>
gap> EnumeratorOfSmallSemigroups(8, IsCommutativeSemigroup, false);
</pre></div>

Note though that an enumerator of semigroups of order 8 can be created if one of the required properties is precomputed and takes <code class="code">true</code> as value. This fact was used in the previous subsection, when creating the enumerator of all bands of order 8 having 1 Green's D-class.

One could try to circumvent the described problem by using a iterator. The command

<div class="example"><pre>
gap> iter := IteratorOfSmallSemigroups(8, IsCommutativeSemigroup, false);
<iterator of semigroups of size 8>
</pre></div>

will succeed. But running through the elements in the iterator can take a long time since the precomputed information is not utilized. A better idea in the current version of Smallsemi is to divide the enumerator into smaller pieces by restricting the range of IDs considered at once to at most 2^28-1 (the maximal length of a list in a 32-bit GAP) or possibly by a smaller value, depending on the amount of memory you have available. For example start with

<div class="example"><pre>
gap> enum1 := EnumeratorOfSmallSemigroupsByIds([8], [[1 .. 2 ^ 24 - 1]]);
<enumerator of semigroups of size 8>
gap> enum2 := EnumeratorOfSmallSemigroups(enum1, IsCommutativeSemigroup, false);
<enumerator of semigroups of size 8>
</pre></div>

Thanks go to Michal Stolorz for the idea of circumventing the current performance issue for enumerators of small semigroups of order 8 by splitting it in the described way.

<a id="X8772952F7B2CFDE1" name="X8772952F7B2CFDE1"></a>

<h4>3.2 Identifying Semigroups</h4>

The data in Smallsemi is as a big catalogue of all structural types of semigroups with at most 8 elements making it possible to refer to the types by their catalogue number, that is by their ID. With <code class="func">IdSmallSemigroup</code> (<a href="chap4.html#X788211A07D67C282">4.1-6</a>) one can find the ID of the structural type of a particular semigroup with at most 8 elements.

<div class="example"><pre>
gap> t1 := RandomTransformation(3);
Transformation( [ 1, 3, 1 ] )
gap> t2 := RandomTransformation(3);
Transformation( [ 1, 2, 3 ] )
gap> sgrp := SemigroupByGenerators([t1, t2]);
<semigroup with 2 generators>
gap> Size(sgrp);
3
gap> IdSmallSemigroup(sgrp);
[ 3, 8 ]
</pre></div>

Moreover, one can draw conclusions about a semigroup of size at most 8 using the precomputed information about the equivalent semigroup from the library. The precomputed properties are all invariant under isomorphism and anti-isomorphism. This is most useful in the case where there is no method in GAP to decide the property in the original representation of the semigroup.

<div class="example"><pre>
gap> # use the semigroup from the previous example
gap> IsCommutative(sgrp); # no need to use the library for this
true
gap> # for the following there exists no method for a trans-
gap> # formation semigroup; access the precomputed information instead
gap> IsMultSemigroupOfNearRing(SmallSemigroup([3, 8]));
false
</pre></div>

<code class="func">EquivalenceSmallSemigroup</code> (<a href="chap4.html#X79D38A3886C7431D">4.1-7</a>) even provides an isomorphism or anti-isomorphism to a semigroup from the library. This means one can map elements between the semigroups. Remember that an isomorphism is returned whenever one exists. This allows to distinguish between structure types up to isomorphism. Note though, that no information about subsets - like the set of idempotents or a generating set - is precomputed for semigroups in the library. If an operation has a method for the semigroup in the original representation, it is usually more sensible to simply call this.

<div class="example"><pre>
gap> t1 := RandomTransformation(3);
Transformation( [ 2, 2, 1 ] )
gap> t2 := RandomTransformation(3);
Transformation( [ 2, 1, 1 ] )
gap> sgrp := Semigroup(t1, t2);
<semigroup with 2 generators>
gap> Size(sgrp);
6
gap> map := EquivalenceSmallSemigroup(sgrp);
MappingByFunction( <semigroup with 2 generators>, , function( x ) ... end )
gap> RespectsMultiplication(map); # verify that this is an anti-isomorphism
false
gap> MinimalGeneratingSet(Range(map));
[ s2, s4 ]
gap> PreImage(map, last); # get a minimal generating set of < sgrp >
[ Transformation( [ 1, 1, 2 ] ), Transformation( [ 2, 1, 1 ] ) ]
gap> Idempotents(Range(map));
[ s1, s3, s5 ]
gap> PreImage(map, last); # in the same way you can get the idempotents .. .
[ Transformation( [ 1, 1, 1 ] ), Transformation( [ 1, 2, 2 ] ),
 Transformation( [ 2, 2, 2 ] ) ]
gap> Idempotents(sgrp); # ... but this can be done directly instead
[ Transformation( [ 1, 1, 1 ] ), Transformation( [ 1, 2, 2 ] ),
 Transformation( [ 2, 2, 2 ] ) ]
</pre></div>

If for a certain application you are interested in the semigroups up to isomorphism you can still use the IDs from Smallsemi. Simply mark the ID with *, or however else you denote the dual of a semigroup, to refer to the semigroup being anti-isomorphic to the one in the library having the same ID. For all semigroups <code class="func">IsSelfDualSemigroup</code> (<a href="chap4.html#X846FC6247EE31607">4.2-25</a>) is precomputed. This will help to decide whether a semigroup and its dual are actually non-isomorphic.

<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap2.html">[Previous Chapter]</a> <a href="chap4.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<hr />
generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

quality100%

¤ Dauer der Verarbeitung: 0.19 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.

Neuigkeiten

Aktuelles

Motto des Tages

Software

Produkte

Quellcodebibliothek

Aktivitäten

Artikel über Sicherheit

Anleitung zur Aktivierung von SSL

Muße

Gedichte

Musik

Bilder

Jenseits des Üblichen ....