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

symmetric_group()	A presentation for the symmetric group.
alternating_group()	A presentation for the alternating group.
full_transformation_monoid()	A presentation for the full transformation monoid.
partial_transformation_monoid()	A presentation for the partial transformation monoid.
symmetric_inverse_monoid()	A presentation for the symmetric inverse monoid.
dual_symmetric_inverse_monoid()	A presentation for the dual symmetric inverse monoid.
uniform_block_bijection_monoid()	A presentation for the uniform block bijection monoid.
partition_monoid()	A presentation for the partition monoid.
brauer_monoid()	A presentation for the Brauer monoid.
rectangular_band()	A presentation for a rectangular band.
stellar_monoid()	A presentation for the stellar monoid.
chinese_monoid()	A presentation for the Chinese monoid.
monogenic_semigroup()	A presentation for a monogenic semigroup.
plactic_monoid()	A presentation for the plactic monoid.
stylic_monoid()	A presentation for the stylic monoid.
fibonacci_semigroup()	A presentation for a Fibonacci semigroup.
temperley_lieb_monoid()	A presentation for the Temperley-Lieb monoid.
singular_brauer_monoid()	A presentation for the singular part of the Brauer monoid.
orientation_preserving_monoid()	A presentation for the monoid of orientation preserving mappings.
orientation_reversing_monoid()	A presentation for the monoid of orientation reversing mappings.
order_preserving_monoid()	A presentation for the monoid of order preserving mappings.
cyclic_inverse_monoid()	A presentation for the cyclic inverse monoid.
order_preserving_cyclic_inverse_monoid()	A presentation for the order-preserving part of the cyclic inverse monoid.
partial_isometries_cycle_graph_monoid()	A presentation for the monoid of partial isometries of a cycle graph.
not_symmetric_group()	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

The default for val is author::Carmichael. The default for index is 0.

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 argument val 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 is author::Moore.

Parameters

• n – the degree of the alternating group

• val – the author of the presentation

Throws

• LibsemigroupsException – if val is not author::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 is author::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 is author::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 argument val 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 not author::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 argument val 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 not author::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 argument val 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 is author::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 by n 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 and index 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 and index = 0 has \(n + 1\) generators and \(\frac{1}{2} \left(n^2 + 3n + 4\right)\) relations.

The presentation with val = author::Fernandes and index = 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 not author::Fernandes

• LibsemigroupsException – if val = author::Fernandes and index is not 0 or 1

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 argument val 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>