1178:
1384:
484:
394:
1031:
1450:
910:
1226:
871:
676:
1069:
777:
604:
208:
827:
558:
522:
246:
179:
141:
1095:
942:
1159:
986:
966:
797:
280:
64:
1598:
1566:
1534:
1502:
1476:
736:
706:
1135:
1115:
644:
624:
437:
417:
348:
328:
304:
99:
1231:
1727:
445:
355:
1698:
419:. The independency relation is symmetric and irreflexive. Conversely, given any symmetric and irreflexive relation
35:
991:
1392:
283:
17:
876:
1187:
832:
649:
1667:
1036:
744:
571:
187:
805:
531:
495:
213:
146:
108:
27:, which is a generalization of the concept of linear dependence among members of a vector space.
1662:
1074:
915:
1144:
971:
951:
782:
265:
49:
1571:
1539:
1507:
257:
8:
1481:
1455:
945:
715:
685:
253:
24:
1120:
1100:
629:
609:
422:
402:
333:
313:
289:
84:
75:
71:
67:
1694:
1683:
1642:
1625:
1138:
1637:
31:
43:
1623:
1177:
1721:
1379:{\displaystyle D=\{(a,b),\,(b,a),\,(a,c),\,(c,a),\,(a,a),\,(b,b),\,(c,c)\}}
1166:
1162:
79:
399:
That is, the independency is the set of all ordered pairs that are not in
800:
1137:
by a finite sequence of swaps of adjacent independent symbols. The
1624:
IJsbrand Jan
Aalbersberg and Grzegorz Rozenberg (Mar 1988).
1619:
1617:
1615:
1613:
1610:
1574:
1542:
1510:
1484:
1458:
1395:
1234:
1190:
1147:
1123:
1103:
1077:
1039:
994:
974:
954:
918:
879:
835:
808:
785:
747:
718:
688:
652:
632:
612:
574:
534:
498:
448:
425:
405:
358:
336:
316:
292:
268:
216:
190:
149:
111:
87:
52:
479:{\displaystyle D=(\Sigma \times \Sigma )\setminus I}
389:{\displaystyle I=(\Sigma \times \Sigma )\setminus D}
1592:
1560:
1528:
1496:
1470:
1444:
1378:
1220:
1153:
1129:
1109:
1089:
1063:
1025:
980:
960:
936:
904:
865:
821:
791:
771:
730:
700:
670:
638:
618:
598:
552:
516:
478:
431:
411:
388:
342:
322:
298:
274:
240:
202:
173:
135:
93:
58:
1719:
829:of all possible strings of finite length by:
568:, but this term may also refer to the triple
1681:
1439:
1402:
1373:
1241:
1215:
1197:
1656:
1666:
1641:
1478:are independent of one another, and e.g.
1423:
1357:
1338:
1319:
1300:
1281:
1262:
256:; thus, they generalize the notion of an
252:In general, dependency relations are not
1689:. In Rozenberg, G.; Diekert, V. (eds.).
1026:{\displaystyle \equiv _{(\Sigma ,D,I)}}
779:, a symmetric and irreflexive relation
1720:
1659:Trace semantics for concurrent objects
1657:Vasconcelos, Vasco Thudichum (1992).
1228:, a possible dependency relation is
1445:{\displaystyle I=\{(b,c),\,(c,b)\}}
439:on a finite alphabet, the relation
13:
1389:The corresponding independency is
1191:
1176:
1043:
1003:
905:{\displaystyle x,y\in \Sigma ^{*}}
893:
810:
751:
665:
578:
538:
502:
464:
458:
374:
368:
269:
197:
78:. That is, it is a finite set of
53:
14:
1739:
1221:{\displaystyle \Sigma =\{a,b,c\}}
470:
380:
1693:. Singapore: World Scientific.
1661:(MsC thesis). Keio University.
866:{\displaystyle xaby\doteq xbay}
1728:Properties of binary relations
1684:"Introduction to Trace Theory"
1675:
1650:
1436:
1424:
1417:
1405:
1370:
1358:
1351:
1339:
1332:
1320:
1313:
1301:
1294:
1282:
1275:
1263:
1256:
1244:
1058:
1040:
1018:
1000:
766:
748:
671:{\displaystyle x,y\in \Sigma }
593:
575:
547:
535:
511:
499:
467:
455:
377:
365:
229:
217:
162:
150:
124:
112:
1:
1682:Mazurkiewicz, Antoni (1995).
1603:
1064:{\displaystyle (\Sigma ,D,I)}
772:{\displaystyle (\Sigma ,D,I)}
599:{\displaystyle (\Sigma ,D,I)}
1643:10.1016/0304-3975(88)90051-5
1630:Theoretical Computer Science
912:and all independent symbols
260:by discarding transitivity.
203:{\displaystyle a\in \Sigma }
7:
1172:
822:{\displaystyle \Sigma ^{*}}
553:{\displaystyle (\Sigma ,I)}
517:{\displaystyle (\Sigma ,D)}
18:Dependency (disambiguation)
10:
1744:
1600:, but to no other string.
1504:are dependent. The string
1071:-equivalence. Informally,
741:Given a reliance alphabet
489:is a dependency relation.
241:{\displaystyle (a,a)\in D}
174:{\displaystyle (b,a)\in D}
136:{\displaystyle (a,b)\in D}
22:
15:
1090:{\displaystyle p\equiv q}
1452:. Then e.g. the symbols
1117:can be transformed into
937:{\displaystyle a,b\in I}
23:Not to be confused with
1154:{\displaystyle \equiv }
981:{\displaystyle \equiv }
961:{\displaystyle \doteq }
792:{\displaystyle \doteq }
330:is the binary relation
275:{\displaystyle \Sigma }
59:{\displaystyle \Sigma }
1594:
1562:
1530:
1498:
1472:
1446:
1380:
1222:
1181:
1155:
1131:
1111:
1091:
1065:
1027:
982:
962:
938:
906:
867:
823:
799:can be defined on the
793:
773:
732:
702:
672:
640:
620:
600:
554:
518:
480:
433:
413:
390:
344:
324:
300:
276:
242:
204:
175:
137:
95:
60:
1595:
1593:{\displaystyle abbca}
1563:
1561:{\displaystyle abcba}
1531:
1529:{\displaystyle acbba}
1499:
1473:
1447:
1381:
1223:
1180:
1165:, and are studied in
1156:
1132:
1112:
1092:
1066:
1028:
983:
963:
939:
907:
868:
824:
794:
774:
733:
703:
673:
641:
621:
601:
562:independency alphabet
555:
519:
481:
434:
414:
391:
345:
325:
301:
277:
243:
205:
176:
138:
96:
61:
1572:
1540:
1508:
1482:
1456:
1393:
1232:
1188:
1145:
1121:
1101:
1097:holds if the string
1075:
1037:
992:
972:
952:
916:
877:
833:
806:
783:
745:
716:
686:
650:
630:
610:
572:
532:
496:
446:
423:
403:
356:
334:
314:
290:
266:
258:equivalence relation
214:
188:
147:
109:
85:
50:
16:For other uses, see
1497:{\displaystyle a,b}
1471:{\displaystyle b,c}
1184:Given the alphabet
1139:equivalence classes
946:equivalence closure
731:{\displaystyle xIy}
701:{\displaystyle xDy}
526:concurrent alphabet
282:is also called the
46:on a finite domain
40:dependency relation
34:, in particular in
25:Dependence relation
1691:The Book of Traces
1626:"Theory of traces"
1590:
1558:
1526:
1494:
1468:
1442:
1376:
1218:
1182:
1151:
1127:
1107:
1087:
1061:
1023:
978:
958:
934:
902:
863:
819:
789:
769:
728:
698:
668:
636:
616:
596:
550:
514:
476:
429:
409:
386:
340:
320:
296:
272:
238:
200:
171:
133:
91:
76:tolerance relation
56:
36:concurrency theory
1536:is equivalent to
1130:{\displaystyle q}
1110:{\displaystyle p}
639:{\displaystyle D}
619:{\displaystyle I}
566:reliance alphabet
432:{\displaystyle I}
412:{\displaystyle D}
343:{\displaystyle I}
323:{\displaystyle D}
299:{\displaystyle D}
94:{\displaystyle D}
1735:
1712:
1711:
1709:
1707:
1688:
1679:
1673:
1672:
1670:
1654:
1648:
1647:
1645:
1621:
1599:
1597:
1596:
1591:
1567:
1565:
1564:
1559:
1535:
1533:
1532:
1527:
1503:
1501:
1500:
1495:
1477:
1475:
1474:
1469:
1451:
1449:
1448:
1443:
1385:
1383:
1382:
1377:
1227:
1225:
1224:
1219:
1160:
1158:
1157:
1152:
1136:
1134:
1133:
1128:
1116:
1114:
1113:
1108:
1096:
1094:
1093:
1088:
1070:
1068:
1067:
1062:
1032:
1030:
1029:
1024:
1022:
1021:
987:
985:
984:
979:
967:
965:
964:
959:
943:
941:
940:
935:
911:
909:
908:
903:
901:
900:
873:for all strings
872:
870:
869:
864:
828:
826:
825:
820:
818:
817:
798:
796:
795:
790:
778:
776:
775:
770:
737:
735:
734:
729:
712:, else (i.e. if
707:
705:
704:
699:
677:
675:
674:
669:
645:
643:
642:
637:
625:
623:
622:
617:
605:
603:
602:
597:
559:
557:
556:
551:
523:
521:
520:
515:
485:
483:
482:
477:
438:
436:
435:
430:
418:
416:
415:
410:
395:
393:
392:
387:
349:
347:
346:
341:
329:
327:
326:
321:
306:is defined. The
305:
303:
302:
297:
281:
279:
278:
273:
247:
245:
244:
239:
209:
207:
206:
201:
180:
178:
177:
172:
142:
140:
139:
134:
100:
98:
97:
92:
74:; i.e. a finite
65:
63:
62:
57:
32:computer science
1743:
1742:
1738:
1737:
1736:
1734:
1733:
1732:
1718:
1717:
1716:
1715:
1705:
1703:
1701:
1686:
1680:
1676:
1655:
1651:
1622:
1611:
1606:
1573:
1570:
1569:
1541:
1538:
1537:
1509:
1506:
1505:
1483:
1480:
1479:
1457:
1454:
1453:
1394:
1391:
1390:
1386:, see picture.
1233:
1230:
1229:
1189:
1186:
1185:
1175:
1146:
1143:
1142:
1122:
1119:
1118:
1102:
1099:
1098:
1076:
1073:
1072:
1038:
1035:
1034:
999:
995:
993:
990:
989:
973:
970:
969:
953:
950:
949:
917:
914:
913:
896:
892:
878:
875:
874:
834:
831:
830:
813:
809:
807:
804:
803:
784:
781:
780:
746:
743:
742:
717:
714:
713:
687:
684:
683:
651:
648:
647:
631:
628:
627:
611:
608:
607:
573:
570:
569:
533:
530:
529:
497:
494:
493:
447:
444:
443:
424:
421:
420:
404:
401:
400:
357:
354:
353:
335:
332:
331:
315:
312:
311:
291:
288:
287:
267:
264:
263:
215:
212:
211:
189:
186:
185:
148:
145:
144:
110:
107:
106:
86:
83:
82:
51:
48:
47:
44:binary relation
28:
21:
12:
11:
5:
1741:
1731:
1730:
1714:
1713:
1699:
1674:
1668:10.1.1.47.7099
1649:
1608:
1607:
1605:
1602:
1589:
1586:
1583:
1580:
1577:
1557:
1554:
1551:
1548:
1545:
1525:
1522:
1519:
1516:
1513:
1493:
1490:
1487:
1467:
1464:
1461:
1441:
1438:
1435:
1432:
1429:
1426:
1422:
1419:
1416:
1413:
1410:
1407:
1404:
1401:
1398:
1375:
1372:
1369:
1366:
1363:
1360:
1356:
1353:
1350:
1347:
1344:
1341:
1337:
1334:
1331:
1328:
1325:
1322:
1318:
1315:
1312:
1309:
1306:
1303:
1299:
1296:
1293:
1290:
1287:
1284:
1280:
1277:
1274:
1271:
1268:
1265:
1261:
1258:
1255:
1252:
1249:
1246:
1243:
1240:
1237:
1217:
1214:
1211:
1208:
1205:
1202:
1199:
1196:
1193:
1174:
1171:
1150:
1126:
1106:
1086:
1083:
1080:
1060:
1057:
1054:
1051:
1048:
1045:
1042:
1020:
1017:
1014:
1011:
1008:
1005:
1002:
998:
977:
957:
933:
930:
927:
924:
921:
899:
895:
891:
888:
885:
882:
862:
859:
856:
853:
850:
847:
844:
841:
838:
816:
812:
788:
768:
765:
762:
759:
756:
753:
750:
727:
724:
721:
697:
694:
691:
667:
664:
661:
658:
655:
635:
615:
595:
592:
589:
586:
583:
580:
577:
560:is called the
549:
546:
543:
540:
537:
524:is called the
513:
510:
507:
504:
501:
487:
486:
475:
472:
469:
466:
463:
460:
457:
454:
451:
428:
408:
397:
396:
385:
382:
379:
376:
373:
370:
367:
364:
361:
339:
319:
295:
271:
250:
249:
237:
234:
231:
228:
225:
222:
219:
199:
196:
193:
182:
170:
167:
164:
161:
158:
155:
152:
132:
129:
126:
123:
120:
117:
114:
90:
55:
9:
6:
4:
3:
2:
1740:
1729:
1726:
1725:
1723:
1702:
1700:981-02-2058-8
1696:
1692:
1685:
1678:
1669:
1664:
1660:
1653:
1644:
1639:
1635:
1631:
1627:
1620:
1618:
1616:
1614:
1609:
1601:
1587:
1584:
1581:
1578:
1575:
1555:
1552:
1549:
1546:
1543:
1523:
1520:
1517:
1514:
1511:
1491:
1488:
1485:
1465:
1462:
1459:
1433:
1430:
1427:
1420:
1414:
1411:
1408:
1399:
1396:
1387:
1367:
1364:
1361:
1354:
1348:
1345:
1342:
1335:
1329:
1326:
1323:
1316:
1310:
1307:
1304:
1297:
1291:
1288:
1285:
1278:
1272:
1269:
1266:
1259:
1253:
1250:
1247:
1238:
1235:
1212:
1209:
1206:
1203:
1200:
1194:
1179:
1170:
1168:
1164:
1148:
1140:
1124:
1104:
1084:
1081:
1078:
1055:
1052:
1049:
1046:
1015:
1012:
1009:
1006:
996:
975:
955:
947:
931:
928:
925:
922:
919:
897:
889:
886:
883:
880:
860:
857:
854:
851:
848:
845:
842:
839:
836:
814:
802:
786:
763:
760:
757:
754:
739:
725:
722:
719:
711:
695:
692:
689:
681:
662:
659:
656:
653:
633:
613:
590:
587:
584:
581:
567:
563:
544:
541:
527:
508:
505:
490:
473:
461:
452:
449:
442:
441:
440:
426:
406:
383:
371:
362:
359:
352:
351:
350:
337:
317:
309:
293:
285:
261:
259:
255:
235:
232:
226:
223:
220:
194:
191:
183:
168:
165:
159:
156:
153:
130:
127:
121:
118:
115:
104:
103:
102:
88:
81:
80:ordered pairs
77:
73:
69:
45:
41:
37:
33:
26:
19:
1704:. Retrieved
1690:
1677:
1658:
1652:
1633:
1629:
1388:
1183:
1167:trace theory
740:
709:
679:
646:). Elements
565:
561:
525:
491:
488:
398:
308:independency
307:
262:
251:
101:, such that
39:
29:
1636:(1): 1–82.
1161:are called
1033:and called
968:is denoted
801:free monoid
710:independent
708:holds, and
678:are called
626:induced by
528:. The pair
310:induced by
248:(reflexive)
181:(symmetric)
1604:References
254:transitive
1663:CiteSeerX
1192:Σ
1149:≡
1082:≡
1044:Σ
1004:Σ
997:≡
976:≡
956:≐
929:∈
898:∗
894:Σ
890:∈
849:≐
815:∗
811:Σ
787:≐
752:Σ
680:dependent
666:Σ
663:∈
579:Σ
539:Σ
503:Σ
492:The pair
471:∖
465:Σ
462:×
459:Σ
381:∖
375:Σ
372:×
369:Σ
286:on which
270:Σ
233:∈
198:Σ
195:∈
166:∈
128:∈
72:reflexive
68:symmetric
54:Σ
1722:Category
1706:18 April
1173:Examples
738:holds).
284:alphabet
210:, then
1568:and to
1697:
1665:
1163:traces
944:. The
606:(with
143:then
70:, and
1687:(PDF)
42:is a
1708:2021
1695:ISBN
38:, a
1638:doi
1141:of
988:or
948:of
682:if
564:or
184:If
105:If
30:In
1724::
1634:60
1632:.
1628:.
1612:^
1169:.
66:,
1710:.
1671:.
1646:.
1640::
1588:a
1585:c
1582:b
1579:b
1576:a
1556:a
1553:b
1550:c
1547:b
1544:a
1524:a
1521:b
1518:b
1515:c
1512:a
1492:b
1489:,
1486:a
1466:c
1463:,
1460:b
1440:}
1437:)
1434:b
1431:,
1428:c
1425:(
1421:,
1418:)
1415:c
1412:,
1409:b
1406:(
1403:{
1400:=
1397:I
1374:}
1371:)
1368:c
1365:,
1362:c
1359:(
1355:,
1352:)
1349:b
1346:,
1343:b
1340:(
1336:,
1333:)
1330:a
1327:,
1324:a
1321:(
1317:,
1314:)
1311:a
1308:,
1305:c
1302:(
1298:,
1295:)
1292:c
1289:,
1286:a
1283:(
1279:,
1276:)
1273:a
1270:,
1267:b
1264:(
1260:,
1257:)
1254:b
1251:,
1248:a
1245:(
1242:{
1239:=
1236:D
1216:}
1213:c
1210:,
1207:b
1204:,
1201:a
1198:{
1195:=
1125:q
1105:p
1085:q
1079:p
1059:)
1056:I
1053:,
1050:D
1047:,
1041:(
1019:)
1016:I
1013:,
1010:D
1007:,
1001:(
932:I
926:b
923:,
920:a
887:y
884:,
881:x
861:y
858:a
855:b
852:x
846:y
843:b
840:a
837:x
767:)
764:I
761:,
758:D
755:,
749:(
726:y
723:I
720:x
696:y
693:D
690:x
660:y
657:,
654:x
634:D
614:I
594:)
591:I
588:,
585:D
582:,
576:(
548:)
545:I
542:,
536:(
512:)
509:D
506:,
500:(
474:I
468:)
456:(
453:=
450:D
427:I
407:D
384:D
378:)
366:(
363:=
360:I
338:I
318:D
294:D
236:D
230:)
227:a
224:,
221:a
218:(
192:a
169:D
163:)
160:a
157:,
154:b
151:(
131:D
125:)
122:b
119:,
116:a
113:(
89:D
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
