<p>In this chapter we describe the functions in <strong class="pkg">Semigroups</strong> for creating and manipulating partitioned binary relations, henceforth referred to by their acronym PBRs. We begin by describing what these objects are.</p>
<p>PBRs were introduced in the paper <a href="chapBib.html#biBMartin2011aa">[MM13]</a> as, roughly speaking, the maximum generalization of bipartitions and related objects. Although, mathematically, bipartitions are a special type of PBR, in <strong class="pkg">Semigroups</strong> 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 <a href="chap4.html#X86B714987C01895F"><span class="RefLink">4.3</span></a> for more details. The reason for this distinct is largely historical, bipartition appeared in the literature, and in the <strong class="pkg">Semigroups</strong> package, before PBRs.</p>
<p>Every PBR in <strong class="pkg">GAP</strong> belongs to the category <code class="code">IsPBR</code>. Basic operations for PBRs are <code class="func">DegreeOfPBR</code> (<a href="chap4.html#X785B576B7823D626"><span class="RefLink">4.5-2</span></a>), <code class="func">ExtRepOfObj</code> (<a href="chap4.html#X78302D7E81BB1E54"><span class="RefLink">4.5-3</span></a>), <code class="func">PBRNumber</code> (<a href="chap4.html#X7F4C8A2B79E6D963"><span class="RefLink">4.5-4</span></a>), <code class="func">NumberPBR</code> (<a href="chap4.html#X7F4C8A2B79E6D963"><spanclass="RefLink">4.5-4</span></a>), <code class="func">StarOp</code> (<a href="chap4.html#X7DFC277E80A50C2F"><span class="RefLink">4.5-1</span></a>), and multiplication of two PBRs of equal degree is via <code class="keyw">*</code>.</p>
<p>Every collection of PBRs belongs to the category <code class="code">IsPBRCollection</code>. For example, PBR semigroups belong to <code class="code">IsPBRCollection</code>.</p>
<p>Every collection of collections of PBRs belongs to <code class="code">IsPBRCollColl</code>. For example, a list of PBR semigroups belongs to <code class="code">IsPBRCollColl</code>.</p>
<p>The arguments <var class="Arg">left</var> and <var class="Arg">right</var> of this function should each be a list of length <code class="code">n</code> whose entries are lists of integers in the ranges <code class="code">[-n .. -1]</code> and <code class="code">[1 .. n]</code> for some <code class="code">n</code> greater than 0.</p>
<p>Given such an argument, <code class="code">PBR</code> returns the PBR <code class="code">x</code> where:</p>
<ul>
<li><p>for each <code class="code">i</code> in the range <code class="code">[1 .. n]</code> there is an edge from <code class="code">i</code> to every <code class="code">j</code> in <var class="Arg">left[i]</var>;</p>
</li>
<li><p>for each <code class="code">i</code> in the range <code class="code">[-n .. -1]</code> there is an edge from <code class="code">i</code> to every <code class="code">j</code> in <var class="Arg">right[-i]</var>;</p>
</li>
</ul>
<p><code class="code">PBR</code> returns an error if the argument does not define a PBR.</p>
<p>If <var class="Arg">n</var> is a positive integer and <var class="Arg">p</var> is an float between <code class="code">0</code> and <code class="code">1</code>, then <code class="code">RandomPBR</code> returns a random PBR of degree <var class="Arg">n</var> where the probability of there being an edge from <code class="code">i</code> to <code class="code">j</code> is approximately <code class="code">p</code>.</p>
<p>If the optional second argument is not present, then a random value <var class="Arg">p</var> is used (chosen with uniform probability).</p>
<p>If <var class="Arg">n</var> is a positive integer, then <code class="code">EmptyPBR</code> returns the PBR of degree <var class="Arg">n</var> with no edges.</p>
<p>If <var class="Arg">n</var> is a positive integer, then <code class="code">IdentityPBR</code> returns the identity PBR of degree <var class="Arg">n</var>. This PBR has <code class="code">2</code><varclass="Arg">n</var> edges: specifically, for each <code class="code">i</code> in the ranges <code class="code">[1 .. n]</code> and <code class="code">[-n .. -1]</code>, the identity PBR has an edge from <code class="code">i</code> to <code class="code">-i</code>.</p>
<p>If <var class="Arg">n</var> is a positive integer, then <code class="code">UniversalPBR</code> returns the PBR of degree <var class="Arg">n</var> with <code class="code">4 * n ^ 2</code> edges, i.e. every possible edge.</p>
<h4>4.3 <span class="Heading">Changing the representation of a PBR</span></h4>
<p>It is possible that a PBR can be represented as another type of object, or that another type of <strong class="pkg">GAP</strong> object can be represented as a PBR. In this section, we describe the functions in the <strong class="pkg">Semigroups</strong> package for changing the representation of PBR, or for changing the representation of another type of object to that of a PBR.</p>
<p>The operations <code class="func">AsPermutation</code> (<a href="chap4.html#X86786B297FBCD064"><span class="RefLink">4.3-4</span></a>), <code class="func">AsPartialPerm</code> (<a href="chap4.html#X795B1C16819905E8"><span class="RefLink">4.3-3</span></a>), <code class="func">AsTransformation</code> (<a href="chap4.html#X8407F516825A514A"><span class="RefLink">4.3-2</span></a>), <code class="func">AsBipartition</code> (<a href="chap3.html#X855126D98583C181"><spanclass="RefLink">3.3-1</span></a>), <code class="func">AsBooleanMat</code> (<a href="chap5.html#X7DA524567E0E7E16"><span class="RefLink">5.3-2</span></a>) can be used to convert PBRs into permutations, partial permutations, transformations, bipartitions, and boolean matrices where appropriate.</p>
<p><code class="code">AsPBR</code> returns the boolean matrix, bipartition, transformation, partial permutation, or permutation <var class="Arg">x</var> as a PBR of degree <var class="Arg">n</var>.</p>
<p>There are several possible arguments for <code class="code">AsPBR</code>:</p>
<dl>
<dt><strong class="Mark">bipartitions</strong></dt>
<dd><p>If <var class="Arg">x</var> is a bipartition and <var class="Arg">n</var> is a positive integer, then <code class="code">AsPBR</code> returns a PBR corresponding to <var class="Arg">x</var> with degree <var class="Arg">n</var>. The resulting PBR has an edge from <code class="code">i</code> to <code class="code">j</code> whenever <code class="code">i</code> and <code class="code">j</code> belong to the same block of <var class="Arg">x</var>.</p>
<p>If the optional second argument <var class="Arg">n</var> is not specified, then degree of the bipartition <var class="Arg">x</var> is used by default.</p>
</dd>
<dt><strong class="Mark">boolean matrices</strong></dt>
<dd><p>If <var class="Arg">x</var> is a boolean matrix of even dimension <code class="code">2 * m</code> and <var class="Arg">n</var> is a positive integer, then <code class="code">AsPBR</code> returns a PBR corresponding to <var class="Arg">x</var> with degree <var class="Arg">n</var>. If the optional second argument <var class="Arg">n</var> is not specified, then dimension of the boolean matrix <var class="Arg">x</var> is used by default.</p>
</dd>
<dt><strong class="Mark">transformations, partial perms, permutations</strong></dt>
<dd><p>If <var class="Arg">x</var> is a transformation, partial perm, or permutation and <var class="Arg">n</var> is a positive integer, then <code class="code">AsPBR</code> is a synonym for <code class="code">AsPBR(AsBipartition(<var class="Arg">x</var>, <var class="Arg">n</var>))</code>. If the optional second argument <var class="Arg">n</var> is not specified, then <code class="code">AsPBR</code> is a synonym for <code class="code">AsPBR(AsBipartition(<var class="Arg">x</var>))</code>. See <code class="func">AsBipartition</code> (<a href="chap3.html#X855126D98583C181"><span class="RefLink">3.3-1</span></a>) for more details.</p>
<p>When the argument <var class="Arg">x</var> is a PBR which satisfies <code class="func">IsTransformationPBR</code> (<a href="chap4.html#X7AF425D17BBE9023"><span class="RefLink">4.5-9</span></a>), then this attribute returns that transformation.</p>
<p>When the argument <var class="Arg">x</var> is a PBR which satisfies <code class="func">IsPartialPermPBR</code> (<a href="chap4.html#X7883CD5D824CC236"><span class="RefLink">4.5-11</span></a>), then this function returns that partial perm.</p>
<p>When the argument <var class="Arg">x</var> is a PBR which satisfies <code class="func">IsPermPBR</code> (<a href="chap4.html#X85B21BB0835FE166"><span class="RefLink">4.5-12</span></a>), then this attribute returns that permutation.</p>
<h4>4.4 <span class="Heading">Operators for PBRs</span></h4>
<dl>
<dt><strong class="Mark"><code class="code"><var class="Arg">x</var> * <var class="Arg">y</var></code></strong></dt>
<dd><p>returns the product of <var class="Arg">x</var> and <var class="Arg">y</var> when <var class="Arg">x</var> and <var class="Arg">y</var> are PBRs.</p>
</dd>
<dt><strong class="Mark"><code class="code"><var class="Arg">x</var> < <var class="Arg">y</var></code></strong></dt>
<dd><p>returns <code class="keyw">true</code> if the degree of <var class="Arg">x</var> is less than the degree of <var class="Arg">y</var>, or the degrees are equal and the out-neighbours of <var class="Arg">x</var> (as a list of list of positive integers) is lexicographically less than the out-neighbours of <var class="Arg">y</var>.</p>
</dd>
<dt><strong class="Mark"><code class="code"><var class="Arg">x</var> = <var class="Arg">y</var></code></strong></dt>
<dd><p>returns <code class="keyw">true</code> if the PBR <var class="Arg">x</var> equals the PBR <var class="Arg">y</var> and returns <code class="keyw">false</code> if it does not.</p>
<p><code class="code">StarOp</code> returns the unique PBR <code class="code">y</code> obtained by exchanging the positive and negative numbers in <var class="Arg">x</var> (i.e. multiplying <code class="func">ExtRepOfObj</code> (<a href="chap4.html#X78302D7E81BB1E54"><span class="RefLink">4.5-3</span></a>) by <code class="code">-1</code> and swapping its first and second components).</p>
<p>The degree of a PBR is, roughly speaking, the number of points where it is defined. More precisely, if <var class="Arg">x</var> is a PBR defined on <code class="code">2 * n</code> points, then the degree of <var class="Arg">x</var> is <code class="code">n</code>.</p>
<p>The degree of a collection <var class="Arg">coll</var> of PBRs of equal degree is just the degree of any (and every) PBR in <var class="Arg">coll</var>. The degree of collection of PBRs of unequal degrees is not defined.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ExtRepOfObj</code>( <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A pair of lists of lists of integers.</p>
<p>If <code class="code">n</code> is the degree of the PBR <var class="Arg">x</var>, then <code class="code">ExtRepOfObj</code> returns the argument required by <code class="func">PBR</code> (<a href="chap4.html#X82A8646F7C70CF3B"><span class="RefLink">4.2-1</span></a>) to create a PBR equal to <var class="Arg">x</var>, i.e. <code class="code">PBR(ExtRepOfObj(<var class="Arg">x</var>))</code> returns a PBR equal to <var class="Arg">x</var>.</p>
<p>These functions implement a bijection from the set of all PBRs of degree <var class="Arg">n</var> and the numbers <code class="code">[1 .. 2 ^ (4 * <var class="Arg">n</var> ^ 2)]</code>.</p>
<p>More precisely, if <var class="Arg">m</var> and <var class="Arg">n</var> are positive integers such that <var class="Arg">m</var> is at most <code class="code">2 ^ (4 * <var class="Arg">n</var> ^ 2)</code>, then <code class="code">PBRNumber</code> returns the <var class="Arg">m</var>th PBR of degree <var class="Arg">n</var>.</p>
<p>If <var class="Arg">mat</var> is a PBR of degree <var class="Arg">n</var>, then <code class="code">NumberPBR</code> returns the number in <code class="code">[1 .. 2 ^ (4 * <var class="Arg">n</var> ^ 2)]</code> that corresponds to <var class="Arg">mat</var>.</p>
<p>A PBR is <strong class="button">empty</strong> if it has no edges. <code class="code">IsEmptyPBR</code> returns <code class="keyw">true</code> if the PBR <var class="Arg">x</var> is empty and <code class="keyw">false</code> if it is not.</p>
<p>A PBR of degree <code class="code">n</code> is the <strong class="button">identity</strong> PBR of degree <code class="code">n</code> if it is the identity of the full PBR monoid of degree <code class="code">n</code>. The identity PBR of degree <code class="code">n</code> has <code class="code">2n</code> edges. Specifically, for each <code class="code">i</code> in the ranges <code class="code">[1 .. n]</code> and <code class="code">[-n .. -1]</code>, the identity PBR has an edge from <code class="code">i</code> to <code class="code">-i</code>.</p>
<p><code class="code">IsIdentityPBR</code> returns <code class="keyw">true</code> is the PBR <var class="Arg">x</var> is an identity PBR and <code class="keyw">false</code> if it is not.</p>
<p>A PBR of degree <code class="code">n</code> is <strong class="button">universal</strong> if it has <code class="code">4 * n ^ 2</code> edges, i.e. every possible edge.</p>
<p>If the PBR <var class="Arg">x</var> defines a bipartition, then <code class="code">IsBipartitionPBR</code> returns <code class="keyw">true</code>, and if not, then it returns <code class="keyw">false</code>.</p>
<p>A PBR <var class="Arg">x</var> defines a bipartition if and only if when considered as a boolean matrix it is an equivalence.</p>
<p>If <var class="Arg">x</var> satisfies <code class="code">IsBipartitionPBR</code> and when considered as a bipartition it is a block bijection, then <code class="code">IsBlockBijectionPBR</code> returns <code class="keyw">true</code>.</p>
<p>If the PBR <var class="Arg">x</var> defines a transformation, then <code class="code">IsTransformationPBR</code> returns <code class="keyw">true</code>, and if not, then <code class="keyw">false</code> is returned.</p>
<p>A PBR <var class="Arg">x</var> defines a transformation if and only if it satisfies <code class="func">IsBipartitionPBR</code> (<a href="chap4.html#X81EC86397E098BC8"><span class="RefLink">4.5-8</span></a>) and when it is considered as a bipartition it satisfies <code class="func">IsTransBipartition</code> (<a href="chap3.html#X79C556827A578509"><span class="RefLink">3.5-12</span></a>).</p>
<p>With this definition, <code class="func">AsPBR</code> (<a href="chap4.html#X81CBBE6080439596"><span class="RefLink">4.3-1</span></a>) and <code class="func">AsTransformation</code> (<a href="chap4.html#X8407F516825A514A"><span class="RefLink">4.3-2</span></a>) define mutually inverse isomorphisms from the full transformation monoid of degree <code class="code">n</code> to the submonoid of the full PBR monoid of degree <code class="code">n</code> consisting of all the elements satisfying <code class="code">IsTransformationPBR</code>.</p>
<p>If the PBR <var class="Arg">x</var> defines a dual transformation, then <code class="code">IsDualTransformationPBR</code> returns <code class="keyw">true</code>, and if not, then <code class="keyw">false</code> is returned.</p>
<p>A PBR <var class="Arg">x</var> defines a dual transformation if and only if <code class="code">Star(<var class="Arg">x</var>)</code> satisfies <code class="func">IsTransformationPBR</code> (<a href="chap4.html#X7AF425D17BBE9023"><span class="RefLink">4.5-9</span></a>).</p>
<p>If the PBR <var class="Arg">x</var> defines a partial permutation, then <code class="code">IsPartialPermPBR</code> returns <code class="keyw">true</code>, and if not, then <code class="keyw">false</code> is returned.</p>
<p>A PBR <var class="Arg">x</var> defines a partial perm if and only if it satisfies <code class="func">IsBipartitionPBR</code> (<a href="chap4.html#X81EC86397E098BC8"><span class="RefLink">4.5-8</span></a>) and and when it is considered as a bipartition it satisfies <code class="func">IsPartialPermBipartition</code> (<a href="chap3.html#X87C771D37B1FE95C"><span class="RefLink">3.5-15</span></a>).</p>
<p>With this definition, <code class="func">AsPBR</code> (<a href="chap4.html#X81CBBE6080439596"><span class="RefLink">4.3-1</span></a>) and <code class="func">AsPartialPerm</code> (<a href="chap4.html#X795B1C16819905E8"><span class="RefLink">4.3-3</span></a>) define mutually inverse isomorphisms from the symmetric inverse monoid of degree <code class="code">n</code> to the submonoid of the full PBR monoid of degree <code class="code">n</code> consisting of all the elements satisfying <code class="code">IsPartialPermPBR</code>.</p>
<p>If the PBR <var class="Arg">x</var> defines a permutation, then <code class="code">IsPermPBR</code> returns <code class="keyw">true</code>, and if not, then <code class="keyw">false</code> is returned.</p>
<p>A PBR <var class="Arg">x</var> defines a permutation if and only if it satisfies <code class="func">IsBipartitionPBR</code> (<a href="chap4.html#X81EC86397E098BC8"><span class="RefLink">4.5-8</span></a>) and and when it is considered as a bipartition it satisfies <code class="func">IsPermBipartition</code> (<a href="chap3.html#X8031B53E7D0ECCFA"><span class="RefLink">3.5-14</span></a>).</p>
<p>With this definition, <code class="func">AsPBR</code> (<a href="chap4.html#X81CBBE6080439596"><span class="RefLink">4.3-1</span></a>) and <code class="func">AsPermutation</code> (<a href="chap4.html#X86786B297FBCD064"><span class="RefLink">4.3-4</span></a>) define mutually inverse isomorphisms from the symmetric group of degree <code class="code">n</code> to the subgroup of the full PBR monoid of degree <code class="code">n</code> consisting of all the elements satisfying <code class="code">IsPermPBR</code> (i.e. the <code class="func">GroupOfUnits</code> (<a href="chap11.html#X811AEDD88280C277"><span class="RefLink">11.9-1</span></a>) of the full PBR monoid of degree <code class="code">n</code>).</p>
<h4>4.6 <span class="Heading">
Semigroups of PBRs
</span></h4>
<p>Semigroups and monoids of PBRs can be created in the usual way in <strong class="pkg">GAP</strong> using the functions <code class="func">Semigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X7F55D28F819B2817"><span class="RefLink">Reference: Semigroup</span></a>) and <code class="func">Monoid</code> (<a href="../../../doc/ref/chap51_mj.html#X7F95328B7C7E49EA"><span class="RefLink">Reference: Monoid</span></a>); see Chapter <a href="chap6.html#X7995B4F18672DDB0"><span class="RefLink">6</span></a> for more details.</p>
<p>It is possible to create inverse semigroups and monoids of PBRs using <code class="func">InverseSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X78B13FED7AFB4326"><span class="RefLink">Reference: InverseSemigroup</span></a>) and <code class="func">InverseMonoid</code> (<a href="../../../doc/ref/chap51_mj.html#X80D9B9A98736051B"><span class="RefLink">Reference: InverseMonoid</span></a>) when the argument is a collection of PBRs satisfying <code class="func">IsBipartitionPBR</code> (<a href="chap4.html#X81EC86397E098BC8"><span class="RefLink">4.5-8</span></a>) and when considered as bipartitions, the collection satisfies <code class="code">IsGeneratorsOfInverseSemigroup</code>.</p>
<p>Note that every PBR semigroup in <strong class="pkg">Semigroups</strong> is finite.</p>
<p>A <em>PBR semigroup</em> is simply a semigroup consisting of PBRs. An object <var class="Arg">obj</var> is a PBR semigroup in <strong class="pkg">GAP</strong> if it satisfies <code class="func">IsSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X7B412E5B8543E9B7"><span class="RefLink">Reference: IsSemigroup</span></a>) and <code class="func">IsPBRCollection</code> (<a href="chap4.html#X854A9CEA7AC14C0A"><span class="RefLink">4.1-2</span></a>).</p>
<p>A <em>PBR monoid</em> is a monoid consisting of PBRs. An object <var class="Arg">obj</var> is a PBR monoid in <strong class="pkg">GAP</strong> if it satisfies <code class="func">IsMonoid</code> (<a href="../../../doc/ref/chap51_mj.html#X861C523483C6248C"><span class="RefLink">Reference: IsMonoid</span></a>) and <code class="func">IsPBRCollection</code> (<a href="chap4.html#X854A9CEA7AC14C0A"><span class="RefLink">4.1-2</span></a>).</p>
<p>Note that it is possible for a PBR semigroup to have a multiplicative neutral element (i.e. an identity element) but not to satisfy <code class="code">IsPBRMonoid</code>. For example,</p>
<p>In this example <code class="code">S</code> cannot be converted into a monoid using <code class="func">AsMonoid</code> (<a href="../../../doc/ref/chap51_mj.html#X7B22038F832B9C0F"><span class="RefLink">Reference: AsMonoid</span></a>) since the <code class="func">One</code> (<a href="../../../doc/ref/chap31_mj.html#X8046262384895B2A"><span class="RefLink">Reference: One</span></a>) of any element in <code class="code">S</code> differs from the multiplicative neutral element.</p>
<p>For more details see <code class="func">IsMagmaWithOne</code> (<a href="../../../doc/ref/chap35_mj.html#X86071DE7835F1C7C"><span class="RefLink">Reference: IsMagmaWithOne</span></a>).</p>
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.
