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 Temperley-Lieb 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 order-preserving part of the cyclic inverse monoid. |
|
A presentation for the monoid of partial isometries of a cycle graph. |
|
A non-presentation 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/978-1-84800-281-4
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/978-1-84800-281-4
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 author-index 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/978-1-84800-281-4)
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/978-1-84800-281-4)
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/978-1-84800-281-4)
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/s11533-006-0017-6.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/s00233-022-10285-3).- 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/s00233-022-10285-3).- 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/0022-4049(94)90005-1.
- 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 Temperley-Lieb monoid.
Returns a vector of relations giving a semigroup presentation defining the Temperley-Lieb 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/s10012-000-0001-1.- 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/s10012-000-0001-1.- 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 order-preserving mappings.
Returns a vector of relations giving a semigroup presentation defining the monoid of order-preserving transformations of degree
n
, as described in Section 2 of the paper 10.1007/s10012-000-0001-1.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 order-preserving part of the cyclic inverse monoid.
Returns a vector of relations giving a semigroup presentation defining the order-preserving 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 non-presentation 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/S0894-0347-08-00590-0
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>