355:; a monoid is a semigroup with an identity element (also called "unit"). Since the notion of functions acting on a set always includes the notion of an identity function, which when applied to the set does nothing, a transformation semigroup can be made into a monoid by adding the identity function.
2882:
2373:
2243:
1603:
346:
987:
2078:
1398:
844:
781:
480:
417:
2516:
1448:
1190:
1949:
1670:
2959:
2460:
2136:
1869:
2995:
2722:
2543:
2169:
2771:
2596:
2417:
2288:
1907:
1222:
246:
2651:
1520:
1972:
2933:
1830:
1741:
1275:
571:
2110:
1311:
670:
2001:
632:
2902:
2762:
2021:
1796:
1768:
1540:
875:
1337:
600:
1697:
1118:
1091:
733:
176:
1007:
910:
702:
515:
1138:
1012:
Once one makes this demand, it is completely safe to drop all parenthesis, as the monoid product and the action of the monoid on the set are completely
3107:
3045:
2296:
3092:
3077:
1613:
29:
2961:. Stated in this way, the quantum semiautomaton has many geometrical generalizations. Thus, for example, one may take a
21:
1748:
2174:
2962:
1567:
262:
918:
3164:
2670:. The structure of all possible transitions driven by strings in the free monoid has a graphical depiction as a
2026:
1775:
1346:
1017:
91:
3169:
3159:
2690:
1020:
of letters, in the computer-science sense of the word "string". This abstraction then allows one to talk about
787:
748:
423:
384:
186:
95:
40:
3128:
2465:
1403:
2682:
1149:
1912:
1618:
2667:
1462:
201:
3065:
2938:
2426:
2115:
1835:
2968:
2877:{\displaystyle (\mathbb {C} P^{n},\Sigma ,\{U_{\sigma _{1}},U_{\sigma _{2}},\dotsc ,U_{\sigma _{p}}\})}
2695:
2521:
2141:
2420:
1707:
257:
2560:
2381:
2252:
1886:
1195:
219:
2618:
1487:
1957:
2911:
1808:
1719:
1230:
526:
2086:
1283:
637:
1980:
256:
are two functions of the transformation semigroup, their semigroup product is defined as their
3103:
3088:
3073:
3041:
3017:
2546:
605:
179:
33:
2887:
2747:
2006:
1781:
1753:
1525:
852:
3009:
3005:
1316:
1025:
1021:
579:
352:
351:
Some authors regard "semigroup" and "monoid" as synonyms. Here a semigroup need not have an
131:
106:
2681:
need not be finite, or even countable. As an example, semiautomata underpin the concept of
1675:
1096:
1069:
711:
149:
2671:
992:
895:
687:
491:
113:
2764:
remains finite, and other typical concerns of automata theory remain in play. Thus, the
3029:
2733:
1123:
892:, they are just elements of some monoid. Therefore, one must demand that the action of
3153:
3033:
79:
1700:
3013:
2554:
1771:
1744:
1013:
87:
17:
1043:, two distinct elements of the monoid may determine the same transformation of
2998:
1952:
884:-act is closely related to a transformation monoid. However the elements of
190:
1016:. In particular, this allows elements of the monoid to be represented as
1612:
is a finite set—it need not be—, a semiautomaton may be thought of as a
117:
2666:
is finite, then the transition functions are commonly represented as
371:
194:
59:
1713:
Any semiautomaton induces an act of a monoid in the following way.
2729:
2368:{\displaystyle M(Q,\Sigma ,T)=\{T_{w}\vert w\in \Sigma ^{*}\}.}
378:
be a non-empty set. If there exists a multiplicative operation
208:
to itself. They are functions in the sense that every element
3136:
Categories and
General Algebraic Structures with Applications
1871:
be the function, defined recursively, as follows, for all
989:), as, in general, this might not hold for some arbitrary
1051:-act is essentially the same as a transformation monoid.
3129:"The symmetric monoidal closed category of cpo M-sets"
706:
right multiplication of elements of Q by elements of M
2971:
2941:
2914:
2890:
2774:
2750:
2698:
2621:
2563:
2524:
2468:
2429:
2384:
2299:
2255:
2177:
2144:
2118:
2089:
2029:
2009:
1983:
1960:
1915:
1889:
1838:
1811:
1784:
1756:
1722:
1678:
1621:
1570:
1528:
1490:
1406:
1349:
1319:
1286:
1233:
1198:
1152:
1126:
1099:
1072:
995:
921:
898:
855:
790:
751:
714:
690:
640:
608:
582:
529:
494:
426:
387:
265:
222:
152:
1009:, in the way that it does for function composition.
43:, a set Σ called the input alphabet, and a function
1770:(so that the superscript * is understood to be the
1024:in general, and eventually leads to the concept of
3040:. American Mathematical Society, volume 2 (1967),
2989:
2953:
2927:
2896:
2876:
2756:
2716:
2645:
2590:
2537:
2510:
2454:
2411:
2367:
2282:
2237:
2163:
2130:
2104:
2072:
2015:
1995:
1966:
1943:
1901:
1863:
1824:
1790:
1762:
1735:
1691:
1664:
1597:
1534:
1514:
1442:
1392:
1331:
1305:
1269:
1216:
1184:
1132:
1112:
1085:
1047:. If we demand that this does not happen, then an
1001:
981:
904:
869:
838:
775:
727:
696:
664:
626:
594:
565:
509:
474:
411:
340:
240:
170:
3083:Mati Kilp, Ulrich Knauer, Alexander V. Mikhalov,
912:be consistent with multiplication in the monoid (
1035:-act and a transformation monoid is that for an
105:In older books like Clifford and Preston (1967)
86:. This may be viewed either as an action of the
2238:{\displaystyle T_{w}(q)=T_{v}(T_{\sigma }(q))}
32:having inputs but no output. It consists of a
2908:letters, so that there is one unitary matrix
1598:{\displaystyle T\colon Q\times \Sigma \to Q.}
341:{\displaystyle (st)(q)=(s\circ t)(q)=s(t(q))}
8:
2868:
2802:
2359:
2340:
2327:
982:{\displaystyle \mu (q,st)=\mu (\mu (q,s),t)}
2724:, and individual states are referred to as
2073:{\displaystyle T_{\sigma }(q)=T(q,\sigma )}
1393:{\displaystyle \mathrm {Hom} (Q_{M},B_{M})}
94:in the input alphabet Σ, or as the induced
2981:
2973:
2972:
2970:
2940:
2919:
2913:
2889:
2860:
2855:
2834:
2829:
2814:
2809:
2787:
2779:
2778:
2773:
2749:
2708:
2700:
2699:
2697:
2620:
2562:
2529:
2523:
2499:
2486:
2473:
2467:
2446:
2428:
2383:
2353:
2334:
2298:
2254:
2217:
2204:
2182:
2176:
2155:
2143:
2117:
2088:
2034:
2028:
2008:
1982:
1959:
1920:
1914:
1888:
1843:
1837:
1816:
1810:
1783:
1755:
1727:
1721:
1683:
1677:
1647:
1620:
1569:
1527:
1489:
1419:
1408:
1405:
1381:
1368:
1350:
1348:
1318:
1297:
1285:
1232:
1197:
1176:
1163:
1151:
1125:
1104:
1098:
1077:
1071:
1028:as being composed of strings of letters.
994:
920:
897:
858:
857:
854:
839:{\displaystyle (m,q)\mapsto mq=\mu (m,q)}
789:
776:{\displaystyle \mu \colon M\times Q\to Q}
750:
719:
713:
689:
639:
607:
581:
528:
493:
475:{\displaystyle (q,m)\mapsto qm=\mu (q,m)}
425:
412:{\displaystyle \mu \colon Q\times M\to Q}
386:
264:
221:
151:
124:Transformation semigroups and monoid acts
3127:Moghbeli-Damaneh, Halimeh (July 2020).
3119:
2511:{\displaystyle T_{w}\circ T_{v}=T_{vw}}
1710:that has no output, and only an input.
1443:{\displaystyle \mathrm {Hom} _{M}(Q,B)}
58:Associated with any semiautomaton is a
1774:); it is the set of all finite-length
1343:-homomorphisms is commonly written as
1185:{\displaystyle f\colon Q_{M}\to B_{M}}
1944:{\displaystyle T_{\varepsilon }(q)=q}
1665:{\displaystyle (Q,\Sigma ,T,q_{0},A)}
7:
2768:may be simply defined as the triple
708:. The right act is often written as
3087:(2000), Walter de Gruyter, Berlin,
2997:, and selections from its group of
3062:(1982), Cambridge University Press
3055:(1972), Akademiai Kiado, Budapest.
3038:The Algebraic Theory of Semigroups
2954:{\displaystyle \sigma \in \Sigma }
2948:
2891:
2796:
2751:
2631:
2576:
2455:{\displaystyle v,w\in \Sigma ^{*}}
2443:
2397:
2350:
2312:
2268:
2152:
2131:{\displaystyle \sigma \in \Sigma }
2125:
2010:
1864:{\displaystyle T_{w}\colon Q\to Q}
1813:
1785:
1757:
1724:
1631:
1583:
1529:
1500:
1415:
1412:
1409:
1357:
1354:
1351:
520:for 1 the unit of the monoid, and
14:
2990:{\displaystyle \mathbb {C} P^{n}}
2732:. State transitions are given by
2717:{\displaystyle \mathbb {C} P^{n}}
3016:to the transition monoid of the
2553:. Since function composition is
2538:{\displaystyle T_{\varepsilon }}
2164:{\displaystyle v\in \Sigma ^{*}}
1672:, but without the initial state
204:, or "transformations", mapping
55:called the transition function.
1550:is a non-empty set, called the
1542:is a non-empty set, called the
1461:-homomorphisms together form a
485:which satisfies the properties
116:, semiautomata essentially are
2871:
2775:
2640:
2622:
2598:is a monoid: it is called the
2591:{\displaystyle M(Q,\Sigma ,T)}
2585:
2567:
2412:{\displaystyle M(Q,\Sigma ,T)}
2406:
2388:
2321:
2303:
2283:{\displaystyle M(Q,\Sigma ,T)}
2277:
2259:
2232:
2229:
2223:
2210:
2194:
2188:
2067:
2055:
2046:
2040:
1932:
1926:
1902:{\displaystyle w=\varepsilon }
1855:
1659:
1622:
1614:deterministic finite automaton
1586:
1509:
1491:
1437:
1425:
1387:
1361:
1261:
1255:
1246:
1237:
1217:{\displaystyle f\colon Q\to B}
1208:
1169:
1031:Another difference between an
976:
967:
955:
949:
940:
925:
833:
821:
806:
803:
791:
767:
659:
641:
557:
548:
542:
533:
469:
457:
442:
439:
427:
403:
335:
332:
326:
320:
311:
305:
302:
290:
284:
278:
275:
266:
241:{\displaystyle m\colon Q\to Q}
232:
165:
153:
30:deterministic finite automaton
1:
3098:Rudolf Lidl and Günter Pilz,
2646:{\displaystyle (Q,\Sigma ,T)}
1515:{\displaystyle (Q,\Sigma ,T)}
3085:Monoids, Acts and Categories
3053:Algebraic Theory of Automata
1967:{\displaystyle \varepsilon }
78:of the semiautomaton, which
22:theoretical computer science
3072:, (1991), Clarendon Press,
2928:{\displaystyle U_{\sigma }}
2685:. There, the set of states
1825:{\displaystyle \Sigma ^{*}}
1778:composed of the letters in
1736:{\displaystyle \Sigma ^{*}}
1270:{\displaystyle f(qm)=f(q)m}
742:is defined similarly, with
566:{\displaystyle q(st)=(qs)t}
3186:
2963:Riemannian symmetric space
2105:{\displaystyle w=\sigma v}
1974:does not change the state.
1306:{\displaystyle q\in Q_{M}}
665:{\displaystyle (Q,M,\mu )}
185:(often called the "set of
129:
3060:Algebraic Automata Theory
3001:as transition functions.
1996:{\displaystyle w=\sigma }
3100:Applied Abstract Algebra
3020:accepting the language.
2691:complex projective space
2608:characteristic semigroup
1120:sharing the same monoid
849:and is often denoted as
627:{\displaystyle s,t\in M}
140:transformation semigroup
96:transformation semigroup
3051:F. Gecseg and I. Peak,
2897:{\displaystyle \Sigma }
2757:{\displaystyle \Sigma }
2683:quantum finite automata
2668:state transition tables
2016:{\displaystyle \Sigma }
1791:{\displaystyle \Sigma }
1763:{\displaystyle \Sigma }
1706:. Alternately, it is a
1608:When the set of states
1535:{\displaystyle \Sigma }
870:{\displaystyle \,_{M}Q}
109:are called "operands".
3070:Automata and Languages
2991:
2955:
2929:
2898:
2878:
2758:
2744:. The input alphabet
2718:
2647:
2592:
2539:
2512:
2456:
2413:
2369:
2284:
2239:
2165:
2132:
2106:
2074:
2017:
1997:
1968:
1945:
1903:
1865:
1826:
1792:
1764:
1737:
1693:
1666:
1599:
1536:
1516:
1444:
1394:
1333:
1332:{\displaystyle m\in M}
1307:
1271:
1218:
1186:
1134:
1114:
1087:
1003:
983:
906:
888:need not be functions
871:
840:
777:
729:
698:
666:
628:
596:
595:{\displaystyle q\in Q}
567:
511:
476:
413:
342:
242:
172:
2992:
2956:
2930:
2899:
2879:
2766:quantum semiautomaton
2759:
2719:
2662:If the set of states
2648:
2614:of the semiautomaton
2604:characteristic monoid
2593:
2540:
2513:
2457:
2414:
2370:
2285:
2240:
2166:
2133:
2107:
2075:
2018:
1998:
1969:
1946:
1904:
1866:
1827:
1793:
1765:
1738:
1694:
1692:{\displaystyle q_{0}}
1667:
1600:
1537:
1517:
1445:
1395:
1334:
1308:
1272:
1219:
1187:
1135:
1115:
1113:{\displaystyle B_{M}}
1088:
1086:{\displaystyle Q_{M}}
1004:
984:
907:
872:
841:
778:
730:
728:{\displaystyle Q_{M}}
699:
667:
629:
597:
568:
512:
477:
414:
343:
243:
173:
171:{\displaystyle (M,Q)}
144:transformation monoid
82:on the set of states
64:characteristic monoid
2969:
2939:
2912:
2888:
2772:
2748:
2696:
2619:
2561:
2522:
2466:
2427:
2421:function composition
2382:
2297:
2253:
2175:
2142:
2116:
2087:
2027:
2007:
1981:
1958:
1913:
1887:
1836:
1809:
1782:
1754:
1720:
1708:finite state machine
1676:
1619:
1568:
1526:
1488:
1404:
1347:
1317:
1284:
1231:
1196:
1150:
1124:
1097:
1070:
1002:{\displaystyle \mu }
993:
919:
905:{\displaystyle \mu }
896:
853:
788:
749:
712:
697:{\displaystyle \mu }
688:
638:
606:
580:
527:
510:{\displaystyle q1=q}
492:
424:
385:
263:
258:function composition
220:
150:
3058:W. M. L. Holcombe,
2518:. It also contains
2423:; that is, for all
1560:transition function
3102:(1998), Springer,
2987:
2951:
2925:
2894:
2884:when the alphabet
2874:
2754:
2714:
2677:The set of states
2643:
2588:
2535:
2508:
2452:
2409:
2365:
2280:
2235:
2161:
2128:
2102:
2070:
2013:
1993:
1964:
1941:
1899:
1861:
1822:
1788:
1760:
1733:
1689:
1662:
1595:
1532:
1512:
1440:
1390:
1339:. The set of all
1329:
1303:
1267:
1214:
1182:
1130:
1110:
1083:
999:
979:
902:
867:
836:
773:
725:
694:
662:
634:, then the triple
624:
592:
563:
507:
472:
409:
338:
238:
168:
3108:978-0-387-98290-8
3046:978-0-8218-0272-4
3018:minimal automaton
2689:are given by the
2612:transition monoid
2547:identity function
1747:generated by the
1133:{\displaystyle M}
1022:string operations
107:semigroup actions
76:transition system
72:transition monoid
3177:
3165:Semigroup theory
3144:
3143:
3133:
3124:
3010:regular language
3006:syntactic monoid
2996:
2994:
2993:
2988:
2986:
2985:
2976:
2960:
2958:
2957:
2952:
2935:for each letter
2934:
2932:
2931:
2926:
2924:
2923:
2903:
2901:
2900:
2895:
2883:
2881:
2880:
2875:
2867:
2866:
2865:
2864:
2841:
2840:
2839:
2838:
2821:
2820:
2819:
2818:
2792:
2791:
2782:
2763:
2761:
2760:
2755:
2723:
2721:
2720:
2715:
2713:
2712:
2703:
2654:
2652:
2650:
2649:
2644:
2597:
2595:
2594:
2589:
2544:
2542:
2541:
2536:
2534:
2533:
2517:
2515:
2514:
2509:
2507:
2506:
2491:
2490:
2478:
2477:
2461:
2459:
2458:
2453:
2451:
2450:
2419:is closed under
2418:
2416:
2415:
2410:
2374:
2372:
2371:
2366:
2358:
2357:
2339:
2338:
2289:
2287:
2286:
2281:
2244:
2242:
2241:
2236:
2222:
2221:
2209:
2208:
2187:
2186:
2170:
2168:
2167:
2162:
2160:
2159:
2137:
2135:
2134:
2129:
2111:
2109:
2108:
2103:
2079:
2077:
2076:
2071:
2039:
2038:
2022:
2020:
2019:
2014:
2002:
2000:
1999:
1994:
1973:
1971:
1970:
1965:
1950:
1948:
1947:
1942:
1925:
1924:
1908:
1906:
1905:
1900:
1870:
1868:
1867:
1862:
1848:
1847:
1831:
1829:
1828:
1823:
1821:
1820:
1797:
1795:
1794:
1789:
1769:
1767:
1766:
1761:
1742:
1740:
1739:
1734:
1732:
1731:
1698:
1696:
1695:
1690:
1688:
1687:
1671:
1669:
1668:
1663:
1652:
1651:
1604:
1602:
1601:
1596:
1541:
1539:
1538:
1533:
1521:
1519:
1518:
1513:
1449:
1447:
1446:
1441:
1424:
1423:
1418:
1399:
1397:
1396:
1391:
1386:
1385:
1373:
1372:
1360:
1338:
1336:
1335:
1330:
1312:
1310:
1309:
1304:
1302:
1301:
1276:
1274:
1273:
1268:
1223:
1221:
1220:
1215:
1191:
1189:
1188:
1183:
1181:
1180:
1168:
1167:
1139:
1137:
1136:
1131:
1119:
1117:
1116:
1111:
1109:
1108:
1092:
1090:
1089:
1084:
1082:
1081:
1026:formal languages
1008:
1006:
1005:
1000:
988:
986:
985:
980:
911:
909:
908:
903:
876:
874:
873:
868:
863:
862:
845:
843:
842:
837:
782:
780:
779:
774:
734:
732:
731:
726:
724:
723:
703:
701:
700:
695:
684:. In long-hand,
671:
669:
668:
663:
633:
631:
630:
625:
601:
599:
598:
593:
572:
570:
569:
564:
516:
514:
513:
508:
481:
479:
478:
473:
418:
416:
415:
410:
353:identity element
347:
345:
344:
339:
247:
245:
244:
239:
178:consisting of a
177:
175:
174:
169:
132:semigroup action
3185:
3184:
3180:
3179:
3178:
3176:
3175:
3174:
3170:Finite automata
3160:Category theory
3150:
3149:
3148:
3147:
3131:
3126:
3125:
3121:
3116:
3026:
2977:
2967:
2966:
2937:
2936:
2915:
2910:
2909:
2886:
2885:
2856:
2851:
2830:
2825:
2810:
2805:
2783:
2770:
2769:
2746:
2745:
2704:
2694:
2693:
2672:de Bruijn graph
2660:
2617:
2616:
2615:
2559:
2558:
2545:, which is the
2525:
2520:
2519:
2495:
2482:
2469:
2464:
2463:
2442:
2425:
2424:
2380:
2379:
2349:
2330:
2295:
2294:
2251:
2250:
2213:
2200:
2178:
2173:
2172:
2151:
2140:
2139:
2114:
2113:
2085:
2084:
2030:
2025:
2024:
2005:
2004:
2003:is a letter in
1979:
1978:
1956:
1955:
1916:
1911:
1910:
1885:
1884:
1839:
1834:
1833:
1812:
1807:
1806:
1801:For every word
1780:
1779:
1752:
1751:
1723:
1718:
1717:
1679:
1674:
1673:
1643:
1617:
1616:
1566:
1565:
1524:
1523:
1486:
1485:
1478:
1407:
1402:
1401:
1377:
1364:
1345:
1344:
1315:
1314:
1293:
1282:
1281:
1229:
1228:
1194:
1193:
1172:
1159:
1148:
1147:
1122:
1121:
1100:
1095:
1094:
1073:
1068:
1067:
1060:
991:
990:
917:
916:
894:
893:
856:
851:
850:
786:
785:
747:
746:
715:
710:
709:
686:
685:
636:
635:
604:
603:
578:
577:
525:
524:
490:
489:
422:
421:
383:
382:
364:
261:
260:
218:
217:
148:
147:
134:
126:
114:category theory
12:
11:
5:
3183:
3181:
3173:
3172:
3167:
3162:
3152:
3151:
3146:
3145:
3118:
3117:
3115:
3112:
3111:
3110:
3096:
3081:
3063:
3056:
3049:
3030:A. H. Clifford
3025:
3022:
2984:
2980:
2975:
2950:
2947:
2944:
2922:
2918:
2893:
2873:
2870:
2863:
2859:
2854:
2850:
2847:
2844:
2837:
2833:
2828:
2824:
2817:
2813:
2808:
2804:
2801:
2798:
2795:
2790:
2786:
2781:
2777:
2753:
2711:
2707:
2702:
2659:
2656:
2642:
2639:
2636:
2633:
2630:
2627:
2624:
2587:
2584:
2581:
2578:
2575:
2572:
2569:
2566:
2532:
2528:
2505:
2502:
2498:
2494:
2489:
2485:
2481:
2476:
2472:
2449:
2445:
2441:
2438:
2435:
2432:
2408:
2405:
2402:
2399:
2396:
2393:
2390:
2387:
2376:
2375:
2364:
2361:
2356:
2352:
2348:
2345:
2342:
2337:
2333:
2329:
2326:
2323:
2320:
2317:
2314:
2311:
2308:
2305:
2302:
2279:
2276:
2273:
2270:
2267:
2264:
2261:
2258:
2247:
2246:
2234:
2231:
2228:
2225:
2220:
2216:
2212:
2207:
2203:
2199:
2196:
2193:
2190:
2185:
2181:
2158:
2154:
2150:
2147:
2127:
2124:
2121:
2101:
2098:
2095:
2092:
2081:
2069:
2066:
2063:
2060:
2057:
2054:
2051:
2048:
2045:
2042:
2037:
2033:
2012:
1992:
1989:
1986:
1975:
1963:
1951:, so that the
1940:
1937:
1934:
1931:
1928:
1923:
1919:
1898:
1895:
1892:
1860:
1857:
1854:
1851:
1846:
1842:
1819:
1815:
1787:
1759:
1730:
1726:
1686:
1682:
1661:
1658:
1655:
1650:
1646:
1642:
1639:
1636:
1633:
1630:
1627:
1624:
1606:
1605:
1594:
1591:
1588:
1585:
1582:
1579:
1576:
1573:
1544:input alphabet
1531:
1511:
1508:
1505:
1502:
1499:
1496:
1493:
1477:
1474:
1439:
1436:
1433:
1430:
1427:
1422:
1417:
1414:
1411:
1389:
1384:
1380:
1376:
1371:
1367:
1363:
1359:
1356:
1353:
1328:
1325:
1322:
1300:
1296:
1292:
1289:
1278:
1277:
1266:
1263:
1260:
1257:
1254:
1251:
1248:
1245:
1242:
1239:
1236:
1213:
1210:
1207:
1204:
1201:
1179:
1175:
1171:
1166:
1162:
1158:
1155:
1129:
1107:
1103:
1080:
1076:
1059:
1053:
998:
978:
975:
972:
969:
966:
963:
960:
957:
954:
951:
948:
945:
942:
939:
936:
933:
930:
927:
924:
901:
866:
861:
847:
846:
835:
832:
829:
826:
823:
820:
817:
814:
811:
808:
805:
802:
799:
796:
793:
783:
772:
769:
766:
763:
760:
757:
754:
722:
718:
693:
661:
658:
655:
652:
649:
646:
643:
623:
620:
617:
614:
611:
591:
588:
585:
574:
573:
562:
559:
556:
553:
550:
547:
544:
541:
538:
535:
532:
518:
517:
506:
503:
500:
497:
483:
482:
471:
468:
465:
462:
459:
456:
453:
450:
447:
444:
441:
438:
435:
432:
429:
419:
408:
405:
402:
399:
396:
393:
390:
363:
357:
337:
334:
331:
328:
325:
322:
319:
316:
313:
310:
307:
304:
301:
298:
295:
292:
289:
286:
283:
280:
277:
274:
271:
268:
237:
234:
231:
228:
225:
167:
164:
161:
158:
155:
136:
135:
130:Main article:
125:
122:
13:
10:
9:
6:
4:
3:
2:
3182:
3171:
3168:
3166:
3163:
3161:
3158:
3157:
3155:
3141:
3137:
3130:
3123:
3120:
3113:
3109:
3105:
3101:
3097:
3094:
3093:3-11-015248-7
3090:
3086:
3082:
3079:
3078:0-19-853442-6
3075:
3071:
3067:
3064:
3061:
3057:
3054:
3050:
3047:
3043:
3039:
3035:
3034:G. B. Preston
3031:
3028:
3027:
3023:
3021:
3019:
3015:
3011:
3007:
3002:
3000:
2982:
2978:
2964:
2945:
2942:
2920:
2916:
2907:
2861:
2857:
2852:
2848:
2845:
2842:
2835:
2831:
2826:
2822:
2815:
2811:
2806:
2799:
2793:
2788:
2784:
2767:
2743:
2741:
2737:
2731:
2727:
2709:
2705:
2692:
2688:
2684:
2680:
2675:
2673:
2669:
2665:
2657:
2655:
2637:
2634:
2628:
2625:
2613:
2609:
2605:
2601:
2582:
2579:
2573:
2570:
2564:
2556:
2552:
2548:
2530:
2526:
2503:
2500:
2496:
2492:
2487:
2483:
2479:
2474:
2470:
2447:
2439:
2436:
2433:
2430:
2422:
2403:
2400:
2394:
2391:
2385:
2362:
2354:
2346:
2343:
2335:
2331:
2324:
2318:
2315:
2309:
2306:
2300:
2293:
2292:
2291:
2274:
2271:
2265:
2262:
2256:
2226:
2218:
2214:
2205:
2201:
2197:
2191:
2183:
2179:
2156:
2148:
2145:
2122:
2119:
2099:
2096:
2093:
2090:
2082:
2064:
2061:
2058:
2052:
2049:
2043:
2035:
2031:
1990:
1987:
1984:
1976:
1961:
1954:
1938:
1935:
1929:
1921:
1917:
1896:
1893:
1890:
1882:
1881:
1880:
1878:
1874:
1858:
1852:
1849:
1844:
1840:
1817:
1804:
1799:
1777:
1773:
1750:
1746:
1728:
1714:
1711:
1709:
1705:
1702:
1701:accept states
1684:
1680:
1656:
1653:
1648:
1644:
1640:
1637:
1634:
1628:
1625:
1615:
1611:
1592:
1589:
1580:
1577:
1574:
1571:
1564:
1563:
1562:
1561:
1557:
1553:
1552:set of states
1549:
1545:
1506:
1503:
1497:
1494:
1483:
1482:semiautomaton
1475:
1473:
1471:
1469:
1464:
1460:
1456:
1451:
1434:
1431:
1428:
1420:
1382:
1378:
1374:
1369:
1365:
1342:
1326:
1323:
1320:
1298:
1294:
1290:
1287:
1264:
1258:
1252:
1249:
1243:
1240:
1234:
1227:
1226:
1225:
1211:
1205:
1202:
1199:
1177:
1173:
1164:
1160:
1156:
1153:
1146:
1145:-homomorphism
1144:
1127:
1105:
1101:
1078:
1074:
1065:
1058:-homomorphism
1057:
1054:
1052:
1050:
1046:
1042:
1038:
1034:
1029:
1027:
1023:
1019:
1015:
1010:
996:
973:
970:
964:
961:
958:
952:
946:
943:
937:
934:
931:
928:
922:
915:
899:
891:
887:
883:
878:
864:
859:
830:
827:
824:
818:
815:
812:
809:
800:
797:
794:
784:
770:
764:
761:
758:
755:
752:
745:
744:
743:
741:
736:
720:
716:
707:
691:
683:
679:
677:
656:
653:
650:
647:
644:
621:
618:
615:
612:
609:
589:
586:
583:
560:
554:
551:
545:
539:
536:
530:
523:
522:
521:
504:
501:
498:
495:
488:
487:
486:
466:
463:
460:
454:
451:
448:
445:
436:
433:
430:
420:
406:
400:
397:
394:
391:
388:
381:
380:
379:
377:
373:
369:
361:
358:
356:
354:
349:
329:
323:
317:
314:
308:
299:
296:
293:
287:
281:
272:
269:
259:
255:
251:
235:
229:
226:
223:
215:
211:
207:
203:
199:
196:
192:
188:
184:
181:
162:
159:
156:
145:
141:
133:
128:
127:
123:
121:
119:
115:
110:
108:
103:
101:
97:
93:
89:
85:
81:
77:
73:
69:
65:
61:
56:
54:
50:
46:
42:
38:
35:
31:
27:
26:semiautomaton
23:
19:
3139:
3135:
3122:
3099:
3084:
3069:
3059:
3052:
3037:
3003:
2965:in place of
2905:
2765:
2739:
2735:
2725:
2686:
2678:
2676:
2663:
2661:
2611:
2607:
2603:
2600:input monoid
2599:
2550:
2377:
2248:
1876:
1872:
1802:
1800:
1715:
1712:
1703:
1609:
1607:
1559:
1555:
1551:
1547:
1543:
1484:is a triple
1481:
1479:
1476:Semiautomata
1467:
1466:
1458:
1454:
1452:
1340:
1279:
1142:
1141:
1063:
1061:
1055:
1048:
1044:
1040:
1036:
1032:
1030:
1011:
913:
889:
885:
881:
879:
848:
739:
737:
705:
681:
680:or simply a
675:
673:
672:is called a
575:
519:
484:
375:
367:
365:
359:
350:
253:
249:
213:
209:
205:
197:
182:
143:
139:
137:
111:
104:
99:
83:
75:
71:
68:input monoid
67:
63:
57:
52:
48:
44:
36:
25:
15:
3066:J. M. Howie
2555:associative
2290:be the set
1772:Kleene star
1745:free monoid
1014:associative
88:free monoid
62:called the
18:mathematics
3154:Categories
3114:References
3024:Literature
3014:isomorphic
2999:isometries
2658:Properties
2557:, the set
2462:, one has
1953:empty word
1699:or set of
1457:-acts and
1224:such that
146:is a pair
2949:Σ
2946:∈
2943:σ
2921:σ
2892:Σ
2858:σ
2846:…
2832:σ
2812:σ
2797:Σ
2752:Σ
2632:Σ
2577:Σ
2531:ε
2480:∘
2448:∗
2444:Σ
2440:∈
2398:Σ
2355:∗
2351:Σ
2347:∈
2313:Σ
2269:Σ
2219:σ
2157:∗
2153:Σ
2149:∈
2126:Σ
2123:∈
2120:σ
2097:σ
2065:σ
2036:σ
2011:Σ
1991:σ
1962:ε
1922:ε
1897:ε
1856:→
1850::
1818:∗
1814:Σ
1786:Σ
1758:Σ
1729:∗
1725:Σ
1632:Σ
1587:→
1584:Σ
1581:×
1575::
1530:Σ
1501:Σ
1324:∈
1291:∈
1209:→
1203::
1192:is a map
1170:→
1157::
997:μ
953:μ
947:μ
923:μ
900:μ
819:μ
807:↦
768:→
762:×
756::
753:μ
692:μ
682:right act
657:μ
619:∈
587:∈
455:μ
443:↦
404:→
398:×
392::
389:μ
297:∘
233:→
227::
216:is a map
202:functions
191:semigroup
189:") and a
2742:matrices
2734:unitary
2378:The set
1749:alphabet
1463:category
1280:for all
1062:For two
740:left act
576:for all
118:functors
2728:-state
2171:, then
2023:, then
1909:, then
1776:strings
1743:be the
1558:is the
1465:called
1018:strings
704:is the
92:strings
3106:
3091:
3076:
3044:
2730:qubits
1832:, let
1554:, and
1522:where
1066:-acts
890:per se
674:right
372:monoid
195:monoid
187:states
60:monoid
51:× Σ →
41:states
3132:(PDF)
3008:of a
1140:, an
1039:-act
370:be a
362:-acts
248:. If
28:is a
3142:(1).
3104:ISBN
3089:ISBN
3074:ISBN
3042:ISBN
3032:and
3004:The
2904:has
2249:Let
2138:and
2112:for
1716:Let
1470:-Act
1453:The
1400:or
1313:and
1093:and
914:i.e.
678:-act
602:and
374:and
366:Let
252:and
80:acts
24:, a
20:and
3012:is
2610:or
2549:on
2083:If
1977:If
1883:If
1875:in
1805:in
880:An
212:of
200:of
193:or
180:set
142:or
112:In
98:of
90:of
74:or
39:of
34:set
16:In
3156::
3140:13
3138:.
3134:.
3068:,
3036:,
2674:.
2606:,
2602:,
1879::
1798:.
1546:,
1480:A
1472:.
1450:.
877:.
738:A
735:.
348:.
138:A
120:.
102:.
70:,
66:,
47::
3095:.
3080:.
3048:.
2983:n
2979:P
2974:C
2917:U
2906:p
2872:)
2869:}
2862:p
2853:U
2849:,
2843:,
2836:2
2827:U
2823:,
2816:1
2807:U
2803:{
2800:,
2794:,
2789:n
2785:P
2780:C
2776:(
2740:n
2738:×
2736:n
2726:n
2710:n
2706:P
2701:C
2687:Q
2679:Q
2664:Q
2653:.
2641:)
2638:T
2635:,
2629:,
2626:Q
2623:(
2586:)
2583:T
2580:,
2574:,
2571:Q
2568:(
2565:M
2551:Q
2527:T
2504:w
2501:v
2497:T
2493:=
2488:v
2484:T
2475:w
2471:T
2437:w
2434:,
2431:v
2407:)
2404:T
2401:,
2395:,
2392:Q
2389:(
2386:M
2363:.
2360:}
2344:w
2341:|
2336:w
2332:T
2328:{
2325:=
2322:)
2319:T
2316:,
2310:,
2307:Q
2304:(
2301:M
2278:)
2275:T
2272:,
2266:,
2263:Q
2260:(
2257:M
2245:.
2233:)
2230:)
2227:q
2224:(
2215:T
2211:(
2206:v
2202:T
2198:=
2195:)
2192:q
2189:(
2184:w
2180:T
2146:v
2100:v
2094:=
2091:w
2080:.
2068:)
2062:,
2059:q
2056:(
2053:T
2050:=
2047:)
2044:q
2041:(
2032:T
1988:=
1985:w
1939:q
1936:=
1933:)
1930:q
1927:(
1918:T
1894:=
1891:w
1877:Q
1873:q
1859:Q
1853:Q
1845:w
1841:T
1803:w
1704:A
1685:0
1681:q
1660:)
1657:A
1654:,
1649:0
1645:q
1641:,
1638:T
1635:,
1629:,
1626:Q
1623:(
1610:Q
1593:.
1590:Q
1578:Q
1572:T
1556:T
1548:Q
1510:)
1507:T
1504:,
1498:,
1495:Q
1492:(
1468:M
1459:M
1455:M
1438:)
1435:B
1432:,
1429:Q
1426:(
1421:M
1416:m
1413:o
1410:H
1388:)
1383:M
1379:B
1375:,
1370:M
1366:Q
1362:(
1358:m
1355:o
1352:H
1341:M
1327:M
1321:m
1299:M
1295:Q
1288:q
1265:m
1262:)
1259:q
1256:(
1253:f
1250:=
1247:)
1244:m
1241:q
1238:(
1235:f
1212:B
1206:Q
1200:f
1178:M
1174:B
1165:M
1161:Q
1154:f
1143:M
1128:M
1106:M
1102:B
1079:M
1075:Q
1064:M
1056:M
1049:M
1045:Q
1041:Q
1037:M
1033:M
977:)
974:t
971:,
968:)
965:s
962:,
959:q
956:(
950:(
944:=
941:)
938:t
935:s
932:,
929:q
926:(
886:M
882:M
865:Q
860:M
834:)
831:q
828:,
825:m
822:(
816:=
813:q
810:m
804:)
801:q
798:,
795:m
792:(
771:Q
765:Q
759:M
721:M
717:Q
676:M
660:)
654:,
651:M
648:,
645:Q
642:(
622:M
616:t
613:,
610:s
590:Q
584:q
561:t
558:)
555:s
552:q
549:(
546:=
543:)
540:t
537:s
534:(
531:q
505:q
502:=
499:1
496:q
470:)
467:m
464:,
461:q
458:(
452:=
449:m
446:q
440:)
437:m
434:,
431:q
428:(
407:Q
401:M
395:Q
376:Q
368:M
360:M
336:)
333:)
330:q
327:(
324:t
321:(
318:s
315:=
312:)
309:q
306:(
303:)
300:t
294:s
291:(
288:=
285:)
282:q
279:(
276:)
273:t
270:s
267:(
254:t
250:s
236:Q
230:Q
224:m
214:M
210:m
206:Q
198:M
183:Q
166:)
163:Q
160:,
157:M
154:(
100:Q
84:Q
53:Q
49:Q
45:T
37:Q
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.