This chapter contains a short example session to illustrate some basic features of the SmallOverlap package. We begin, naturally enough, by loading the package:
gap> LoadPackage("smalloverlap"); Loading package SmallOverlap (version 0.1) Mark Kambites, School of Mathematics, University of Manchester This is an experimental development version and may contain bugs. All usage is at your own risk. Please send comments and bug reports to Mark.Kambites@manchester.ac.uk SmallOverlap routines are now installed for explicit use only; to enable implicit use call PreferSmallOverlapEqualityTest() true |
Next we define a finitely presented monoid to play with, and give some names to its generators. (See [GG, Chapter 51] for information on defining finitely presented monoids and semigroups in GAP.)
gap> f := FreeMonoid(["a", "b", "c"]); <free monoid on the generators [ a, b, c ]> gap> gens := GeneratorsOfMonoid(f);; A := gens[1];; B := gens[2];; C := gens[3];; gap> s := f / [[A^2 * B * C, A * C * B * A]]; <fp monoid on the generators [ a, b, c ]> gap> a:=GeneratorsOfMonoid(s)[1];; gap> b:=GeneratorsOfMonoid(s)[2];; gap> c:=GeneratorsOfMonoid(s)[3];; |
Now we make our first use of the SmallOverlap package, to compute the small overlap class of our newly defined monoid.
gap> SmallOverlapClass(s); 4 |
So the presentation we gave for s
satisfies the small overlap condition C(4). Note that SmallOverlapClass
(4.1-2) is implemented as an attribute of finitely presented monoids and semigroups, which means that when once we have computed it, GAP knows it for the rest of the session:
gap> s; <C(4) small overlap fp monoid on the generators [ a, b, c ]> |
For this presentation, GAP's standard Knuth-Bendix completion algorithm does not terminate, so it does not know how to solve the word problem:
gap> a = b; |
At this point, GAP will enter an infinite loop, and nothing further will happen! (If you are following along with the example in GAP, you will need to interrupt this computation - on most platforms hold down Ctrl and press C to break into the computation, and then type "quit;
" at the break prompt to return to the normal GAP prompt.)
Now we try the same test, making explicit use of the SmallOverlap routines:
gap> C4WordProblem(a, b); false |
To enable implicit use of the SmallOverlap routines for equality testing, we use the function PreferSmallOverlapEqualityTest
(4.3-1):
gap> PreferSmallOverlapEqualityTest(true); SmallOverlap routines will now be used (where applicable) for testing equality in finitely presented semigroups and monoids. And you'll know about it. |
We can now just use the equality test operator (=
) and GAP will automatically use the small overlap routines if applicable...
gap> a = b; (using SmallOverlap equality test) false gap> a*a*b*c*a*b*c = a*a*b*c*c*b*a; (using SmallOverlap equality test) true |
The output "(using SmallOverlap equality test)
" is because we passed the argument true
to PreferSmallOverlapEqualityTest
(4.3-1). If we had instead used the argument false
(or no argument), the selection of small overlap routines would have been entirely transparent.
Note that the selection of the small overlap equality tester is not dependent on the fact that we had previously called SmallOverlapClass
(4.1-2) to check the small overlap class of the presentation. Had we not done so, it would have been checked automatically.
For semigroups and monoids not satisfying C(4), the equality tester reverts to whatever GAP would have used had the package not been installed (usually Knuth-Bendix completion, although it could be something different if you have other packages installed or the semigroup or monoid has other special properties).
gap> t := f / [[A^2, B]]; <fp monoid on the generators [ a, b, c ]> gap> GeneratorsOfMonoid(t)[1] = GeneratorsOfMonoid(t)[2]; (using GAP's default (Knuth-Bendix?) equality test) false |
In this case GAP reverts to the usual Knuth-Bendix method (which, fortunately, works this time!). This is because....
gap> IsC4(t); false gap> SmallOverlapClass(t); 2 |
....the presentation we have given for t
does not have sufficiently good small overlap properties for the new routines to be applicable.
generated by GAPDoc2HTML