1270:. If we consider the rewriting relation as an indexed set of relations, as some authors do, then a labeled transition system is equivalent to an abstract rewriting system with the indices being the labels. The focus of the study and the terminology are different, however. In a transition system one is interested in interpreting the labels as actions, whereas in an abstract rewriting system the focus is on how objects may be transformed (rewritten) into others.
597:
Labels can represent different things depending on the language of interest. Typical uses of labels include representing input expected, conditions that must be true to trigger the transition, or actions performed during the transition. Labelled transitions systems were originally introduced as
1257:
There are many relations between these concepts. Some are simple, such as observing that a labelled transition system where the set of labels consists of only one element is equivalent to an unlabelled transition system. However, not all these relations are equally trivial.
1200:
1118:
994:
590:
444:
1247:
548:
1060:
1018:
348:
303:
832:
687:
277:
199:
945:
388:
872:
794:
727:
649:
504:
1128:
129:
54:
and transitions between states, which may be labeled with labels chosen from a set; the same label may appear on more than one transition. If the label set is a
925:
896:
852:
774:
751:
707:
629:
484:
464:
408:
368:
239:
219:
169:
149:
1282:, a transition system is sometimes defined to include an additional labeling function for the states as well, resulting in a notion that encompasses that of
1065:
1454:
954:
1427:
558:
1497:
417:
1445:
1215:
35:
509:
1267:
62:
1027:
999:
315:
282:
799:
654:
58:, the system is essentially unlabeled, and a simpler definition that omits the labels is possible.
51:
55:
244:
178:
1195:{\displaystyle p\mapsto \{\,(\alpha ,q)\in \Lambda \times S\mid p\xrightarrow {\alpha } q\,\}}
930:
373:
1359:
1339:
857:
779:
712:
634:
489:
70:
20:
1369:
102:
1266:
As a mathematical object, an unlabeled transition system is identical with an (unindexed)
8:
1349:
1374:
907:
The formal definition can be rephrased as follows. Labelled state transition systems on
910:
881:
837:
759:
736:
692:
614:
469:
449:
393:
353:
224:
204:
154:
134:
1450:
1423:
1334:
1364:
1344:
1329:
1283:
1324:
1289:
47:
24:
1440:
1279:
66:
1491:
1252:
28:
1394:
1354:
1209:
43:
1021:
948:
1179:
569:
80:
The set of transitions is not necessarily finite, or even countable.
1471:
Linköping
Electronic Articles in Computer and Information Science
1439:
1469:
Micheal
Gelfond, Vladimir Lifschitz (1998) "Action Languages",
77:
The set of states is not necessarily finite, or even countable.
1113:{\displaystyle \xi _{T}:S\to {\mathcal {P}}(\Lambda \times S)}
1261:
1253:
Relation between labelled and unlabelled transition system
87:
Transition systems can be represented as directed graphs.
1208:
In other words, a labelled state transition system is a
1292:
are extensions of transition systems, adding a set of
1218:
1131:
1068:
1030:
1002:
989:{\displaystyle S\to {\mathcal {P}}(\Lambda \times S)}
957:
933:
913:
884:
860:
840:
802:
782:
762:
739:
715:
695:
657:
637:
617:
561:
512:
492:
472:
452:
420:
396:
376:
356:
318:
285:
247:
227:
207:
181:
157:
137:
105:
19:
This article is about transition systems as used in
1418:Marc Bezem, J. W. Klop, Roel de Vrijer ("Terese"),
46:. It is used to describe the potential behavior of
1241:
1194:
1112:
1054:
1012:
988:
939:
919:
890:
866:
846:
826:
788:
768:
745:
721:
701:
681:
643:
623:
584:
542:
498:
478:
458:
438:
402:
382:
362:
342:
297:
271:
233:
213:
193:
163:
143:
123:
1489:
61:Transition systems coincide mathematically with
446:. We say that there is a transition from state
201:. We say that there is a transition from state
1433:
83:No "start" state or "final" states are given.
1189:
1138:
585:{\displaystyle p\xrightarrow {\alpha } q\,.}
65:(as explained further in this article) and
16:State machine that may have infinite states
1262:Comparison with abstract rewriting systems
1188:
1141:
578:
1395:Formal Verification of Parallel Programs
902:
439:{\displaystyle S\times \Lambda \times S}
1490:
1242:{\displaystyle P(\Lambda \times {-})}
1422:, Cambridge University Press, 2003,
90:
651:, there exists only a single tuple
13:
1225:
1160:
1098:
1090:
1040:
1005:
974:
966:
934:
796:, there exists at least one tuple
543:{\displaystyle (p,\alpha ,q)\in T}
427:
377:
328:
42:is a concept used in the study of
14:
1509:
605:
1463:
1443:; Joost-Pieter Katoen (2008).
1412:
1393:Robert M. Keller (July 1976) "
1387:
1236:
1222:
1154:
1142:
1135:
1107:
1095:
1085:
1055:{\displaystyle (S,\Lambda ,T)}
1049:
1031:
1013:{\displaystyle {\mathcal {P}}}
983:
971:
961:
821:
803:
676:
658:
531:
513:
343:{\displaystyle (S,\Lambda ,T)}
337:
319:
298:{\displaystyle p\rightarrow q}
289:
260:
248:
118:
106:
1:
1449:. The MIT Press. p. 20.
1380:
1273:
827:{\displaystyle (p,\alpha ,q)}
682:{\displaystyle (p,\alpha ,q)}
1446:Principles of Model Checking
412:labelled transition relation
36:theoretical computer science
7:
1318:
1303:, and a function that maps
10:
1514:
310:labelled transition system
272:{\displaystyle (p,q)\in T}
63:abstract rewriting systems
18:
1399:Communications of the ACM
1268:abstract rewriting system
194:{\displaystyle S\times S}
940:{\displaystyle \Lambda }
390:is a set of labels, and
383:{\displaystyle \Lambda }
1024:. Under this bijection
867:{\displaystyle \alpha }
789:{\displaystyle \alpha }
722:{\displaystyle \alpha }
644:{\displaystyle \alpha }
499:{\displaystyle \alpha }
151:is a set of states and
1420:Term rewriting systems
1243:
1196:
1114:
1056:
1014:
990:
941:
921:
892:
868:
848:
828:
790:
770:
747:
723:
703:
683:
645:
625:
586:
544:
500:
480:
460:
440:
404:
384:
364:
344:
299:
273:
235:
215:
195:
165:
145:
125:
1498:Models of computation
1360:Operational semantics
1340:Transformation monoid
1244:
1197:
1115:
1057:
1015:
991:
942:
922:
903:Coalgebra formulation
893:
869:
854:, then one says that
849:
829:
791:
771:
748:
724:
709:, then one says that
704:
684:
646:
626:
587:
545:
501:
481:
461:
441:
405:
385:
365:
345:
300:
274:
236:
216:
196:
166:
146:
126:
124:{\displaystyle (S,T)}
71:finite-state automata
27:-theoretic view, see
21:operational semantics
1370:Finite-state machine
1216:
1129:
1066:
1028:
1000:
955:
931:
911:
882:
858:
838:
800:
780:
760:
737:
713:
693:
655:
635:
615:
602:transition systems.
559:
510:
490:
470:
450:
418:
394:
374:
370:is a set of states,
354:
316:
283:
245:
225:
205:
179:
155:
135:
103:
1350:Simulation preorder
1183:
1020:is the (covariant)
573:
173:transition relation
69:. They differ from
1299:, a set of values
1239:
1192:
1110:
1052:
1010:
986:
937:
917:
888:
864:
844:
824:
786:
766:
756:If, for any given
743:
719:
699:
679:
641:
621:
611:If, for any given
582:
540:
496:
476:
456:
436:
400:
380:
360:
340:
295:
269:
231:
211:
191:
161:
141:
121:
50:. It consists of
1456:978-0-262-02649-9
1335:Transition monoid
1184:
927:with labels from
920:{\displaystyle S}
891:{\displaystyle p}
847:{\displaystyle T}
769:{\displaystyle p}
746:{\displaystyle p}
702:{\displaystyle T}
624:{\displaystyle p}
574:
479:{\displaystyle q}
459:{\displaystyle p}
414:, is a subset of
403:{\displaystyle T}
363:{\displaystyle S}
234:{\displaystyle q}
214:{\displaystyle p}
175:, is a subset of
164:{\displaystyle T}
144:{\displaystyle S}
97:transition system
91:Formal definition
73:in several ways:
40:transition system
1505:
1482:
1467:
1461:
1460:
1437:
1431:
1416:
1410:
1391:
1375:Modal μ-calculus
1365:Kripke structure
1345:Semigroup action
1330:Ternary relation
1290:Action languages
1284:Kripke structure
1248:
1246:
1245:
1240:
1235:
1212:for the functor
1201:
1199:
1198:
1193:
1175:
1119:
1117:
1116:
1111:
1094:
1093:
1078:
1077:
1061:
1059:
1058:
1053:
1022:powerset functor
1019:
1017:
1016:
1011:
1009:
1008:
995:
993:
992:
987:
970:
969:
946:
944:
943:
938:
926:
924:
923:
918:
897:
895:
894:
889:
873:
871:
870:
865:
853:
851:
850:
845:
833:
831:
830:
825:
795:
793:
792:
787:
775:
773:
772:
767:
752:
750:
749:
744:
728:
726:
725:
720:
708:
706:
705:
700:
688:
686:
685:
680:
650:
648:
647:
642:
630:
628:
627:
622:
591:
589:
588:
583:
565:
549:
547:
546:
541:
505:
503:
502:
497:
485:
483:
482:
477:
465:
463:
462:
457:
445:
443:
442:
437:
409:
407:
406:
401:
389:
387:
386:
381:
369:
367:
366:
361:
349:
347:
346:
341:
304:
302:
301:
296:
279:, and denote it
278:
276:
275:
270:
240:
238:
237:
232:
220:
218:
217:
212:
200:
198:
197:
192:
170:
168:
167:
162:
150:
148:
147:
142:
130:
128:
127:
122:
48:discrete systems
1513:
1512:
1508:
1507:
1506:
1504:
1503:
1502:
1488:
1487:
1486:
1485:
1468:
1464:
1457:
1438:
1434:
1417:
1413:
1392:
1388:
1383:
1325:Binary relation
1321:
1276:
1264:
1255:
1231:
1217:
1214:
1213:
1130:
1127:
1126:
1089:
1088:
1073:
1069:
1067:
1064:
1063:
1029:
1026:
1025:
1004:
1003:
1001:
998:
997:
965:
964:
956:
953:
952:
951:with functions
932:
929:
928:
912:
909:
908:
905:
883:
880:
879:
859:
856:
855:
839:
836:
835:
801:
798:
797:
781:
778:
777:
761:
758:
757:
738:
735:
734:
714:
711:
710:
694:
691:
690:
656:
653:
652:
636:
633:
632:
616:
613:
612:
608:
560:
557:
556:
550:and denote it
511:
508:
507:
491:
488:
487:
471:
468:
467:
451:
448:
447:
419:
416:
415:
395:
392:
391:
375:
372:
371:
355:
352:
351:
317:
314:
313:
284:
281:
280:
246:
243:
242:
226:
223:
222:
206:
203:
202:
180:
177:
176:
156:
153:
152:
136:
133:
132:
104:
101:
100:
93:
67:directed graphs
32:
17:
12:
11:
5:
1511:
1501:
1500:
1484:
1483:
1462:
1455:
1441:Christel Baier
1432:
1411:
1409:, pp. 371–384.
1385:
1384:
1382:
1379:
1378:
1377:
1372:
1367:
1362:
1357:
1352:
1347:
1342:
1337:
1332:
1327:
1320:
1317:
1280:model checking
1275:
1272:
1263:
1260:
1254:
1251:
1238:
1234:
1230:
1227:
1224:
1221:
1206:
1205:
1204:
1203:
1191:
1187:
1182:
1178:
1174:
1171:
1168:
1165:
1162:
1159:
1156:
1153:
1150:
1147:
1144:
1140:
1137:
1134:
1109:
1106:
1103:
1100:
1097:
1092:
1087:
1084:
1081:
1076:
1072:
1051:
1048:
1045:
1042:
1039:
1036:
1033:
1007:
985:
982:
979:
976:
973:
968:
963:
960:
936:
916:
904:
901:
900:
899:
887:
863:
843:
823:
820:
817:
814:
811:
808:
805:
785:
765:
754:
742:
718:
698:
678:
675:
672:
669:
666:
663:
660:
640:
620:
607:
604:
595:
594:
593:
592:
581:
577:
572:
568:
564:
539:
536:
533:
530:
527:
524:
521:
518:
515:
495:
475:
455:
435:
432:
429:
426:
423:
399:
379:
359:
339:
336:
333:
330:
327:
324:
321:
294:
291:
288:
268:
265:
262:
259:
256:
253:
250:
230:
210:
190:
187:
184:
160:
140:
120:
117:
114:
111:
108:
92:
89:
85:
84:
81:
78:
15:
9:
6:
4:
3:
2:
1510:
1499:
1496:
1495:
1493:
1480:
1476:
1472:
1466:
1458:
1452:
1448:
1447:
1442:
1436:
1429:
1428:0-521-39115-6
1425:
1421:
1415:
1408:
1404:
1400:
1396:
1390:
1386:
1376:
1373:
1371:
1368:
1366:
1363:
1361:
1358:
1356:
1353:
1351:
1348:
1346:
1343:
1341:
1338:
1336:
1333:
1331:
1328:
1326:
1323:
1322:
1316:
1314:
1310:
1306:
1302:
1298:
1295:
1291:
1287:
1285:
1281:
1271:
1269:
1259:
1250:
1232:
1228:
1219:
1211:
1185:
1180:
1176:
1172:
1169:
1166:
1163:
1157:
1151:
1148:
1145:
1132:
1125:
1124:
1123:
1122:
1121:
1120:, defined by
1104:
1101:
1082:
1079:
1074:
1070:
1046:
1043:
1037:
1034:
1023:
980:
977:
958:
950:
914:
885:
877:
861:
841:
818:
815:
812:
809:
806:
783:
763:
755:
740:
732:
731:deterministic
716:
696:
673:
670:
667:
664:
661:
638:
618:
610:
609:
606:Special cases
603:
601:
579:
575:
570:
566:
562:
555:
554:
553:
552:
551:
537:
534:
528:
525:
522:
519:
516:
493:
473:
453:
433:
430:
424:
421:
413:
397:
357:
334:
331:
325:
322:
311:
306:
292:
286:
266:
263:
257:
254:
251:
228:
208:
188:
185:
182:
174:
158:
138:
115:
112:
109:
98:
88:
82:
79:
76:
75:
74:
72:
68:
64:
59:
57:
53:
49:
45:
41:
37:
30:
29:semiautomaton
26:
22:
1478:
1474:
1470:
1465:
1444:
1435:
1419:
1414:
1406:
1402:
1398:
1389:
1355:Bisimulation
1312:
1308:
1304:
1300:
1296:
1293:
1288:
1277:
1265:
1256:
1207:
906:
875:
730:
599:
596:
411:
309:
307:
172:
96:
95:Formally, a
94:
86:
60:
39:
33:
1062:is sent to
947:correspond
486:with label
312:is a tuple
44:computation
1430:. pp. 7–8.
1381:References
1274:Extensions
949:one-to-one
876:executable
99:is a pair
1233:−
1229:×
1226:Λ
1210:coalgebra
1181:α
1170:∣
1164:×
1161:Λ
1158:∈
1146:α
1136:↦
1102:×
1099:Λ
1086:→
1071:ξ
1041:Λ
978:×
975:Λ
962:→
935:Λ
862:α
813:α
784:α
717:α
668:α
639:α
571:α
535:∈
523:α
494:α
466:to state
431:×
428:Λ
425:×
378:Λ
329:Λ
290:→
264:∈
221:to state
186:×
56:singleton
23:. For an
1492:Category
1319:See also
1177:→
996:, where
567:→
25:automata
1473:, vol.
1401:, vol.
1307:×
1294:fluents
1477:, nr.
1453:
1426:
1405:, nr.
410:, the
350:where
171:, the
131:where
52:states
878:(for
733:(for
600:named
1451:ISBN
1424:ISBN
776:and
631:and
506:iff
241:iff
38:, a
1397:",
1311:to
1278:In
874:is
834:in
729:is
689:in
34:In
1494::
1479:16
1403:19
1315:.
1286:.
1249:.
898:).
753:).
308:A
305:.
1481:.
1475:3
1459:.
1407:7
1313:V
1309:S
1305:F
1301:V
1297:F
1237:)
1223:(
1220:P
1202:.
1190:}
1186:q
1173:p
1167:S
1155:)
1152:q
1149:,
1143:(
1139:{
1133:p
1108:)
1105:S
1096:(
1091:P
1083:S
1080::
1075:T
1050:)
1047:T
1044:,
1038:,
1035:S
1032:(
1006:P
984:)
981:S
972:(
967:P
959:S
915:S
886:p
842:T
822:)
819:q
816:,
810:,
807:p
804:(
764:p
741:p
697:T
677:)
674:q
671:,
665:,
662:p
659:(
619:p
580:.
576:q
563:p
538:T
532:)
529:q
526:,
520:,
517:p
514:(
474:q
454:p
434:S
422:S
398:T
358:S
338:)
335:T
332:,
326:,
323:S
320:(
293:q
287:p
267:T
261:)
258:q
255:,
252:p
249:(
229:q
209:p
189:S
183:S
159:T
139:S
119:)
116:T
113:,
110:S
107:(
31:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.