Goto Chapter: Top 1 2 3 4 5 Bib Ind
 Top of Book   Previous Chapter   Next Chapter 

4 Reference
 4.1 Attributes for Monoids and Semigroups
  4.1-1 IsFpMonoidOrSemigroup

  4.1-2 SmallOverlapClass

  4.1-3 IsC4, IsC3, IsC2, IsC1

  4.1-4 RelationWords

  4.1-5 RelationWordLengths

  4.1-6 MaxPiecePrefixLengths, MiddleWordLengths, MaxPieceSuffixLengths

  4.1-7 MaxPieceSuffixLengthBound
 4.2 Attributes for Elements of Monoids and Semigroups
  4.2-1 IsElementOfFpMonoidOrSemigroup

  4.2-2 IsElementOfC4, IsElementOfC3, IsElementOfC2, IsElementOfC1
 4.3 Functions
  4.3-1 PreferSmallOverlapEqualityTest

  4.3-2 C4WordProblem

  4.3-3 C4WordProblemReckless

  4.3-4 ComplementRelationWord

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
> IsC4( S )( filter )
> IsC3( S )( filter )
> IsC2( S )( filter )
> IsC1( S )( filter )

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.

 Top of Book   Previous Chapter   Next Chapter 
Goto Chapter: Top 1 2 3 4 5 Bib Ind

generated by GAPDoc2HTML