471:
different(?) notion of input monoid. They define a semiautomaton (A,X,δ) the usual way (A - states, X - input alphabet, δ - next state function), and immediately after that comes "If X is a generating set of a monoid S and one has δ(a, xx') = δ(δ(a, x), x') for any a ∈ A, x,x' ∈ X then S is called the input monoid of (A,X,δ)." It's not clear no me how δ can involve strings (they don't make the extensions to strings until later), and even if you assume that construction, I don't see how this input monoid can be non-free...
81:
71:
53:
521:
Aut(TM(A)) does not equal A, but TM(Aut(X)) is isomorphic with X. Howie also gives an example where picking the right generator set G (which is by no means unique) for TM(A), the automaton Aut(G) is the same as A. I think this is what KK&M want to prove. BTW, Howie's definition of a transformation monoid is a bit unusual. He defines it as a semigroup act which is effective (as the article on
22:
308:
s=(B,A) and the projections a=(A,A) and b=(B,B). The free monoid on the empty set has one element, the identity. The free monoid on any nonempty set has infinitely many elements. The full transformation group is e.g. a quotient of the free monoid on {a,s}: it satisfies relations like aa=a, as=a, ss=e,...
504:
to be true but don't prove. Of course, if one allows non-free input monoids (meaning that there are relations on the alphabet) then anything is possible (any monoid is a quotient of the free monoid on any generating set). Similarly, Lidl and Pilz want the notion of a semiautomaton to be "the same" as
485:
Howie in his 1991 book (Automata and
Languages) initially defines an automaton as nothing more than the action of a semigroup (which is the same as this article's notion semiautomaton). But he also goes on to extend the concept to non-deterministic automata. I'm going to update the article to reflect
190:
makes a point of saying that the input alphabets / state spaces can be infinite, certainly the same can be true for automata, semigroups and acts, and the like, as long as the word "finite" is not invoked. Incidentally, do you have any information about abelian semiautomata (i.e., the transformations
450:
A semiautomaton is not the same thing as a monoid action. It induces a monoid action of the free monoid on its alphabet, and hence also a transformation monoid, but one cannot recover the input alphabet from the transformation monoid (although it can be recovered as the set of free generators of the
311:
A semiautomaton is not the same thing as a monoid action. It induces a monoid action of the free monoid on its alphabet, and hence also a transformation monoid, but one cannot recover the input alphabet from the transformation monoid (although it can be recovered as the set of free generators of the
296:
Transformation semigroups/monoids are not the same thing as semigroup/monoid (S,M,left,right...-)acts/actions because there is no requirement that the action should be faithful/effective. In other words, distinct elements of the monoid M could act in the same way on Q. Instead, if a monoid M acts on
210:
I concur. "Labelled transition systems are aguably the most fundamental model within theoretical computer science." Winskel et al. 1993, Models for
Concurrency, chapter in Oxford Handbook of Logic and the Foundations of Computer Science. Semiautomata were not even mentioned, which suggests the two
200:
I don't think they should be merged, since there is a significantly different emphasis in the presentation and the usage. Many people I know talk all the time about labelled transition systems, for example in structural operational semantics, but would never talk about semiautomata, group actions
373:
I don't recommend remerging. One fundamental distinction is that semiautomata have an input alphabet. General monoid actions don't. Another is that general monoid actions include actions of non-free monoids which are not effective. Semiautomata don't give these, however you interpret them. Sure
307:
The full transformation monoid of a set is not a free monoid. We've already seen this for semigroups using a 1-element set. For monoids, we need a two element set {A,B}. Then the full transformation monoid has four elements, determined by what they do to A and B: the identity e=(A,B), the swap
520:
Yeah, the KK&M proof is a bit hand-wavish. The best treatment of the correspondence I found is in Howie (1991), pages 82-86. In a nutshell, denoting TM(A) the transformation monoid corresponding to a (semi)automaton, and Aut(X) the automaton obtained from a transformation monoid X, then
470:
Well, I'm pretty confused here. KK&M claim that the two a notions are equivalent in a sense: Proposition 4.5 on page 45 states that "Semiautomata can be considered as S-acts and S-acts can be considered as semiautomata (with a possibly non-free input monoid)". But the proof relies on a
303:
Free monoids and free semigroups are different. For instance if Q has one element, then its transformation group consists only of the identity. This is the free monoid on the empty set, but it isn't a free semigroup (the free semigroup on one element consists of all powers of that
417:, for example. This article has plenty of things to say about semiautomata that would be a digression in the context of general monoid actions. And despite your clean-up edit summary (I barely removed any content from this article), it says them better now than it did before.
361:
as possible, but I've removed the incorrect assertions and eliminated some of the overlap with the new article. More substantial change is probably needed here (the first section is now largely redundant) but I leave that to a computer science oriented editor.
393:
Not quite the same; there's a difference of notability here. There are many books a about permutation groups, but I don't know any that deal just with semiautomata. Having stub-class entry for semiautomaton is certainly feasible, but what would be the point?
201:
etc.. I agree that there should be more linking between the two articles, though. I also propose to include at the head of this article (which redirects from transition system) the phrase saying "if you were looking for state transition systems, see ...".
605:
Adding this to the article is a step in the right direction. It will help make clear that the notion of a semiautomaton can be formalized in different ways, and that analysis in terms of monoids or monoid actions are just two ways of doing this.
985:
543:
Very good, that makes sense. An effective semigroup action is isomorphic to a transformation semigroup in a canonical way, so Howie is not confusing the issue as much as KK&M and others do. Another term for "effective" is "faithful".
408:
First point agreed, but I hope you are not saying that semiautomata are not notable! Second point, "stub-class" does not mean "short", it means in need of substantial expansion. There is no limit on how short a (for example)
505:
a monoid (rather than a monoid action). It isn't quite, but it is close enough for them. Knowledge should focus on the common ground and describe the relations between the concepts that appear in the literature, without
284:
Transformation semigroups are indeed more-or-less the same thing as transformation monoids. Problems arise, however, when there is additional structure. Suppose that a transformation semigroup consists of
280:
This article claims that a number of related concepts are equivalent. They aren't. There are so many mistakes that I'm not sure where to begin. I start with a minor issue and move on from there.
133:
710:
413:
can be, as long as it is broad, well-written and reliably sourced. Knowledge articles do not need to have entire books written solely about them! There are not (I hope) whole books on
374:
semiautomaton theory is a great application of monoid actions, but they really are different concepts. Merging the two articles would be like (indeed worse than) merging
778:
740:
812:
1030:
1077:
1005:
127:
319:
The notion of an M-homomorphism requires that a monoid M is fixed. Consequently the category should be (and usually is) denoted M-Act, where M is a fixed monoid.
335:
There are indeed some minor ambiguities, but I don't think you need to split the page for those. Can't you just clarify them on the article page itself?
1072:
103:
587:
It looks like other sources let a semiautomaton be non-deterministic, i.e. δ can be a multi-valued function (basically a relation). See
176:
Hmm. I defering a merge until I get a good book on this. There are a few subtle points I'll get wrong if I bullishly force this merge.
94:
58:
211:
traditions had not yet even begun to merge just a little over ten years ago. Can you recommend a good source comparing the two? --
33:
1051:
638:
595:
534:
491:
476:
399:
340:
21:
242:
187:
163:
152:
608:
546:
511:
457:
419:
384:
364:
325:
591:
530:
487:
472:
395:
336:
1047:
522:
39:
80:
265:
250:
225:
375:
564:
Why not delete the entire chapter "Transformation semigroups and monoid acts"? It just duplicates
102:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
86:
796:
70:
52:
980:{\displaystyle (Q,M,\mu )\to (Q',M,\mu '),f:Q\to Q',\forall q\in Q(\mu '(f(q),m)=f(\mu (q,m)))}
631:
is defined as sending elements of right acts to other element of right acts, so I would expect
443:
414:
379:
238:
1037:
573:
565:
354:
297:
Q, there is a homomorphism from M to a transformation monoid of Q. It need not be injective.
286:
757:
719:
800:
261:
246:
221:
202:
588:
323:
I intend to split this page to resolve the many ambiguities and errors indicated above.
1010:
990:
1066:
358:
290:
220:
Is it OK to close the merge now, and leave the pages as they are for the time being?
212:
159:
712:, just to be consistent with the notation above. Instead, I just infer the type of
410:
192:
1033:
569:
455:). It is also not true that any monoid action is obtained from a semiautomaton.
452:
313:
99:
316:). It is also not true that any monoid action is obtained from a semiautomaton.
300:
There is no equivalence in general between left and right actions of a monoid.
293:. Then we don't want to add the identity, because it isn't a compact operator.
177:
167:
76:
1055:
1041:
804:
612:
599:
577:
550:
538:
515:
495:
480:
461:
423:
403:
388:
368:
344:
329:
269:
254:
229:
215:
205:
195:
180:
170:
245:. And I'd then put a tag at the top of that page. Any objections?
446:
to this new section so we can discuss it easily. The point was:
15:
509:
things to be the same, when they are actually different.
186:
I agree that they should probably be merged. Although
1013:
993:
815:
760:
722:
641:
589:
http://planetmath.org/encyclopedia/Semiautomaton.html
98:, a collaborative effort to improve the coverage of
1024:
999:
979:
772:
734:
704:
132:This article has not yet received a rating on the
1046:I changed the section accordingly yesterday. -
442:I've pastied one of the points raised above by
525:defined effective, Howie doesn't use the term
780:, that would work too... But I don't see how
8:
788:could be seen as elements of a right act...
705:{\displaystyle (Q,M,\mu )\to (Q',M',\mu ')}
19:
276:Disambiguation of a multiply wrong article
47:
1012:
992:
814:
759:
721:
640:
357:. I've tried to make as little change to
234:I removed the tag, for the time being.
158:I just got done writing the article on
49:
623:I'm rather confused by the section on
1078:Unknown-priority mathematics articles
7:
260:No-one objected, so I've done this.
92:This article is within the scope of
349:(ec) Transformation semigroups and
166:, which is exactly the same thing.
38:It is of interest to the following
897:
750:so that they can be multiplied by
500:Don't be confused by what authors
14:
112:Knowledge:WikiProject Mathematics
1073:Start-Class mathematics articles
742:, since it can take elements of
486:the lack of common terminology.
438:Difference from semigroup action
115:Template:WikiProject Mathematics
79:
69:
51:
20:
746:, and has to yield elements of
974:
971:
968:
956:
950:
941:
932:
926:
920:
909:
883:
868:
840:
837:
834:
816:
764:
726:
699:
666:
663:
660:
642:
613:20:08, 15 September 2008 (UTC)
600:14:35, 15 September 2008 (UTC)
551:21:08, 15 September 2008 (UTC)
539:20:34, 15 September 2008 (UTC)
516:20:06, 15 September 2008 (UTC)
496:19:13, 15 September 2008 (UTC)
481:02:02, 15 September 2008 (UTC)
462:22:56, 13 September 2008 (UTC)
424:18:46, 14 September 2008 (UTC)
404:18:04, 14 September 2008 (UTC)
389:17:45, 14 September 2008 (UTC)
369:17:31, 14 September 2008 (UTC)
345:17:22, 14 September 2008 (UTC)
330:22:56, 13 September 2008 (UTC)
237:A related suggestion: I think
196:20:52, 12 September 2007 (UTC)
1:
583:A less restrictive definition
230:09:52, 18 February 2008 (UTC)
216:04:25, 12 November 2007 (UTC)
106:and see a list of open tasks.
805:12:29, 2 November 2010 (UTC)
206:19:11, 28 October 2007 (UTC)
162:when I found the article on
1042:14:58, 20 August 2011 (UTC)
578:14:46, 20 August 2011 (UTC)
1094:
1056:07:03, 21 April 2014 (UTC)
270:12:24, 13 April 2008 (UTC)
181:03:09, 25 April 2007 (UTC)
171:03:53, 19 April 2007 (UTC)
353:-acts are now covered by
255:07:44, 4 April 2008 (UTC)
131:
64:
46:
164:state transition systems
134:project's priority scale
791:Furthermore, what does
754:, or maybe it could be
243:state transition system
188:state transition system
153:state transition system
95:WikiProject Mathematics
1026:
1001:
981:
774:
773:{\displaystyle Q\to M}
736:
735:{\displaystyle Q\to Q}
706:
28:This article is rated
1027:
1002:
982:
775:
737:
707:
523:transformation monoid
1011:
1007:is another name for
991:
813:
758:
720:
639:
118:mathematics articles
376:group (mathematics)
241:should redirect to
1025:{\displaystyle Q'}
1022:
997:
977:
770:
732:
702:
415:absorbing elements
87:Mathematics portal
34:content assessment
1000:{\displaystyle B}
635:to be defined as
444:User:Geometry guy
380:permutation group
287:compact operators
239:transition system
148:
147:
144:
143:
140:
139:
1085:
1048:Jochen Burghardt
1031:
1029:
1028:
1023:
1021:
1006:
1004:
1003:
998:
986:
984:
983:
978:
919:
893:
867:
850:
779:
777:
776:
771:
741:
739:
738:
733:
711:
709:
708:
703:
698:
687:
676:
566:Semigroup action
355:semigroup action
120:
119:
116:
113:
110:
89:
84:
83:
73:
66:
65:
55:
48:
31:
25:
24:
16:
1093:
1092:
1088:
1087:
1086:
1084:
1083:
1082:
1063:
1062:
1014:
1009:
1008:
989:
988:
912:
886:
860:
843:
811:
810:
795:stands for ? --
756:
755:
718:
717:
691:
680:
669:
637:
636:
621:
585:
440:
278:
156:
117:
114:
111:
108:
107:
85:
78:
32:on Knowledge's
29:
12:
11:
5:
1091:
1089:
1081:
1080:
1075:
1065:
1064:
1061:
1060:
1059:
1058:
1020:
1017:
996:
976:
973:
970:
967:
964:
961:
958:
955:
952:
949:
946:
943:
940:
937:
934:
931:
928:
925:
922:
918:
915:
911:
908:
905:
902:
899:
896:
892:
889:
885:
882:
879:
876:
873:
870:
866:
863:
859:
856:
853:
849:
846:
842:
839:
836:
833:
830:
827:
824:
821:
818:
769:
766:
763:
731:
728:
725:
701:
697:
694:
690:
686:
683:
679:
675:
672:
668:
665:
662:
659:
656:
653:
650:
647:
644:
627:-homorphisms.
620:
619:M-homomorphism
617:
616:
615:
592:VasileGaburici
584:
581:
562:
561:
560:
559:
558:
557:
556:
555:
554:
553:
531:VasileGaburici
488:VasileGaburici
483:
473:VasileGaburici
465:
464:
439:
436:
435:
434:
433:
432:
431:
430:
429:
428:
427:
426:
396:VasileGaburici
337:VasileGaburici
321:
320:
317:
309:
305:
301:
298:
294:
277:
274:
273:
272:
184:
183:
155:
149:
146:
145:
142:
141:
138:
137:
130:
124:
123:
121:
104:the discussion
91:
90:
74:
62:
61:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
1090:
1079:
1076:
1074:
1071:
1070:
1068:
1057:
1053:
1049:
1045:
1044:
1043:
1039:
1035:
1018:
1015:
994:
965:
962:
959:
953:
947:
944:
938:
935:
929:
923:
916:
913:
906:
903:
900:
894:
890:
887:
880:
877:
874:
871:
864:
861:
857:
854:
851:
847:
844:
831:
828:
825:
822:
819:
809:
808:
807:
806:
802:
798:
794:
789:
787:
783:
767:
761:
753:
749:
745:
729:
723:
715:
695:
692:
688:
684:
681:
677:
673:
670:
657:
654:
651:
648:
645:
634:
630:
626:
618:
614:
611:
610:
604:
603:
602:
601:
597:
593:
590:
582:
580:
579:
575:
571:
567:
552:
549:
548:
542:
541:
540:
536:
532:
528:
524:
519:
518:
517:
514:
513:
508:
503:
499:
498:
497:
493:
489:
484:
482:
478:
474:
469:
468:
467:
466:
463:
460:
459:
454:
449:
448:
447:
445:
437:
425:
422:
421:
416:
412:
407:
406:
405:
401:
397:
392:
391:
390:
387:
386:
381:
377:
372:
371:
370:
367:
366:
360:
359:semiautomaton
356:
352:
348:
347:
346:
342:
338:
334:
333:
332:
331:
328:
327:
318:
315:
310:
306:
302:
299:
295:
292:
291:Hilbert space
288:
283:
282:
281:
275:
271:
267:
263:
259:
258:
257:
256:
252:
248:
244:
240:
235:
232:
231:
227:
223:
218:
217:
214:
208:
207:
204:
198:
197:
194:
189:
182:
179:
175:
174:
173:
172:
169:
165:
161:
160:semiautomaton
154:
150:
135:
129:
126:
125:
122:
105:
101:
97:
96:
88:
82:
77:
75:
72:
68:
67:
63:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
792:
790:
785:
781:
751:
747:
743:
713:
632:
628:
624:
622:
609:Geometry guy
607:
586:
563:
547:Geometry guy
545:
526:
512:Geometry guy
510:
506:
501:
458:Geometry guy
456:
441:
420:Geometry guy
418:
411:good article
385:Geometry guy
383:
365:Geometry guy
363:
350:
326:Geometry guy
324:
322:
279:
236:
233:
219:
209:
199:
185:
157:
93:
40:WikiProjects
453:free monoid
314:free monoid
151:Merge from
109:Mathematics
100:mathematics
59:Mathematics
30:Start-class
1067:Categories
262:Sam Staton
247:Sam Staton
222:Sam Staton
203:Sam Staton
191:commute)?
716:as being
527:effective
304:element).
213:Jrgetsin
507:wanting
193:Daveagp
1034:Beroal
570:Beroal
36:scale.
797:Gzorg
289:on a
178:linas
168:linas
1052:talk
1038:talk
1032:. --
801:talk
596:talk
574:talk
568:. --
535:talk
502:want
492:talk
477:talk
400:talk
378:and
341:talk
266:talk
251:talk
226:talk
784:or
529:).
128:???
1069::
1054:)
1040:)
987:.
954:μ
914:μ
904:∈
898:∀
884:→
862:μ
838:→
832:μ
803:)
786:qm
765:→
727:→
693:μ
664:→
658:μ
598:)
576:)
537:)
494:)
479:)
402:)
382:.
343:)
268:)
253:)
228:)
1050:(
1036:(
1019:′
1016:Q
995:B
975:)
972:)
969:)
966:m
963:,
960:q
957:(
951:(
948:f
945:=
942:)
939:m
936:,
933:)
930:q
927:(
924:f
921:(
917:′
910:(
907:Q
901:q
895:,
891:′
888:Q
881:Q
878::
875:f
872:,
869:)
865:′
858:,
855:M
852:,
848:′
845:Q
841:(
835:)
829:,
826:M
823:,
820:Q
817:(
799:(
793:B
782:q
768:M
762:Q
752:m
748:Q
744:Q
730:Q
724:Q
714:f
700:)
696:′
689:,
685:′
682:M
678:,
674:′
671:Q
667:(
661:)
655:,
652:M
649:,
646:Q
643:(
633:f
629:f
625:M
594:(
572:(
533:(
490:(
475:(
398:(
351:M
339:(
264:(
249:(
224:(
136:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
