33:
1685:
1814:
1227:
813:
510:
951:
1060:
366:
1412:
418:
1560:
1696:
1332:
1281:
694:
573:
1552:
1515:
1106:
878:
849:
981:
1447:
1367:
1098:
640:
1478:
1005:
720:
728:
1886:
1868:
1854:
73:
433:
144:(also known as a semi-Thue system). Every monoid may be presented by a semi-Thue system (possibly over an infinite alphabet).
901:
1013:
287:
55:
1372:
374:
699:
1680:{\displaystyle \mathrm {FIM} (X)=\mathrm {Inv} ^{1}\langle X|\varnothing \rangle =({X\cup X^{-1}})^{*}/\rho _{X},}
1902:
51:
1809:{\displaystyle \mathrm {FIS} (X)=\mathrm {Inv} \langle X|\varnothing \rangle =({X\cup X^{-1}})^{+}/\rho _{X}.}
141:
1286:
1235:
1222:{\displaystyle \mathrm {Inv} ^{1}\langle X|T\rangle =(X\cup X^{-1})^{*}/(T\cup \rho _{X})^{\mathrm {c} }.}
650:
522:
153:
1520:
1483:
854:
825:
881:
885:
43:
130:
959:
1882:
1864:
1850:
984:
177:
607:
Presentations of inverse monoids and semigroups can be defined in a similar way using a pair
1420:
1340:
1071:
613:
819:
424:
166:
126:
17:
519:
of degree 2 (it has infinite order). Elements of this plactic monoid may be written as
129:
of the free monoid (or the free semigroup) by these relations. This is an analogue of a
1874:
1463:
990:
705:
516:
1896:
134:
111:
1861:
Monoids, Acts and
Categories with Applications to Wreath Products and Graphs
103:
1863:, De Gruyter Expositions in Mathematics vol. 29, Walter de Gruyter, 2000,
87:
808:{\displaystyle T\subseteq (X\cup X^{-1})^{*}\times (X\cup X^{-1})^{*}}
140:
As a mathematical structure, a monoid presentation is identical to a
99:
176:. To form the quotient monoid, these relations are extended to
273:. Finally, one takes the reflexive and transitive closure of
26:
505:{\displaystyle \langle a,b\,\vert \;aba=baa,bba=bab\rangle }
895:
We use this pair of objects to define an inverse monoid
946:{\displaystyle \mathrm {Inv} ^{1}\langle X|T\rangle .}
1699:
1563:
1523:
1486:
1466:
1423:
1375:
1343:
1289:
1238:
1232:
In the previous discussion, if we replace everywhere
1109:
1074:
1055:{\displaystyle \mathrm {Inv} ^{1}\langle X|T\rangle }
1016:
993:
962:
904:
857:
828:
731:
708:
653:
616:
525:
436:
377:
361:{\displaystyle R=\{u_{1}=v_{1},\ldots ,u_{n}=v_{n}\}}
290:
1808:
1679:
1546:
1509:
1472:
1441:
1406:
1361:
1326:
1275:
1221:
1092:
1054:
999:
975:
945:
872:
843:
807:
714:
688:
634:
567:
504:
412:
360:
1407:{\displaystyle \mathrm {Inv} \langle X|T\rangle }
413:{\displaystyle \langle p,q\,\vert \;pq=1\rangle }
197:. This is then extended to a symmetric relation
284:is simply given as a set of equations, so that
8:
1748:
1734:
1619:
1605:
1401:
1387:
1142:
1128:
1049:
1035:
937:
923:
499:
450:
437:
407:
391:
378:
355:
297:
110:of generators and a set of relations on the
54:. There might be a discussion about this on
453:
394:
1797:
1788:
1782:
1768:
1757:
1740:
1723:
1700:
1698:
1668:
1659:
1653:
1639:
1628:
1611:
1599:
1588:
1564:
1562:
1524:
1522:
1487:
1485:
1465:
1422:
1393:
1376:
1374:
1342:
1318:
1304:
1293:
1288:
1267:
1253:
1242:
1237:
1209:
1208:
1198:
1180:
1174:
1161:
1134:
1122:
1111:
1108:
1073:
1041:
1029:
1018:
1015:
992:
967:
961:
929:
917:
906:
903:
863:
862:
856:
834:
833:
827:
799:
786:
764:
751:
730:
707:
680:
667:
652:
615:
559:
540:
530:
524:
449:
435:
390:
376:
349:
336:
317:
304:
289:
74:Learn how and when to remove this message
1825:
1745:
1616:
1452:A trivial but important example is the
1336:presentation (for an inverse semigroup)
423:is the equational presentation for the
280:In the typical situation, the relation
183:First, one takes the symmetric closure
165:The relations are given as a (finite)
125:. The monoid is then presented as the
822:relation between words. We denote by
277:, which then is a monoid congruence.
7:
1832:Book and Otto, Theorem 7.1.7, p. 149
1327:{\displaystyle ({X\cup X^{-1}})^{+}}
1276:{\displaystyle ({X\cup X^{-1}})^{*}}
1889:, chapter 7, "Algebraic Properties"
1859:M. Kilp, U. Knauer, A.V. Mikhalev,
1730:
1727:
1724:
1707:
1704:
1701:
1595:
1592:
1589:
1571:
1568:
1565:
1531:
1528:
1525:
1494:
1491:
1488:
1383:
1380:
1377:
1210:
1118:
1115:
1112:
1025:
1022:
1019:
913:
910:
907:
864:
835:
689:{\displaystyle (X\cup X^{-1})^{*}}
568:{\displaystyle a^{i}b^{j}(ba)^{k}}
25:
1547:{\displaystyle \mathrm {FIS} (X)}
1510:{\displaystyle \mathrm {FIM} (X)}
1849:(1995), Clarendon Press, Oxford
1847:Fundamentals of Semigroup Theory
873:{\displaystyle T^{\mathrm {c} }}
844:{\displaystyle T^{\mathrm {e} }}
31:
1007:, we define the inverse monoid
1779:
1754:
1741:
1717:
1711:
1650:
1625:
1612:
1581:
1575:
1541:
1535:
1504:
1498:
1436:
1424:
1394:
1356:
1344:
1315:
1290:
1264:
1239:
1205:
1185:
1171:
1148:
1135:
1087:
1075:
1042:
930:
796:
773:
761:
738:
677:
654:
629:
617:
603:Inverse monoids and semigroups
556:
546:
151:should not be confused with a
1:
1480:, that is usually denoted by
587:, as the relations show that
700:free monoid with involution
96:presentation of a semigroup
1919:
1369:and an inverse semigroup
976:{\displaystyle \rho _{X}}
18:Finitely presented monoid
1879:String-rewriting Systems
98:) is a description of a
92:presentation of a monoid
142:string rewriting system
117:(or the free semigroup
1810:
1681:
1548:
1511:
1474:
1458:free inverse semigroup
1443:
1408:
1363:
1328:
1277:
1223:
1094:
1056:
1001:
977:
947:
874:
845:
809:
716:
690:
636:
569:
506:
414:
362:
1811:
1682:
1549:
1512:
1475:
1444:
1442:{\displaystyle (X;T)}
1409:
1364:
1362:{\displaystyle (X;T)}
1329:
1278:
1224:
1095:
1093:{\displaystyle (X;T)}
1057:
1002:
978:
948:
875:
846:
810:
717:
691:
637:
635:{\displaystyle (X;T)}
570:
507:
415:
368:. Thus, for example,
363:
1877:and Friedrich Otto,
1697:
1561:
1554:) and is defined by
1521:
1484:
1464:
1421:
1373:
1341:
1287:
1236:
1107:
1072:
1014:
991:
960:
902:
882:equivalence relation
855:
826:
729:
706:
651:
614:
523:
434:
375:
288:
106:) in terms of a set
44:confusing or unclear
1454:free inverse monoid
884:(respectively, the
591:commutes with both
52:clarify the article
1881:, Springer, 1993,
1806:
1677:
1544:
1507:
1470:
1439:
1404:
1359:
1324:
1273:
1219:
1090:
1052:
997:
973:
943:
870:
841:
805:
712:
686:
632:
565:
502:
410:
358:
178:monoid congruences
131:group presentation
1473:{\displaystyle X}
1000:{\displaystyle X}
985:Wagner congruence
715:{\displaystyle X}
235:for some strings
84:
83:
76:
16:(Redirected from
1910:
1903:Semigroup theory
1833:
1830:
1815:
1813:
1812:
1807:
1802:
1801:
1792:
1787:
1786:
1777:
1776:
1775:
1744:
1733:
1710:
1686:
1684:
1683:
1678:
1673:
1672:
1663:
1658:
1657:
1648:
1647:
1646:
1615:
1604:
1603:
1598:
1574:
1553:
1551:
1550:
1545:
1534:
1516:
1514:
1513:
1508:
1497:
1479:
1477:
1476:
1471:
1448:
1446:
1445:
1440:
1413:
1411:
1410:
1405:
1397:
1386:
1368:
1366:
1365:
1360:
1333:
1331:
1330:
1325:
1323:
1322:
1313:
1312:
1311:
1282:
1280:
1279:
1274:
1272:
1271:
1262:
1261:
1260:
1228:
1226:
1225:
1220:
1215:
1214:
1213:
1203:
1202:
1184:
1179:
1178:
1169:
1168:
1138:
1127:
1126:
1121:
1099:
1097:
1096:
1091:
1061:
1059:
1058:
1053:
1045:
1034:
1033:
1028:
1006:
1004:
1003:
998:
982:
980:
979:
974:
972:
971:
952:
950:
949:
944:
933:
922:
921:
916:
879:
877:
876:
871:
869:
868:
867:
850:
848:
847:
842:
840:
839:
838:
814:
812:
811:
806:
804:
803:
794:
793:
769:
768:
759:
758:
721:
719:
718:
713:
695:
693:
692:
687:
685:
684:
675:
674:
641:
639:
638:
633:
574:
572:
571:
566:
564:
563:
545:
544:
535:
534:
511:
509:
508:
503:
419:
417:
416:
411:
367:
365:
364:
359:
354:
353:
341:
340:
322:
321:
309:
308:
283:
276:
272:
253:
234:
230:
226:
222:
218:
203:
196:
192:
175:
171:
124:
120:
116:
109:
79:
72:
68:
65:
59:
35:
34:
27:
21:
1918:
1917:
1913:
1912:
1911:
1909:
1908:
1907:
1893:
1892:
1845:John M. Howie,
1842:
1837:
1836:
1831:
1827:
1822:
1793:
1778:
1764:
1695:
1694:
1664:
1649:
1635:
1587:
1559:
1558:
1519:
1518:
1482:
1481:
1462:
1461:
1419:
1418:
1371:
1370:
1339:
1338:
1314:
1300:
1285:
1284:
1263:
1249:
1234:
1233:
1204:
1194:
1170:
1157:
1110:
1105:
1104:
1070:
1069:
1017:
1012:
1011:
989:
988:
963:
958:
957:
905:
900:
899:
888:) generated by
858:
853:
852:
829:
824:
823:
795:
782:
760:
747:
727:
726:
704:
703:
676:
663:
649:
648:
612:
611:
605:
555:
536:
526:
521:
520:
432:
431:
425:bicyclic monoid
373:
372:
345:
332:
313:
300:
286:
285:
281:
274:
255:
236:
232:
228:
224:
220:
219:if and only if
214:
205:
198:
194:
184:
173:
169:
167:binary relation
163:
122:
121:) generated by
118:
114:
107:
80:
69:
63:
60:
49:
36:
32:
23:
22:
15:
12:
11:
5:
1916:
1914:
1906:
1905:
1895:
1894:
1891:
1890:
1875:Ronald V. Book
1872:
1857:
1841:
1838:
1835:
1834:
1824:
1823:
1821:
1818:
1817:
1816:
1805:
1800:
1796:
1791:
1785:
1781:
1774:
1771:
1767:
1763:
1760:
1756:
1753:
1750:
1747:
1743:
1739:
1736:
1732:
1729:
1726:
1722:
1719:
1716:
1713:
1709:
1706:
1703:
1688:
1687:
1676:
1671:
1667:
1662:
1656:
1652:
1645:
1642:
1638:
1634:
1631:
1627:
1624:
1621:
1618:
1614:
1610:
1607:
1602:
1597:
1594:
1591:
1586:
1583:
1580:
1577:
1573:
1570:
1567:
1543:
1540:
1537:
1533:
1530:
1527:
1517:(respectively
1506:
1503:
1500:
1496:
1493:
1490:
1469:
1438:
1435:
1432:
1429:
1426:
1403:
1400:
1396:
1392:
1389:
1385:
1382:
1379:
1358:
1355:
1352:
1349:
1346:
1321:
1317:
1310:
1307:
1303:
1299:
1296:
1292:
1270:
1266:
1259:
1256:
1252:
1248:
1245:
1241:
1230:
1229:
1218:
1212:
1207:
1201:
1197:
1193:
1190:
1187:
1183:
1177:
1173:
1167:
1164:
1160:
1156:
1153:
1150:
1147:
1144:
1141:
1137:
1133:
1130:
1125:
1120:
1117:
1114:
1089:
1086:
1083:
1080:
1077:
1063:
1062:
1051:
1048:
1044:
1040:
1037:
1032:
1027:
1024:
1021:
996:
970:
966:
954:
953:
942:
939:
936:
932:
928:
925:
920:
915:
912:
909:
866:
861:
851:(respectively
837:
832:
816:
815:
802:
798:
792:
789:
785:
781:
778:
775:
772:
767:
763:
757:
754:
750:
746:
743:
740:
737:
734:
711:
683:
679:
673:
670:
666:
662:
659:
656:
643:
642:
631:
628:
625:
622:
619:
604:
601:
562:
558:
554:
551:
548:
543:
539:
533:
529:
517:plactic monoid
513:
512:
501:
498:
495:
492:
489:
486:
483:
480:
477:
474:
471:
468:
465:
462:
459:
456:
452:
448:
445:
442:
439:
421:
420:
409:
406:
403:
400:
397:
393:
389:
386:
383:
380:
357:
352:
348:
344:
339:
335:
331:
328:
325:
320:
316:
312:
307:
303:
299:
296:
293:
210:
162:
159:
154:representation
82:
81:
39:
37:
30:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1915:
1904:
1901:
1900:
1898:
1888:
1887:0-387-97965-4
1884:
1880:
1876:
1873:
1870:
1869:3-11-015248-7
1866:
1862:
1858:
1856:
1855:0-19-851194-9
1852:
1848:
1844:
1843:
1839:
1829:
1826:
1819:
1803:
1798:
1794:
1789:
1783:
1772:
1769:
1765:
1761:
1758:
1751:
1737:
1720:
1714:
1693:
1692:
1691:
1674:
1669:
1665:
1660:
1654:
1643:
1640:
1636:
1632:
1629:
1622:
1608:
1600:
1584:
1578:
1557:
1556:
1555:
1538:
1501:
1467:
1459:
1455:
1450:
1433:
1430:
1427:
1416:
1398:
1390:
1353:
1350:
1347:
1337:
1319:
1308:
1305:
1301:
1297:
1294:
1268:
1257:
1254:
1250:
1246:
1243:
1216:
1199:
1195:
1191:
1188:
1181:
1175:
1165:
1162:
1158:
1154:
1151:
1145:
1139:
1131:
1123:
1103:
1102:
1101:
1084:
1081:
1078:
1067:
1046:
1038:
1030:
1010:
1009:
1008:
994:
986:
968:
964:
940:
934:
926:
918:
898:
897:
896:
893:
891:
887:
883:
859:
830:
821:
800:
790:
787:
783:
779:
776:
770:
765:
755:
752:
748:
744:
741:
735:
732:
725:
724:
723:
709:
701:
696:
681:
671:
668:
664:
660:
657:
646:
626:
623:
620:
610:
609:
608:
602:
600:
598:
594:
590:
586:
582:
578:
575:for integers
560:
552:
549:
541:
537:
531:
527:
518:
496:
493:
490:
487:
484:
481:
478:
475:
472:
469:
466:
463:
460:
457:
454:
446:
443:
440:
430:
429:
428:
426:
404:
401:
398:
395:
387:
384:
381:
371:
370:
369:
350:
346:
342:
337:
333:
329:
326:
323:
318:
314:
310:
305:
301:
294:
291:
278:
271:
267:
263:
259:
251:
247:
243:
239:
217:
213:
208:
201:
191:
187:
181:
179:
168:
160:
158:
156:
155:
150:
145:
143:
138:
136:
132:
128:
113:
105:
101:
97:
93:
89:
78:
75:
67:
57:
56:the talk page
53:
47:
45:
40:This article
38:
29:
28:
19:
1878:
1860:
1846:
1828:
1689:
1457:
1453:
1451:
1414:
1335:
1334:we obtain a
1231:
1065:
1064:
955:
894:
889:
817:
697:
647:
644:
606:
596:
592:
588:
584:
580:
576:
514:
422:
279:
269:
265:
261:
257:
249:
245:
241:
237:
215:
211:
206:
204:by defining
199:
189:
185:
182:
180:as follows:
164:
161:Construction
152:
149:presentation
148:
146:
139:
135:group theory
95:
91:
85:
70:
61:
50:Please help
41:
112:free monoid
1840:References
886:congruence
64:March 2011
46:to readers
1795:ρ
1770:−
1762:∪
1749:⟩
1746:∅
1735:⟨
1666:ρ
1655:∗
1641:−
1633:∪
1620:⟩
1617:∅
1606:⟨
1415:presented
1402:⟩
1388:⟨
1306:−
1298:∪
1269:∗
1255:−
1247:∪
1196:ρ
1192:∪
1176:∗
1163:−
1155:∪
1143:⟩
1129:⟨
1066:presented
1050:⟩
1036:⟨
965:ρ
938:⟩
924:⟨
801:∗
788:−
780:∪
771:×
766:∗
753:−
745:∪
736:⊆
682:∗
669:−
661:∪
500:⟩
438:⟨
408:⟩
379:⟨
327:…
104:semigroup
1897:Category
127:quotient
983:be the
698:is the
515:is the
202:⊂ Σ × Σ
88:algebra
42:may be
1885:
1867:
1853:
880:) the
820:binary
722:, and
645:where
427:, and
102:(or a
100:monoid
94:(or a
1820:Notes
1460:) on
1283:with
818:is a
254:with
1883:ISBN
1865:ISBN
1851:ISBN
1456:(or
956:Let
595:and
264:) ∈
227:and
90:, a
1690:or
1417:by
1100:as
1068:by
987:on
702:on
252:∈ Σ
233:svt
225:sut
193:of
172:on
133:in
86:In
1899::
1449:.
892:.
599:.
589:ba
583:,
579:,
268:∪
248:,
244:,
240:,
231:=
223:=
188:∪
157:.
147:A
137:.
1871:.
1804:.
1799:X
1790:/
1784:+
1780:)
1773:1
1766:X
1759:X
1755:(
1752:=
1742:|
1738:X
1731:v
1728:n
1725:I
1721:=
1718:)
1715:X
1712:(
1708:S
1705:I
1702:F
1675:,
1670:X
1661:/
1651:)
1644:1
1637:X
1630:X
1626:(
1623:=
1613:|
1609:X
1601:1
1596:v
1593:n
1590:I
1585:=
1582:)
1579:X
1576:(
1572:M
1569:I
1566:F
1542:)
1539:X
1536:(
1532:S
1529:I
1526:F
1505:)
1502:X
1499:(
1495:M
1492:I
1489:F
1468:X
1437:)
1434:T
1431:;
1428:X
1425:(
1399:T
1395:|
1391:X
1384:v
1381:n
1378:I
1357:)
1354:T
1351:;
1348:X
1345:(
1320:+
1316:)
1309:1
1302:X
1295:X
1291:(
1265:)
1258:1
1251:X
1244:X
1240:(
1217:.
1211:c
1206:)
1200:X
1189:T
1186:(
1182:/
1172:)
1166:1
1159:X
1152:X
1149:(
1146:=
1140:T
1136:|
1132:X
1124:1
1119:v
1116:n
1113:I
1088:)
1085:T
1082:;
1079:X
1076:(
1047:T
1043:|
1039:X
1031:1
1026:v
1023:n
1020:I
995:X
969:X
941:.
935:T
931:|
927:X
919:1
914:v
911:n
908:I
890:T
865:c
860:T
836:e
831:T
797:)
791:1
784:X
777:X
774:(
762:)
756:1
749:X
742:X
739:(
733:T
710:X
678:)
672:1
665:X
658:X
655:(
630:)
627:T
624:;
621:X
618:(
597:b
593:a
585:k
581:j
577:i
561:k
557:)
553:a
550:b
547:(
542:j
538:b
532:i
528:a
497:b
494:a
491:b
488:=
485:a
482:b
479:b
476:,
473:a
470:a
467:b
464:=
461:a
458:b
455:a
451:|
447:b
444:,
441:a
405:1
402:=
399:q
396:p
392:|
388:q
385:,
382:p
356:}
351:n
347:v
343:=
338:n
334:u
330:,
324:,
319:1
315:v
311:=
306:1
302:u
298:{
295:=
292:R
282:R
275:E
270:R
266:R
262:v
260:,
258:u
256:(
250:t
246:s
242:v
238:u
229:y
221:x
216:y
212:E
209:~
207:x
200:E
195:R
190:R
186:R
174:Σ
170:R
123:Σ
119:Σ
115:Σ
108:Σ
77:)
71:(
66:)
62:(
58:.
48:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.