Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Bib Ind

### 4 Partitioned binary relations (PBRs)

In this chapter we describe the functions in Semigroups for creating and manipulating partitioned binary relations, henceforth referred to by their acronym PBRs. We begin by describing what these objects are.

PBRs were introduced in the paper [MM11] as, roughly speaking, the maximum generalization of bipartitions and related objects. Although, mathematically, bipartitions are a special type of PBR, in Semigroups bipartitions and PBRs are currently distinct types of objects. It is possible to change the representation from bipartition to PBR, and from PBR to bipartition, when appropriate; see Section 4.3 for more details. The reason for this distinct is largely historical, bipartition appeared in the literature, and in the Semigroups package, before PBRs.

#### 4.1 The family and categories of PBRs

##### 4.1-1 IsPBR
 ‣ IsPBR( obj ) ( category )

Returns: true or false.

Every PBR in GAP belongs to the category IsPBR. Basic operations for PBRs are DegreeOfPBR (4.5-2), ExtRepOfObj (4.5-3), PBRNumber (4.5-4), NumberPBR (4.5-4), StarOp (4.5-1), and multiplication of two PBRs of equal degree is via *.

##### 4.1-2 IsPBRCollection
 ‣ IsPBRCollection( obj ) ( category )
 ‣ IsPBRCollColl( obj ) ( category )

Returns: true or false.

Every collection of PBRs belongs to the category IsPBRCollection. For example, PBR semigroups belong to IsPBRCollection.

Every collection of collections of PBRs belongs to IsPBRCollColl. For example, a list of PBR semigroups belongs to IsPBRCollColl.

#### 4.2 Creating PBRs

There are several ways of creating PBRs in GAP, which are described in this section.

##### 4.2-1 PBR
 ‣ PBR( left, right ) ( operation )

Returns: A PBR.

The arguments left and right of this function should each be a list of length n whose entries are lists of integers in the ranges [-n .. -1] and [1 .. n] for some n greater than 0.

Given such an argument, PBR returns the PBR x where:

• for each i in the range [1 .. n] there is an edge from i to every j in left[i];

• for each i in the range [-n .. -1] there is an edge from i to every j in right[-i];

PBR returns an error if the argument does not define a PBR.

gap> PBR([[-3, -2, -1, 2, 3], [-1], [-3, -2, 1, 2]],
>        [[-2, -1, 1, 2, 3], [3], [-3, -2, -1, 1, 3]]);
PBR([ [ -3, -2, -1, 2, 3 ], [ -1 ], [ -3, -2, 1, 2 ] ],
[ [ -2, -1, 1, 2, 3 ], [ 3 ], [ -3, -2, -1, 1, 3 ] ])

##### 4.2-2 RandomPBR
 ‣ RandomPBR( n[, p] ) ( operation )

Returns: A PBR.

If n is a positive integer and p is an float between 0 and 1, then RandomPBR returns a random PBR of degree n where the probability of there being an edge from i to j is approximately p.

If the optional second argument is not present, then a random value p is used (chosen with uniform probability).

gap> RandomPBR(6);
PBR(
[ [ -5, 1, 2, 3 ], [ -6, -3, -1, 2, 5 ], [ -5, -2, 2, 3, 5 ],
[ -6, -4, -1, 2, 3, 6 ], [ -4, -1, 2, 4 ],
[ -5, -3, -1, 1, 2, 3, 5 ] ],
[ [ -6, -4, -2, 1, 3, 5, 6 ], [ -5, -2, 1, 2, 3, 5 ],
[ -6, -5, -2, 1, 5 ], [ -6, -5, -3, -2, 1, 3, 4 ],
[ -6, -5, -4, -2, 3, 5 ], [ -6, -4, -2, -1, 1, 2, 6 ] ])

##### 4.2-3 EmptyPBR
 ‣ EmptyPBR( n ) ( operation )

Returns: A PBR.

If n is a positive integer, then EmptyPBR returns the PBR of degree n with no edges.

gap> x := EmptyPBR(3);
PBR([ [  ], [  ], [  ] ], [ [  ], [  ], [  ] ])
gap> IsEmptyPBR(x);
true

##### 4.2-4 IdentityPBR
 ‣ IdentityPBR( n ) ( operation )

Returns: A PBR.

If n is a positive integer, then IdentityPBR returns the identity PBR of degree n. This PBR has 2n edges: specifically, for each i in the ranges [1 .. n] and [-n .. -1], the identity PBR has an edge from i to -i.

gap> x := IdentityPBR(3);
PBR([ [ -1 ], [ -2 ], [ -3 ] ], [ [ 1 ], [ 2 ], [ 3 ] ])
gap> IsIdentityPBR(x);
true

##### 4.2-5 UniversalPBR
 ‣ UniversalPBR( n ) ( operation )

Returns: A PBR.

If n is a positive integer, then UniversalPBR returns the PBR of degree n with 4 * n ^ 2 edges, i.e. every possible edge.

gap> x := UniversalPBR(2);
PBR([ [ -2, -1, 1, 2 ], [ -2, -1, 1, 2 ] ],
[ [ -2, -1, 1, 2 ], [ -2, -1, 1, 2 ] ])
gap> IsUniversalPBR(x);
true

#### 4.3 Changing the representation of a PBR

It is possible that a PBR can be represented as another type of object, or that another type of GAP object can be represented as a PBR. In this section, we describe the functions in the Semigroups package for changing the representation of PBR, or for changing the representation of another type of object to that of a PBR.

The operations AsPermutation (4.3-4), AsPartialPerm (4.3-3), AsTransformation (4.3-2), AsBipartition (3.3-1), AsBooleanMat (5.3-2) can be used to convert PBRs into permutations, partial permutations, transformations, bipartitions, and boolean matrices where appropriate.

##### 4.3-1 AsPBR
 ‣ AsPBR( x[, n] ) ( operation )

Returns: A PBR.

AsPBR returns the boolean matrix, bipartition, transformation, partial permutation, or permutation x as a PBR of degree n.

There are several possible arguments for AsPBR:

bipartitions

If x is a bipartition and n is a positive integer, then AsPBR returns a PBR corresponding to x with degree n. The resulting PBR has an edge from i to j whenever i and j belong to the same block of x.

If the optional second argument n is not specified, then degree of the bipartition x is used by default.

boolean matrices

If x is a boolean matrix of even dimension 2 * m and n is a positive integer, then AsPBR returns a PBR corresponding to x with degree n. If the optional second argument n is not specified, then dimension of the boolean matrix x is used by default.

transformations, partial perms, permutations

If x is a transformation, partial perm, or permutation and n is a positive integer, then AsPBR is a synonym for AsPBR(AsBipartition(x, n)). If the optional second argument n is not specified, then AsPBR is a synonym for AsPBR(AsBipartition(x)). See AsBipartition (3.3-1) for more details.

gap> x := Bipartition([[1, 2, -1], [3, -2], [4, -3, -4]]);
<block bijection: [ 1, 2, -1 ], [ 3, -2 ], [ 4, -3, -4 ]>
gap> AsPBR(x, 2);
PBR([ [ -1, 1, 2 ], [ -1, 1, 2 ] ], [ [ -1, 1, 2 ], [ -2 ] ])
gap> AsPBR(x, 5);
PBR([ [ -1, 1, 2 ], [ -1, 1, 2 ], [ -2, 3 ], [ -4, -3, 4 ], [  ] ],
[ [ -1, 1, 2 ], [ -2, 3 ], [ -4, -3, 4 ], [ -4, -3, 4 ], [  ] ])
gap> AsPBR(x);
PBR([ [ -1, 1, 2 ], [ -1, 1, 2 ], [ -2, 3 ], [ -4, -3, 4 ] ],
[ [ -1, 1, 2 ], [ -2, 3 ], [ -4, -3, 4 ], [ -4, -3, 4 ] ])
gap> mat := Matrix(IsBooleanMat, [[1, 0, 0, 1],
>                                 [0, 1, 1, 0],
>                                 [1, 0, 1, 1],
>                                 [0, 0, 0, 1]]);;
gap> AsPBR(mat);
PBR([ [ -2, 1 ], [ -1, 2 ] ], [ [ -2, -1, 1 ], [ -2 ] ])
gap> AsPBR(mat, 2);
PBR([ [ 1 ] ], [ [ -1 ] ])
gap> AsPBR(mat, 6);
PBR([ [ -2, 1 ], [ -1, 2 ], [  ] ], [ [ -2, -1, 1 ], [ -2 ], [  ] ])
gap> x := Transformation([2, 2, 1]);;
gap> AsPBR(x);
PBR([ [ -2 ], [ -2 ], [ -1 ] ], [ [ 3 ], [ 1, 2 ], [  ] ])
gap> AsPBR(x, 2);
PBR([ [ -2 ], [ -2 ] ], [ [  ], [ 1, 2 ] ])
gap> AsPBR(x, 4);
PBR([ [ -2 ], [ -2 ], [ -1 ], [ -4 ] ],
[ [ 3 ], [ 1, 2 ], [  ], [ 4 ] ])
gap> x := PartialPerm([4, 3]);
[1,4][2,3]
gap> AsPBR(x);
PBR([ [ -4 ], [ -3 ], [  ], [  ] ], [ [  ], [  ], [ 2 ], [ 1 ] ])
gap> AsPBR(x, 2);
PBR([ [  ], [  ] ], [ [  ], [  ] ])
gap> AsPBR(x, 5);
PBR([ [ -4 ], [ -3 ], [  ], [  ], [  ] ],
[ [  ], [  ], [ 2 ], [ 1 ], [  ] ])
gap> x := (1, 3)(2, 4);
(1,3)(2,4)
gap> AsPBR(x);
PBR([ [ -3, 1 ], [ -4, 2 ], [ -1, 3 ], [ -2, 4 ] ],
[ [ -1, 3 ], [ -2, 4 ], [ -3, 1 ], [ -4, 2 ] ])
gap> AsPBR(x, 5);
PBR([ [ -3, 1 ], [ -4, 2 ], [ -1, 3 ], [ -2, 4 ], [ -5, 5 ] ],
[ [ -1, 3 ], [ -2, 4 ], [ -3, 1 ], [ -4, 2 ], [ -5, 5 ] ])

##### 4.3-2 AsTransformation
 ‣ AsTransformation( x ) ( attribute )

Returns: A transformation.

When the argument x is a PBR which satisfies IsTransformationPBR (4.5-9), then this attribute returns that transformation.

gap> x := PBR([[-3], [-3], [-2]], [[], [3], [1, 2]]);;
gap> IsTransformationPBR(x);
true
gap> AsTransformation(x);
Transformation( [ 3, 3, 2 ] )
gap> x := PBR([[1], [1, 2]], [[-2, -1], [-2, -1]]);;
gap> AsTransformation(x);
Error, Semigroups: AsTransformation: usage,
the argument <x> must be a transformation PBR,

##### 4.3-3 AsPartialPerm
 ‣ AsPartialPerm( x ) ( operation )

Returns: A partial perm.

When the argument x is a PBR which satisfies IsPartialPermPBR (4.5-11), then this function returns that partial perm.

gap> x := PBR([[-1, 1], [-3, 2], [-4, 3], [4], [5]],
>             [[-1, 1], [-2], [-3, 2], [-4, 3], [-5]]);;
gap> IsPartialPermPBR(x);
true
gap> AsPartialPerm(x);
[2,3,4](1)

##### 4.3-4 AsPermutation
 ‣ AsPermutation( x ) ( attribute )

Returns: A permutation.

When the argument x is a PBR which satisfies IsPermPBR (4.5-12), then this attribute returns that permutation.

gap> x := PBR([[-1, 1], [-4, 2], [-2, 3], [-3, 4]],
>             [[-1, 1], [-2, 3], [-3, 4], [-4, 2]]);;
gap> IsPermPBR(x);
true
gap> AsPermutation(x);
(2,4,3)

#### 4.4 Operators for PBRs

x * y

returns the product of x and y when x and y are PBRs.

x < y

returns true if the degree of x is less than the degree of y, or the degrees are equal and the out-neighbours of x (as a list of list of positive integers) is lexicographically less than the out-neighbours of y.

x = y

returns true if the PBR x equals the PBR y and returns false if it does not.

#### 4.5 Attributes for PBRs

In this section we describe various attributes that a PBR can possess.

##### 4.5-1 StarOp
 ‣ StarOp( x ) ( operation )
 ‣ Star( x ) ( attribute )

Returns: A PBR.

StarOp returns the unique PBR y obtained by exchanging the positive and negative numbers in x (i.e. multiplying ExtRepOfObj (4.5-3) by -1 and swapping its first and second components).

gap> x := PBR([[], [-1], []], [[-3, -2, 2, 3], [-2, 1], []]);;
gap> Star(x);
PBR([ [ -3, -2, 2, 3 ], [ -1, 2 ], [  ] ], [ [  ], [ 1 ], [  ] ])

##### 4.5-2 DegreeOfPBR
 ‣ DegreeOfPBR( x ) ( attribute )
 ‣ DegreeOfPBRCollection( x ) ( attribute )

Returns: A positive integer.

The degree of a PBR is, roughly speaking, the number of points where it is defined. More precisely, if x is a PBR defined on 2 * n points, then the degree of x is n.

The degree of a collection coll of PBRs of equal degree is just the degree of any (and every) PBR in coll. The degree of collection of PBRs of unequal degrees is not defined.

gap> x := PBR([[-2], [-2, -1, 2, 3], [-1, 1, 2, 3]],
>             [[-1, 1], [2, 3], [-3, 2, 3]]);
PBR([ [ -2 ], [ -2, -1, 2, 3 ], [ -1, 1, 2, 3 ] ],
[ [ -1, 1 ], [ 2, 3 ], [ -3, 2, 3 ] ])
gap> DegreeOfPBR(x);
3
gap> S := FullPBRMonoid(2);
<pbr monoid of degree 2 with 10 generators>
gap> DegreeOfPBRCollection(S);
2

##### 4.5-3 ExtRepOfObj
 ‣ ExtRepOfObj( x ) ( operation )

Returns: A pair of lists of lists of integers.

If n is the degree of the PBR x, then ExtRepOfObj returns the argument required by PBR (4.2-1) to create a PBR equal to x, i.e. PBR(ExtRepOfObj(x)) returns a PBR equal to x.

gap> x := PBR([[-1, 1], [-2, 2]],
>             [[-2, -1, 1], [-1, 1, 2]]);
PBR([ [ -1, 1 ], [ -2, 2 ] ], [ [ -2, -1, 1 ], [ -1, 1, 2 ] ])
gap> ExtRepOfObj(x);
[ [ [ -1, 1 ], [ -2, 2 ] ], [ [ -2, -1, 1 ], [ -1, 1, 2 ] ] ]

##### 4.5-4 PBRNumber
 ‣ PBRNumber( m, n ) ( operation )
 ‣ NumberPBR( mat ) ( operation )

Returns: A PBR, or a positive integer.

These functions implement a bijection from the set of all PBRs of degree n and the numbers [1 .. 2 ^ (4 * n ^ 2)].

More precisely, if m and n are positive integers such that m is at most 2 ^ (4 * n ^ 2), then PBRNumber returns the mth PBR of degree n.

If mat is a PBR of degree n, then NumberPBR returns the number in [1 .. 2 ^ (4 * n ^ 2)] that corresponds to mat.

gap> S := FullPBRMonoid(1);
<pbr monoid of degree 1 with 4 generators>
gap> List(S, NumberPBR);
[ 3, 15, 5, 7, 8, 1, 4, 11, 13, 16, 6, 2, 9, 12, 14, 10 ]

##### 4.5-5 IsEmptyPBR
 ‣ IsEmptyPBR( x ) ( property )

Returns: true or false.

A PBR is if it has no edges. IsEmptyPBR returns true if the PBR x is empty and false if it is not.

gap> x := PBR([[]], [[]]);;
gap> IsEmptyPBR(x);
true
gap> x := PBR([[-2, 1], [2]], [[-1], [-2, 1]]);
PBR([ [ -2, 1 ], [ 2 ] ], [ [ -1 ], [ -2, 1 ] ])
gap> IsEmptyPBR(x);
false

##### 4.5-6 IsIdentityPBR
 ‣ IsIdentityPBR( x ) ( property )

Returns: true or false.

A PBR of degree n is the PBR of degree n if it is the identity of the full PBR monoid of degree n. The identity PBR of degree n has 2n edges. Specifically, for each i in the ranges [1 .. n] and [-n .. -1], the identity PBR has an edge from i to -i.

IsIdentityPBR returns true is the PBR x is an identity PBR and false if it is not.

gap> x := PBR([[-2], [-1]], [[1], [2]]);
PBR([ [ -2 ], [ -1 ] ], [ [ 1 ], [ 2 ] ])
gap> IsIdentityPBR(x);
false
gap> x := PBR([[-1]], [[1]]);
PBR([ [ -1 ] ], [ [ 1 ] ])
gap> IsIdentityPBR(x);
true

##### 4.5-7 IsUniversalPBR
 ‣ IsUniversalPBR( x ) ( property )

Returns: true or false.

A PBR of degree n is if it has 4 * n ^ 2 edges, i.e. every possible edge.

gap> x := PBR([[]], [[]]);
PBR([ [  ] ], [ [  ] ])
gap> IsUniversalPBR(x);
false
gap> x := PBR([[-2, 1], [2]], [[-1], [-2, 1]]);
PBR([ [ -2, 1 ], [ 2 ] ], [ [ -1 ], [ -2, 1 ] ])
gap> IsUniversalPBR(x);
false
gap> x := PBR([[-1, 1]], [[-1, 1]]);
PBR([ [ -1, 1 ] ], [ [ -1, 1 ] ])
gap> IsUniversalPBR(x);
true

##### 4.5-8 IsBipartitionPBR
 ‣ IsBipartitionPBR( x ) ( property )
 ‣ IsBlockBijectionPBR( x ) ( property )

Returns: true or false.

If the PBR x defines a bipartition, then IsBipartitionPBR returns true, and if not, then it returns false.

A PBR x defines a bipartition if and only if when considered as a boolean matrix it is an equivalence.

If x satisfies IsBipartitionPBR and when considered as a bipartition it is a block bijection, then IsBlockBijectionPBR returns true.

gap> x := PBR([[-1, 3], [-1, 3], [-2, 1, 2, 3]],
>             [[-2, -1, 2], [-2, -1, 1, 2, 3],
>              [-2, -1, 1, 2]]);
PBR([ [ -1, 3 ], [ -1, 3 ], [ -2, 1, 2, 3 ] ],
[ [ -2, -1, 2 ], [ -2, -1, 1, 2, 3 ], [ -2, -1, 1, 2 ] ])
gap> IsBipartitionPBR(x);
false
gap> x := PBR([[-2, -1, 1], [2, 3], [2, 3]],
>             [[-2, -1, 1], [-2, -1, 1], [-3]]);
PBR([ [ -2, -1, 1 ], [ 2, 3 ], [ 2, 3 ] ],
[ [ -2, -1, 1 ], [ -2, -1, 1 ], [ -3 ] ])
gap> IsBipartitionPBR(x);
true
gap> IsBlockBijectionPBR(x);
false

##### 4.5-9 IsTransformationPBR
 ‣ IsTransformationPBR( x ) ( property )

Returns: true or false.

If the PBR x defines a transformation, then IsTransformationPBR returns true, and if not, then false is returned.

A PBR x defines a transformation if and only if it satisfies IsBipartitionPBR (4.5-8) and when it is considered as a bipartition it satisfies IsTransBipartition (3.5-12).

With this definition, AsPBR (4.3-1) and AsTransformation (4.3-2) define mutually inverse isomorphisms from the full transformation monoid of degree n to the submonoid of the full PBR monoid of degree n consisting of all the elements satisfying IsTransformationPBR.

gap> x := PBR([[-3], [-1], [-3]], [[2], [], [1, 3]]);
PBR([ [ -3 ], [ -1 ], [ -3 ] ], [ [ 2 ], [  ], [ 1, 3 ] ])
gap> IsTransformationPBR(x);
true
gap> x := AsTransformation(x);
Transformation( [ 3, 1, 3 ] )
gap> AsPBR(x) * AsPBR(x) = AsPBR(x ^ 2);
true
gap> Number(FullPBRMonoid(1), IsTransformationPBR);
1
gap> x := PBR([[-2, -1, 2], [-2, 1, 2]], [[-1, 1], [-2]]);
PBR([ [ -2, -1, 2 ], [ -2, 1, 2 ] ], [ [ -1, 1 ], [ -2 ] ])
gap> IsTransformationPBR(x);
false

##### 4.5-10 IsDualTransformationPBR
 ‣ IsDualTransformationPBR( x ) ( property )

Returns: true or false.

If the PBR x defines a dual transformation, then IsDualTransformationPBR returns true, and if not, then false is returned.

A PBR x defines a dual transformation if and only if Star(x) satisfies IsTransformationPBR (4.5-9).

gap> x := PBR([[-3, 1, 3], [-1, 2], [-3, 1, 3]],
>             [[-1, 2], [-2], [-3, 1, 3]]);
PBR([ [ -3, 1, 3 ], [ -1, 2 ], [ -3, 1, 3 ] ],
[ [ -1, 2 ], [ -2 ], [ -3, 1, 3 ] ])
gap> IsDualTransformationPBR(x);
false
gap> IsDualTransformationPBR(Star(x));
true
gap> Number(FullPBRMonoid(1), IsDualTransformationPBR);
1

##### 4.5-11 IsPartialPermPBR
 ‣ IsPartialPermPBR( x ) ( property )

Returns: true or false.

If the PBR x defines a partial permutation, then IsPartialPermPBR returns true, and if not, then false is returned.

A PBR x defines a partial perm if and only if it satisfies IsBipartitionPBR (4.5-8) and and when it is considered as a bipartition it satisfies IsPartialPermBipartition (3.5-15).

With this definition, AsPBR (4.3-1) and AsPartialPerm (4.3-3) define mutually inverse isomorphisms from the symmetric inverse monoid of degree n to the submonoid of the full PBR monoid of degree n consisting of all the elements satisfying IsPartialPermPBR.

gap> x := PBR([[-1, 1], [2]], [[-1, 1], [-2]]);
PBR([ [ -1, 1 ], [ 2 ] ], [ [ -1, 1 ], [ -2 ] ])
gap> IsPartialPermPBR(x);
true
gap> x := PartialPerm([3, 1]);
[2,1,3]
gap> AsPBR(x) * AsPBR(x) = AsPBR(x ^ 2);
true
gap> Number(FullPBRMonoid(1), IsPartialPermPBR);
2

##### 4.5-12 IsPermPBR
 ‣ IsPermPBR( x ) ( property )

Returns: true or false.

If the PBR x defines a permutation, then IsPermPBR returns true, and if not, then false is returned.

A PBR x defines a permutation if and only if it satisfies IsBipartitionPBR (4.5-8) and and when it is considered as a bipartition it satisfies IsPermBipartition (3.5-14).

With this definition, AsPBR (4.3-1) and AsPermutation (4.3-4) define mutually inverse isomorphisms from the symmetric group of degree n to the subgroup of the full PBR monoid of degree n consisting of all the elements satisfying IsPermPBR (i.e. the GroupOfUnits (13.8-1) of the full PBR monoid of degree n).

gap> x := PBR([[-2, 1], [-4, 2], [-1, 3], [-3, 4]],
> [[-1, 3], [-2, 1], [-3, 4], [-4, 2]]);;
gap> IsPermPBR(x);
true
gap> x := (1, 5)(2, 4, 3);
(1,5)(2,4,3)
gap> y := (1, 4, 3)(2, 5);
(1,4,3)(2,5)
gap> AsPBR(x) * AsPBR(y) = AsPBR(x * y);
true
gap> Number(FullPBRMonoid(1), IsPermPBR);
1

#### 4.6 Semigroups of PBRs

Semigroups and monoids of PBRs can be created in the usual way in GAP using the functions Semigroup (Reference: Semigroup) and Monoid (Reference: Monoid); see Chapter 6 for more details.

It is possible to create inverse semigroups and monoids of PBRs using InverseSemigroup (Reference: InverseSemigroup) and InverseMonoid (Reference: InverseMonoid) when the argument is a collection of PBRs satisfying IsBipartitionPBR (4.5-8) and when considered as bipartitions, the collection satisfies IsGeneratorsOfInverseSemigroup.

Note that every PBR semigroup in Semigroups is finite.

##### 4.6-1 IsPBRSemigroup
 ‣ IsPBRSemigroup( S ) ( filter )
 ‣ IsPBRMonoid( S ) ( filter )

Returns: true or false.

A PBR semigroup is simply a semigroup consisting of PBRs. An object obj is a PBR semigroup in GAP if it satisfies IsSemigroup (Reference: IsSemigroup) and IsPBRCollection (4.1-2).

A PBR monoid is a monoid consisting of PBRs. An object obj is a PBR monoid in GAP if it satisfies IsMonoid (Reference: IsMonoid) and IsPBRCollection (4.1-2).

Note that it is possible for a PBR semigroup to have a multiplicative neutral element (i.e. an identity element) but not to satisfy IsPBRMonoid. For example,

gap> x := PBR([[-2, -1, 3], [-2, 2], [-3, -2, 1, 2, 3]],
>             [[-3, -2, -1, 2, 3], [-3, -2, -1, 2, 3], [-1]]);;
gap> S := Semigroup(x, One(x));
<commutative pbr monoid of degree 3 with 1 generator>
gap> IsMonoid(S);
true
gap> IsPBRMonoid(S);
true
gap> S := Semigroup([
>  PBR([[-2, 1], [-3, 2], [-1, 3], [-4, 4, 5], [-4, 4, 5]],
>      [[-1, 3], [-2, 1], [-3, 2], [-4, 4, 5], [-5]]),
>  PBR([[-2, 1], [-1, 2], [-3, 3], [-4, 4, 5], [-4, 4, 5]],
>      [[-1, 2], [-2, 1], [-3, 3], [-4, 4, 5], [-5]]),
>  PBR([[-1, 1, 3], [-2, 2], [-1, 1, 3], [-4, 4, 5], [-4, 4, 5]],
>      [[-1, 1, 3], [-2, 2], [-3], [-4, 4, 5], [-5]])]);
<pbr semigroup of degree 5 with 3 generators>
gap> One(S);
fail
gap> MultiplicativeNeutralElement(S);
PBR([ [ -1, 1 ], [ -2, 2 ], [ -3, 3 ], [ -4, 4, 5 ], [ -4, 4, 5 ] ],
[ [ -1, 1 ], [ -2, 2 ], [ -3, 3 ], [ -4, 4, 5 ], [ -5 ] ])
gap> IsPBRMonoid(S);
false

In this example S cannot be converted into a monoid using AsMonoid (Reference: AsMonoid) since the One (Reference: One) of any element in S differs from the multiplicative neutral element.

For more details see IsMagmaWithOne (Reference: IsMagmaWithOne).

##### 4.6-2 DegreeOfPBRSemigroup
 ‣ DegreeOfPBRSemigroup( S ) ( attribute )

Returns: A non-negative integer.

The degree of a PBR semigroup S is just the degree of any (and every) element of S.

gap> S := Semigroup(
>  PBR([[-1, 1], [-2, 2], [-3, 3]],
>      [[-1, 1], [-2, 2], [-3, 3]]),
>  PBR([[1, 2], [1, 2], [-3, 3]],
>      [[-2, -1], [-2, -1], [-3, 3]]),
>  PBR([[-1, 1], [2, 3], [2, 3]],
>      [[-1, 1], [-3, -2], [-3, -2]]));
<pbr semigroup of degree 3 with 3 generators>
gap> DegreeOfPBRSemigroup(S);
3
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Bib Ind

generated by GAPDoc2HTML