311:
192:
340:
127:
816:
699:
368:
87:
583:
266:
228:
772:
541:
414:
612:
508:
482:
739:
719:
655:
635:
456:
436:
147:
944:
901:
271:
152:
319:
949:
99:
939:
835:
44:
849:
777:
660:
347:
53:
552:
235:
197:
16:"Multiset ordering" redirects here. For the multiset variant of the recursive path ordering, see
744:
513:
844:
375:
17:
896:
591:
90:
28:
487:
461:
922:
886:
Huet, G.; Oppen, D. C. (1980), "Equations and rewrite rules: A survey", in Book, R. (ed.),
866:
8:
870:
724:
704:
640:
620:
441:
421:
132:
914:
36:
874:
910:
854:
882:, Graz, Lecture Notes in Computer Science 71, Springer-Verlag, pp. 188–202 .)
880:
Proceedings of the
International Colloquium on Automata, Languages and Programming
918:
862:
933:
93:
858:
830:
40:
32:
547:
An equivalent definition was given by Huet and Oppen as follows:
43:. It is often used in context of termination of programs or
833:(1979), "Proving termination with multiset orderings",
888:
Formal
Language Theory: Perspectives and Open Problems
780:
747:
727:
707:
663:
643:
623:
594:
555:
516:
490:
464:
444:
424:
378:
350:
322:
274:
238:
200:
155:
135:
102:
56:
899:; Lescanne, Pierre (1982), "On multiset orderings",
810:
766:
733:
713:
693:
649:
629:
606:
577:
535:
502:
476:
450:
430:
408:
362:
334:
305:
260:
222:
186:
141:
121:
81:
895:
931:
828:
890:, New York: Academic Press, pp. 349–405
885:
848:
306:{\displaystyle X,Y\in {\mathcal {M}}(S)}
194:we define the Dershowitz–Manna ordering
187:{\displaystyle M,N\in {\mathcal {M}}(S)}
932:
129:be the set of all finite multisets on
268:whenever there exist two multisets
13:
335:{\displaystyle X\neq \varnothing }
289:
170:
105:
14:
961:
329:
122:{\displaystyle {\mathcal {M}}(S)}
313:with the following properties:
902:Information Processing Letters
805:
799:
790:
784:
688:
682:
673:
667:
397:
385:
300:
294:
181:
175:
116:
110:
76:
57:
1:
822:
915:10.1016/0020-0190(82)90107-7
811:{\displaystyle M(x)<N(x)}
694:{\displaystyle M(y)>N(y)}
363:{\displaystyle X\subseteq N}
82:{\displaystyle (S,<_{S})}
7:
578:{\displaystyle M<_{DM}N}
261:{\displaystyle M<_{DM}N}
223:{\displaystyle M<_{DM}N}
10:
966:
767:{\displaystyle y<_{S}x}
536:{\displaystyle y<_{S}x}
15:
945:Logic in computer science
836:Communications of the ACM
409:{\displaystyle M=(N-X)+Y}
25:Dershowitz–Manna ordering
607:{\displaystyle M\neq N}
897:Jouannaud, Jean-Pierre
812:
768:
735:
715:
695:
651:
631:
608:
579:
537:
504:
503:{\displaystyle x\in X}
478:
477:{\displaystyle y\in Y}
452:
432:
410:
364:
336:
307:
262:
224:
188:
143:
123:
83:
45:term rewriting systems
18:multiset path ordering
859:10.1145/359138.359142
813:
769:
736:
716:
696:
652:
632:
609:
580:
538:
505:
479:
453:
433:
411:
365:
337:
308:
263:
225:
189:
144:
124:
84:
829:Dershowitz, Nachum;
778:
745:
725:
705:
661:
641:
621:
592:
553:
514:
488:
462:
458:, that is, for all
442:
422:
376:
348:
320:
272:
236:
198:
153:
133:
100:
54:
23:In mathematics, the
701:then there is some
808:
764:
731:
711:
691:
647:
627:
604:
575:
533:
500:
474:
448:
428:
406:
360:
332:
303:
258:
220:
184:
139:
119:
79:
950:Rewriting systems
734:{\displaystyle S}
714:{\displaystyle x}
650:{\displaystyle S}
630:{\displaystyle y}
451:{\displaystyle Y}
431:{\displaystyle X}
142:{\displaystyle S}
37:Nachum Dershowitz
957:
940:Formal languages
925:
891:
877:
852:
817:
815:
814:
809:
773:
771:
770:
765:
760:
759:
740:
738:
737:
732:
720:
718:
717:
712:
700:
698:
697:
692:
656:
654:
653:
648:
636:
634:
633:
628:
613:
611:
610:
605:
585:if and only if
584:
582:
581:
576:
571:
570:
542:
540:
539:
534:
529:
528:
509:
507:
506:
501:
484:, there is some
483:
481:
480:
475:
457:
455:
454:
449:
437:
435:
434:
429:
415:
413:
412:
407:
369:
367:
366:
361:
341:
339:
338:
333:
312:
310:
309:
304:
293:
292:
267:
265:
264:
259:
254:
253:
229:
227:
226:
221:
216:
215:
193:
191:
190:
185:
174:
173:
149:. For multisets
148:
146:
145:
140:
128:
126:
125:
120:
109:
108:
88:
86:
85:
80:
75:
74:
965:
964:
960:
959:
958:
956:
955:
954:
930:
929:
850:10.1.1.1013.432
825:
779:
776:
775:
755:
751:
746:
743:
742:
726:
723:
722:
706:
703:
702:
662:
659:
658:
642:
639:
638:
622:
619:
618:
593:
590:
589:
563:
559:
554:
551:
550:
524:
520:
515:
512:
511:
489:
486:
485:
463:
460:
459:
443:
440:
439:
423:
420:
419:
377:
374:
373:
349:
346:
345:
321:
318:
317:
288:
287:
273:
270:
269:
246:
242:
237:
234:
233:
208:
204:
199:
196:
195:
169:
168:
154:
151:
150:
134:
131:
130:
104:
103:
101:
98:
97:
70:
66:
55:
52:
51:
21:
12:
11:
5:
963:
953:
952:
947:
942:
928:
927:
893:
883:
843:(8): 465–476,
824:
821:
820:
819:
807:
804:
801:
798:
795:
792:
789:
786:
783:
763:
758:
754:
750:
730:
710:
690:
687:
684:
681:
678:
675:
672:
669:
666:
646:
626:
615:
603:
600:
597:
574:
569:
566:
562:
558:
545:
544:
532:
527:
523:
519:
499:
496:
493:
473:
470:
467:
447:
427:
417:
405:
402:
399:
396:
393:
390:
387:
384:
381:
371:
359:
356:
353:
343:
331:
328:
325:
302:
299:
296:
291:
286:
283:
280:
277:
257:
252:
249:
245:
241:
219:
214:
211:
207:
203:
183:
180:
177:
172:
167:
164:
161:
158:
138:
118:
115:
112:
107:
78:
73:
69:
65:
62:
59:
9:
6:
4:
3:
2:
962:
951:
948:
946:
943:
941:
938:
937:
935:
924:
920:
916:
912:
908:
904:
903:
898:
894:
889:
884:
881:
876:
872:
868:
864:
860:
856:
851:
846:
842:
838:
837:
832:
827:
826:
802:
796:
793:
787:
781:
761:
756:
752:
748:
728:
708:
685:
679:
676:
670:
664:
644:
624:
616:
601:
598:
595:
588:
587:
586:
572:
567:
564:
560:
556:
548:
530:
525:
521:
517:
497:
494:
491:
471:
468:
465:
445:
425:
418:
403:
400:
394:
391:
388:
382:
379:
372:
357:
354:
351:
344:
326:
323:
316:
315:
314:
297:
284:
281:
278:
275:
255:
250:
247:
243:
239:
231:
217:
212:
209:
205:
201:
178:
165:
162:
159:
156:
136:
113:
95:
94:partial order
92:
71:
67:
63:
60:
50:Suppose that
48:
46:
42:
38:
34:
30:
26:
19:
909:(2): 57–63,
906:
900:
887:
879:
840:
834:
831:Manna, Zohar
549:
546:
232:
230:as follows:
91:well-founded
49:
35:named after
31:ordering on
29:well-founded
24:
22:
878:. (Also in
41:Zohar Manna
934:Categories
823:References
741:such that
510:such that
438:dominates
845:CiteSeerX
599:≠
495:∈
469:∈
392:−
355:⊆
330:∅
327:≠
285:∈
166:∈
33:multisets
875:17906810
617:for all
96:and let
923:0675869
867:0540043
921:
873:
865:
847:
871:S2CID
657:, if
614:, and
416:, and
89:is a
27:is a
794:<
774:and
753:<
677:>
561:<
522:<
244:<
206:<
68:<
39:and
911:doi
855:doi
721:in
637:in
936::
919:MR
917:,
907:15
905:,
869:,
863:MR
861:,
853:,
841:22
839:,
47:.
926:.
913::
892:.
857::
818:.
806:)
803:x
800:(
797:N
791:)
788:x
785:(
782:M
762:x
757:S
749:y
729:S
709:x
689:)
686:y
683:(
680:N
674:)
671:y
668:(
665:M
645:S
625:y
602:N
596:M
573:N
568:M
565:D
557:M
543:.
531:x
526:S
518:y
498:X
492:x
472:Y
466:y
446:Y
426:X
404:Y
401:+
398:)
395:X
389:N
386:(
383:=
380:M
370:,
358:N
352:X
342:,
324:X
301:)
298:S
295:(
290:M
282:Y
279:,
276:X
256:N
251:M
248:D
240:M
218:N
213:M
210:D
202:M
182:)
179:S
176:(
171:M
163:N
160:,
157:M
137:S
117:)
114:S
111:(
106:M
77:)
72:S
64:,
61:S
58:(
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.