Examples¶
This page contains the documentation for various examples of presentations of finitely presented semigroups and monoids.
Presentations from the following sources are implemented: [GH19]; [God09]; [Eas21]; [MM07]; [AR00]; [KM07]; [Bur12]; [GM09]; [CEK+01]; [CRRT94]; [AR22]; [EEF07]; [Fit03]; [Eas11]; [ACOConnorR00]; [Rus95]; [Aiz58]; [CM79]; [Knu70]; [LSchutzenberger81]; [Moo97]; [Aiz62]; [Fer22]; [FP22].

type libsemigroups::fpsemigroup::author¶
The values in this enum class are used to specify the authors of a presentation. Where there are different presentations by different authors, values of this type can be passed as an argument to disambiguate which presentation is wanted.

inline author libsemigroups::fpsemigroup::operator+(author auth1, author auth2)¶
This operator can be used arbitrarily to combine author values (see author).

std::ostringstream &libsemigroups::fpsemigroup::operator<<(std::ostringstream &oss, author val)¶
This operator can be used to produce string representations of author values.
Contents¶
A presentation for the symmetric group. 

A presentation for the alternating group. 

A presentation for the full transformation monoid. 

A presentation for the partial transformation monoid. 

A presentation for the symmetric inverse monoid. 

A presentation for the dual symmetric inverse monoid. 

A presentation for the uniform block bijection monoid. 

A presentation for the partition monoid. 

A presentation for the Brauer monoid. 

A presentation for a rectangular band. 

A presentation for the stellar monoid. 

A presentation for the Chinese monoid. 

A presentation for a monogenic semigroup. 

A presentation for the plactic monoid. 

A presentation for the stylic monoid. 

A presentation for a Fibonacci semigroup. 

A presentation for the TemperleyLieb monoid. 

A presentation for the singular part of the Brauer monoid. 

A presentation for the monoid of orientation preserving mappings. 

A presentation for the monoid of orientation reversing mappings. 

A presentation for the monoid of order preserving mappings. 

A presentation for the cyclic inverse monoid. 

A presentation for the orderpreserving part of the cyclic inverse monoid. 

A presentation for the monoid of partial isometries of a cycle graph. 

A nonpresentation for the symmetric group. 
Full API¶

std::vector<relation_type> libsemigroups::fpsemigroup::symmetric_group(size_t n, author val = author::Carmichael, size_t index = 0)¶
A presentation for the symmetric group.
Returns a vector of relations giving a monoid presentation for the symmetric group. The argument
val
determines the specific presentation which is returned. The options are:Author
Index
No. generators
No. relations
Reference
author::Burnside + author::Miller
0
\(n  1\)
\(n^3  5n^2 + 9n  5\)
p.464 of 10.1017/CBO9781139237253
author::Carmichael
0
\(n  1\)
\((n  1)^2\)
Comment 9.5.2 of 10.1007/9781848002814
author::Coxeter + author::Moser
0
\(n  1\)
\(n(n + 1)/2\)
Ch.3, Prop 1.2 of hdl.handle.net/10023/2821
author::Moore
0
\(2\)
\(n + 1\)
Ch. 3, Prop 1.1 of hdl.handle.net/10023/2821
1
\(n  1\)
\(n(n + 1)/2\)
Comment 9.5.3 of 10.1007/9781848002814
val
isauthor::Carmichael
. The default forindex
is0
. Parameters
n – the degree of the symmetric group
val – the author of the presentation
 Throws
LibsemigroupsException – if
n < 4
LibsemigroupsException – if the authorindex combination is invalid
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::alternating_group(size_t n, author val = author::Moore)¶
A presentation for the alternating group.
Returns a vector of relations giving a monoid presentation defining the alternating group of degree
n
. The argumentval
determines the specific presentation which is returned. The options are:author::Moore
(see Ch. 3, Prop 1.3 of hdl.handle.net/10023/2821)
The default for
val
isauthor::Moore
. Parameters
n – the degree of the alternating group
val – the author of the presentation
 Throws
LibsemigroupsException – if
val
is notauthor::Moore
LibsemigroupsException – if
n < 4
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::full_transformation_monoid(size_t n, author val = author::Iwahori)¶
A presentation for the full transformation monoid.
Returns a vector of relations giving a monoid presentation defining the full transformation monoid. The argument
val
determines the specific presentation which is returned. The options are:author::Aizenstat
(see Ch. 3, Prop 1.7 of http://hdl.handle.net/10023/2821)author::Iwahori
(see Theorem 9.3.1 of 10.1007/9781848002814)
The default for
val
isauthor::Iwahori
. Parameters
n – the degree of the full transformation monoid
val – the author of the presentation
 Throws
LibsemigroupsException – if
val
is not listed above (modulo order of author)LibsemigroupsException – if
n < 4
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::partial_transformation_monoid(size_t n, author val = author::Sutov)¶
A presentation for the partial transformation monoid.
Returns a vector of relations giving a monoid presentation defining the partial transformation monoid. The argument
val
determines the specific presentation which is returned. The options are:author::Machine
author::Sutov
(see Theorem 9.4.1 of 10.1007/9781848002814)
The default for
val
isauthor::Sutov
. Parameters
n – the degree of the partial transformation monoid
val – the author of the presentation
 Throws
LibsemigroupsException – if
val
is not listed above (modulo order of author) Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::symmetric_inverse_monoid(size_t n, author val = author::Sutov)¶
A presentation for the symmetric inverse monoid.
Returns a vector of relations giving a monoid presentation defining the symmetric inverse monoid. The argument
val
determines the specific presentation which is returned. The options are:author::Sutov
(see Theorem 9.2.2 of 10.1007/9781848002814)
The default for
val
is the only option above. Parameters
n – the degree of the symmetric inverse monoid
val – the author of the presentation
 Throws
LibsemigroupsException – if
val
is not listed above (modulo order of author) Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::dual_symmetric_inverse_monoid(size_t n, author val = author::Easdown + author::East + author::FitzGerald)¶
A presentation for the dual symmetric inverse monoid.
Returns a vector of relations giving a semigroup presentation defining the dual symmetric inverse monoid of degree
n
. The argumentval
determines the specific presentation which is returned. The options are:author::Easdown + author::East + author::FitzGerald
(from Section 3 of 10.48550/arxiv.0707.2439)
The default for
val
is the only option above. Parameters
n – the degree
val – the author of the presentation
 Throws
LibsemigroupsException – if
n < 3
LibsemigroupsException – if
val
is notauthor::Easdown + author::East + author::FitzGerald
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::uniform_block_bijection_monoid(size_t n, author val = author::FitzGerald)¶
A presentation for the uniform block bijection monoid.
Returns a vector of relations giving a semigroup presentation defining the uniform block bijection monoid of degree
n
. The argumentval
determines the specific presentation which is returned. The only option is:author::FitzGerald
(see 10.1017/s0004972700037692)
The default for
val
is the only option above. Parameters
n – the degree
val – the author of the presentation
 Throws
LibsemigroupsException – if
n < 3
LibsemigroupsException – if
val
is notauthor::FitzGerald
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::partition_monoid(size_t n, author val = author::East)¶
A presentation for the partition monoid.
Returns a vector of relations giving a semigroup presentation defining the partition monoid of degree
n
. The argumentval
determines the specific presentation which is returned. The options are:author::Machine
author::East
(see Theorem 41 of 10.1016/j.jalgebra.2011.04.008)
The default for
val
isauthor::East
. Parameters
n – the degree
val – the author of the presentation
 Throws
LibsemigroupsException – if
val = author::Machine and n != 3
LibsemigroupsException – if
val = author::East and n < 4
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::brauer_monoid(size_t n)¶
A presentation for the Brauer monoid.
Returns a vector of relations giving a semigroup presentation defining the Brauer monoid of degree
n
, as described in Theorem 3.1 of the paper 10.2478/s1153300600176.This function is
noexcept
and is guaranteed never to throw. Parameters
n – the degree
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::rectangular_band(size_t m, size_t n)¶
A presentation for a rectangular band.
Returns a vector of relations giving a semigroup presentation defining the
m
byn
rectangular band, as given in Proposition 4.2 of 10.1007/s002339910016. Parameters
m – the number of rows
n – the number of columns
 Throws
LibsemigroupsException – if
m = 0
LibsemigroupsException – if
n = 0
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::stellar_monoid(size_t l)¶
A presentation for the stellar monoid.
Returns a vector of relations giving a semigroup presentation defining the stellar monoid with
l
generators, as in Theorem 4.39 of 10.48550/arXiv.1910.11740. Parameters
l – the number of generators
 Throws
LibsemigroupsException – if
l < 2
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::chinese_monoid(size_t n)¶
A presentation for the Chinese monoid.
Returns a vector of relations giving a semigroup presentation defining the Chinese monoid, as described in 10.1142/S0218196701000425.
 Parameters
n – the number of generators
 Throws
LibsemigroupsException – if
n < 2
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::monogenic_semigroup(size_t m, size_t r)¶
A presentation for a monogenic semigroup.
Returns a vector of relations giving a semigroup presentation defining the monogenic semigroup defined by the presentation \(\langle a \mid a^{m + r} = a^m \rangle\).
 Parameters
m – the index
r – the period
 Throws
LibsemigroupsException – if
r = 0
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::plactic_monoid(size_t n)¶
A presentation for the plactic monoid.
Returns a vector of relations giving a semigroup presentation defining the plactic monoid with
n
generators (see Section 3 of 10.1007/s00233022102853). Parameters
n – the number of generators
 Throws
LibsemigroupsException – if
n < 2
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::stylic_monoid(size_t n)¶
A presentation for the stylic monoid.
Returns a vector of relations giving a semigroup presentation defining the stylic monoid with
n
generators (see Theorem 8.1 of 10.1007/s00233022102853). Parameters
n – the number of generators
 Throws
LibsemigroupsException – if
n < 2
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::fibonacci_semigroup(size_t r, size_t n)¶
A presentation for a Fibonacci semigroup.
Returns a vector of relations giving a semigroup presentation defining the Fibonacci semigroup \(F(r, n)\), as described in 10.1016/00224049(94)900051.
 Parameters
r – the length of the left hand sides of the relations
n – the number of generators
 Throws
LibsemigroupsException – if
n = 0
LibsemigroupsException – if
r = 0
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::temperley_lieb_monoid(size_t n)¶
A presentation for the TemperleyLieb monoid.
Returns a vector of relations giving a semigroup presentation defining the TemperleyLieb monoid with
n
generators, as described in Theorem 2.2 of 10.1093/qmath/haab001. Parameters
n – the number of generators
 Throws
LibsemigroupsException – if
n < 3
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::singular_brauer_monoid(size_t n)¶
A presentation for the singular part of the Brauer monoid.
Returns a vector of relations giving a semigroup presentation for the singular part of the Brauer monoid of degree
n
, as in Theorem 5 of 10.21136/MB.2007.134125). Parameters
n – the degree
 Throws
LibsemigroupsException – if
n < 3
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::orientation_preserving_monoid(size_t n)¶
A presentation for the monoid of orientation preserving mappings.
Returns a vector of relations giving a semigroup presentation defining the monoid of orientation preserving mappings on a finite chain of order
n
, as described in 10.1007/s1001200000011. Parameters
n – the order of the chain
 Throws
LibsemigroupsException – if
n < 3
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::orientation_reversing_monoid(size_t n)¶
A presentation for the monoid of orientation reversing mappings.
Returns a vector of relations giving a semigroup presentation defining the monoid of orientation reversing mappings on a finite chain of order
n
, as described in 10.1007/s1001200000011. Parameters
n – the order of the chain
 Throws
LibsemigroupsException – if
n < 3
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::order_preserving_monoid(size_t n)¶
A presentation for the monoid of orderpreserving mappings.
Returns a vector of relations giving a semigroup presentation defining the monoid of orderpreserving transformations of degree
n
, as described in Section 2 of the paper 10.1007/s1001200000011.This presentation has \(2n  2\) generators and \(n^2\) relations.
 Parameters
n – the degree
val – the author
 Throws
LibsemigroupsException – if
n < 3
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::cyclic_inverse_monoid(size_t n, author val = author::Fernandes, size_t index = 1)¶
A presentation for the cyclic inverse monoid.
Returns a vector of relations giving a monoid presentation defining the cyclic inverse monoid of degree
n
.The combination of
val
andindex
determines the specific presentation which is returned. The options for these are:val = author::Fernandes
index = 0
(see Theorem 2.6 of 10.48550/arxiv.2211.02155)index = 1
(see Theorem 2.7 of 10.48550/arxiv.2211.02155)
The presentation with
val = author::Fernandes
andindex = 0
has \(n + 1\) generators and \(\frac{1}{2} \left(n^2 + 3n + 4\right)\) relations.The presentation with
val = author::Fernandes
andindex = 1
has \(2\) generators and \(\frac{1}{2}\left(n^2  n + 6\right)\) relations. Parameters
n – the degree
val – the author
index – the index
 Throws
LibsemigroupsException – if
n < 3
LibsemigroupsException – if
val
is notauthor::Fernandes
LibsemigroupsException – if
val = author::Fernandes
andindex
is not0
or1
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::order_preserving_cyclic_inverse_monoid(size_t n)¶
A presentation for the orderpreserving part of the cyclic inverse monoid.
Returns a vector of relations giving a semigroup presentation defining the orderpreserving part of the cyclic inverse monoid of degree
n
, as described in Theorem 2.17 of the paper 10.48550/arxiv.2211.02155. Parameters
n – the degree
 Throws
LibsemigroupsException – if
n < 3
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::partial_isometries_cycle_graph_monoid(size_t n)¶
A presentation for the monoid of partial isometries of a cycle graph.
Returns a vector of relations giving a monoid presentation defining the monoid of partial isometries of an \(n\)cycle graph, as described in Theorem 2.8 of 10.48550/arxiv.2205.02196.
 Parameters
n – the number of vertices of the cycle graph
 Throws
LibsemigroupsException – if
n < 3
 Returns
A
std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::not_symmetric_group(size_t n, author val = author::Guralnick + author::Kantor + author::Kassabov + author::Lubotzky)¶
A nonpresentation for the symmetric group.
Returns a vector of relations giving a monoid presentation which is claimed to define the symmetric group of degree
n
, but does not. The argumentval
determines the specific presentation which is returned. The options are:author::Guralnick + author::Kantor + author::Kassabov + author::Lubotzky
doi.org/10.1090/S0894034708005900
The default for
val
is the only option above. Parameters
n – the claimed degree of the symmetric group
val – the author of the presentation
 Throws
LibsemigroupsException – if
val
is not listed above (modulo order of author)LibsemigroupsException – if
n < 4
 Returns
A
std::vector<relation_type>