1774:
119:
as well. (The preference for the word "reduction" here instead of "rewriting" constitutes a departure from the uniform use of "rewriting" in the names of systems that are particularizations of ARS. Because the word "reduction" does not appear in the names of more specialized systems, in older texts
1899:
Because of these equivalences, a fair bit of variation in definitions is encountered in the literature. For instance, in Terese the Church–Rosser property and confluence are defined to be synonymous and identical to the definition of confluence presented here; Church–Rosser as defined here remains
94:
Historically, there have been several formalizations of rewriting in an abstract setting, each with its idiosyncrasies. This is due in part to the fact that some notions are equivalent, see below in this article. The formalization that is most commonly encountered in monographs and textbooks, and
1420:
Various properties, simpler than Church–Rosser, are equivalent to it. The existence of these equivalent properties allows one to prove that a system is Church–Rosser with less work. Furthermore, the notions of confluence can be defined as properties of a particular object, something that's not
230:, and if the relation is considered as an indexed union, then an ARS is the same as a labeled state transition system with the indices being the labels. The focus of the study, and the terminology are different however. In a
2020:
1221:
1532:
1169:
2143:
2095:
213:
2484:
This is a comprehensive monograph. It uses, however, a fair deal of notations and definitions not commonly encountered elsewhere. For instance the Church–Rosser property is defined to be identical with
1412:
has this property; hence the name of the property. In an ARS with the Church–Rosser property the word problem may be reduced to the search for a common successor. In a Church–Rosser system, an object has
1641:
2153:. In a convergent ARS, every object has a unique normal form. But it is sufficient for the system to be confluent and normalizing for a unique normal to exist for every element, as seen in example 1.
79:; this definition can be further refined if we index (label) subsets of the binary relation. Despite its simplicity, an ARS is sufficient to describe important properties of rewriting systems like
1949:
1827:
1360:
869:
770:
2101:.) In a terminating ARS, every object has at least one normal form, thus it is normalizing. The converse is not true. In example 1 for instance, there is an infinite rewriting chain, namely
1893:
1009:
510:
407:
348:
603:
570:
1954:
Local confluence on the other hand is not equivalent with the other notions of confluence given in this section, but it is strictly weaker than confluence. The typical counterexample is
1083:
1763:
1733:
1671:
1562:
1390:
1295:
836:
157:
In some contexts it may be beneficial to distinguish between some subsets of the rules, i.e. some subsets of the reduction relation →, e.g. the entire reduction relation may consist of
473:
1451:
669:
954:
647:
735:
625:
2184:
1044:
893:
794:
713:
693:
534:
431:
372:
77:
1265:
2166:
The original 1942 proof of this result by Newman was rather complicated. It wasn't until 1980 that Huet published a much simpler proof exploiting the fact that when
1241:
115:) is the most general (unidimensional) notion about specifying a set of objects and rules that can be applied to transform them. More recently, authors use the term
1951:. This definition, found in Book and Otto, is equivalent to the common one given here in a confluent system, but it is more inclusive in a non-confluent ARS.
1900:
unnamed, but is given as an equivalent property; this departure from other texts is deliberate. Because of the above corollary, one may define a normal form
154:. This (entrenched) terminology using "reduction" is a little misleading, because the relation is not necessarily reducing some measure of the objects.
1957:
1174:
2465:
1784:
For an ARS the following three conditions are equivalent: (i) it has the Church–Rosser property, (ii) it is confluent, (iii) it is semi-confluent.
234:
one is interested in interpreting the labels as actions, whereas in an ARS the focus is on how objects may be transformed (rewritten) into others.
1479:
1116:
2104:
2041:
168:
2457:
1400:. Equivalently, the Church–Rosser property means that the reflexive transitive symmetric closure is contained in the joinability relation.
2526:), October 1980, Volume 27, Issue 4, pp. 797–821. Huet's paper established many of the modern concepts, results and notations.
1601:
773:
2501:
165:
rules. Consequently, some authors define the reduction relation → as the indexed union of some relations; for instance if
1915:
1793:
1326:
2607:
841:
742:
2477:
2447:
2424:
2389:
1859:
975:
905:
482:
379:
320:
80:
575:
542:
1314:
1053:
88:
1738:
1706:
1646:
1537:
1365:
1270:
803:
1773:
440:
410:
84:
24:
2612:
2199:
1424:
1417:
normal form; that is, the normal form of an object is unique if it exists, but it may well not exist.
654:
2602:
933:
630:
1244:
718:
608:
2169:
1026:
878:
779:
698:
678:
519:
416:
357:
62:
2406:
1564:. Roughly speaking, confluence says that no matter how two paths diverge from a common ancestor (
1250:
231:
227:
44:
2187:
2530:
2403:
1097:
A related, but weaker notion than the existence of normal forms is that of two objects being
1226:
872:
8:
2098:
2581:
797:
434:
351:
20:
2573:
2497:
2473:
2443:
2420:
2399:
2385:
2160:
1405:
672:
476:
128:
52:
2520:
Confluent
Reductions: Abstract Properties and Applications to Term Rewriting Systems
2563:
2509:
2145:, even though the system is normalizing. A confluent and terminating ARS is called
1777:
Example of a locally confluent rewrite system not having the Church–Rosser property
2461:
2412:
2379:
1409:
1171:. From this definition, it's apparent one may define the joinability relation as
135:
56:
2431:
of this chapter is freely available from the authors, but it misses the figures.
1572:
common successor. This notion may be refined as property of a particular object
2435:
2417:
Handbook of
Theoretical Computer Science, Volume B: Formal Models and Semantics
2015:{\displaystyle \{b\rightarrow c,c\rightarrow b,b\rightarrow a,c\rightarrow d\}}
1216:{\displaystyle {\stackrel {*}{\rightarrow }}\circ {\stackrel {*}{\leftarrow }}}
2515:
2494:
Handbook of
Practical Logic and Automated Reasoning Cambridge University Press
96:
2596:
2577:
2489:
2375:
1401:
162:
158:
1527:{\displaystyle x{\stackrel {*}{\leftarrow }}w{\stackrel {*}{\rightarrow }}y}
1164:{\displaystyle x{\stackrel {*}{\rightarrow }}z{\stackrel {*}{\leftarrow }}y}
2371:
2138:{\displaystyle a\rightarrow b\rightarrow a\rightarrow b\rightarrow \cdots }
2163:): A terminating ARS is confluent if and only if it is locally confluent.
2090:{\displaystyle x_{0}\rightarrow x_{1}\rightarrow x_{2}\rightarrow \cdots }
1267:, but in this notation the down arrow is a binary relation, i.e. we write
306:
to transform it any further. Such a property is clearly an important one.
2508:
Abstract rewriting from the practical perspective of solving problems in
2585:
1308:
208:{\displaystyle {\rightarrow _{1}\cup \rightarrow _{2}}={\rightarrow }}
226:
As a mathematical object, an ARS is exactly the same as an unlabeled
48:
2568:
2551:
1576:, and the system called confluent if all its elements are confluent.
2428:
513:
1247:. Joinability is usually denoted, somewhat confusingly, also with
1085:. If every object has at least one normal form, the ARS is called
1673:. This differs from confluence by the single step reduction from
16:
Formal system for transcribing expressions into equivalent terms
2535:
International
Journal of Mathematics and Mathematical Sciences
2022:, which is locally confluent but not confluent (cf. picture).
2438:; Otto, Friedrich (1993). "1, "Abstract reduction systems"".
134:, whose elements are usually called objects, together with a
2523:
1636:{\displaystyle x\leftarrow w{\stackrel {*}{\rightarrow }}y}
1309:
The Church–Rosser property and notions of confluence
47:
that captures the quintessential notion and properties of
2202:— particularly the section on abstract rewriting systems
2097:. (This is just saying that the rewriting relation is a
2244:
2242:
2172:
2107:
2044:
1960:
1918:
1862:
1796:
1741:
1709:
1649:
1604:
1540:
1482:
1427:
1368:
1329:
1273:
1253:
1229:
1177:
1119:
1056:
1029:
978:
936:
881:
844:
806:
782:
745:
721:
701:
681:
657:
633:
611:
578:
545:
522:
485:
443:
419:
382:
360:
323:
171:
65:
2239:
1944:{\displaystyle x{\stackrel {*}{\leftrightarrow }}y}
1822:{\displaystyle x{\stackrel {*}{\leftrightarrow }}y}
1355:{\displaystyle x{\stackrel {*}{\leftrightarrow }}y}
2178:
2137:
2089:
2014:
1943:
1887:
1821:
1757:
1727:
1665:
1635:
1556:
1526:
1445:
1384:
1354:
1289:
1259:
1235:
1215:
1163:
1077:
1038:
1003:
948:
887:
863:
830:
788:
764:
729:
707:
687:
663:
641:
619:
597:
564:
528:
504:
467:
425:
401:
366:
342:
290:. Observe that these rules can be applied to both
207:
71:
51:systems. In its simplest form, an ARS is simply a
2556:Transactions of the American Mathematical Society
2537:, Volume 2010 (2010), Article ID 458563, 6 pages.
864:{\displaystyle {\stackrel {*}{\leftrightarrow }}}
765:{\displaystyle {\stackrel {*}{\leftrightarrow }}}
2594:
258:} and the binary relation is given by the rules
2531:"The 3x+1 Problem as a String Rewriting System"
1888:{\displaystyle x{\stackrel {*}{\rightarrow }}y}
1023:normal form, then this is usually denoted with
1004:{\displaystyle x{\stackrel {*}{\rightarrow }}y}
314:First define some basic notions and notations.
2025:
1109:are said to be joinable if there exists some
505:{\displaystyle {\stackrel {*}{\rightarrow }}}
402:{\displaystyle {\stackrel {*}{\rightarrow }}}
343:{\displaystyle {\stackrel {+}{\rightarrow }}}
142:, traditionally denoted by →, and called the
2549:
2370:
2319:
2307:
2295:
2284:
2272:
2009:
1961:
598:{\displaystyle {\stackrel {*}{\leftarrow }}}
565:{\displaystyle {\stackrel {+}{\leftarrow }}}
95:which is generally followed here, is due to
2030:An abstract rewriting system is said to be
1078:{\displaystyle c=a\downarrow =b\downarrow }
1758:{\displaystyle x{\mathbin {\downarrow }}y}
1728:{\displaystyle x\leftarrow w\rightarrow y}
1666:{\displaystyle x{\mathbin {\downarrow }}y}
1557:{\displaystyle x{\mathbin {\downarrow }}y}
1385:{\displaystyle x{\mathbin {\downarrow }}y}
1290:{\displaystyle x{\mathbin {\downarrow }}y}
831:{\displaystyle (\leftrightarrow )\cup (=)}
302:. Furthermore, nothing can be applied to
2567:
2229:
2227:
2488:
2434:
2355:
2248:
2218:
1772:
2543:Principles of Automated Theorem Proving
2396:A textbook suitable for undergraduates.
2595:
2550:Church, Alonzo; Rosser, J. B. (1936).
2456:
2331:
2260:
2233:
2224:
774:reflexive transitive symmetric closure
468:{\displaystyle (\rightarrow )\cup (=)}
2540:
2343:
1765:. This property is sometimes called
1421:possible for Church–Rosser. An ARS
13:
14:
2624:
2419:, Elsevier and MIT Press, 1990,
1446:{\displaystyle (A,\rightarrow )}
906:Normal form (abstract rewriting)
664:{\displaystyle \leftrightarrow }
309:
2552:"Some Properties of Conversion"
2349:
2337:
2325:
1315:Confluence (abstract rewriting)
899:
55:(of "objects") together with a
2472:. Cambridge University Press.
2427:, pp. 243–320. The
2384:. Cambridge University Press.
2313:
2301:
2289:
2278:
2266:
2254:
2212:
2173:
2129:
2123:
2117:
2111:
2081:
2068:
2055:
2038:if there is no infinite chain
2003:
1991:
1979:
1967:
1926:
1870:
1804:
1747:
1719:
1713:
1655:
1618:
1608:
1546:
1509:
1490:
1440:
1437:
1428:
1374:
1337:
1319:An ARS is said to possess the
1279:
1254:
1201:
1182:
1146:
1127:
1092:
1072:
1066:
1033:
986:
949:{\displaystyle x\rightarrow y}
940:
882:
849:
825:
819:
813:
810:
807:
783:
750:
723:
702:
682:
658:
642:{\displaystyle {\rightarrow }}
635:
613:
583:
550:
523:
490:
462:
456:
450:
447:
444:
420:
387:
361:
328:
242:Suppose the set of objects is
201:
187:
174:
66:
1:
2364:
730:{\displaystyle {\leftarrow }}
620:{\displaystyle {\leftarrow }}
102:
59:, traditionally denoted with
2186:is terminating we can apply
2179:{\displaystyle \rightarrow }
1568:), the paths are joining at
1039:{\displaystyle x\downarrow }
888:{\displaystyle \rightarrow }
789:{\displaystyle \rightarrow }
708:{\displaystyle \rightarrow }
688:{\displaystyle \rightarrow }
529:{\displaystyle \rightarrow }
426:{\displaystyle \rightarrow }
411:reflexive transitive closure
367:{\displaystyle \rightarrow }
237:
215:, the notation used is (A, →
72:{\displaystyle \rightarrow }
25:theoretical computer science
7:
2381:Term Rewriting and All That
2193:
2026:Termination and convergence
1260:{\displaystyle \downarrow }
968:is called a normal form of
627:, the converse relation of
33:(abstract) reduction system
10:
2629:
2200:Word problem (mathematics)
1312:
922:if there exist some other
903:
2608:Logic in computer science
2346:, p. 153, sect.7.2.1
956:; otherwise it is called
117:abstract rewriting system
109:abstract reduction system
87:, and various notions of
29:abstract rewriting system
2541:Duffy, David A. (1991).
2492:(2009). "4 "Equality"".
2440:String-rewriting Systems
2320:Baader & Nipkow 1998
2308:Baader & Nipkow 1998
2296:Baader & Nipkow 1998
2285:Church & Rosser 1936
2273:Baader & Nipkow 1998
2206:
1790:. In a confluent ARS if
1245:composition of relations
695:, that is, the union of
1912:with the property that
1856:is a normal form, then
1841:are normal forms, then
1687:if and only if for all
1582:if and only if for all
1460:if and only if for all
1113:with the property that
232:state transition system
228:state transition system
124:is a synonym for ARS.)
37:abstract rewrite system
2522:, Journal of the ACM (
2470:Term rewriting systems
2468:; Terese (2003). "1".
2188:well-founded induction
2180:
2139:
2091:
2016:
1945:
1889:
1823:
1778:
1759:
1729:
1667:
1637:
1558:
1528:
1447:
1386:
1356:
1321:Church–Rosser property
1291:
1261:
1237:
1236:{\displaystyle \circ }
1217:
1165:
1079:
1050:is a normal form, and
1046:. In example 1 above,
1040:
1005:
950:
889:
865:
832:
790:
766:
731:
709:
689:
665:
643:
621:
599:
566:
530:
506:
469:
427:
403:
368:
344:
209:
73:
2404:Jean-Pierre Jouannaud
2181:
2140:
2092:
2017:
1946:
1890:
1824:
1776:
1760:
1730:
1668:
1638:
1559:
1529:
1448:
1387:
1357:
1292:
1262:
1238:
1218:
1166:
1080:
1041:
1006:
951:
890:
866:
833:
791:
767:
732:
710:
690:
666:
644:
622:
600:
567:
531:
507:
470:
428:
404:
369:
345:
210:
74:
2249:Book & Otto 1993
2219:Book & Otto 1993
2170:
2105:
2042:
1958:
1916:
1860:
1794:
1739:
1707:
1647:
1602:
1538:
1480:
1425:
1408:proved in 1936 that
1366:
1327:
1271:
1251:
1227:
1175:
1117:
1054:
1027:
976:
934:
879:
873:equivalence relation
842:
804:
780:
743:
719:
699:
679:
655:
631:
609:
576:
543:
520:
483:
441:
417:
380:
358:
321:
169:
63:
2099:Noetherian relation
1015:is irreducible. If
2176:
2135:
2087:
2012:
1941:
1908:as an irreducible
1885:
1819:
1779:
1755:
1725:
1663:
1633:
1554:
1524:
1443:
1382:
1352:
1287:
1257:
1233:
1213:
1161:
1075:
1036:
1001:
946:
885:
861:
828:
798:transitive closure
786:
762:
727:
705:
685:
661:
639:
617:
595:
562:
526:
502:
465:
435:transitive closure
423:
399:
364:
352:transitive closure
340:
205:
144:reduction relation
69:
21:mathematical logic
2613:Rewriting systems
2503:978-0-521-89957-4
2400:Nachum Dershowitz
1935:
1879:
1813:
1685:locally confluent
1627:
1518:
1499:
1406:J. Barkley Rosser
1346:
1210:
1191:
1155:
1136:
995:
858:
759:
673:symmetric closure
592:
559:
499:
477:identity relation
475:, where = is the
396:
337:
2620:
2603:Formal languages
2589:
2571:
2546:
2510:equational logic
2507:
2483:
2453:
2395:
2359:
2353:
2347:
2341:
2335:
2329:
2323:
2317:
2311:
2305:
2299:
2293:
2287:
2282:
2276:
2270:
2264:
2258:
2252:
2246:
2237:
2231:
2222:
2216:
2185:
2183:
2182:
2177:
2144:
2142:
2141:
2136:
2096:
2094:
2093:
2088:
2080:
2079:
2067:
2066:
2054:
2053:
2021:
2019:
2018:
2013:
1950:
1948:
1947:
1942:
1937:
1936:
1934:
1929:
1924:
1894:
1892:
1891:
1886:
1881:
1880:
1878:
1873:
1868:
1828:
1826:
1825:
1820:
1815:
1814:
1812:
1807:
1802:
1764:
1762:
1761:
1756:
1751:
1750:
1734:
1732:
1731:
1726:
1672:
1670:
1669:
1664:
1659:
1658:
1642:
1640:
1639:
1634:
1629:
1628:
1626:
1621:
1616:
1563:
1561:
1560:
1555:
1550:
1549:
1533:
1531:
1530:
1525:
1520:
1519:
1517:
1512:
1507:
1501:
1500:
1498:
1493:
1488:
1452:
1450:
1449:
1444:
1392:for all objects
1391:
1389:
1388:
1383:
1378:
1377:
1361:
1359:
1358:
1353:
1348:
1347:
1345:
1340:
1335:
1296:
1294:
1293:
1288:
1283:
1282:
1266:
1264:
1263:
1258:
1242:
1240:
1239:
1234:
1222:
1220:
1219:
1214:
1212:
1211:
1209:
1204:
1199:
1193:
1192:
1190:
1185:
1180:
1170:
1168:
1167:
1162:
1157:
1156:
1154:
1149:
1144:
1138:
1137:
1135:
1130:
1125:
1084:
1082:
1081:
1076:
1045:
1043:
1042:
1037:
1010:
1008:
1007:
1002:
997:
996:
994:
989:
984:
955:
953:
952:
947:
894:
892:
891:
886:
871:is the smallest
870:
868:
867:
862:
860:
859:
857:
852:
847:
838:. Equivalently,
837:
835:
834:
829:
795:
793:
792:
787:
771:
769:
768:
763:
761:
760:
758:
753:
748:
736:
734:
733:
728:
726:
714:
712:
711:
706:
694:
692:
691:
686:
670:
668:
667:
662:
648:
646:
645:
640:
638:
626:
624:
623:
618:
616:
605:are closures of
604:
602:
601:
596:
594:
593:
591:
586:
581:
571:
569:
568:
563:
561:
560:
558:
553:
548:
535:
533:
532:
527:
512:is the smallest
511:
509:
508:
503:
501:
500:
498:
493:
488:
479:. Equivalently,
474:
472:
471:
466:
432:
430:
429:
424:
408:
406:
405:
400:
398:
397:
395:
390:
385:
373:
371:
370:
365:
349:
347:
346:
341:
339:
338:
336:
331:
326:
214:
212:
211:
206:
204:
196:
195:
194:
182:
181:
148:rewrite relation
122:reduction system
78:
76:
75:
70:
2628:
2627:
2623:
2622:
2621:
2619:
2618:
2617:
2593:
2592:
2569:10.2307/1989762
2504:
2480:
2462:Jan Willem Klop
2450:
2436:Book, Ronald V.
2413:Jan van Leeuwen
2411:, Chapter 6 in
2408:Rewrite Systems
2392:
2367:
2362:
2354:
2350:
2342:
2338:
2330:
2326:
2318:
2314:
2306:
2302:
2294:
2290:
2283:
2279:
2271:
2267:
2259:
2255:
2247:
2240:
2232:
2225:
2217:
2213:
2209:
2196:
2171:
2168:
2167:
2106:
2103:
2102:
2075:
2071:
2062:
2058:
2049:
2045:
2043:
2040:
2039:
2028:
1959:
1956:
1955:
1930:
1925:
1923:
1922:
1917:
1914:
1913:
1874:
1869:
1867:
1866:
1861:
1858:
1857:
1808:
1803:
1801:
1800:
1795:
1792:
1791:
1767:weak confluence
1746:
1745:
1740:
1737:
1736:
1708:
1705:
1704:
1654:
1653:
1648:
1645:
1644:
1622:
1617:
1615:
1614:
1603:
1600:
1599:
1545:
1544:
1539:
1536:
1535:
1513:
1508:
1506:
1505:
1494:
1489:
1487:
1486:
1481:
1478:
1477:
1453:is said to be,
1426:
1423:
1422:
1410:lambda calculus
1373:
1372:
1367:
1364:
1363:
1341:
1336:
1334:
1333:
1328:
1325:
1324:
1323:if and only if
1317:
1311:
1278:
1277:
1272:
1269:
1268:
1252:
1249:
1248:
1228:
1225:
1224:
1205:
1200:
1198:
1197:
1186:
1181:
1179:
1178:
1176:
1173:
1172:
1150:
1145:
1143:
1142:
1131:
1126:
1124:
1123:
1118:
1115:
1114:
1095:
1055:
1052:
1051:
1028:
1025:
1024:
990:
985:
983:
982:
977:
974:
973:
935:
932:
931:
908:
902:
880:
877:
876:
853:
848:
846:
845:
843:
840:
839:
805:
802:
801:
781:
778:
777:
754:
749:
747:
746:
744:
741:
740:
722:
720:
717:
716:
700:
697:
696:
680:
677:
676:
656:
653:
652:
634:
632:
629:
628:
612:
610:
607:
606:
587:
582:
580:
579:
577:
574:
573:
554:
549:
547:
546:
544:
541:
540:
521:
518:
517:
494:
489:
487:
486:
484:
481:
480:
442:
439:
438:
418:
415:
414:
391:
386:
384:
383:
381:
378:
377:
359:
356:
355:
332:
327:
325:
324:
322:
319:
318:
312:
240:
222:
218:
200:
190:
186:
177:
173:
172:
170:
167:
166:
136:binary relation
105:
64:
61:
60:
57:binary relation
17:
12:
11:
5:
2626:
2616:
2615:
2610:
2605:
2591:
2590:
2562:(3): 472–482.
2547:
2538:
2527:
2513:
2502:
2490:Harrison, John
2486:
2478:
2466:Roel de Vrijer
2454:
2448:
2432:
2397:
2390:
2376:Nipkow, Tobias
2366:
2363:
2361:
2360:
2348:
2336:
2324:
2312:
2300:
2288:
2277:
2275:, pp. 8–9
2265:
2263:, pp. 7–8
2253:
2238:
2223:
2210:
2208:
2205:
2204:
2203:
2195:
2192:
2175:
2161:Newman's Lemma
2134:
2131:
2128:
2125:
2122:
2119:
2116:
2113:
2110:
2086:
2083:
2078:
2074:
2070:
2065:
2061:
2057:
2052:
2048:
2027:
2024:
2011:
2008:
2005:
2002:
1999:
1996:
1993:
1990:
1987:
1984:
1981:
1978:
1975:
1972:
1969:
1966:
1963:
1940:
1933:
1928:
1921:
1897:
1896:
1884:
1877:
1872:
1865:
1850:
1818:
1811:
1806:
1799:
1771:
1770:
1754:
1749:
1744:
1724:
1721:
1718:
1715:
1712:
1682:
1662:
1657:
1652:
1632:
1625:
1620:
1613:
1610:
1607:
1580:semi-confluent
1577:
1553:
1548:
1543:
1523:
1516:
1511:
1504:
1497:
1492:
1485:
1442:
1439:
1436:
1433:
1430:
1381:
1376:
1371:
1351:
1344:
1339:
1332:
1313:Main article:
1310:
1307:
1305:are joinable.
1286:
1281:
1276:
1256:
1232:
1208:
1203:
1196:
1189:
1184:
1160:
1153:
1148:
1141:
1134:
1129:
1122:
1094:
1091:
1074:
1071:
1068:
1065:
1062:
1059:
1035:
1032:
1000:
993:
988:
981:
945:
942:
939:
904:Main article:
901:
898:
897:
896:
884:
856:
851:
827:
824:
821:
818:
815:
812:
809:
785:
757:
752:
738:
725:
704:
684:
660:
650:
637:
615:
590:
585:
557:
552:
537:
525:
497:
492:
464:
461:
458:
455:
452:
449:
446:
422:
394:
389:
375:
363:
335:
330:
311:
308:
239:
236:
220:
216:
203:
199:
193:
189:
185:
180:
176:
104:
101:
68:
39:; abbreviated
15:
9:
6:
4:
3:
2:
2625:
2614:
2611:
2609:
2606:
2604:
2601:
2600:
2598:
2587:
2583:
2579:
2575:
2570:
2565:
2561:
2557:
2553:
2548:
2544:
2539:
2536:
2532:
2528:
2525:
2521:
2517:
2514:
2511:
2505:
2499:
2495:
2491:
2487:
2481:
2479:0-521-39115-6
2475:
2471:
2467:
2463:
2459:
2455:
2451:
2449:0-387-97965-4
2445:
2441:
2437:
2433:
2430:
2426:
2425:0-444-88074-7
2422:
2418:
2414:
2410:
2409:
2405:
2401:
2398:
2393:
2391:9780521779203
2387:
2383:
2382:
2377:
2373:
2372:Baader, Franz
2369:
2368:
2358:, p. 260
2357:
2356:Harrison 2009
2352:
2345:
2340:
2333:
2328:
2321:
2316:
2309:
2304:
2297:
2292:
2286:
2281:
2274:
2269:
2262:
2257:
2250:
2245:
2243:
2235:
2230:
2228:
2220:
2215:
2211:
2201:
2198:
2197:
2191:
2189:
2164:
2162:
2158:
2154:
2152:
2148:
2132:
2126:
2120:
2114:
2108:
2100:
2084:
2076:
2072:
2063:
2059:
2050:
2046:
2037:
2033:
2023:
2006:
2000:
1997:
1994:
1988:
1985:
1982:
1976:
1973:
1970:
1964:
1952:
1938:
1931:
1919:
1911:
1907:
1903:
1882:
1875:
1863:
1855:
1851:
1848:
1844:
1840:
1836:
1832:
1831:
1830:
1816:
1809:
1797:
1789:
1785:
1783:
1775:
1768:
1752:
1742:
1722:
1716:
1710:
1702:
1698:
1694:
1690:
1686:
1683:
1680:
1676:
1660:
1650:
1630:
1623:
1611:
1605:
1597:
1593:
1589:
1585:
1581:
1578:
1575:
1571:
1567:
1551:
1541:
1521:
1514:
1502:
1495:
1483:
1475:
1471:
1467:
1463:
1459:
1456:
1455:
1454:
1434:
1431:
1418:
1416:
1411:
1407:
1403:
1402:Alonzo Church
1399:
1395:
1379:
1369:
1349:
1342:
1330:
1322:
1316:
1306:
1304:
1300:
1284:
1274:
1246:
1230:
1206:
1194:
1187:
1158:
1151:
1139:
1132:
1120:
1112:
1108:
1104:
1100:
1090:
1088:
1069:
1063:
1060:
1057:
1049:
1030:
1022:
1018:
1014:
998:
991:
979:
971:
967:
963:
959:
943:
937:
929:
925:
921:
917:
913:
907:
874:
854:
822:
816:
799:
775:
755:
739:
674:
651:
588:
555:
538:
515:
495:
478:
459:
453:
436:
412:
392:
376:
353:
333:
317:
316:
315:
310:Basic notions
307:
305:
301:
297:
293:
289:
285:
281:
277:
273:
269:
265:
261:
257:
253:
249:
245:
235:
233:
229:
224:
197:
191:
183:
178:
164:
163:commutativity
160:
159:associativity
155:
153:
149:
145:
141:
137:
133:
130:
125:
123:
118:
114:
110:
100:
98:
92:
90:
86:
82:
58:
54:
50:
46:
42:
38:
34:
30:
26:
22:
2559:
2555:
2542:
2534:
2529:Sinyor, J.;
2519:
2493:
2469:
2442:. Springer.
2439:
2416:
2407:
2380:
2351:
2339:
2334:, p. 11
2327:
2322:, p. 12
2315:
2310:, p. 11
2303:
2291:
2280:
2268:
2256:
2251:, p. 10
2214:
2165:
2156:
2155:
2150:
2146:
2035:
2031:
2029:
1953:
1909:
1905:
1901:
1898:
1853:
1846:
1842:
1838:
1834:
1787:
1786:
1781:
1780:
1766:
1700:
1696:
1692:
1688:
1684:
1678:
1674:
1595:
1591:
1587:
1583:
1579:
1573:
1569:
1565:
1473:
1469:
1465:
1461:
1457:
1419:
1414:
1397:
1393:
1320:
1318:
1302:
1298:
1110:
1106:
1102:
1098:
1096:
1086:
1047:
1020:
1016:
1012:
969:
965:
964:. An object
961:
957:
927:
923:
919:
915:
911:
909:
900:Normal forms
313:
303:
299:
295:
291:
287:
283:
279:
275:
271:
267:
263:
259:
255:
251:
247:
243:
241:
225:
156:
151:
147:
143:
139:
131:
127:An ARS is a
126:
121:
116:
112:
108:
106:
93:
81:normal forms
40:
36:
32:
28:
18:
2516:GĂ©rard Huet
2485:confluence.
2332:Terese 2003
2298:, p. 9
2261:Terese 2003
2236:, p. 7
2234:Terese 2003
2221:, p. 9
2032:terminating
1415:at most one
1093:Joinability
1087:normalizing
962:normal form
958:irreducible
875:containing
796:, i.e. the
539:Similarly,
516:containing
433:, i.e. the
97:GĂ©rard Huet
85:termination
2597:Categories
2458:Marc Bezem
2365:References
2344:Duffy 1991
2151:convergent
2036:noetherian
1067:↓ =
918:is called
910:An object
103:Definition
89:confluence
2578:0002-9947
2174:→
2147:canonical
2133:⋯
2130:→
2124:→
2118:→
2112:→
2085:⋯
2082:→
2069:→
2056:→
2004:→
1992:→
1980:→
1968:→
1932:∗
1927:↔
1876:∗
1871:→
1810:∗
1805:↔
1788:Corollary
1748:↓
1720:→
1714:←
1656:↓
1624:∗
1619:→
1609:←
1547:↓
1515:∗
1510:→
1496:∗
1491:←
1458:confluent
1438:→
1375:↓
1343:∗
1338:↔
1280:↓
1255:↓
1231:∘
1207:∗
1202:←
1195:∘
1188:∗
1183:→
1152:∗
1147:←
1133:∗
1128:→
1073:↓
1034:↓
992:∗
987:→
941:→
920:reducible
883:→
855:∗
850:↔
817:∪
811:↔
784:→
756:∗
751:↔
724:←
703:→
683:→
659:↔
636:→
614:←
589:∗
584:←
551:←
524:→
496:∗
491:→
454:∪
448:→
421:→
393:∗
388:→
362:→
329:→
238:Example 1
202:→
188:→
184:∪
175:→
152:reduction
67:→
49:rewriting
45:formalism
2545:. Wiley.
2429:preprint
2378:(1998).
2194:See also
1833:If both
1782:Theorem.
1735:implies
1643:implies
1534:implies
1362:implies
1223:, where
1099:joinable
514:preorder
150:or just
99:(1980).
2586:1989762
2415:(Ed.),
2157:Theorem
1243:is the
772:is the
671:is the
409:is the
350:is the
298:to get
43:) is a
2584:
2576:
2500:
2476:
2446:
2423:
2388:
1695:, and
1590:, and
1468:, and
1021:unique
1019:has a
572:, and
282:, and
31:(also
2582:JSTOR
2207:Notes
2149:, or
1829:then
960:or a
715:with
27:, an
2574:ISSN
2524:JACM
2498:ISBN
2474:ISBN
2444:ISBN
2421:ISBN
2402:and
2386:ISBN
1837:and
1570:some
1404:and
1301:and
1105:and
1011:and
930:and
294:and
161:and
23:and
2564:doi
2034:or
1904:of
1852:If
1703:,
1699:in
1677:to
1598:,
1594:in
1476:,
1472:in
1297:if
972:if
926:in
914:in
800:of
776:of
675:of
437:of
413:of
354:of
246:= {
223:).
219:, →
138:on
129:set
113:ARS
107:An
53:set
41:ARS
35:or
19:In
2599::
2580:.
2572:.
2560:39
2558:.
2554:.
2533:,
2518:,
2496:.
2464:;
2460:;
2374:;
2241:^
2226:^
2190:.
1845:=
1691:,
1586:,
1464:,
1396:,
1101::
1089:.
286:→
278:→
274:,
270:→
266:,
262:→
254:,
250:,
146:,
91:.
83:,
2588:.
2566::
2512:.
2506:.
2482:.
2452:.
2394:.
2159:(
2127:b
2121:a
2115:b
2109:a
2077:2
2073:x
2064:1
2060:x
2051:0
2047:x
2010:}
2007:d
2001:c
1998:,
1995:a
1989:b
1986:,
1983:b
1977:c
1974:,
1971:c
1965:b
1962:{
1939:y
1920:x
1910:y
1906:x
1902:y
1895:.
1883:y
1864:x
1854:y
1849:.
1847:y
1843:x
1839:y
1835:x
1817:y
1798:x
1769:.
1753:y
1743:x
1723:y
1717:w
1711:x
1701:A
1697:y
1693:x
1689:w
1681:.
1679:x
1675:w
1661:y
1651:x
1631:y
1612:w
1606:x
1596:A
1592:y
1588:x
1584:w
1574:w
1566:w
1552:y
1542:x
1522:y
1503:w
1484:x
1474:A
1470:y
1466:x
1462:w
1441:)
1435:,
1432:A
1429:(
1398:y
1394:x
1380:y
1370:x
1350:y
1331:x
1303:y
1299:x
1285:y
1275:x
1159:y
1140:z
1121:x
1111:z
1107:y
1103:x
1070:b
1064:a
1061:=
1058:c
1048:c
1031:x
1017:x
1013:y
999:y
980:x
970:x
966:y
944:y
938:x
928:A
924:y
916:A
912:x
895:.
826:)
823:=
820:(
814:)
808:(
737:.
649:.
556:+
536:.
463:)
460:=
457:(
451:)
445:(
374:.
334:+
304:c
300:c
296:b
292:a
288:c
284:b
280:c
276:a
272:a
268:b
264:b
260:a
256:c
252:b
248:a
244:T
221:2
217:1
198:=
192:2
179:1
140:A
132:A
111:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.