libsemigroups  v3.1.2
C++ library for semigroups and monoids
Loading...
Searching...
No Matches
presentation-examples.hpp
1//
2// libsemigroups - C++ library for semigroups and monoids
3// Copyright (C) 2022-2025 Murray T. Whyte
4//
5// This program is free software: you can redistribute it and/or modify
6// it under the terms of the GNU General Public License as published by
7// the Free Software Foundation, either version 3 of the License, or
8// (at your option) any later version.
9//
10// This program is distributed in the hope that it will be useful,
11// but WITHOUT ANY WARRANTY; without even the implied warranty of
12// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13// GNU General Public License for more details.
14//
15// You should have received a copy of the GNU General Public License
16// along with this program. If not, see <http://www.gnu.org/licenses/>.
17//
18// This file contains declarations of functions for constructing various
19// standard examples of presentations.
20
21#ifndef LIBSEMIGROUPS_PRESENTATION_EXAMPLES_HPP_
22#define LIBSEMIGROUPS_PRESENTATION_EXAMPLES_HPP_
23
24#include <cstddef> // for size_t
25#include <vector> // for vector
26
27#include "presentation.hpp" // for Presentation
28#include "types.hpp" // for word_type
29
30namespace libsemigroups {
41
42#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
45 // Forward declarations of the functions so they appear first in the
46 // documentation
71 Presentation<word_type> rectangular_band(size_t m, size_t n);
86#endif
87
100
123 size_t d);
124
136
149
161
176 [[nodiscard]] Presentation<word_type>
178
194 [[nodiscard]] Presentation<word_type>
196
208 [[nodiscard]] Presentation<word_type>
210
225 size_t n);
226
239 [[nodiscard]] Presentation<word_type>
241
253 [[nodiscard]] Presentation<word_type>
255
268 [[nodiscard]] Presentation<word_type>
270
285 [[nodiscard]] Presentation<word_type>
287
302
317
335 [[nodiscard]] Presentation<word_type>
337
353 [[nodiscard]] Presentation<word_type>
355
368
381 [[nodiscard]] Presentation<word_type>
383
397 [[nodiscard]] Presentation<word_type>
399
412 [[nodiscard]] Presentation<word_type>
414
427 [[nodiscard]] Presentation<word_type>
429
442
455 [[nodiscard]] Presentation<word_type>
457
469 [[nodiscard]] Presentation<word_type>
471
483 [[nodiscard]] Presentation<word_type>
485
497
509
521
535 size_t n);
536
554 int q);
555
572 int q);
573
592 [[nodiscard]] Presentation<word_type>
594
607
624
636
648
661
674
688
702
714 // TODO(1) rename this function and/or include the presentation
715 // from Joel's thesis (Example 7.1.2).
716 [[nodiscard]] Presentation<word_type>
718
730 [[nodiscard]] Presentation<word_type>
732
744 [[nodiscard]] Presentation<word_type>
746
759
770 [[nodiscard]] Presentation<word_type>
772
773 // TODO(1) add okada_monoid
774 // TODO(1) add free_semilattice
775
786 // When q = 0, the a_i^2 = 1 relations from the C+M symmetric group
787 // presentation are replaced with a_i^2 = a_i. See Definition 4.1.1 in
788 // Joel Gay's thesis https://theses.hal.science/tel-01861199
789 //
790 // This could also be called the RennerTypeAMonoid
792
794
804
815 [[nodiscard]] inline Presentation<word_type> alternating_group(size_t n) {
816 return alternating_group_Moo97(n);
817 }
818
829 [[nodiscard]] inline Presentation<word_type> brauer_monoid(size_t n) {
830 return brauer_monoid_KM07(n);
831 }
832
843 [[nodiscard]] inline Presentation<word_type> chinese_monoid(size_t n) {
844 return chinese_monoid_CEKNH01(n);
845 }
846
861 [[nodiscard]] inline Presentation<word_type>
864 }
865
877 [[nodiscard]] inline Presentation<word_type>
881
892 [[nodiscard]] inline Presentation<word_type> fibonacci_semigroup(size_t r,
893 size_t n) {
894 return fibonacci_semigroup_CRRT94(r, n);
895 }
896
923
934 [[nodiscard]] inline Presentation<word_type> hypo_plactic_monoid(size_t n) {
936 }
937
953 [[nodiscard]] Presentation<word_type> monogenic_semigroup(size_t m,
954 size_t r);
955
966 [[nodiscard]] inline Presentation<word_type> motzkin_monoid(size_t n) {
967 return motzkin_monoid_PHL13(n);
968 }
969
981 [[nodiscard]] inline Presentation<word_type>
982 not_renner_type_B_monoid(size_t l, int q) {
984 }
985
997 [[nodiscard]] inline Presentation<word_type>
998 not_renner_type_D_monoid(size_t l, int q) {
1000 }
1001
1013 [[nodiscard]] inline Presentation<word_type> not_symmetric_group(size_t n) {
1015 }
1016
1028 [[nodiscard]] inline Presentation<word_type>
1032
1044 [[nodiscard]] inline Presentation<word_type>
1047 }
1048
1060 [[nodiscard]] inline Presentation<word_type>
1064
1077 [[nodiscard]] inline Presentation<word_type>
1081
1092 [[nodiscard]] inline Presentation<word_type>
1095 }
1096
1108 [[nodiscard]] inline Presentation<word_type>
1112
1127 [[nodiscard]] inline Presentation<word_type>
1131
1154 [[nodiscard]] inline Presentation<word_type> partition_monoid(size_t n) {
1155 return partition_monoid_Eas11(n);
1156 }
1157
1168 [[nodiscard]] inline Presentation<word_type> plactic_monoid(size_t n) {
1169 return plactic_monoid_Knu70(n);
1170 }
1171
1182 [[nodiscard]] inline Presentation<word_type> rectangular_band(size_t m,
1183 size_t n) {
1184 return rectangular_band_ACOR00(m, n);
1185 }
1186
1197 [[nodiscard]] inline Presentation<word_type> renner_type_B_monoid(size_t l,
1198 int q) {
1199 return renner_type_B_monoid_Gay18(l, q);
1200 }
1201
1212 [[nodiscard]] inline Presentation<word_type> renner_type_D_monoid(size_t l,
1213 int q) {
1214 return renner_type_D_monoid_Gay18(l, q);
1215 }
1216
1227 [[nodiscard]] inline Presentation<word_type>
1231
1243 [[nodiscard]] inline Presentation<word_type>
1246 }
1247
1259 [[nodiscard]] inline Presentation<word_type>
1262 }
1263
1274 [[nodiscard]] inline Presentation<word_type> stellar_monoid(size_t l) {
1275 return stellar_monoid_GH19(l);
1276 }
1277
1288 [[nodiscard]] inline Presentation<word_type> stylic_monoid(size_t n) {
1289 return stylic_monoid_AR22(n);
1290 }
1291
1307 [[nodiscard]] inline Presentation<word_type> symmetric_group(size_t n) {
1308 return symmetric_group_Car56(n);
1309 }
1310
1326 [[nodiscard]] inline Presentation<word_type>
1330
1341 [[nodiscard]] inline Presentation<word_type>
1344 }
1345
1357 [[nodiscard]] inline Presentation<word_type>
1361
1372 [[nodiscard]] inline Presentation<word_type> zero_rook_monoid(size_t n) {
1373 return zero_rook_monoid_Gay18(n);
1374 }
1375
1386 [[nodiscard]] inline Presentation<word_type> abacus_jones_monoid(size_t n,
1387 size_t d) {
1388 return abacus_jones_monoid_AJP25(n, d);
1389 }
1390
1402 [[nodiscard]] Presentation<word_type> braid_group(size_t n);
1403
1405
1406 } // namespace presentation::examples
1407} // namespace libsemigroups
1408#endif // LIBSEMIGROUPS_PRESENTATION_EXAMPLES_HPP_
For an implementation of presentations for semigroups or monoids.
Definition presentation.hpp:102
Namespace for presentations of some finitely presented semigroups.
Definition presentation-examples.hpp:40
Presentation< word_type > symmetric_group_Moo97_a(size_t n)
A presentation for the symmetric group.
Presentation< word_type > hypo_plactic_monoid_Nov00(size_t n)
A presentation for the hypoplactic monoid.
Presentation< word_type > partition_monoid_Eas11(size_t n)
A presentation for the partition monoid.
Presentation< word_type > order_preserving_monoid_AR00(size_t n)
A presentation for the monoid of order preserving mappings.
Presentation< word_type > stylic_monoid(size_t n)
A presentation for the stylic monoid.
Definition presentation-examples.hpp:1288
Presentation< word_type > cyclic_inverse_monoid_Fer22_b(size_t n)
A presentation for the cyclic inverse monoid.
Presentation< word_type > dual_symmetric_inverse_monoid_EEF07(size_t n)
A presentation for the dual symmetric inverse monoid.
Presentation< word_type > rectangular_band_ACOR00(size_t m, size_t n)
A presentation for a rectangular band.
Presentation< word_type > special_linear_group_2_CR80(size_t q)
A presentation for the special linear group .
Presentation< word_type > symmetric_inverse_monoid(size_t n)
A presentation for the partial transformation monoid.
Definition presentation-examples.hpp:1327
Presentation< word_type > symmetric_inverse_monoid_MW24(size_t n)
A presentation for the symmetric inverse monoid.
Presentation< word_type > not_symmetric_group(size_t n)
A non-presentation for the symmetric group.
Definition presentation-examples.hpp:1013
Presentation< word_type > not_renner_type_B_monoid_Gay18(size_t l, int q)
A presentation that incorrectly claims to be the Renner monoid of type B.
Presentation< word_type > fibonacci_semigroup(size_t r, size_t n)
A presentation for a Fibonacci semigroup.
Definition presentation-examples.hpp:892
Presentation< word_type > not_renner_type_D_monoid(size_t l, int q)
A presentation that incorrectly claims to be the Renner monoid of type D.
Definition presentation-examples.hpp:998
Presentation< word_type > rectangular_band(size_t m, size_t n)
A presentation for a rectangular band.
Definition presentation-examples.hpp:1182
Presentation< word_type > brauer_monoid(size_t n)
A presentation for the Brauer monoid.
Definition presentation-examples.hpp:829
Presentation< word_type > full_transformation_monoid_II74(size_t n)
A presentation for the full transformation monoid.
Presentation< word_type > symmetric_inverse_monoid_Sol04(size_t n)
A presentation for the symmetric inverse monoid.
Presentation< word_type > full_transformation_monoid_MW24_b(size_t n)
A presentation for the full transformation monoid.
Presentation< word_type > fibonacci_semigroup_CRRT94(size_t r, size_t n)
A presentation for a Fibonacci semigroup.
Presentation< word_type > not_renner_type_D_monoid_God09(size_t l, int q)
A presentation that incorrectly claims to be the Renner monoid of type D.
Presentation< word_type > monogenic_semigroup(size_t m, size_t r)
A presentation for a monogenic semigroup.
Presentation< word_type > orientation_preserving_reversing_monoid(size_t n)
A presentation for the monoid of orientation preserving or reversing mappings.
Definition presentation-examples.hpp:1078
Presentation< word_type > alternating_group_Moo97(size_t n)
A presentation for the alternating group.
Presentation< word_type > brauer_monoid_KM07(size_t n)
A presentation for the Brauer monoid.
Presentation< word_type > abacus_jones_monoid_AJP25(size_t n, size_t d)
A presentation for the abacus Jones monoid.
Presentation< word_type > singular_brauer_monoid_MM07(size_t n)
A presentation for the singular part of the Brauer monoid.
Presentation< word_type > uniform_block_bijection_monoid_Fit03(size_t n)
A presentation for the uniform block bijection monoid.
Presentation< word_type > order_preserving_monoid(size_t n)
A presentation for the monoid of order preserving mappings.
Definition presentation-examples.hpp:1045
Presentation< word_type > renner_type_D_monoid(size_t l, int q)
A presentation for the Renner monoid of type D.
Definition presentation-examples.hpp:1212
Presentation< word_type > motzkin_monoid_PHL13(size_t n)
A presentation for the Motzkin monoid.
Presentation< word_type > renner_type_D_monoid_Gay18(size_t l, int q)
A presentation for the Renner monoid of type D.
Presentation< word_type > cyclic_inverse_monoid(size_t n)
A presentation for the cyclic inverse monoid.
Definition presentation-examples.hpp:862
Presentation< word_type > orientation_preserving_monoid(size_t n)
A presentation for the monoid of orientation preserving mappings.
Definition presentation-examples.hpp:1061
Presentation< word_type > chinese_monoid_CEKNH01(size_t n)
A presentation for the Chinese monoid.
Presentation< word_type > zero_rook_monoid(size_t n)
A presentation for the -rook monoid.
Definition presentation-examples.hpp:1372
Presentation< word_type > singular_brauer_monoid(size_t n)
A presentation for the singular part of the Brauer monoid.
Definition presentation-examples.hpp:1244
Presentation< word_type > special_linear_group_2(size_t q)
A presentation for the special linear group .
Definition presentation-examples.hpp:1260
Presentation< word_type > symmetric_group(size_t n)
A presentation for the symmetric group.
Definition presentation-examples.hpp:1307
Presentation< word_type > partition_monoid_HR05(size_t n)
A presentation for the partition monoid.
Presentation< word_type > temperley_lieb_monoid(size_t n)
A presentation for the Temperley-Lieb monoid.
Definition presentation-examples.hpp:1342
Presentation< word_type > dual_symmetric_inverse_monoid(size_t n)
A presentation for the dual symmetric inverse monoid.
Definition presentation-examples.hpp:878
Presentation< word_type > partial_transformation_monoid(size_t n)
A presentation for the partial transformation monoid.
Definition presentation-examples.hpp:1128
Presentation< word_type > partial_transformation_monoid_MW24(size_t n)
A presentation for the partial transformation monoid.
Presentation< word_type > not_renner_type_B_monoid(size_t l, int q)
A presentation that incorrectly claims to be the Renner monoid of type B.
Definition presentation-examples.hpp:982
Presentation< word_type > orientation_preserving_reversing_monoid_AR00(size_t n)
A presentation for the monoid of orientation preserving or reversing mappings.
Presentation< word_type > order_preserving_cyclic_inverse_monoid_Fer22(size_t n)
A presentation for the order preserving part of the cyclic inverse monoid.
Presentation< word_type > partial_transformation_monoid_Shu60(size_t n)
A presentation for the partial transformation monoid.
Presentation< word_type > full_transformation_monoid_Aiz58(size_t n)
A presentation for the full transformation monoid.
Presentation< word_type > partial_isometries_cycle_graph_monoid(size_t n)
A presentation for the monoid of partial isometries of a cycle graph.
Definition presentation-examples.hpp:1109
Presentation< word_type > partition_monoid(size_t n)
A presentation for the partition monoid.
Definition presentation-examples.hpp:1154
Presentation< word_type > partial_brauer_monoid_KM07(size_t n)
A presentation for the partial Brauer monoid.
Presentation< word_type > temperley_lieb_monoid_Eas21(size_t n)
A presentation for the Temperley-Lieb monoid.
Presentation< word_type > renner_type_B_monoid(size_t l, int q)
A presentation for the Renner monoid of type B.
Definition presentation-examples.hpp:1197
Presentation< word_type > stellar_monoid_GH19(size_t l)
A presentation for the stellar monoid.
Presentation< word_type > order_preserving_cyclic_inverse_monoid(size_t n)
A presentation for the order preserving part of the cyclic inverse monoid.
Definition presentation-examples.hpp:1029
Presentation< word_type > partial_isometries_cycle_graph_monoid_FP22(size_t n)
A presentation for the monoid of partial isometries of a cycle graph.
Presentation< word_type > symmetric_group_Moo97_b(size_t n)
A presentation for the symmetric group.
Presentation< word_type > motzkin_monoid(size_t n)
A presentation for the Motzkin monoid.
Definition presentation-examples.hpp:966
Presentation< word_type > plactic_monoid(size_t n)
A presentation for the plactic monoid.
Definition presentation-examples.hpp:1168
Presentation< word_type > abacus_jones_monoid(size_t n, size_t d)
A presentation for the abacus Jones monoid.
Definition presentation-examples.hpp:1386
Presentation< word_type > braid_group(size_t n)
A presentation for the Braid group.
Presentation< word_type > orientation_preserving_monoid_AR00(size_t n)
A presentation for the monoid of orientation preserving mappings.
Presentation< word_type > not_symmetric_group_GKKL08(size_t n)
A non-presentation for the symmetric group.
Presentation< word_type > hypo_plactic_monoid(size_t n)
A presentation for the hypoplactic monoid.
Definition presentation-examples.hpp:934
Presentation< word_type > partial_brauer_monoid(size_t n)
A presentation for the partial Brauer monoid.
Definition presentation-examples.hpp:1093
Presentation< word_type > plactic_monoid_Knu70(size_t n)
A presentation for the plactic monoid.
Presentation< word_type > sigma_plactic_monoid_AHMNT24(std::vector< size_t > const &sigma)
A presentation for the -plactic monoid.
Presentation< word_type > symmetric_inverse_monoid_Shu60(size_t n)
A presentation for the symmetric inverse monoid.
Presentation< word_type > alternating_group(size_t n)
A presentation for the alternating group.
Definition presentation-examples.hpp:815
Presentation< word_type > symmetric_group_Bur12(size_t n)
A presentation for the symmetric group.
Presentation< word_type > stellar_monoid(size_t l)
A presentation for the stellar monoid.
Definition presentation-examples.hpp:1274
Presentation< word_type > renner_type_B_monoid_Gay18(size_t l, int q)
A presentation for the Renner monoid of type B.
Presentation< word_type > cyclic_inverse_monoid_Fer22_a(size_t n)
A presentation for the cyclic inverse monoid.
Presentation< word_type > uniform_block_bijection_monoid(size_t n)
A presentation for the uniform block bijection monoid.
Definition presentation-examples.hpp:1358
Presentation< word_type > symmetric_group_Car56(size_t n)
A presentation for the symmetric group.
Presentation< word_type > stylic_monoid_AR22(size_t n)
A presentation for the stylic monoid.
Presentation< word_type > sigma_plactic_monoid(std::vector< size_t > const &sigma)
A presentation for the -plactic monoid.
Definition presentation-examples.hpp:1228
Presentation< word_type > full_transformation_monoid(size_t n)
A presentation for the full transformation monoid.
Presentation< word_type > full_transformation_monoid_MW24_a(size_t n)
A presentation for the full transformation monoid.
Presentation< word_type > chinese_monoid(size_t n)
A presentation for the Chinese monoid.
Definition presentation-examples.hpp:843
Presentation< word_type > zero_rook_monoid_Gay18(size_t n)
A presentation for the -rook monoid.
Namespace for everything in the libsemigroups library.
Definition action.hpp:44