1021:
of bisimilarity. From this follows that if similarity is a simulation, it equals bisimilarity. And if it equals bisimilarity, it is naturally a simulation (since bisimilarity is a simulation). Therefore, similarity is a simulation if and only if it equals bisimilarity. If it does not, it must be its
507:
1030:
When comparing two different transition systems (S', Λ', →') and (S", Λ", →"), the basic notions of simulation and similarity can be used by forming the disjoint composition of the two machines, (S, Λ, →) with S = S' ∐ S", Λ = Λ' ∪ Λ" and → = →' ∪ →", where ∐ is the
827:
The set of simulations is closed under union; therefore, the simulation preorder is itself a simulation. Since it is the union of all simulations, it is the unique largest simulation. Simulations are also closed under
432:
368:
330:
179:
416:
211:
764:
53:
The basic definition relates states within one transition system, but this is easily adapted to relate two separate transition systems by building a system consisting of the
915:
642:
802:
700:
1146:
287:
147:
107:
720:
247:
1108:
995:
975:
955:
935:
885:
865:
822:
662:
614:
590:
570:
550:
530:
267:
127:
87:
836:
closure; therefore, the largest simulation must be reflexive and transitive. From this follows that the largest simulation—the simulation preorder—is indeed a
997:. Similarity is thus the maximal symmetric subset of the simulation preorder, which means it is reflexive, symmetric, and transitive; hence an
1001:. However, it is not necessarily a simulation, and precisely in those cases when it is not a simulation, it is strictly coarser than
502:{\displaystyle R^{-1}\,;\,{\overset {\lambda }{\rightarrow }}\quad {\subseteq }\quad {\overset {\lambda }{\rightarrow }}\,;\,R^{-1}}
1169:
1302:
1242:
1252:
van
Glabbeek, R. J. (2001). "The Linear Time – Branching Time Spectrum I: The Semantics of Concrete, Sequential Processes".
335:
297:
17:
1222:
1281:
152:
1017:
of bisimilarity, which is the union of all bisimulations. Yet it is easy to see that similarity is always a
28:
184:
1307:
729:
840:. Note that there can be more than one relation that is both a simulation and a preorder; the term
423:
894:
373:
1044:
619:
66:
40:
769:
667:
1113:
36:
272:
132:
92:
1059:
1211:
998:
705:
220:
1090:
8:
980:
960:
940:
920:
870:
850:
833:
807:
647:
599:
575:
555:
535:
515:
252:
112:
72:
1277:
1238:
1188:
829:
1230:
1178:
1005:(meaning it is a superset of bisimilarity). To witness, consider a similarity that
149:
is a set of labels and → is a set of labelled transitions (i.e., a subset of
1226:
50:
Intuitively, a system simulates another system if it can match all of its moves.
1032:
54:
1183:
1164:
1296:
1192:
43:
associating systems that behave in the same way in the sense that one system
1269:
1049:
1002:
844:
refers to the largest one of them (which is a superset of all the others).
1054:
1234:
837:
1022:
strict superset; hence a strictly coarser equivalence relation.
1025:
1165:"NFA reduction algorithms by means of regular inequalities"
363:{\displaystyle q{\overset {\lambda }{\rightarrow }}q'}
325:{\displaystyle p{\overset {\lambda }{\rightarrow }}p'}
1116:
1093:
1078:
Meaning the union of two simulations is a simulation.
983:
963:
943:
923:
897:
873:
853:
810:
772:
732:
708:
670:
650:
622:
602:
578:
558:
538:
518:
435:
376:
338:
300:
275:
255:
223:
187:
155:
135:
115:
95:
75:
1140:
1102:
989:
969:
949:
929:
909:
879:
859:
816:
796:
758:
714:
694:
656:
636:
608:
584:
564:
544:
524:
501:
410:
362:
324:
281:
261:
241:
205:
173:
141:
121:
101:
81:
1162:
1294:
1212:"Concurrency and Automata on Infinite Sequences"
1219:Proceedings of the 5th GI-Conference, Karlsruhe
1009:a simulation. Since it is symmetric, it is a
1251:
1135:
1117:
1097:
1094:
1148:—each is both a simulation and a preorder.
726:, and it is the union of all simulations:
1182:
1026:Similarity of separate transition systems
755:
751:
630:
626:
485:
481:
453:
449:
217:if and only if for every pair of states
174:{\displaystyle S\times \Lambda \times S}
644:, if and only if there is a simulation
14:
1295:
1268:
1163:Champarnaud, J.-M; Coulon, F. (2004).
1209:
206:{\displaystyle R\subseteq S\times S}
60:
24:
759:{\displaystyle (p,q)\in \,\leq \,}
276:
162:
136:
96:
25:
1319:
1223:Lecture Notes in Computer Science
57:of the corresponding components.
67:labelled state transition system
470:
464:
1262:
1151:
1132:
1120:
1081:
1072:
785:
773:
745:
733:
683:
671:
473:
456:
399:
377:
344:
306:
236:
224:
13:
1:
1274:Communication and Concurrency
1203:
1303:Theoretical computer science
1170:Theoretical Computer Science
910:{\displaystyle p\leq \geq q}
411:{\displaystyle (p',q')\in R}
29:theoretical computer science
7:
1276:. USA: Prentice-Hall, Inc.
1254:Handbook of Process Algebra
1217:. In Deussen, Peter (ed.).
1038:
637:{\displaystyle p\,\leq \,q}
10:
1324:
1256:. Elsevier. pp. 3–99.
797:{\displaystyle (p,q)\in R}
695:{\displaystyle (p,q)\in R}
422:Equivalently, in terms of
1184:10.1016/j.tcs.2004.02.048
1141:{\displaystyle \{(0,0)\}}
269:and all labels λ in
1065:
282:{\displaystyle \Lambda }
142:{\displaystyle \Lambda }
102:{\displaystyle \Lambda }
41:state transition systems
1087:Consider the relations
1045:State transition system
1035:operator between sets.
1142:
1104:
991:
971:
951:
931:
911:
881:
861:
818:
798:
760:
716:
696:
658:
638:
610:
586:
566:
546:
526:
503:
424:relational composition
412:
364:
326:
283:
263:
243:
207:
175:
143:
123:
103:
83:
1143:
1105:
1060:Operational semantics
992:
972:
952:
932:
912:
882:
862:
819:
799:
761:
717:
715:{\displaystyle \leq }
697:
659:
639:
611:
587:
567:
547:
527:
504:
413:
365:
327:
284:
264:
244:
242:{\displaystyle (p,q)}
208:
176:
144:
124:
104:
84:
1229:. pp. 167–183.
1210:Park, David (1981).
1157:For an example, see
1114:
1103:{\displaystyle \{\}}
1091:
1013:. It must then be a
999:equivalence relation
981:
977:can be simulated by
961:
941:
937:can be simulated by
921:
895:
871:
851:
808:
804:for some simulation
770:
730:
706:
668:
648:
620:
600:
576:
556:
536:
516:
433:
374:
336:
298:
273:
253:
221:
185:
153:
133:
129:is a set of states,
113:
93:
73:
842:simulation preorder
724:simulation preorder
18:Simulation preorder
1308:Transition systems
1235:10.1007/BFb0017309
1138:
1100:
987:
967:
947:
927:
907:
902:≤ ≥
877:
857:
814:
794:
756:
712:
692:
654:
634:
606:
582:
562:
542:
522:
499:
408:
360:
322:
279:
259:
239:
203:
171:
139:
119:
109:, →), where
99:
79:
1244:978-3-540-10576-3
1225:. Vol. 104.
990:{\displaystyle p}
970:{\displaystyle q}
950:{\displaystyle q}
930:{\displaystyle p}
917:, if and only if
880:{\displaystyle q}
860:{\displaystyle p}
838:preorder relation
817:{\displaystyle R}
657:{\displaystyle R}
609:{\displaystyle q}
585:{\displaystyle p}
565:{\displaystyle S}
545:{\displaystyle q}
525:{\displaystyle p}
512:Given two states
479:
462:
350:
312:
262:{\displaystyle R}
122:{\displaystyle S}
82:{\displaystyle S}
61:Formal definition
16:(Redirected from
1315:
1288:
1287:
1266:
1257:
1248:
1216:
1197:
1196:
1186:
1155:
1149:
1147:
1145:
1144:
1139:
1109:
1107:
1106:
1101:
1085:
1079:
1076:
996:
994:
993:
988:
976:
974:
973:
968:
956:
954:
953:
948:
936:
934:
933:
928:
916:
914:
913:
908:
886:
884:
883:
878:
866:
864:
863:
858:
823:
821:
820:
815:
803:
801:
800:
795:
765:
763:
762:
757:
721:
719:
718:
713:
701:
699:
698:
693:
663:
661:
660:
655:
643:
641:
640:
635:
615:
613:
612:
607:
591:
589:
588:
583:
571:
569:
568:
563:
551:
549:
548:
543:
531:
529:
528:
523:
508:
506:
505:
500:
498:
497:
480:
472:
469:
463:
455:
448:
447:
417:
415:
414:
409:
398:
387:
369:
367:
366:
361:
359:
351:
343:
332:, then there is
331:
329:
328:
323:
321:
313:
305:
288:
286:
285:
280:
268:
266:
265:
260:
248:
246:
245:
240:
212:
210:
209:
204:
180:
178:
177:
172:
148:
146:
145:
140:
128:
126:
125:
120:
108:
106:
105:
100:
88:
86:
85:
80:
21:
1323:
1322:
1318:
1317:
1316:
1314:
1313:
1312:
1293:
1292:
1291:
1284:
1267:
1263:
1245:
1227:Springer-Verlag
1214:
1206:
1201:
1200:
1156:
1152:
1115:
1112:
1111:
1092:
1089:
1088:
1086:
1082:
1077:
1073:
1068:
1041:
1028:
982:
979:
978:
962:
959:
958:
942:
939:
938:
922:
919:
918:
896:
893:
892:
887:are said to be
872:
869:
868:
852:
849:
848:
809:
806:
805:
771:
768:
767:
766:precisely when
731:
728:
727:
707:
704:
703:
702:. The relation
669:
666:
665:
649:
646:
645:
621:
618:
617:
601:
598:
597:
577:
574:
573:
557:
554:
553:
537:
534:
533:
517:
514:
513:
490:
486:
471:
465:
454:
440:
436:
434:
431:
430:
391:
380:
375:
372:
371:
352:
342:
337:
334:
333:
314:
304:
299:
296:
295:
274:
271:
270:
254:
251:
250:
222:
219:
218:
186:
183:
182:
154:
151:
150:
134:
131:
130:
114:
111:
110:
94:
91:
90:
74:
71:
70:
63:
23:
22:
15:
12:
11:
5:
1321:
1311:
1310:
1305:
1290:
1289:
1282:
1260:
1259:
1258:
1249:
1243:
1205:
1202:
1199:
1198:
1177:(3): 241–253.
1150:
1137:
1134:
1131:
1128:
1125:
1122:
1119:
1099:
1096:
1080:
1070:
1069:
1067:
1064:
1063:
1062:
1057:
1052:
1047:
1040:
1037:
1033:disjoint union
1027:
1024:
986:
966:
946:
926:
906:
903:
900:
876:
856:
813:
793:
790:
787:
784:
781:
778:
775:
754:
750:
747:
744:
741:
738:
735:
722:is called the
711:
691:
688:
685:
682:
679:
676:
673:
653:
633:
629:
625:
605:
581:
561:
541:
521:
510:
509:
496:
493:
489:
484:
478:
475:
468:
461:
458:
452:
446:
443:
439:
420:
419:
407:
404:
401:
397:
394:
390:
386:
383:
379:
358:
355:
349:
346:
341:
320:
317:
311:
308:
303:
278:
258:
238:
235:
232:
229:
226:
202:
199:
196:
193:
190:
181:), a relation
170:
167:
164:
161:
158:
138:
118:
98:
78:
62:
59:
55:disjoint union
9:
6:
4:
3:
2:
1320:
1309:
1306:
1304:
1301:
1300:
1298:
1285:
1279:
1275:
1271:
1270:Milner, Robin
1265:
1261:
1255:
1250:
1246:
1240:
1236:
1232:
1228:
1224:
1220:
1213:
1208:
1207:
1194:
1190:
1185:
1180:
1176:
1172:
1171:
1166:
1160:
1154:
1129:
1126:
1123:
1084:
1075:
1071:
1061:
1058:
1056:
1053:
1051:
1048:
1046:
1043:
1042:
1036:
1034:
1023:
1020:
1016:
1012:
1008:
1004:
1000:
984:
964:
944:
924:
904:
901:
898:
890:
874:
854:
845:
843:
839:
835:
831:
825:
811:
791:
788:
782:
779:
776:
752:
748:
742:
739:
736:
725:
709:
689:
686:
680:
677:
674:
651:
631:
627:
623:
603:
595:
579:
559:
539:
519:
494:
491:
487:
482:
476:
466:
459:
450:
444:
441:
437:
429:
428:
427:
425:
418:
405:
402:
395:
392:
388:
384:
381:
356:
353:
347:
339:
318:
315:
309:
301:
292:
291:
290:
256:
233:
230:
227:
216:
200:
197:
194:
191:
188:
168:
165:
159:
156:
116:
76:
68:
58:
56:
51:
48:
46:
42:
38:
34:
30:
19:
1273:
1264:
1253:
1218:
1174:
1168:
1158:
1153:
1083:
1074:
1050:Bisimulation
1029:
1018:
1014:
1011:bisimulation
1010:
1006:
1003:bisimilarity
888:
846:
841:
826:
723:
593:
511:
421:
293:
214:
64:
52:
49:
44:
32:
26:
1055:Coinduction
847:Two states
47:the other.
1297:Categories
1283:0131149849
1204:References
891:, written
834:transitive
664:such that
616:, written
370:such that
215:simulation
33:simulation
1193:0304-3975
830:reflexive
789:∈
753:≤
749:∈
710:≤
687:∈
628:≤
594:simulated
492:−
477:λ
474:→
467:⊆
460:λ
457:→
442:−
403:∈
348:λ
345:→
310:λ
307:→
277:Λ
198:×
192:⊆
166:×
163:Λ
160:×
137:Λ
97:Λ
45:simulates
1272:(1989).
1039:See also
1019:superset
396:′
385:′
357:′
319:′
65:Given a
39:between
37:relation
889:similar
592:can be
1280:
1241:
1191:
1159:Fig. 1
1015:subset
1215:(PDF)
1066:Notes
213:is a
35:is a
1278:ISBN
1239:ISBN
1189:ISSN
1110:and
957:and
867:and
832:and
532:and
1231:doi
1179:doi
1175:327
1161:in
596:by
552:in
294:if
249:in
27:In
1299::
1237:.
1221:.
1187:.
1173:.
1167:.
1007:is
824:.
572:,
426::
289::
89:,
31:a
1286:.
1247:.
1233::
1195:.
1181::
1136:}
1133:)
1130:0
1127:,
1124:0
1121:(
1118:{
1098:}
1095:{
985:p
965:q
945:q
925:p
905:q
899:p
875:q
855:p
812:R
792:R
786:)
783:q
780:,
777:p
774:(
746:)
743:q
740:,
737:p
734:(
690:R
684:)
681:q
678:,
675:p
672:(
652:R
632:q
624:p
604:q
580:p
560:S
540:q
520:p
495:1
488:R
483:;
451:;
445:1
438:R
406:R
400:)
393:q
389:,
382:p
378:(
354:q
340:q
316:p
302:p
257:R
237:)
234:q
231:,
228:p
225:(
201:S
195:S
189:R
169:S
157:S
117:S
77:S
69:(
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.