462:
of the semigroup operation, and means that all parentheses can be omitted. It is common practice, especially in computer science, to omit the operations as well so that both the semigroup operation and the action are indicated by juxtaposition. In this way
1214:
1043:
1852:
1599:
3300:
2672:
128:. This is a semigroup of transformations of a set, and hence it has a tautological action on that set. This concept is linked to the more general notion of a semigroup by an analogue of
1309:
951:
3479:
3081:
2225:
2055:
1069:
591:
2259:
1951:
1115:
1428:
757:
843:
2298:
2121:
987:
3119:
2508:
1107:
2470:
1484:
2803:
2762:
2549:
1773:
675:
3164:
2991:
2966:
2941:
2896:
2717:
1536:
1510:
649:
2148:
2082:
2001:
1884:
1727:
3204:
3184:
3139:
3011:
2916:
2871:
2843:
2823:
2692:
2616:
2596:
2576:
2420:
2400:
2380:
2360:
2340:
2188:
2168:
2021:
1974:
1904:
1793:
1747:
1353:
1333:
1277:
1257:
1237:
886:
866:
780:
715:
695:
614:
550:
136:(A note on terminology: the terminology used in this area varies, sometimes significantly, from one author to another. See the article for details.)
3650:
3630:
3615:
3596:
3581:
502:
It is also quite common to work with right acts rather than left acts. However, every right S-act can be interpreted as a left act over the
2322:
Any transformation semigroup can be turned into a semigroup action by the following construction. For any transformation semigroup
370:
can be made into monoid act by adjoining an identity to the semigroup and requiring that it acts as the identity transformation on
3310:
992:
1801:
31:
84:: the set models the state of the automaton and the action models transformations of that state in response to inputs.
119:. This immediately provides a generalization to monoid acts on objects in categories other than the category of sets.
2918:
is faithful, then we forget nothing important. This claim is made precise by the following observation: if we turn
239:
73:
3267:
2315:
A correspondence between transformation semigroups and semigroup actions is described below. If we restrict it to
64:
of the two corresponding transformations. The terminology conveys the idea that the elements of the semigroup are
3645:
532:
It is often convenient (for instance if there is more than one act under consideration) to use a letter, such as
464:
53:
351:. This correspondingly gives a monoid homomorphism. Right monoid actions are defined in a similar way. A monoid
3385:
2310:
1282:
894:
124:
3490:
3425:
1549:
1209:{\displaystyle \operatorname {curry} (T)(s*t)=\operatorname {curry} (T)(s)\circ \operatorname {curry} (T)(t).}
3499:, gives powerful decomposition results for finite transformation semigroups by cascading simpler components.
2621:
2196:
2026:
1054:
558:
104:
3419:
of strings generated by the alphabet Σ, and the action of strings extends the action of Σ via the property
2230:
1909:
3206:. Thus, some authors see no distinction between faithful semigroup actions and transformation semigroups.
1312:
112:
524:, so the two notions are essentially equivalent. Here we primarily adopt the point of view of left acts.
429:. Some authors do not distinguish between semigroup and monoid actions, by regarding the identity axiom (
723:
3016:
788:
3226:
1666:
1396:
81:
61:
2264:
2087:
959:
3086:
2720:
2475:
1655:
1074:
129:
77:
69:
20:
506:, which has the same elements as S, but where multiplication is defined by reversing the factors,
2425:
1670:
1439:
108:
56:
of the set in such a way that the product of two elements of the semigroup (using the semigroup
3626:
3611:
3592:
3577:
3407:
2767:
2726:
2513:
1752:
654:
49:
1515:
1489:
619:
181:
116:
100:
57:
2126:
2060:
1979:
1857:
1700:
3230:
2316:
3144:
2971:
2946:
2921:
2876:
2697:
3565:
3189:
3169:
3124:
2996:
2901:
2856:
2828:
2808:
2677:
2601:
2581:
2561:
2405:
2385:
2365:
2345:
2325:
2173:
2153:
2006:
1959:
1889:
1778:
1732:
1338:
1318:
1262:
1242:
1222:
871:
851:
765:
700:
680:
599:
535:
3639:
3569:
3220:
459:
80:. From the computer science point of view, semigroup actions are closely related to
3225:
Transformation semigroups are of essential importance for the structure theory of
3515:
The monoid operation is concatenation; the identity element is the empty string.
3416:
2850:
3604:
Monoids, Acts and
Categories: with Applications to Wreath Products and Graphs
2846:
2552:
243:
44:
250:. Right semigroup actions are defined in a similar way using an operation
1047:
72:
perspective, a semigroup action is a generalization of the notion of a
27:
96:
443:) as empty when there is no identity element, or by using the term
115:
with one object, and an act is a functor from that category to the
1071:
is a bijection, semigroup actions can be defined as functions
52:
is a rule which associates to each element of the semigroup a
3401:). This semigroup is a monoid, so this monoid is called the
3313:
by ignoring the initial state and the set of accept states.
394:
acts as above (on the left, say) is also known as a (left)
19:"S-set" redirects here. For the suburban train fleet, see
3602:
Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev (2000),
1775:. The action property holds due to the associativity of
3555:
Algebraic Theory of
Machines, Languages, and Semigroups
1038:{\displaystyle \operatorname {curry} (T):S\to (X\to X)}
3428:
3270:
3192:
3172:
3147:
3127:
3089:
3019:
2999:
2974:
2949:
2924:
2904:
2879:
2859:
2831:
2811:
2770:
2729:
2700:
2680:
2624:
2604:
2584:
2564:
2516:
2478:
2428:
2408:
2388:
2368:
2348:
2328:
2267:
2233:
2199:
2176:
2156:
2129:
2090:
2063:
2029:
2009:
1982:
1962:
1912:
1892:
1860:
1804:
1781:
1755:
1735:
1703:
1552:
1518:
1492:
1442:
1399:
1341:
1321:
1285:
1265:
1245:
1225:
1118:
1077:
1057:
995:
962:
897:
874:
854:
791:
768:
726:
703:
683:
657:
622:
602:
561:
538:
238:
This is the analogue in semigroup theory of a (left)
1847:{\displaystyle F\colon (S,*)\rightarrow (T,\oplus )}
1646:-homomorphisms. The corresponding category of right
458:
The defining property of an act is analogous to the
3557:. New York and London: Academic Press. p. 83.
3473:
3294:
3198:
3178:
3158:
3133:
3113:
3075:
3005:
2985:
2960:
2935:
2910:
2890:
2865:
2837:
2817:
2797:
2756:
2711:
2686:
2666:
2610:
2590:
2570:
2543:
2510:. This action is faithful, which is equivalent to
2502:
2464:
2414:
2394:
2374:
2354:
2334:
2292:
2253:
2219:
2182:
2162:
2142:
2115:
2076:
2049:
2015:
1995:
1968:
1945:
1898:
1878:
1846:
1787:
1767:
1741:
1721:
1593:
1530:
1504:
1478:
1422:
1347:
1327:
1303:
1271:
1251:
1231:
1208:
1101:
1063:
1037:
981:
945:
880:
860:
837:
774:
751:
709:
689:
669:
643:
608:
585:
544:
1798:More generally, for any semigroup homomorphism
1615:a monoid, are defined in exactly the same way.
3534:Kilp, Knauer and Mikhalev, 2000, pages 43–44.
1638:-acts are the objects of a category, denoted
8:
3411:. It is also sometimes viewed as a Σ-act on
3366:). Then the semigroup of transformations of
3295:{\displaystyle T\colon \Sigma \times X\to X}
2661:
2636:
3591:, volume 2. American Mathematical Society,
3576:, volume 1. American Mathematical Society,
3495:Krohn–Rhodes theory, sometimes also called
2674:. In this construction we "forget" the set
2319:semigroup actions, it has nice properties.
355:with an action on a set is also called an
3587:A. H. Clifford and G. B. Preston (1967),
3462:
3449:
3433:
3427:
3269:
3245:), where Σ is a non-empty set called the
3191:
3171:
3146:
3126:
3088:
3018:
2998:
2973:
2948:
2923:
2903:
2878:
2858:
2830:
2810:
2769:
2728:
2699:
2679:
2643:
2623:
2603:
2583:
2563:
2515:
2477:
2427:
2407:
2387:
2367:
2347:
2327:
2284:
2266:
2238:
2237:
2232:
2204:
2203:
2198:
2175:
2155:
2134:
2128:
2107:
2089:
2068:
2062:
2034:
2033:
2028:
2008:
1987:
1981:
1961:
1911:
1891:
1859:
1803:
1780:
1754:
1734:
1702:
1565:
1554:
1551:
1517:
1491:
1441:
1398:
1340:
1320:
1304:{\displaystyle \operatorname {curry} (T)}
1284:
1264:
1244:
1224:
1117:
1076:
1056:
994:
973:
961:
946:{\displaystyle T_{s*t}=T_{s}\circ T_{t}.}
934:
921:
902:
896:
873:
853:
796:
790:
767:
731:
725:
702:
682:
656:
621:
601:
560:
537:
3474:{\displaystyle T_{vw}=T_{w}\circ T_{v}.}
1594:{\displaystyle \mathrm {Hom} _{S}(X,X')}
16:An action or act of a semigroup on a set
3527:
3508:
2667:{\displaystyle S'=\{T_{s}\mid s\in S\}}
2003:be the set of sequences of elements of
180:which is compatible with the semigroup
68:as transformations of the set. From an
2220:{\displaystyle (\mathbb {N} ,\times )}
2050:{\displaystyle (\mathbb {N} ,\times )}
1546:-homomorphisms is commonly written as
1064:{\displaystyle \operatorname {curry} }
586:{\displaystyle T\colon S\times X\to X}
2558:Conversely, for any semigroup action
2254:{\displaystyle (\mathbb {N} ,\cdot )}
1946:{\displaystyle s\cdot t=F(s)\oplus t}
1335:to the full transformation monoid of
386:is a semigroup or monoid, then a set
7:
2618:, define a transformation semigroup
122:Another important special case is a
3589:The Algebraic Theory of Semigroups
3574:The Algebraic Theory of Semigroups
3337:∈ Σ, denote the transformation of
3277:
1650:-acts is sometimes denoted by Act-
1561:
1558:
1555:
752:{\displaystyle T_{s}\colon X\to X}
316:with the additional property that
14:
3186:, i.e., we essentially recovered
3076:{\displaystyle T'(f(s),x)=T(s,x)}
3543:Kilp, Knauer and Mikhalev, 2000.
3210:Applications to computer science
838:{\displaystyle T_{s}(x)=T(s,x).}
312:is a (left) semigroup action of
3553:Arbib, Michael A., ed. (1968).
1423:{\displaystyle F\colon X\to X'}
848:By the defining property of an
87:An important special case is a
3286:
3253:is a non-empty set called the
3070:
3058:
3049:
3040:
3034:
3028:
2792:
2786:
2751:
2745:
2538:
2532:
2459:
2453:
2444:
2432:
2293:{\displaystyle x\cdot y=x^{y}}
2248:
2234:
2214:
2200:
2116:{\displaystyle n\cdot s=s^{n}}
2044:
2030:
1934:
1928:
1873:
1861:
1841:
1829:
1826:
1823:
1811:
1716:
1704:
1642:-Act, whose morphisms are the
1588:
1571:
1473:
1467:
1455:
1446:
1409:
1298:
1292:
1200:
1194:
1191:
1185:
1173:
1167:
1164:
1158:
1146:
1134:
1131:
1125:
1096:
1090:
1084:
1081:
1032:
1026:
1020:
1017:
1008:
1002:
982:{\displaystyle s\mapsto T_{s}}
966:
829:
817:
808:
802:
743:
638:
626:
577:
149:be a semigroup. Then a (left)
95:, in which the semigroup is a
1:
3621:Rudolf Lidl and Günter Pilz,
3610:, Walter de Gruyter, Berlin,
3606:, Expositions in Mathematics
3114:{\displaystyle s\in S,x\in X}
2943:back into a semigroup action
2503:{\displaystyle s\in S,x\in X}
1688:are defined in the same way.
1102:{\displaystyle S\to (X\to X)}
956:Further, consider a function
246:into the set of functions on
111:point of view, a monoid is a
3651:Theoretical computer science
2362:, define a semigroup action
1654:. (This is analogous to the
32:theoretical computer science
3316:Given a semiautomaton, let
2465:{\displaystyle T(s,x)=s(x)}
1479:{\displaystyle F(sx)=sF(x)}
347:is the identity element of
300:is a monoid, then a (left)
165:together with an operation
3667:
3488:
3309:. Semiautomata arise from
3218:
2308:
103:of the monoid acts as the
18:
3497:algebraic automata theory
2849:, then it is a semigroup
2305:Transformation semigroups
1239:is a semigroup action of
552:, to denote the function
242:, and is equivalent to a
60:) is associated with the
3623:Applied Abstract Algebra
3386:characteristic semigroup
2798:{\displaystyle curry(T)}
2757:{\displaystyle curry(T)}
2544:{\displaystyle curry(T)}
2311:Transformation semigroup
1768:{\displaystyle \cdot =*}
670:{\displaystyle s\cdot x}
616:-action and hence write
528:Acts and transformations
378:Terminology and notation
125:transformation semigroup
475:, as in the expression
455:-act with an identity.
105:identity transformation
3475:
3311:deterministic automata
3296:
3200:
3180:
3160:
3135:
3115:
3077:
3007:
2987:
2962:
2937:
2912:
2892:
2867:
2839:
2819:
2799:
2758:
2713:
2688:
2668:
2612:
2592:
2572:
2545:
2504:
2466:
2416:
2396:
2376:
2356:
2336:
2294:
2255:
2221:
2184:
2164:
2144:
2117:
2078:
2051:
2017:
1997:
1970:
1947:
1900:
1880:
1848:
1789:
1769:
1743:
1723:
1630:For a fixed semigroup
1595:
1532:
1531:{\displaystyle x\in X}
1506:
1505:{\displaystyle s\in S}
1480:
1424:
1349:
1329:
1313:semigroup homomorphism
1305:
1273:
1253:
1233:
1210:
1103:
1065:
1039:
983:
947:
882:
862:
839:
776:
762:the transformation of
753:
711:
691:
671:
645:
644:{\displaystyle T(s,x)}
610:
587:
546:
362:A semigroup action of
244:semigroup homomorphism
3476:
3297:
3227:finite state machines
3201:
3181:
3166:are "isomorphic" via
3161:
3136:
3116:
3078:
3008:
2988:
2963:
2938:
2913:
2898:. In other words, if
2893:
2868:
2840:
2820:
2800:
2759:
2714:
2689:
2669:
2613:
2593:
2573:
2546:
2505:
2467:
2417:
2397:
2377:
2357:
2337:
2295:
2256:
2222:
2185:
2165:
2145:
2143:{\displaystyle s^{n}}
2118:
2079:
2077:{\displaystyle X^{*}}
2052:
2018:
1998:
1996:{\displaystyle X^{*}}
1971:
1948:
1901:
1881:
1879:{\displaystyle (S,*)}
1849:
1790:
1770:
1744:
1724:
1722:{\displaystyle (S,*)}
1596:
1533:
1507:
1481:
1425:
1350:
1330:
1306:
1274:
1254:
1234:
1211:
1104:
1066:
1040:
984:
948:
883:
863:
840:
777:
754:
712:
692:
672:
646:
611:
588:
547:
3426:
3268:
3190:
3170:
3145:
3125:
3087:
3017:
2997:
2972:
2947:
2922:
2902:
2877:
2857:
2829:
2809:
2768:
2727:
2698:
2678:
2622:
2602:
2582:
2562:
2514:
2476:
2426:
2406:
2386:
2366:
2346:
2326:
2265:
2231:
2197:
2174:
2154:
2127:
2088:
2061:
2027:
2007:
1980:
1960:
1910:
1890:
1858:
1802:
1779:
1753:
1733:
1701:
1550:
1542:The set of all such
1516:
1490:
1440:
1397:
1339:
1319:
1283:
1263:
1243:
1223:
1116:
1075:
1055:
993:
989:. It is the same as
960:
895:
872:
852:
789:
766:
724:
701:
681:
655:
620:
600:
559:
536:
3491:Krohn–Rhodes theory
3485:Krohn–Rhodes theory
3383:∈ Σ} is called the
3307:transition function
3233:. In particular, a
2227:has a right action
1382:-homomorphism from
21:Sydney Trains S set
3625:(1998), Springer,
3471:
3292:
3196:
3176:
3159:{\displaystyle T'}
3156:
3131:
3111:
3073:
3003:
2986:{\displaystyle S'}
2983:
2961:{\displaystyle T'}
2958:
2936:{\displaystyle S'}
2933:
2908:
2891:{\displaystyle S'}
2888:
2863:
2835:
2815:
2795:
2754:
2712:{\displaystyle S'}
2709:
2684:
2664:
2608:
2588:
2568:
2541:
2500:
2462:
2412:
2392:
2372:
2352:
2332:
2290:
2251:
2217:
2180:
2160:
2140:
2113:
2074:
2047:
2013:
1993:
1966:
1943:
1896:
1876:
1844:
1785:
1765:
1739:
1719:
1665:of left and right
1607:-homomorphisms of
1591:
1528:
1502:
1476:
1420:
1345:
1325:
1301:
1269:
1249:
1229:
1206:
1099:
1061:
1035:
979:
943:
878:
858:
835:
772:
749:
707:
687:
667:
641:
606:
583:
542:
504:opposite semigroup
141:Formal definitions
109:category theoretic
3631:978-0-387-98290-8
3616:978-3-11-015248-7
3597:978-0-8218-0272-4
3582:978-0-8218-0272-4
3415:, where Σ is the
3408:transition monoid
3391:transition system
3199:{\displaystyle T}
3179:{\displaystyle f}
3134:{\displaystyle T}
3006:{\displaystyle X}
2911:{\displaystyle T}
2866:{\displaystyle S}
2838:{\displaystyle f}
2818:{\displaystyle f}
2687:{\displaystyle S}
2611:{\displaystyle X}
2591:{\displaystyle S}
2571:{\displaystyle T}
2415:{\displaystyle X}
2395:{\displaystyle S}
2375:{\displaystyle T}
2355:{\displaystyle X}
2335:{\displaystyle S}
2183:{\displaystyle n}
2163:{\displaystyle s}
2057:has an action on
2016:{\displaystyle X}
1969:{\displaystyle X}
1899:{\displaystyle T}
1886:has an action on
1788:{\displaystyle *}
1742:{\displaystyle S}
1729:has an action on
1680:, the categories
1348:{\displaystyle X}
1328:{\displaystyle S}
1272:{\displaystyle X}
1252:{\displaystyle S}
1232:{\displaystyle T}
881:{\displaystyle T}
861:{\displaystyle S}
775:{\displaystyle X}
710:{\displaystyle S}
690:{\displaystyle s}
609:{\displaystyle S}
545:{\displaystyle T}
107:of a set. From a
3658:
3646:Semigroup theory
3559:
3558:
3550:
3544:
3541:
3535:
3532:
3516:
3513:
3480:
3478:
3477:
3472:
3467:
3466:
3454:
3453:
3441:
3440:
3301:
3299:
3298:
3293:
3205:
3203:
3202:
3197:
3185:
3183:
3182:
3177:
3165:
3163:
3162:
3157:
3155:
3140:
3138:
3137:
3132:
3120:
3118:
3117:
3112:
3082:
3080:
3079:
3074:
3027:
3012:
3010:
3009:
3004:
2992:
2990:
2989:
2984:
2982:
2967:
2965:
2964:
2959:
2957:
2942:
2940:
2939:
2934:
2932:
2917:
2915:
2914:
2909:
2897:
2895:
2894:
2889:
2887:
2872:
2870:
2869:
2864:
2844:
2842:
2841:
2836:
2825:for brevity. If
2824:
2822:
2821:
2816:
2804:
2802:
2801:
2796:
2764:. Let us denote
2763:
2761:
2760:
2755:
2719:is equal to the
2718:
2716:
2715:
2710:
2708:
2693:
2691:
2690:
2685:
2673:
2671:
2670:
2665:
2648:
2647:
2632:
2617:
2615:
2614:
2609:
2597:
2595:
2594:
2589:
2577:
2575:
2574:
2569:
2550:
2548:
2547:
2542:
2509:
2507:
2506:
2501:
2471:
2469:
2468:
2463:
2421:
2419:
2418:
2413:
2401:
2399:
2398:
2393:
2381:
2379:
2378:
2373:
2361:
2359:
2358:
2353:
2341:
2339:
2338:
2333:
2299:
2297:
2296:
2291:
2289:
2288:
2260:
2258:
2257:
2252:
2241:
2226:
2224:
2223:
2218:
2207:
2189:
2187:
2186:
2181:
2169:
2167:
2166:
2161:
2149:
2147:
2146:
2141:
2139:
2138:
2122:
2120:
2119:
2114:
2112:
2111:
2083:
2081:
2080:
2075:
2073:
2072:
2056:
2054:
2053:
2048:
2037:
2023:. The semigroup
2022:
2020:
2019:
2014:
2002:
2000:
1999:
1994:
1992:
1991:
1975:
1973:
1972:
1967:
1952:
1950:
1949:
1944:
1905:
1903:
1902:
1897:
1885:
1883:
1882:
1877:
1854:, the semigroup
1853:
1851:
1850:
1845:
1794:
1792:
1791:
1786:
1774:
1772:
1771:
1766:
1748:
1746:
1745:
1740:
1728:
1726:
1725:
1720:
1600:
1598:
1597:
1592:
1587:
1570:
1569:
1564:
1537:
1535:
1534:
1529:
1511:
1509:
1508:
1503:
1485:
1483:
1482:
1477:
1429:
1427:
1426:
1421:
1419:
1354:
1352:
1351:
1346:
1334:
1332:
1331:
1326:
1310:
1308:
1307:
1302:
1278:
1276:
1275:
1270:
1258:
1256:
1255:
1250:
1238:
1236:
1235:
1230:
1215:
1213:
1212:
1207:
1108:
1106:
1105:
1100:
1070:
1068:
1067:
1062:
1044:
1042:
1041:
1036:
988:
986:
985:
980:
978:
977:
952:
950:
949:
944:
939:
938:
926:
925:
913:
912:
887:
885:
884:
879:
867:
865:
864:
859:
844:
842:
841:
836:
801:
800:
781:
779:
778:
773:
758:
756:
755:
750:
736:
735:
716:
714:
713:
708:
696:
694:
693:
688:
676:
674:
673:
668:
650:
648:
647:
642:
615:
613:
612:
607:
592:
590:
589:
584:
551:
549:
548:
543:
523:
467:of letters from
442:
292:
264:
233:
179:
151:semigroup action
130:Cayley's theorem
117:category of sets
101:identity element
3666:
3665:
3661:
3660:
3659:
3657:
3656:
3655:
3636:
3635:
3562:
3552:
3551:
3547:
3542:
3538:
3533:
3529:
3525:
3520:
3519:
3514:
3510:
3505:
3493:
3487:
3458:
3445:
3429:
3424:
3423:
3378:
3349:
3324:
3266:
3265:
3237:is a triple (Σ,
3231:automata theory
3223:
3217:
3212:
3188:
3187:
3168:
3167:
3148:
3143:
3142:
3123:
3122:
3085:
3084:
3020:
3015:
3014:
2995:
2994:
2975:
2970:
2969:
2950:
2945:
2944:
2925:
2920:
2919:
2900:
2899:
2880:
2875:
2874:
2855:
2854:
2827:
2826:
2807:
2806:
2766:
2765:
2725:
2724:
2701:
2696:
2695:
2676:
2675:
2639:
2625:
2620:
2619:
2600:
2599:
2580:
2579:
2560:
2559:
2512:
2511:
2474:
2473:
2424:
2423:
2404:
2403:
2384:
2383:
2364:
2363:
2344:
2343:
2324:
2323:
2313:
2307:
2280:
2263:
2262:
2229:
2228:
2195:
2194:
2172:
2171:
2152:
2151:
2130:
2125:
2124:
2103:
2086:
2085:
2064:
2059:
2058:
2025:
2024:
2005:
2004:
1983:
1978:
1977:
1958:
1957:
1908:
1907:
1888:
1887:
1856:
1855:
1800:
1799:
1777:
1776:
1751:
1750:
1731:
1730:
1699:
1698:
1694:
1628:
1580:
1553:
1548:
1547:
1514:
1513:
1488:
1487:
1438:
1437:
1412:
1395:
1394:
1378:-acts. Then an
1364:
1337:
1336:
1317:
1316:
1281:
1280:
1279:if and only if
1261:
1260:
1241:
1240:
1221:
1220:
1114:
1113:
1073:
1072:
1053:
1052:
991:
990:
969:
958:
957:
930:
917:
898:
893:
892:
870:
869:
850:
849:
792:
787:
786:
764:
763:
727:
722:
721:
717:, we denote by
699:
698:
679:
678:
677:. Then for any
653:
652:
618:
617:
598:
597:
557:
556:
534:
533:
530:
507:
430:
380:
357:operator monoid
266:
251:
209:
166:
143:
24:
17:
12:
11:
5:
3664:
3662:
3654:
3653:
3648:
3638:
3637:
3634:
3633:
3619:
3600:
3585:
3566:A. H. Clifford
3561:
3560:
3545:
3536:
3526:
3524:
3521:
3518:
3517:
3507:
3506:
3504:
3501:
3489:Main article:
3486:
3483:
3482:
3481:
3470:
3465:
3461:
3457:
3452:
3448:
3444:
3439:
3436:
3432:
3403:characteristic
3374:
3370:generated by {
3345:
3320:
3303:
3302:
3291:
3288:
3285:
3282:
3279:
3276:
3273:
3261:is a function
3247:input alphabet
3219:Main article:
3216:
3213:
3211:
3208:
3195:
3175:
3154:
3151:
3130:
3110:
3107:
3104:
3101:
3098:
3095:
3092:
3072:
3069:
3066:
3063:
3060:
3057:
3054:
3051:
3048:
3045:
3042:
3039:
3036:
3033:
3030:
3026:
3023:
3002:
2981:
2978:
2956:
2953:
2931:
2928:
2907:
2886:
2883:
2862:
2834:
2814:
2794:
2791:
2788:
2785:
2782:
2779:
2776:
2773:
2753:
2750:
2747:
2744:
2741:
2738:
2735:
2732:
2707:
2704:
2683:
2663:
2660:
2657:
2654:
2651:
2646:
2642:
2638:
2635:
2631:
2628:
2607:
2587:
2567:
2540:
2537:
2534:
2531:
2528:
2525:
2522:
2519:
2499:
2496:
2493:
2490:
2487:
2484:
2481:
2461:
2458:
2455:
2452:
2449:
2446:
2443:
2440:
2437:
2434:
2431:
2411:
2391:
2371:
2351:
2331:
2309:Main article:
2306:
2303:
2302:
2301:
2287:
2283:
2279:
2276:
2273:
2270:
2250:
2247:
2244:
2240:
2236:
2216:
2213:
2210:
2206:
2202:
2193:The semigroup
2191:
2179:
2159:
2137:
2133:
2110:
2106:
2102:
2099:
2096:
2093:
2071:
2067:
2046:
2043:
2040:
2036:
2032:
2012:
1990:
1986:
1965:
1954:
1942:
1939:
1936:
1933:
1930:
1927:
1924:
1921:
1918:
1915:
1895:
1875:
1872:
1869:
1866:
1863:
1843:
1840:
1837:
1834:
1831:
1828:
1825:
1822:
1819:
1816:
1813:
1810:
1807:
1796:
1784:
1764:
1761:
1758:
1738:
1718:
1715:
1712:
1709:
1706:
1697:Any semigroup
1693:
1690:
1627:
1617:
1590:
1586:
1583:
1579:
1576:
1573:
1568:
1563:
1560:
1557:
1540:
1539:
1527:
1524:
1521:
1501:
1498:
1495:
1475:
1472:
1469:
1466:
1463:
1460:
1457:
1454:
1451:
1448:
1445:
1431:
1430:
1418:
1415:
1411:
1408:
1405:
1402:
1363:
1362:-homomorphisms
1357:
1344:
1324:
1300:
1297:
1294:
1291:
1288:
1268:
1248:
1228:
1217:
1216:
1205:
1202:
1199:
1196:
1193:
1190:
1187:
1184:
1181:
1178:
1175:
1172:
1169:
1166:
1163:
1160:
1157:
1154:
1151:
1148:
1145:
1142:
1139:
1136:
1133:
1130:
1127:
1124:
1121:
1109:which satisfy
1098:
1095:
1092:
1089:
1086:
1083:
1080:
1060:
1034:
1031:
1028:
1025:
1022:
1019:
1016:
1013:
1010:
1007:
1004:
1001:
998:
976:
972:
968:
965:
954:
953:
942:
937:
933:
929:
924:
920:
916:
911:
908:
905:
901:
877:
857:
846:
845:
834:
831:
828:
825:
822:
819:
816:
813:
810:
807:
804:
799:
795:
771:
760:
759:
748:
745:
742:
739:
734:
730:
706:
686:
666:
663:
660:
640:
637:
634:
631:
628:
625:
605:
594:
593:
582:
579:
576:
573:
570:
567:
564:
541:
529:
526:
424:left act over
379:
376:
341:
340:
236:
235:
184:∗ as follows:
142:
139:
54:transformation
15:
13:
10:
9:
6:
4:
3:
2:
3663:
3652:
3649:
3647:
3644:
3643:
3641:
3632:
3628:
3624:
3620:
3617:
3613:
3609:
3605:
3601:
3598:
3594:
3590:
3586:
3583:
3579:
3575:
3571:
3570:G. B. Preston
3567:
3564:
3563:
3556:
3549:
3546:
3540:
3537:
3531:
3528:
3522:
3512:
3509:
3502:
3500:
3498:
3492:
3484:
3468:
3463:
3459:
3455:
3450:
3446:
3442:
3437:
3434:
3430:
3422:
3421:
3420:
3418:
3414:
3410:
3409:
3404:
3400:
3396:
3392:
3388:
3387:
3382:
3377:
3373:
3369:
3365:
3361:
3357:
3353:
3348:
3344:
3340:
3336:
3332:
3328:
3323:
3319:
3314:
3312:
3308:
3289:
3283:
3280:
3274:
3271:
3264:
3263:
3262:
3260:
3256:
3255:set of states
3252:
3248:
3244:
3240:
3236:
3235:semiautomaton
3232:
3228:
3222:
3221:Semiautomaton
3214:
3209:
3207:
3193:
3173:
3152:
3149:
3128:
3108:
3105:
3102:
3099:
3096:
3093:
3090:
3067:
3064:
3061:
3055:
3052:
3046:
3043:
3037:
3031:
3024:
3021:
3000:
2979:
2976:
2954:
2951:
2929:
2926:
2905:
2884:
2881:
2860:
2852:
2848:
2832:
2812:
2789:
2783:
2780:
2777:
2774:
2771:
2748:
2742:
2739:
2736:
2733:
2730:
2722:
2705:
2702:
2681:
2658:
2655:
2652:
2649:
2644:
2640:
2633:
2629:
2626:
2605:
2585:
2565:
2556:
2554:
2535:
2529:
2526:
2523:
2520:
2517:
2497:
2494:
2491:
2488:
2485:
2482:
2479:
2456:
2450:
2447:
2441:
2438:
2435:
2429:
2409:
2389:
2369:
2349:
2329:
2320:
2318:
2312:
2304:
2285:
2281:
2277:
2274:
2271:
2268:
2245:
2242:
2211:
2208:
2192:
2177:
2157:
2135:
2131:
2108:
2104:
2100:
2097:
2094:
2091:
2069:
2065:
2041:
2038:
2010:
1988:
1984:
1963:
1955:
1940:
1937:
1931:
1925:
1922:
1919:
1916:
1913:
1893:
1870:
1867:
1864:
1838:
1835:
1832:
1820:
1817:
1814:
1808:
1805:
1797:
1782:
1762:
1759:
1756:
1736:
1713:
1710:
1707:
1696:
1695:
1691:
1689:
1687:
1684:-Act and Act-
1683:
1679:
1676:For a monoid
1674:
1672:
1668:
1664:
1663:
1660:-Mod and Mod-
1659:
1653:
1649:
1645:
1641:
1637:
1633:
1625:
1621:
1618:
1616:
1614:
1610:
1606:
1602:
1584:
1581:
1577:
1574:
1566:
1545:
1525:
1522:
1519:
1499:
1496:
1493:
1470:
1464:
1461:
1458:
1452:
1449:
1443:
1436:
1435:
1434:
1416:
1413:
1406:
1403:
1400:
1393:
1392:
1391:
1389:
1385:
1381:
1377:
1373:
1369:
1361:
1358:
1356:
1342:
1322:
1314:
1295:
1289:
1286:
1266:
1246:
1226:
1203:
1197:
1188:
1182:
1179:
1176:
1170:
1161:
1155:
1152:
1149:
1143:
1140:
1137:
1128:
1122:
1119:
1112:
1111:
1110:
1093:
1087:
1078:
1058:
1050:
1049:
1029:
1023:
1014:
1011:
1005:
999:
996:
974:
970:
963:
940:
935:
931:
927:
922:
918:
914:
909:
906:
903:
899:
891:
890:
889:
875:
855:
832:
826:
823:
820:
814:
811:
805:
797:
793:
785:
784:
783:
769:
746:
740:
737:
732:
728:
720:
719:
718:
704:
684:
664:
661:
658:
635:
632:
629:
623:
603:
596:defining the
580:
574:
571:
568:
565:
562:
555:
554:
553:
539:
527:
525:
522:
518:
514:
510:
505:
500:
498:
494:
490:
486:
482:
478:
474:
470:
466:
461:
460:associativity
456:
454:
450:
448:
441:
437:
433:
428:
427:
421:
419:
414:
412:
407:
405:
400:
398:
393:
389:
385:
377:
375:
373:
369:
365:
360:
358:
354:
350:
346:
339:
335:
331:
327:
323:
319:
318:
317:
315:
311:
307:
303:
302:monoid action
299:
294:
290:
286:
282:
278:
274:
270:
263:
259:
255:
249:
245:
241:
232:
228:
224:
220:
216:
212:
207:
203:
199:
195:
191:
187:
186:
185:
183:
178:
174:
170:
164:
160:
156:
152:
148:
140:
138:
137:
133:
131:
127:
126:
120:
118:
114:
110:
106:
102:
98:
94:
90:
89:monoid action
85:
83:
79:
75:
71:
67:
63:
59:
55:
51:
47:
46:
41:
37:
33:
29:
22:
3622:
3607:
3603:
3588:
3573:
3554:
3548:
3539:
3530:
3511:
3496:
3494:
3412:
3406:
3402:
3398:
3394:
3390:
3384:
3380:
3375:
3371:
3367:
3363:
3359:
3355:
3351:
3346:
3342:
3338:
3334:
3330:
3326:
3321:
3317:
3315:
3306:
3304:
3258:
3254:
3250:
3246:
3242:
3238:
3234:
3224:
3215:Semiautomata
2557:
2321:
2314:
1956:For any set
1685:
1681:
1677:
1675:
1661:
1657:
1651:
1647:
1643:
1639:
1635:
1631:
1629:
1623:
1619:
1612:
1608:
1604:
1603:
1543:
1541:
1432:
1387:
1383:
1379:
1375:
1371:
1367:
1365:
1359:
1218:
1046:
955:
847:
761:
651:in place of
595:
531:
520:
516:
512:
508:
503:
501:
496:
492:
488:
484:
480:
476:
472:
468:
457:
452:
446:
444:
439:
435:
431:
425:
423:
417:
416:
410:
409:
403:
402:
396:
395:
391:
387:
383:
381:
371:
367:
363:
361:
356:
352:
348:
344:
342:
337:
333:
329:
325:
321:
313:
309:
305:
301:
297:
295:
288:
284:
280:
276:
272:
268:
261:
257:
253:
247:
240:group action
237:
230:
226:
222:
218:
214:
210:
205:
201:
197:
193:
189:
176:
172:
168:
162:
158:
154:
150:
146:
144:
135:
134:
123:
121:
92:
88:
86:
78:group theory
74:group action
65:
43:
39:
35:
25:
3417:free monoid
3341:defined by
3305:called the
2851:isomorphism
2261:, given by
1656:categories
1634:, the left
1611:-acts, for
1433:such that
1390:′ is a map
1051:). Because
782:defined by
265:satisfying
3640:Categories
3523:References
888:satisfies
3456:∘
3287:→
3281:×
3278:Σ
3275::
3106:∈
3094:∈
2847:injective
2656:∈
2650:∣
2553:injective
2495:∈
2483:∈
2272:⋅
2246:⋅
2212:×
2170:repeated
2095:⋅
2084:given by
2070:∗
2042:×
1989:∗
1938:⊕
1917:⋅
1906:given by
1871:∗
1839:⊕
1827:→
1821:∗
1809::
1783:∗
1763:∗
1757:⋅
1714:∗
1622:-Act and
1523:∈
1497:∈
1410:→
1404::
1290:
1219:That is,
1183:
1177:∘
1156:
1141:∗
1123:
1091:→
1082:→
1027:→
1018:→
1000:
967:↦
928:∘
907:∗
744:→
738::
662:⋅
578:→
572:×
566::
390:on which
252:• :
182:operation
167:• :
161:is a set
70:algebraic
62:composite
58:operation
45:semigroup
3572:(1961),
3379: :
3153:′
3083:for all
3025:′
2980:′
2955:′
2930:′
2885:′
2706:′
2630:′
2317:faithful
2150:denotes
1749:, where
1692:Examples
1585:′
1486:for all
1417:′
1048:Currying
445:unitary
420:-operand
320:for all
188:for all
113:category
99:and the
82:automata
3013:, then
2190:times).
2123:(where
1669:over a
1667:modules
471:act on
465:strings
451:for an
413:-action
28:algebra
3629:
3614:
3595:
3580:
3393:of (Σ,
3333:, for
2551:being
1976:, let
868:-act,
343:where
97:monoid
66:acting
36:action
3503:Notes
2853:from
2721:image
1374:′ be
1315:from
1311:is a
1287:curry
1180:curry
1153:curry
1120:curry
1059:curry
1045:(see
997:curry
422:, or
308:) of
221:) = (
157:) of
48:on a
42:of a
34:, an
3627:ISBN
3612:ISBN
3593:ISBN
3578:ISBN
3568:and
3354:) =
3257:and
3141:and
2472:for
1671:ring
1626:-Act
1512:and
1370:and
1366:Let
491:and
479:for
449:-act
406:-set
399:-act
304:(or
275:) •
229:) •
200:and
153:(or
145:Let
30:and
3405:or
3389:or
3229:in
2993:on
2968:of
2873:to
2845:is
2805:as
2723:of
2598:on
2578:of
2422:as
2402:on
2382:of
2342:of
1673:.)
1386:to
1259:on
697:in
495:in
487:in
477:stx
382:If
366:on
324:in
306:act
296:If
283:• (
213:• (
204:in
196:in
155:act
93:act
91:or
76:in
50:set
40:act
38:or
26:In
3642::
3608:29
3329:→
3325::
3249:,
3121:.
2694:.
2555:.
1601:.
1355:.
519:•
515:=
511:•
499:.
483:,
438:=
434:•
415:,
408:,
401:,
374:.
359:.
336:=
332:•
328::
293:.
287:∗
279:=
271:•
260:→
256:×
225:∗
217:•
208:,
192:,
175:→
171:×
132:.
3618:.
3599:.
3584:.
3469:.
3464:v
3460:T
3451:w
3447:T
3443:=
3438:w
3435:v
3431:T
3413:X
3399:T
3397:,
3395:X
3381:a
3376:a
3372:T
3368:X
3364:x
3362:,
3360:a
3358:(
3356:T
3352:x
3350:(
3347:a
3343:T
3339:X
3335:a
3331:X
3327:X
3322:a
3318:T
3290:X
3284:X
3272:T
3259:T
3251:X
3243:T
3241:,
3239:X
3194:T
3174:f
3150:T
3129:T
3109:X
3103:x
3100:,
3097:S
3091:s
3071:)
3068:x
3065:,
3062:s
3059:(
3056:T
3053:=
3050:)
3047:x
3044:,
3041:)
3038:s
3035:(
3032:f
3029:(
3022:T
3001:X
2977:S
2952:T
2927:S
2906:T
2882:S
2861:S
2833:f
2813:f
2793:)
2790:T
2787:(
2784:y
2781:r
2778:r
2775:u
2772:c
2752:)
2749:T
2746:(
2743:y
2740:r
2737:r
2734:u
2731:c
2703:S
2682:S
2662:}
2659:S
2653:s
2645:s
2641:T
2637:{
2634:=
2627:S
2606:X
2586:S
2566:T
2539:)
2536:T
2533:(
2530:y
2527:r
2524:r
2521:u
2518:c
2498:X
2492:x
2489:,
2486:S
2480:s
2460:)
2457:x
2454:(
2451:s
2448:=
2445:)
2442:x
2439:,
2436:s
2433:(
2430:T
2410:X
2390:S
2370:T
2350:X
2330:S
2300:.
2286:y
2282:x
2278:=
2275:y
2269:x
2249:)
2243:,
2239:N
2235:(
2215:)
2209:,
2205:N
2201:(
2178:n
2158:s
2136:n
2132:s
2109:n
2105:s
2101:=
2098:s
2092:n
2066:X
2045:)
2039:,
2035:N
2031:(
2011:X
1985:X
1964:X
1953:.
1941:t
1935:)
1932:s
1929:(
1926:F
1923:=
1920:t
1914:s
1894:T
1874:)
1868:,
1865:S
1862:(
1842:)
1836:,
1833:T
1830:(
1824:)
1818:,
1815:S
1812:(
1806:F
1795:.
1760:=
1737:S
1717:)
1711:,
1708:S
1705:(
1686:M
1682:M
1678:M
1662:R
1658:R
1652:S
1648:S
1644:S
1640:S
1636:S
1632:S
1624:M
1620:S
1613:M
1609:M
1605:M
1589:)
1582:X
1578:,
1575:X
1572:(
1567:S
1562:m
1559:o
1556:H
1544:S
1538:.
1526:X
1520:x
1500:S
1494:s
1474:)
1471:x
1468:(
1465:F
1462:s
1459:=
1456:)
1453:x
1450:s
1447:(
1444:F
1414:X
1407:X
1401:F
1388:X
1384:X
1380:S
1376:S
1372:X
1368:X
1360:S
1343:X
1323:S
1299:)
1296:T
1293:(
1267:X
1247:S
1227:T
1204:.
1201:)
1198:t
1195:(
1192:)
1189:T
1186:(
1174:)
1171:s
1168:(
1165:)
1162:T
1159:(
1150:=
1147:)
1144:t
1138:s
1135:(
1132:)
1129:T
1126:(
1097:)
1094:X
1088:X
1085:(
1079:S
1033:)
1030:X
1024:X
1021:(
1015:S
1012::
1009:)
1006:T
1003:(
975:s
971:T
964:s
941:.
936:t
932:T
923:s
919:T
915:=
910:t
904:s
900:T
876:T
856:S
833:.
830:)
827:x
824:,
821:s
818:(
815:T
812:=
809:)
806:x
803:(
798:s
794:T
770:X
747:X
741:X
733:s
729:T
705:S
685:s
665:x
659:s
639:)
636:x
633:,
630:s
627:(
624:T
604:S
581:X
575:X
569:S
563:T
540:T
521:s
517:t
513:t
509:s
497:X
493:x
489:S
485:t
481:s
473:X
469:S
453:S
447:S
440:x
436:x
432:e
426:S
418:S
411:S
404:S
397:S
392:S
388:X
384:S
372:X
368:X
364:S
353:M
349:M
345:e
338:x
334:x
330:e
326:X
322:x
314:M
310:M
298:M
291:)
289:b
285:a
281:x
277:b
273:a
269:x
267:(
262:X
258:S
254:X
248:X
234:.
231:x
227:t
223:s
219:x
215:t
211:s
206:X
202:x
198:S
194:t
190:s
177:X
173:X
169:S
163:X
159:S
147:S
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.