4 Reference
This chapter documents in detail the new attributes and functions provided by the SmallOverlap; examples of the use of the most important functions can be found in the example session in Chapter 3.
4.1 Attributes for Monoids and Semigroups
This section documents new attributes and filters defined by the package for finitely presented monoids and semigroups.
4.1-1 IsFpMonoidOrSemigroup
> IsFpMonoidOrSemigroup ( S ) | ( filter ) |
The filter IsFpMonoidOrSemigroup
is true
if the argument S is either a finitely presented monoid or a finitely presented semigroup, and false
otherwise. It is the disjunction of the standard GAP filters IsFpMonoid
and IsFpSemigroup
(see [GG, Chapter 51]).
4.1-2 SmallOverlapClass
> SmallOverlapClass ( S ) | ( attribute ) |
The SmallOverlapClass
of a finitely presented monoid or semigroup S, is the greatest positive integer n such that the presentation defining S satisfies the small overlap condition C(n). It returns infinity
if the presentation satisfies C(n) for all n, and 0 if the presentation does not satisfy C(n) for any n.
4.1-3 IsC4, IsC3, IsC2, IsC1
The filters IsC4
, IsC3
, IsC2
, IsC1
indicate whether the defining presentation for the finitely presented monoid or semigroup S satisfies the small overlap conditions C(4), C(3), C(2) and C(1) respectively. (They are currently implemented using the attribute SmallOverlapClass
(4.1-2); they could in principle be made more efficient by using dedicated code, but for "everyday"-sized presentations SmallOverlapClass
(4.1-2) is so fast that it makes no difference.)
4.1-4 RelationWords
> RelationWords ( S ) | ( attribute ) |
The attribute RelationWords
of the finitely presented semigroup or monoid S is a list of the relation words in the defining presentation in their letter representations (see [GG, Section 35.6]). Relation words paired in the presentation occur as adjacent elements of the list; given the index of a relation word in the list, the index of complement relation word can be retrieved with ComplementRelationWord
(4.3-4).
4.1-5 RelationWordLengths
> RelationWordLengths ( S ) | ( attribute ) |
The attribute RelationWordLengths
of the finitely presented semigroup or monoid S is a list of the lengths of the relation words in the defining presentation, in an order corresponding to RelationWords
(4.1-4).
4.1-6 MaxPiecePrefixLengths, MiddleWordLengths, MaxPieceSuffixLengths
> MaxPiecePrefixLengths ( S ) | ( attribute ) |
> MiddleWordLengths ( S ) | ( attribute ) |
> MaxPieceSuffixLengths ( S ) | ( attribute ) |
These attributes of a finitely presented monoid or semigroup S are lists containing respectively the length of the longest piece prefix, length of the middle word, and length of the longest piece suffix of each relation word, in an order corresponding to RelationWords
(4.1-4).
4.1-7 MaxPieceSuffixLengthBound
> MaxPieceSuffixLengthBound ( S ) | ( attribute ) |
This is the length of the longest maximal piece suffix of any relation word in the defining presentation for the finitely presented monoid or semigroup S. It is useful for estimating buffer sizes required for certain computations.
4.2 Attributes for Elements of Monoids and Semigroups
This section documents new attributes and filters defined by the package for elements of monoids and semigroups.
4.2-1 IsElementOfFpMonoidOrSemigroup
> IsElementOfFpMonoidOrSemigroup ( u ) | ( filter ) |
The filter IsElementOfFpMonoidOrSemigroup
is true
if the argument u is an element of a finitely presented monoid or semigroup and false
otherwise. It is the disjunction of the standard GAP filters IsElementOfFpMonoid
and IsElementOfFpSemigroup
(see [GG, Chapter 51]).
4.2-2 IsElementOfC4, IsElementOfC3, IsElementOfC2, IsElementOfC1
> IsElementOfC4 ( u ) | ( filter ) |
> IsElementOfC3 ( u ) | ( filter ) |
> IsElementOfC2 ( u ) | ( filter ) |
> IsElementOfC1 ( u ) | ( filter ) |
The filters IsElementOfC4
, IsElementOfC3
, IsElementOfC2
, IsElementOfC1
indicate whether the defining presentation for the containing monoid or semigroup of u satisfies the small overlap conditions C(4), C(3), C(2) and C(1) respectively.
4.3 Functions
This section documents functions defined by the package.
4.3-1 PreferSmallOverlapEqualityTest
> PreferSmallOverlapEqualityTest ( [verbose] ) | ( function ) |
A call to the function to PreferSmallOverlapEqualityTest
installs new methods for the equality test operator for elements of finitely presented monoids and semigroups respectively, which check if the defining presentation satisfies C(4) and apply C4WordProblemReckless
(4.3-3) if applicable. This is not installed by default since checking the C(4) condition imposes a small overhead on equality tests in non-C(4) semigroups (see 5.2).
The optional argument verbose is a boolean value indicating whether the equality tester should write to the standard output each time it performs an equality test, to tell the user which equality test routine is being used; this can be useful in interactive mode but is clearly undesirable when the equality tester is being employed in a program. The default behaviour is to produce no such output (equivalent to the argument false
).
4.3-2 C4WordProblem
> C4WordProblem ( u, v ) | ( function ) |
C4WordProblem
decides very efficiently whether the arguments u and v represent the same element of a finitely presented semigroup or monoid with defining presentation satisfying the small overlap condition C(4). It returns true
if they do represent the same element, false
if they do not, and fail
if u and v are not elements of the same finitely presented semigroup or monoid, or if the defining presentation does not satisfy C(4).
4.3-3 C4WordProblemReckless
> C4WordProblemReckless ( S, u, v ) | ( function ) |
C4WordProblemReckless
tests whether the arguments u and v are equal as elements of the C(4) finitely presented monoid or semigroup S, returning true
if they are and false
if they are not. Unlike C4WordProblem
(4.3-2), no checks are performed on the arguments and if they do not have the correct properties the behaviour is undefined - it may crash, not terminate, return the wrong answer, cause your computer to explode or occasionally even return the right answer. This function is available because it has slightly lower constant function call overhead that C4WordProblem
(4.3-2), which may be significant when performing very large numbers of equality tests in the same semigroup or monoid. For all other purposes, and if in any doubt, use C4WordProblem
(4.3-2) instead.
4.3-4 ComplementRelationWord
> ComplementRelationWord ( n ) | ( function ) |
ComplementRelationWord
takes as its argument an integer n, and simply returns n-1 if n is even, and n+1 if n is odd. Hence, if n is an index into the list of relation words returned by RelationWords
(4.1-4), then the valued returned is the index in the list corresponding to the complement relation word.