YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) Overlay + Local Confluence [EQUIVALENT, 24 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 137 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) QDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) QDP (10) ATransformationProof [EQUIVALENT, 0 ms] (11) QDP (12) QReductionProof [EQUIVALENT, 0 ms] (13) QDP (14) QDPSizeChangeProof [EQUIVALENT, 0 ms] (15) YES (16) QDP (17) UsableRulesProof [EQUIVALENT, 0 ms] (18) QDP (19) ATransformationProof [EQUIVALENT, 0 ms] (20) QDP (21) QReductionProof [EQUIVALENT, 0 ms] (22) QDP (23) QDPSizeChangeProof [EQUIVALENT, 0 ms] (24) YES (25) QDP (26) UsableRulesProof [EQUIVALENT, 0 ms] (27) QDP (28) ATransformationProof [EQUIVALENT, 0 ms] (29) QDP (30) QReductionProof [EQUIVALENT, 0 ms] (31) QDP (32) QDPOrderProof [EQUIVALENT, 21 ms] (33) QDP (34) DependencyGraphProof [EQUIVALENT, 0 ms] (35) TRUE (36) QDP (37) UsableRulesProof [EQUIVALENT, 0 ms] (38) QDP (39) ATransformationProof [EQUIVALENT, 0 ms] (40) QDP (41) QReductionProof [EQUIVALENT, 0 ms] (42) QDP (43) QDPSizeChangeProof [EQUIVALENT, 0 ms] (44) YES (45) QDP (46) UsableRulesProof [EQUIVALENT, 0 ms] (47) QDP (48) ATransformationProof [EQUIVALENT, 0 ms] (49) QDP (50) QReductionProof [EQUIVALENT, 0 ms] (51) QDP (52) QDPSizeChangeProof [EQUIVALENT, 0 ms] (53) YES (54) QDP (55) UsableRulesProof [EQUIVALENT, 0 ms] (56) QDP (57) ATransformationProof [EQUIVALENT, 0 ms] (58) QDP (59) QReductionProof [EQUIVALENT, 0 ms] (60) QDP (61) QDPOrderProof [EQUIVALENT, 107 ms] (62) QDP (63) UsableRulesProof [EQUIVALENT, 0 ms] (64) QDP (65) QReductionProof [EQUIVALENT, 0 ms] (66) QDP (67) QDPSizeChangeProof [EQUIVALENT, 0 ms] (68) YES (69) QDP (70) QDPSizeChangeProof [EQUIVALENT, 0 ms] (71) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: app'(app'(eq, 0), 0) -> true app'(app'(eq, 0), app'(s, x)) -> false app'(app'(eq, app'(s, x)), 0) -> false app'(app'(eq, app'(s, x)), app'(s, y)) -> app'(app'(eq, x), y) app'(app'(le, 0), y) -> true app'(app'(le, app'(s, x)), 0) -> false app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y) app'(app'(app, nil), y) -> y app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y)) app'(min, app'(app'(add, n), nil)) -> n app'(min, app'(app'(add, n), app'(app'(add, m), x))) -> app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x))) app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, n), x)) app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, m), x)) app'(app'(rm, n), nil) -> nil app'(app'(rm, n), app'(app'(add, m), x)) -> app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x)) app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) -> app'(app'(rm, n), x) app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(rm, n), x)) app'(app'(minsort, nil), nil) -> nil app'(app'(minsort, app'(app'(add, n), x)), y) -> app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y) app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil)) app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) -> app'(app'(minsort, x), app'(app'(add, n), y)) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(add, x), xs)) -> app'(app'(add, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(add, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(add, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) Q is empty. ---------------------------------------- (1) Overlay + Local Confluence (EQUIVALENT) The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: app'(app'(eq, 0), 0) -> true app'(app'(eq, 0), app'(s, x)) -> false app'(app'(eq, app'(s, x)), 0) -> false app'(app'(eq, app'(s, x)), app'(s, y)) -> app'(app'(eq, x), y) app'(app'(le, 0), y) -> true app'(app'(le, app'(s, x)), 0) -> false app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y) app'(app'(app, nil), y) -> y app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y)) app'(min, app'(app'(add, n), nil)) -> n app'(min, app'(app'(add, n), app'(app'(add, m), x))) -> app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x))) app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, n), x)) app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, m), x)) app'(app'(rm, n), nil) -> nil app'(app'(rm, n), app'(app'(add, m), x)) -> app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x)) app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) -> app'(app'(rm, n), x) app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(rm, n), x)) app'(app'(minsort, nil), nil) -> nil app'(app'(minsort, app'(app'(add, n), x)), y) -> app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y) app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil)) app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) -> app'(app'(minsort, x), app'(app'(add, n), y)) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(add, x), xs)) -> app'(app'(add, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(add, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(add, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) The set Q consists of the following terms: app'(app'(eq, 0), 0) app'(app'(eq, 0), app'(s, x0)) app'(app'(eq, app'(s, x0)), 0) app'(app'(eq, app'(s, x0)), app'(s, x1)) app'(app'(le, 0), x0) app'(app'(le, app'(s, x0)), 0) app'(app'(le, app'(s, x0)), app'(s, x1)) app'(app'(app, nil), x0) app'(app'(app, app'(app'(add, x0), x1)), x2) app'(min, app'(app'(add, x0), nil)) app'(min, app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(rm, x0), nil) app'(app'(rm, x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2)) app'(app'(minsort, nil), nil) app'(app'(minsort, app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2) app'(app'(map, x0), nil) app'(app'(map, x0), app'(app'(add, x1), x2)) app'(app'(filter, x0), nil) app'(app'(filter, x0), app'(app'(add, x1), x2)) app'(app'(app'(app'(filter2, true), x0), x1), x2) app'(app'(app'(app'(filter2, false), x0), x1), x2) ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(eq, app'(s, x)), app'(s, y)) -> APP'(app'(eq, x), y) APP'(app'(eq, app'(s, x)), app'(s, y)) -> APP'(eq, x) APP'(app'(le, app'(s, x)), app'(s, y)) -> APP'(app'(le, x), y) APP'(app'(le, app'(s, x)), app'(s, y)) -> APP'(le, x) APP'(app'(app, app'(app'(add, n), x)), y) -> APP'(app'(add, n), app'(app'(app, x), y)) APP'(app'(app, app'(app'(add, n), x)), y) -> APP'(app'(app, x), y) APP'(app'(app, app'(app'(add, n), x)), y) -> APP'(app, x) APP'(min, app'(app'(add, n), app'(app'(add, m), x))) -> APP'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x))) APP'(min, app'(app'(add, n), app'(app'(add, m), x))) -> APP'(if_min, app'(app'(le, n), m)) APP'(min, app'(app'(add, n), app'(app'(add, m), x))) -> APP'(app'(le, n), m) APP'(min, app'(app'(add, n), app'(app'(add, m), x))) -> APP'(le, n) APP'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) -> APP'(min, app'(app'(add, n), x)) APP'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) -> APP'(app'(add, n), x) APP'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) -> APP'(min, app'(app'(add, m), x)) APP'(app'(rm, n), app'(app'(add, m), x)) -> APP'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x)) APP'(app'(rm, n), app'(app'(add, m), x)) -> APP'(app'(if_rm, app'(app'(eq, n), m)), n) APP'(app'(rm, n), app'(app'(add, m), x)) -> APP'(if_rm, app'(app'(eq, n), m)) APP'(app'(rm, n), app'(app'(add, m), x)) -> APP'(app'(eq, n), m) APP'(app'(rm, n), app'(app'(add, m), x)) -> APP'(eq, n) APP'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) -> APP'(app'(rm, n), x) APP'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) -> APP'(rm, n) APP'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) -> APP'(app'(add, m), app'(app'(rm, n), x)) APP'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) -> APP'(app'(rm, n), x) APP'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) -> APP'(rm, n) APP'(app'(minsort, app'(app'(add, n), x)), y) -> APP'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y) APP'(app'(minsort, app'(app'(add, n), x)), y) -> APP'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)) APP'(app'(minsort, app'(app'(add, n), x)), y) -> APP'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))) APP'(app'(minsort, app'(app'(add, n), x)), y) -> APP'(app'(eq, n), app'(min, app'(app'(add, n), x))) APP'(app'(minsort, app'(app'(add, n), x)), y) -> APP'(eq, n) APP'(app'(minsort, app'(app'(add, n), x)), y) -> APP'(min, app'(app'(add, n), x)) APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> APP'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil)) APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> APP'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil) APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> APP'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)) APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> APP'(app'(app, app'(app'(rm, n), x)), y) APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> APP'(app, app'(app'(rm, n), x)) APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> APP'(app'(rm, n), x) APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> APP'(rm, n) APP'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) -> APP'(app'(minsort, x), app'(app'(add, n), y)) APP'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) -> APP'(minsort, x) APP'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) -> APP'(app'(add, n), y) APP'(app'(map, f), app'(app'(add, x), xs)) -> APP'(app'(add, app'(f, x)), app'(app'(map, f), xs)) APP'(app'(map, f), app'(app'(add, x), xs)) -> APP'(add, app'(f, x)) APP'(app'(map, f), app'(app'(add, x), xs)) -> APP'(f, x) APP'(app'(map, f), app'(app'(add, x), xs)) -> APP'(app'(map, f), xs) APP'(app'(filter, f), app'(app'(add, x), xs)) -> APP'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) APP'(app'(filter, f), app'(app'(add, x), xs)) -> APP'(app'(app'(filter2, app'(f, x)), f), x) APP'(app'(filter, f), app'(app'(add, x), xs)) -> APP'(app'(filter2, app'(f, x)), f) APP'(app'(filter, f), app'(app'(add, x), xs)) -> APP'(filter2, app'(f, x)) APP'(app'(filter, f), app'(app'(add, x), xs)) -> APP'(f, x) APP'(app'(app'(app'(filter2, true), f), x), xs) -> APP'(app'(add, x), app'(app'(filter, f), xs)) APP'(app'(app'(app'(filter2, true), f), x), xs) -> APP'(add, x) APP'(app'(app'(app'(filter2, true), f), x), xs) -> APP'(app'(filter, f), xs) APP'(app'(app'(app'(filter2, true), f), x), xs) -> APP'(filter, f) APP'(app'(app'(app'(filter2, false), f), x), xs) -> APP'(app'(filter, f), xs) APP'(app'(app'(app'(filter2, false), f), x), xs) -> APP'(filter, f) The TRS R consists of the following rules: app'(app'(eq, 0), 0) -> true app'(app'(eq, 0), app'(s, x)) -> false app'(app'(eq, app'(s, x)), 0) -> false app'(app'(eq, app'(s, x)), app'(s, y)) -> app'(app'(eq, x), y) app'(app'(le, 0), y) -> true app'(app'(le, app'(s, x)), 0) -> false app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y) app'(app'(app, nil), y) -> y app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y)) app'(min, app'(app'(add, n), nil)) -> n app'(min, app'(app'(add, n), app'(app'(add, m), x))) -> app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x))) app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, n), x)) app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, m), x)) app'(app'(rm, n), nil) -> nil app'(app'(rm, n), app'(app'(add, m), x)) -> app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x)) app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) -> app'(app'(rm, n), x) app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(rm, n), x)) app'(app'(minsort, nil), nil) -> nil app'(app'(minsort, app'(app'(add, n), x)), y) -> app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y) app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil)) app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) -> app'(app'(minsort, x), app'(app'(add, n), y)) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(add, x), xs)) -> app'(app'(add, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(add, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(add, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) The set Q consists of the following terms: app'(app'(eq, 0), 0) app'(app'(eq, 0), app'(s, x0)) app'(app'(eq, app'(s, x0)), 0) app'(app'(eq, app'(s, x0)), app'(s, x1)) app'(app'(le, 0), x0) app'(app'(le, app'(s, x0)), 0) app'(app'(le, app'(s, x0)), app'(s, x1)) app'(app'(app, nil), x0) app'(app'(app, app'(app'(add, x0), x1)), x2) app'(min, app'(app'(add, x0), nil)) app'(min, app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(rm, x0), nil) app'(app'(rm, x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2)) app'(app'(minsort, nil), nil) app'(app'(minsort, app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2) app'(app'(map, x0), nil) app'(app'(map, x0), app'(app'(add, x1), x2)) app'(app'(filter, x0), nil) app'(app'(filter, x0), app'(app'(add, x1), x2)) app'(app'(app'(app'(filter2, true), x0), x1), x2) app'(app'(app'(app'(filter2, false), x0), x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 7 SCCs with 37 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(app, app'(app'(add, n), x)), y) -> APP'(app'(app, x), y) The TRS R consists of the following rules: app'(app'(eq, 0), 0) -> true app'(app'(eq, 0), app'(s, x)) -> false app'(app'(eq, app'(s, x)), 0) -> false app'(app'(eq, app'(s, x)), app'(s, y)) -> app'(app'(eq, x), y) app'(app'(le, 0), y) -> true app'(app'(le, app'(s, x)), 0) -> false app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y) app'(app'(app, nil), y) -> y app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y)) app'(min, app'(app'(add, n), nil)) -> n app'(min, app'(app'(add, n), app'(app'(add, m), x))) -> app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x))) app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, n), x)) app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, m), x)) app'(app'(rm, n), nil) -> nil app'(app'(rm, n), app'(app'(add, m), x)) -> app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x)) app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) -> app'(app'(rm, n), x) app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(rm, n), x)) app'(app'(minsort, nil), nil) -> nil app'(app'(minsort, app'(app'(add, n), x)), y) -> app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y) app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil)) app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) -> app'(app'(minsort, x), app'(app'(add, n), y)) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(add, x), xs)) -> app'(app'(add, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(add, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(add, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) The set Q consists of the following terms: app'(app'(eq, 0), 0) app'(app'(eq, 0), app'(s, x0)) app'(app'(eq, app'(s, x0)), 0) app'(app'(eq, app'(s, x0)), app'(s, x1)) app'(app'(le, 0), x0) app'(app'(le, app'(s, x0)), 0) app'(app'(le, app'(s, x0)), app'(s, x1)) app'(app'(app, nil), x0) app'(app'(app, app'(app'(add, x0), x1)), x2) app'(min, app'(app'(add, x0), nil)) app'(min, app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(rm, x0), nil) app'(app'(rm, x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2)) app'(app'(minsort, nil), nil) app'(app'(minsort, app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2) app'(app'(map, x0), nil) app'(app'(map, x0), app'(app'(add, x1), x2)) app'(app'(filter, x0), nil) app'(app'(filter, x0), app'(app'(add, x1), x2)) app'(app'(app'(app'(filter2, true), x0), x1), x2) app'(app'(app'(app'(filter2, false), x0), x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(app, app'(app'(add, n), x)), y) -> APP'(app'(app, x), y) R is empty. The set Q consists of the following terms: app'(app'(eq, 0), 0) app'(app'(eq, 0), app'(s, x0)) app'(app'(eq, app'(s, x0)), 0) app'(app'(eq, app'(s, x0)), app'(s, x1)) app'(app'(le, 0), x0) app'(app'(le, app'(s, x0)), 0) app'(app'(le, app'(s, x0)), app'(s, x1)) app'(app'(app, nil), x0) app'(app'(app, app'(app'(add, x0), x1)), x2) app'(min, app'(app'(add, x0), nil)) app'(min, app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(rm, x0), nil) app'(app'(rm, x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2)) app'(app'(minsort, nil), nil) app'(app'(minsort, app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2) app'(app'(map, x0), nil) app'(app'(map, x0), app'(app'(add, x1), x2)) app'(app'(filter, x0), nil) app'(app'(filter, x0), app'(app'(add, x1), x2)) app'(app'(app'(app'(filter2, true), x0), x1), x2) app'(app'(app'(app'(filter2, false), x0), x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) ATransformationProof (EQUIVALENT) We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: app1(add(n, x), y) -> app1(x, y) R is empty. The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) app(nil, x0) app(add(x0, x1), x2) min(add(x0, nil)) min(add(x0, add(x1, x2))) if_min(true, add(x0, add(x1, x2))) if_min(false, add(x0, add(x1, x2))) rm(x0, nil) rm(x0, add(x1, x2)) if_rm(true, x0, add(x1, x2)) if_rm(false, x0, add(x1, x2)) minsort(nil, nil) minsort(add(x0, x1), x2) if_minsort(true, add(x0, x1), x2) if_minsort(false, add(x0, x1), x2) map(x0, nil) map(x0, add(x1, x2)) filter(x0, nil) filter(x0, add(x1, x2)) filter2(true, x0, x1, x2) filter2(false, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) app(nil, x0) app(add(x0, x1), x2) min(add(x0, nil)) min(add(x0, add(x1, x2))) if_min(true, add(x0, add(x1, x2))) if_min(false, add(x0, add(x1, x2))) rm(x0, nil) rm(x0, add(x1, x2)) if_rm(true, x0, add(x1, x2)) if_rm(false, x0, add(x1, x2)) minsort(nil, nil) minsort(add(x0, x1), x2) if_minsort(true, add(x0, x1), x2) if_minsort(false, add(x0, x1), x2) map(x0, nil) map(x0, add(x1, x2)) filter(x0, nil) filter(x0, add(x1, x2)) filter2(true, x0, x1, x2) filter2(false, x0, x1, x2) ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: app1(add(n, x), y) -> app1(x, y) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *app1(add(n, x), y) -> app1(x, y) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (15) YES ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(le, app'(s, x)), app'(s, y)) -> APP'(app'(le, x), y) The TRS R consists of the following rules: app'(app'(eq, 0), 0) -> true app'(app'(eq, 0), app'(s, x)) -> false app'(app'(eq, app'(s, x)), 0) -> false app'(app'(eq, app'(s, x)), app'(s, y)) -> app'(app'(eq, x), y) app'(app'(le, 0), y) -> true app'(app'(le, app'(s, x)), 0) -> false app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y) app'(app'(app, nil), y) -> y app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y)) app'(min, app'(app'(add, n), nil)) -> n app'(min, app'(app'(add, n), app'(app'(add, m), x))) -> app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x))) app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, n), x)) app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, m), x)) app'(app'(rm, n), nil) -> nil app'(app'(rm, n), app'(app'(add, m), x)) -> app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x)) app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) -> app'(app'(rm, n), x) app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(rm, n), x)) app'(app'(minsort, nil), nil) -> nil app'(app'(minsort, app'(app'(add, n), x)), y) -> app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y) app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil)) app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) -> app'(app'(minsort, x), app'(app'(add, n), y)) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(add, x), xs)) -> app'(app'(add, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(add, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(add, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) The set Q consists of the following terms: app'(app'(eq, 0), 0) app'(app'(eq, 0), app'(s, x0)) app'(app'(eq, app'(s, x0)), 0) app'(app'(eq, app'(s, x0)), app'(s, x1)) app'(app'(le, 0), x0) app'(app'(le, app'(s, x0)), 0) app'(app'(le, app'(s, x0)), app'(s, x1)) app'(app'(app, nil), x0) app'(app'(app, app'(app'(add, x0), x1)), x2) app'(min, app'(app'(add, x0), nil)) app'(min, app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(rm, x0), nil) app'(app'(rm, x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2)) app'(app'(minsort, nil), nil) app'(app'(minsort, app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2) app'(app'(map, x0), nil) app'(app'(map, x0), app'(app'(add, x1), x2)) app'(app'(filter, x0), nil) app'(app'(filter, x0), app'(app'(add, x1), x2)) app'(app'(app'(app'(filter2, true), x0), x1), x2) app'(app'(app'(app'(filter2, false), x0), x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(le, app'(s, x)), app'(s, y)) -> APP'(app'(le, x), y) R is empty. The set Q consists of the following terms: app'(app'(eq, 0), 0) app'(app'(eq, 0), app'(s, x0)) app'(app'(eq, app'(s, x0)), 0) app'(app'(eq, app'(s, x0)), app'(s, x1)) app'(app'(le, 0), x0) app'(app'(le, app'(s, x0)), 0) app'(app'(le, app'(s, x0)), app'(s, x1)) app'(app'(app, nil), x0) app'(app'(app, app'(app'(add, x0), x1)), x2) app'(min, app'(app'(add, x0), nil)) app'(min, app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(rm, x0), nil) app'(app'(rm, x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2)) app'(app'(minsort, nil), nil) app'(app'(minsort, app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2) app'(app'(map, x0), nil) app'(app'(map, x0), app'(app'(add, x1), x2)) app'(app'(filter, x0), nil) app'(app'(filter, x0), app'(app'(add, x1), x2)) app'(app'(app'(app'(filter2, true), x0), x1), x2) app'(app'(app'(app'(filter2, false), x0), x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) ATransformationProof (EQUIVALENT) We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: le1(s(x), s(y)) -> le1(x, y) R is empty. The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) app(nil, x0) app(add(x0, x1), x2) min(add(x0, nil)) min(add(x0, add(x1, x2))) if_min(true, add(x0, add(x1, x2))) if_min(false, add(x0, add(x1, x2))) rm(x0, nil) rm(x0, add(x1, x2)) if_rm(true, x0, add(x1, x2)) if_rm(false, x0, add(x1, x2)) minsort(nil, nil) minsort(add(x0, x1), x2) if_minsort(true, add(x0, x1), x2) if_minsort(false, add(x0, x1), x2) map(x0, nil) map(x0, add(x1, x2)) filter(x0, nil) filter(x0, add(x1, x2)) filter2(true, x0, x1, x2) filter2(false, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) app(nil, x0) app(add(x0, x1), x2) min(add(x0, nil)) min(add(x0, add(x1, x2))) if_min(true, add(x0, add(x1, x2))) if_min(false, add(x0, add(x1, x2))) rm(x0, nil) rm(x0, add(x1, x2)) if_rm(true, x0, add(x1, x2)) if_rm(false, x0, add(x1, x2)) minsort(nil, nil) minsort(add(x0, x1), x2) if_minsort(true, add(x0, x1), x2) if_minsort(false, add(x0, x1), x2) map(x0, nil) map(x0, add(x1, x2)) filter(x0, nil) filter(x0, add(x1, x2)) filter2(true, x0, x1, x2) filter2(false, x0, x1, x2) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: le1(s(x), s(y)) -> le1(x, y) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *le1(s(x), s(y)) -> le1(x, y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (24) YES ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(min, app'(app'(add, n), app'(app'(add, m), x))) -> APP'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x))) APP'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) -> APP'(min, app'(app'(add, n), x)) APP'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) -> APP'(min, app'(app'(add, m), x)) The TRS R consists of the following rules: app'(app'(eq, 0), 0) -> true app'(app'(eq, 0), app'(s, x)) -> false app'(app'(eq, app'(s, x)), 0) -> false app'(app'(eq, app'(s, x)), app'(s, y)) -> app'(app'(eq, x), y) app'(app'(le, 0), y) -> true app'(app'(le, app'(s, x)), 0) -> false app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y) app'(app'(app, nil), y) -> y app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y)) app'(min, app'(app'(add, n), nil)) -> n app'(min, app'(app'(add, n), app'(app'(add, m), x))) -> app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x))) app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, n), x)) app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, m), x)) app'(app'(rm, n), nil) -> nil app'(app'(rm, n), app'(app'(add, m), x)) -> app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x)) app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) -> app'(app'(rm, n), x) app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(rm, n), x)) app'(app'(minsort, nil), nil) -> nil app'(app'(minsort, app'(app'(add, n), x)), y) -> app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y) app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil)) app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) -> app'(app'(minsort, x), app'(app'(add, n), y)) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(add, x), xs)) -> app'(app'(add, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(add, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(add, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) The set Q consists of the following terms: app'(app'(eq, 0), 0) app'(app'(eq, 0), app'(s, x0)) app'(app'(eq, app'(s, x0)), 0) app'(app'(eq, app'(s, x0)), app'(s, x1)) app'(app'(le, 0), x0) app'(app'(le, app'(s, x0)), 0) app'(app'(le, app'(s, x0)), app'(s, x1)) app'(app'(app, nil), x0) app'(app'(app, app'(app'(add, x0), x1)), x2) app'(min, app'(app'(add, x0), nil)) app'(min, app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(rm, x0), nil) app'(app'(rm, x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2)) app'(app'(minsort, nil), nil) app'(app'(minsort, app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2) app'(app'(map, x0), nil) app'(app'(map, x0), app'(app'(add, x1), x2)) app'(app'(filter, x0), nil) app'(app'(filter, x0), app'(app'(add, x1), x2)) app'(app'(app'(app'(filter2, true), x0), x1), x2) app'(app'(app'(app'(filter2, false), x0), x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(min, app'(app'(add, n), app'(app'(add, m), x))) -> APP'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x))) APP'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) -> APP'(min, app'(app'(add, n), x)) APP'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) -> APP'(min, app'(app'(add, m), x)) The TRS R consists of the following rules: app'(app'(le, 0), y) -> true app'(app'(le, app'(s, x)), 0) -> false app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y) The set Q consists of the following terms: app'(app'(eq, 0), 0) app'(app'(eq, 0), app'(s, x0)) app'(app'(eq, app'(s, x0)), 0) app'(app'(eq, app'(s, x0)), app'(s, x1)) app'(app'(le, 0), x0) app'(app'(le, app'(s, x0)), 0) app'(app'(le, app'(s, x0)), app'(s, x1)) app'(app'(app, nil), x0) app'(app'(app, app'(app'(add, x0), x1)), x2) app'(min, app'(app'(add, x0), nil)) app'(min, app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(rm, x0), nil) app'(app'(rm, x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2)) app'(app'(minsort, nil), nil) app'(app'(minsort, app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2) app'(app'(map, x0), nil) app'(app'(map, x0), app'(app'(add, x1), x2)) app'(app'(filter, x0), nil) app'(app'(filter, x0), app'(app'(add, x1), x2)) app'(app'(app'(app'(filter2, true), x0), x1), x2) app'(app'(app'(app'(filter2, false), x0), x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) ATransformationProof (EQUIVALENT) We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: min1(add(n, add(m, x))) -> if_min1(le(n, m), add(n, add(m, x))) if_min1(true, add(n, add(m, x))) -> min1(add(n, x)) if_min1(false, add(n, add(m, x))) -> min1(add(m, x)) The TRS R consists of the following rules: le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) app(nil, x0) app(add(x0, x1), x2) min(add(x0, nil)) min(add(x0, add(x1, x2))) if_min(true, add(x0, add(x1, x2))) if_min(false, add(x0, add(x1, x2))) rm(x0, nil) rm(x0, add(x1, x2)) if_rm(true, x0, add(x1, x2)) if_rm(false, x0, add(x1, x2)) minsort(nil, nil) minsort(add(x0, x1), x2) if_minsort(true, add(x0, x1), x2) if_minsort(false, add(x0, x1), x2) map(x0, nil) map(x0, add(x1, x2)) filter(x0, nil) filter(x0, add(x1, x2)) filter2(true, x0, x1, x2) filter2(false, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (30) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) app(nil, x0) app(add(x0, x1), x2) min(add(x0, nil)) min(add(x0, add(x1, x2))) if_min(true, add(x0, add(x1, x2))) if_min(false, add(x0, add(x1, x2))) rm(x0, nil) rm(x0, add(x1, x2)) if_rm(true, x0, add(x1, x2)) if_rm(false, x0, add(x1, x2)) minsort(nil, nil) minsort(add(x0, x1), x2) if_minsort(true, add(x0, x1), x2) if_minsort(false, add(x0, x1), x2) map(x0, nil) map(x0, add(x1, x2)) filter(x0, nil) filter(x0, add(x1, x2)) filter2(true, x0, x1, x2) filter2(false, x0, x1, x2) ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: min1(add(n, add(m, x))) -> if_min1(le(n, m), add(n, add(m, x))) if_min1(true, add(n, add(m, x))) -> min1(add(n, x)) if_min1(false, add(n, add(m, x))) -> min1(add(m, x)) The TRS R consists of the following rules: le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (32) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. if_min1(true, add(n, add(m, x))) -> min1(add(n, x)) if_min1(false, add(n, add(m, x))) -> min1(add(m, x)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( if_min1_2(x_1, x_2) ) = 2x_2 + 2 POL( le_2(x_1, x_2) ) = 0 POL( 0 ) = 0 POL( true ) = 2 POL( s_1(x_1) ) = 2x_1 + 2 POL( false ) = 2 POL( min1_1(x_1) ) = 2x_1 + 2 POL( add_2(x_1, x_2) ) = 2x_2 + 2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: min1(add(n, add(m, x))) -> if_min1(le(n, m), add(n, add(m, x))) The TRS R consists of the following rules: le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (34) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (35) TRUE ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(eq, app'(s, x)), app'(s, y)) -> APP'(app'(eq, x), y) The TRS R consists of the following rules: app'(app'(eq, 0), 0) -> true app'(app'(eq, 0), app'(s, x)) -> false app'(app'(eq, app'(s, x)), 0) -> false app'(app'(eq, app'(s, x)), app'(s, y)) -> app'(app'(eq, x), y) app'(app'(le, 0), y) -> true app'(app'(le, app'(s, x)), 0) -> false app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y) app'(app'(app, nil), y) -> y app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y)) app'(min, app'(app'(add, n), nil)) -> n app'(min, app'(app'(add, n), app'(app'(add, m), x))) -> app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x))) app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, n), x)) app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, m), x)) app'(app'(rm, n), nil) -> nil app'(app'(rm, n), app'(app'(add, m), x)) -> app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x)) app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) -> app'(app'(rm, n), x) app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(rm, n), x)) app'(app'(minsort, nil), nil) -> nil app'(app'(minsort, app'(app'(add, n), x)), y) -> app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y) app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil)) app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) -> app'(app'(minsort, x), app'(app'(add, n), y)) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(add, x), xs)) -> app'(app'(add, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(add, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(add, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) The set Q consists of the following terms: app'(app'(eq, 0), 0) app'(app'(eq, 0), app'(s, x0)) app'(app'(eq, app'(s, x0)), 0) app'(app'(eq, app'(s, x0)), app'(s, x1)) app'(app'(le, 0), x0) app'(app'(le, app'(s, x0)), 0) app'(app'(le, app'(s, x0)), app'(s, x1)) app'(app'(app, nil), x0) app'(app'(app, app'(app'(add, x0), x1)), x2) app'(min, app'(app'(add, x0), nil)) app'(min, app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(rm, x0), nil) app'(app'(rm, x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2)) app'(app'(minsort, nil), nil) app'(app'(minsort, app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2) app'(app'(map, x0), nil) app'(app'(map, x0), app'(app'(add, x1), x2)) app'(app'(filter, x0), nil) app'(app'(filter, x0), app'(app'(add, x1), x2)) app'(app'(app'(app'(filter2, true), x0), x1), x2) app'(app'(app'(app'(filter2, false), x0), x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(eq, app'(s, x)), app'(s, y)) -> APP'(app'(eq, x), y) R is empty. The set Q consists of the following terms: app'(app'(eq, 0), 0) app'(app'(eq, 0), app'(s, x0)) app'(app'(eq, app'(s, x0)), 0) app'(app'(eq, app'(s, x0)), app'(s, x1)) app'(app'(le, 0), x0) app'(app'(le, app'(s, x0)), 0) app'(app'(le, app'(s, x0)), app'(s, x1)) app'(app'(app, nil), x0) app'(app'(app, app'(app'(add, x0), x1)), x2) app'(min, app'(app'(add, x0), nil)) app'(min, app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(rm, x0), nil) app'(app'(rm, x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2)) app'(app'(minsort, nil), nil) app'(app'(minsort, app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2) app'(app'(map, x0), nil) app'(app'(map, x0), app'(app'(add, x1), x2)) app'(app'(filter, x0), nil) app'(app'(filter, x0), app'(app'(add, x1), x2)) app'(app'(app'(app'(filter2, true), x0), x1), x2) app'(app'(app'(app'(filter2, false), x0), x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) ATransformationProof (EQUIVALENT) We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: eq1(s(x), s(y)) -> eq1(x, y) R is empty. The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) app(nil, x0) app(add(x0, x1), x2) min(add(x0, nil)) min(add(x0, add(x1, x2))) if_min(true, add(x0, add(x1, x2))) if_min(false, add(x0, add(x1, x2))) rm(x0, nil) rm(x0, add(x1, x2)) if_rm(true, x0, add(x1, x2)) if_rm(false, x0, add(x1, x2)) minsort(nil, nil) minsort(add(x0, x1), x2) if_minsort(true, add(x0, x1), x2) if_minsort(false, add(x0, x1), x2) map(x0, nil) map(x0, add(x1, x2)) filter(x0, nil) filter(x0, add(x1, x2)) filter2(true, x0, x1, x2) filter2(false, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) app(nil, x0) app(add(x0, x1), x2) min(add(x0, nil)) min(add(x0, add(x1, x2))) if_min(true, add(x0, add(x1, x2))) if_min(false, add(x0, add(x1, x2))) rm(x0, nil) rm(x0, add(x1, x2)) if_rm(true, x0, add(x1, x2)) if_rm(false, x0, add(x1, x2)) minsort(nil, nil) minsort(add(x0, x1), x2) if_minsort(true, add(x0, x1), x2) if_minsort(false, add(x0, x1), x2) map(x0, nil) map(x0, add(x1, x2)) filter(x0, nil) filter(x0, add(x1, x2)) filter2(true, x0, x1, x2) filter2(false, x0, x1, x2) ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: eq1(s(x), s(y)) -> eq1(x, y) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *eq1(s(x), s(y)) -> eq1(x, y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (44) YES ---------------------------------------- (45) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(rm, n), app'(app'(add, m), x)) -> APP'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x)) APP'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) -> APP'(app'(rm, n), x) APP'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) -> APP'(app'(rm, n), x) The TRS R consists of the following rules: app'(app'(eq, 0), 0) -> true app'(app'(eq, 0), app'(s, x)) -> false app'(app'(eq, app'(s, x)), 0) -> false app'(app'(eq, app'(s, x)), app'(s, y)) -> app'(app'(eq, x), y) app'(app'(le, 0), y) -> true app'(app'(le, app'(s, x)), 0) -> false app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y) app'(app'(app, nil), y) -> y app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y)) app'(min, app'(app'(add, n), nil)) -> n app'(min, app'(app'(add, n), app'(app'(add, m), x))) -> app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x))) app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, n), x)) app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, m), x)) app'(app'(rm, n), nil) -> nil app'(app'(rm, n), app'(app'(add, m), x)) -> app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x)) app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) -> app'(app'(rm, n), x) app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(rm, n), x)) app'(app'(minsort, nil), nil) -> nil app'(app'(minsort, app'(app'(add, n), x)), y) -> app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y) app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil)) app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) -> app'(app'(minsort, x), app'(app'(add, n), y)) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(add, x), xs)) -> app'(app'(add, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(add, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(add, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) The set Q consists of the following terms: app'(app'(eq, 0), 0) app'(app'(eq, 0), app'(s, x0)) app'(app'(eq, app'(s, x0)), 0) app'(app'(eq, app'(s, x0)), app'(s, x1)) app'(app'(le, 0), x0) app'(app'(le, app'(s, x0)), 0) app'(app'(le, app'(s, x0)), app'(s, x1)) app'(app'(app, nil), x0) app'(app'(app, app'(app'(add, x0), x1)), x2) app'(min, app'(app'(add, x0), nil)) app'(min, app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(rm, x0), nil) app'(app'(rm, x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2)) app'(app'(minsort, nil), nil) app'(app'(minsort, app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2) app'(app'(map, x0), nil) app'(app'(map, x0), app'(app'(add, x1), x2)) app'(app'(filter, x0), nil) app'(app'(filter, x0), app'(app'(add, x1), x2)) app'(app'(app'(app'(filter2, true), x0), x1), x2) app'(app'(app'(app'(filter2, false), x0), x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (46) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (47) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(rm, n), app'(app'(add, m), x)) -> APP'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x)) APP'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) -> APP'(app'(rm, n), x) APP'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) -> APP'(app'(rm, n), x) The TRS R consists of the following rules: app'(app'(eq, 0), 0) -> true app'(app'(eq, 0), app'(s, x)) -> false app'(app'(eq, app'(s, x)), 0) -> false app'(app'(eq, app'(s, x)), app'(s, y)) -> app'(app'(eq, x), y) The set Q consists of the following terms: app'(app'(eq, 0), 0) app'(app'(eq, 0), app'(s, x0)) app'(app'(eq, app'(s, x0)), 0) app'(app'(eq, app'(s, x0)), app'(s, x1)) app'(app'(le, 0), x0) app'(app'(le, app'(s, x0)), 0) app'(app'(le, app'(s, x0)), app'(s, x1)) app'(app'(app, nil), x0) app'(app'(app, app'(app'(add, x0), x1)), x2) app'(min, app'(app'(add, x0), nil)) app'(min, app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(rm, x0), nil) app'(app'(rm, x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2)) app'(app'(minsort, nil), nil) app'(app'(minsort, app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2) app'(app'(map, x0), nil) app'(app'(map, x0), app'(app'(add, x1), x2)) app'(app'(filter, x0), nil) app'(app'(filter, x0), app'(app'(add, x1), x2)) app'(app'(app'(app'(filter2, true), x0), x1), x2) app'(app'(app'(app'(filter2, false), x0), x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (48) ATransformationProof (EQUIVALENT) We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. ---------------------------------------- (49) Obligation: Q DP problem: The TRS P consists of the following rules: rm1(n, add(m, x)) -> if_rm1(eq(n, m), n, add(m, x)) if_rm1(true, n, add(m, x)) -> rm1(n, x) if_rm1(false, n, add(m, x)) -> rm1(n, x) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) app(nil, x0) app(add(x0, x1), x2) min(add(x0, nil)) min(add(x0, add(x1, x2))) if_min(true, add(x0, add(x1, x2))) if_min(false, add(x0, add(x1, x2))) rm(x0, nil) rm(x0, add(x1, x2)) if_rm(true, x0, add(x1, x2)) if_rm(false, x0, add(x1, x2)) minsort(nil, nil) minsort(add(x0, x1), x2) if_minsort(true, add(x0, x1), x2) if_minsort(false, add(x0, x1), x2) map(x0, nil) map(x0, add(x1, x2)) filter(x0, nil) filter(x0, add(x1, x2)) filter2(true, x0, x1, x2) filter2(false, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (50) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) app(nil, x0) app(add(x0, x1), x2) min(add(x0, nil)) min(add(x0, add(x1, x2))) if_min(true, add(x0, add(x1, x2))) if_min(false, add(x0, add(x1, x2))) rm(x0, nil) rm(x0, add(x1, x2)) if_rm(true, x0, add(x1, x2)) if_rm(false, x0, add(x1, x2)) minsort(nil, nil) minsort(add(x0, x1), x2) if_minsort(true, add(x0, x1), x2) if_minsort(false, add(x0, x1), x2) map(x0, nil) map(x0, add(x1, x2)) filter(x0, nil) filter(x0, add(x1, x2)) filter2(true, x0, x1, x2) filter2(false, x0, x1, x2) ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: rm1(n, add(m, x)) -> if_rm1(eq(n, m), n, add(m, x)) if_rm1(true, n, add(m, x)) -> rm1(n, x) if_rm1(false, n, add(m, x)) -> rm1(n, x) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (52) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *rm1(n, add(m, x)) -> if_rm1(eq(n, m), n, add(m, x)) The graph contains the following edges 1 >= 2, 2 >= 3 *if_rm1(true, n, add(m, x)) -> rm1(n, x) The graph contains the following edges 2 >= 1, 3 > 2 *if_rm1(false, n, add(m, x)) -> rm1(n, x) The graph contains the following edges 2 >= 1, 3 > 2 ---------------------------------------- (53) YES ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> APP'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil) APP'(app'(minsort, app'(app'(add, n), x)), y) -> APP'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y) APP'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) -> APP'(app'(minsort, x), app'(app'(add, n), y)) The TRS R consists of the following rules: app'(app'(eq, 0), 0) -> true app'(app'(eq, 0), app'(s, x)) -> false app'(app'(eq, app'(s, x)), 0) -> false app'(app'(eq, app'(s, x)), app'(s, y)) -> app'(app'(eq, x), y) app'(app'(le, 0), y) -> true app'(app'(le, app'(s, x)), 0) -> false app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y) app'(app'(app, nil), y) -> y app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y)) app'(min, app'(app'(add, n), nil)) -> n app'(min, app'(app'(add, n), app'(app'(add, m), x))) -> app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x))) app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, n), x)) app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, m), x)) app'(app'(rm, n), nil) -> nil app'(app'(rm, n), app'(app'(add, m), x)) -> app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x)) app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) -> app'(app'(rm, n), x) app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(rm, n), x)) app'(app'(minsort, nil), nil) -> nil app'(app'(minsort, app'(app'(add, n), x)), y) -> app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y) app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil)) app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) -> app'(app'(minsort, x), app'(app'(add, n), y)) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(add, x), xs)) -> app'(app'(add, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(add, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(add, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) The set Q consists of the following terms: app'(app'(eq, 0), 0) app'(app'(eq, 0), app'(s, x0)) app'(app'(eq, app'(s, x0)), 0) app'(app'(eq, app'(s, x0)), app'(s, x1)) app'(app'(le, 0), x0) app'(app'(le, app'(s, x0)), 0) app'(app'(le, app'(s, x0)), app'(s, x1)) app'(app'(app, nil), x0) app'(app'(app, app'(app'(add, x0), x1)), x2) app'(min, app'(app'(add, x0), nil)) app'(min, app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(rm, x0), nil) app'(app'(rm, x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2)) app'(app'(minsort, nil), nil) app'(app'(minsort, app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2) app'(app'(map, x0), nil) app'(app'(map, x0), app'(app'(add, x1), x2)) app'(app'(filter, x0), nil) app'(app'(filter, x0), app'(app'(add, x1), x2)) app'(app'(app'(app'(filter2, true), x0), x1), x2) app'(app'(app'(app'(filter2, false), x0), x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (55) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> APP'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil) APP'(app'(minsort, app'(app'(add, n), x)), y) -> APP'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y) APP'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) -> APP'(app'(minsort, x), app'(app'(add, n), y)) The TRS R consists of the following rules: app'(min, app'(app'(add, n), nil)) -> n app'(min, app'(app'(add, n), app'(app'(add, m), x))) -> app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x))) app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, n), x)) app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, m), x)) app'(app'(eq, 0), 0) -> true app'(app'(eq, 0), app'(s, x)) -> false app'(app'(eq, app'(s, x)), 0) -> false app'(app'(eq, app'(s, x)), app'(s, y)) -> app'(app'(eq, x), y) app'(app'(le, 0), y) -> true app'(app'(le, app'(s, x)), 0) -> false app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y) app'(app'(rm, n), nil) -> nil app'(app'(rm, n), app'(app'(add, m), x)) -> app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x)) app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) -> app'(app'(rm, n), x) app'(app'(app, nil), y) -> y app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y)) app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(rm, n), x)) The set Q consists of the following terms: app'(app'(eq, 0), 0) app'(app'(eq, 0), app'(s, x0)) app'(app'(eq, app'(s, x0)), 0) app'(app'(eq, app'(s, x0)), app'(s, x1)) app'(app'(le, 0), x0) app'(app'(le, app'(s, x0)), 0) app'(app'(le, app'(s, x0)), app'(s, x1)) app'(app'(app, nil), x0) app'(app'(app, app'(app'(add, x0), x1)), x2) app'(min, app'(app'(add, x0), nil)) app'(min, app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(rm, x0), nil) app'(app'(rm, x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2)) app'(app'(minsort, nil), nil) app'(app'(minsort, app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2) app'(app'(map, x0), nil) app'(app'(map, x0), app'(app'(add, x1), x2)) app'(app'(filter, x0), nil) app'(app'(filter, x0), app'(app'(add, x1), x2)) app'(app'(app'(app'(filter2, true), x0), x1), x2) app'(app'(app'(app'(filter2, false), x0), x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (57) ATransformationProof (EQUIVALENT) We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: if_minsort1(true, add(n, x), y) -> minsort1(app(rm(n, x), y), nil) minsort1(add(n, x), y) -> if_minsort1(eq(n, min(add(n, x))), add(n, x), y) if_minsort1(false, add(n, x), y) -> minsort1(x, add(n, y)) The TRS R consists of the following rules: min(add(n, nil)) -> n min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) if_min(true, add(n, add(m, x))) -> min(add(n, x)) if_min(false, add(n, add(m, x))) -> min(add(m, x)) eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) rm(n, nil) -> nil rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) if_rm(true, n, add(m, x)) -> rm(n, x) app(nil, y) -> y app(add(n, x), y) -> add(n, app(x, y)) if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) app(nil, x0) app(add(x0, x1), x2) min(add(x0, nil)) min(add(x0, add(x1, x2))) if_min(true, add(x0, add(x1, x2))) if_min(false, add(x0, add(x1, x2))) rm(x0, nil) rm(x0, add(x1, x2)) if_rm(true, x0, add(x1, x2)) if_rm(false, x0, add(x1, x2)) minsort(nil, nil) minsort(add(x0, x1), x2) if_minsort(true, add(x0, x1), x2) if_minsort(false, add(x0, x1), x2) map(x0, nil) map(x0, add(x1, x2)) filter(x0, nil) filter(x0, add(x1, x2)) filter2(true, x0, x1, x2) filter2(false, x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (59) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. minsort(nil, nil) minsort(add(x0, x1), x2) if_minsort(true, add(x0, x1), x2) if_minsort(false, add(x0, x1), x2) map(x0, nil) map(x0, add(x1, x2)) filter(x0, nil) filter(x0, add(x1, x2)) filter2(true, x0, x1, x2) filter2(false, x0, x1, x2) ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: if_minsort1(true, add(n, x), y) -> minsort1(app(rm(n, x), y), nil) minsort1(add(n, x), y) -> if_minsort1(eq(n, min(add(n, x))), add(n, x), y) if_minsort1(false, add(n, x), y) -> minsort1(x, add(n, y)) The TRS R consists of the following rules: min(add(n, nil)) -> n min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) if_min(true, add(n, add(m, x))) -> min(add(n, x)) if_min(false, add(n, add(m, x))) -> min(add(m, x)) eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) rm(n, nil) -> nil rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) if_rm(true, n, add(m, x)) -> rm(n, x) app(nil, y) -> y app(add(n, x), y) -> add(n, app(x, y)) if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) app(nil, x0) app(add(x0, x1), x2) min(add(x0, nil)) min(add(x0, add(x1, x2))) if_min(true, add(x0, add(x1, x2))) if_min(false, add(x0, add(x1, x2))) rm(x0, nil) rm(x0, add(x1, x2)) if_rm(true, x0, add(x1, x2)) if_rm(false, x0, add(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (61) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. if_minsort1(true, add(n, x), y) -> minsort1(app(rm(n, x), y), nil) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( app_2(x_1, x_2) ) = x_1 + x_2 POL( minsort1_2(x_1, x_2) ) = max{0, 2x_1 + 2x_2 - 1} POL( rm_2(x_1, x_2) ) = x_2 POL( nil ) = 0 POL( add_2(x_1, x_2) ) = x_2 + 1 POL( if_rm_3(x_1, ..., x_3) ) = 2x_1 + x_3 POL( eq_2(x_1, x_2) ) = max{0, -2} POL( true ) = 0 POL( if_minsort1_3(x_1, ..., x_3) ) = max{0, 2x_2 + 2x_3 - 1} POL( min_1(x_1) ) = 2 POL( if_min_2(x_1, x_2) ) = max{0, -2} POL( le_2(x_1, x_2) ) = 0 POL( false ) = 0 POL( 0 ) = 0 POL( s_1(x_1) ) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: rm(n, nil) -> nil rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) if_rm(true, n, add(m, x)) -> rm(n, x) app(nil, y) -> y app(add(n, x), y) -> add(n, app(x, y)) eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) ---------------------------------------- (62) Obligation: Q DP problem: The TRS P consists of the following rules: minsort1(add(n, x), y) -> if_minsort1(eq(n, min(add(n, x))), add(n, x), y) if_minsort1(false, add(n, x), y) -> minsort1(x, add(n, y)) The TRS R consists of the following rules: min(add(n, nil)) -> n min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) if_min(true, add(n, add(m, x))) -> min(add(n, x)) if_min(false, add(n, add(m, x))) -> min(add(m, x)) eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) rm(n, nil) -> nil rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) if_rm(true, n, add(m, x)) -> rm(n, x) app(nil, y) -> y app(add(n, x), y) -> add(n, app(x, y)) if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) app(nil, x0) app(add(x0, x1), x2) min(add(x0, nil)) min(add(x0, add(x1, x2))) if_min(true, add(x0, add(x1, x2))) if_min(false, add(x0, add(x1, x2))) rm(x0, nil) rm(x0, add(x1, x2)) if_rm(true, x0, add(x1, x2)) if_rm(false, x0, add(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (63) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (64) Obligation: Q DP problem: The TRS P consists of the following rules: minsort1(add(n, x), y) -> if_minsort1(eq(n, min(add(n, x))), add(n, x), y) if_minsort1(false, add(n, x), y) -> minsort1(x, add(n, y)) The TRS R consists of the following rules: min(add(n, nil)) -> n min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) if_min(true, add(n, add(m, x))) -> min(add(n, x)) if_min(false, add(n, add(m, x))) -> min(add(m, x)) eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) app(nil, x0) app(add(x0, x1), x2) min(add(x0, nil)) min(add(x0, add(x1, x2))) if_min(true, add(x0, add(x1, x2))) if_min(false, add(x0, add(x1, x2))) rm(x0, nil) rm(x0, add(x1, x2)) if_rm(true, x0, add(x1, x2)) if_rm(false, x0, add(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (65) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. app(nil, x0) app(add(x0, x1), x2) rm(x0, nil) rm(x0, add(x1, x2)) if_rm(true, x0, add(x1, x2)) if_rm(false, x0, add(x1, x2)) ---------------------------------------- (66) Obligation: Q DP problem: The TRS P consists of the following rules: minsort1(add(n, x), y) -> if_minsort1(eq(n, min(add(n, x))), add(n, x), y) if_minsort1(false, add(n, x), y) -> minsort1(x, add(n, y)) The TRS R consists of the following rules: min(add(n, nil)) -> n min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) if_min(true, add(n, add(m, x))) -> min(add(n, x)) if_min(false, add(n, add(m, x))) -> min(add(m, x)) eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(add(x0, nil)) min(add(x0, add(x1, x2))) if_min(true, add(x0, add(x1, x2))) if_min(false, add(x0, add(x1, x2))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (67) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *if_minsort1(false, add(n, x), y) -> minsort1(x, add(n, y)) The graph contains the following edges 2 > 1 *minsort1(add(n, x), y) -> if_minsort1(eq(n, min(add(n, x))), add(n, x), y) The graph contains the following edges 1 >= 2, 2 >= 3 ---------------------------------------- (68) YES ---------------------------------------- (69) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(map, f), app'(app'(add, x), xs)) -> APP'(app'(map, f), xs) APP'(app'(map, f), app'(app'(add, x), xs)) -> APP'(f, x) APP'(app'(filter, f), app'(app'(add, x), xs)) -> APP'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) APP'(app'(app'(app'(filter2, true), f), x), xs) -> APP'(app'(filter, f), xs) APP'(app'(filter, f), app'(app'(add, x), xs)) -> APP'(f, x) APP'(app'(app'(app'(filter2, false), f), x), xs) -> APP'(app'(filter, f), xs) The TRS R consists of the following rules: app'(app'(eq, 0), 0) -> true app'(app'(eq, 0), app'(s, x)) -> false app'(app'(eq, app'(s, x)), 0) -> false app'(app'(eq, app'(s, x)), app'(s, y)) -> app'(app'(eq, x), y) app'(app'(le, 0), y) -> true app'(app'(le, app'(s, x)), 0) -> false app'(app'(le, app'(s, x)), app'(s, y)) -> app'(app'(le, x), y) app'(app'(app, nil), y) -> y app'(app'(app, app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(app, x), y)) app'(min, app'(app'(add, n), nil)) -> n app'(min, app'(app'(add, n), app'(app'(add, m), x))) -> app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x))) app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, n), x)) app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) -> app'(min, app'(app'(add, m), x)) app'(app'(rm, n), nil) -> nil app'(app'(rm, n), app'(app'(add, m), x)) -> app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x)) app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) -> app'(app'(rm, n), x) app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) -> app'(app'(add, m), app'(app'(rm, n), x)) app'(app'(minsort, nil), nil) -> nil app'(app'(minsort, app'(app'(add, n), x)), y) -> app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y) app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) -> app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil)) app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) -> app'(app'(minsort, x), app'(app'(add, n), y)) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(add, x), xs)) -> app'(app'(add, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(add, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(add, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) The set Q consists of the following terms: app'(app'(eq, 0), 0) app'(app'(eq, 0), app'(s, x0)) app'(app'(eq, app'(s, x0)), 0) app'(app'(eq, app'(s, x0)), app'(s, x1)) app'(app'(le, 0), x0) app'(app'(le, app'(s, x0)), 0) app'(app'(le, app'(s, x0)), app'(s, x1)) app'(app'(app, nil), x0) app'(app'(app, app'(app'(add, x0), x1)), x2) app'(min, app'(app'(add, x0), nil)) app'(min, app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2))) app'(app'(rm, x0), nil) app'(app'(rm, x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2)) app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2)) app'(app'(minsort, nil), nil) app'(app'(minsort, app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2) app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2) app'(app'(map, x0), nil) app'(app'(map, x0), app'(app'(add, x1), x2)) app'(app'(filter, x0), nil) app'(app'(filter, x0), app'(app'(add, x1), x2)) app'(app'(app'(app'(filter2, true), x0), x1), x2) app'(app'(app'(app'(filter2, false), x0), x1), x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (70) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *APP'(app'(filter, f), app'(app'(add, x), xs)) -> APP'(f, x) The graph contains the following edges 1 > 1, 2 > 2 *APP'(app'(map, f), app'(app'(add, x), xs)) -> APP'(f, x) The graph contains the following edges 1 > 1, 2 > 2 *APP'(app'(map, f), app'(app'(add, x), xs)) -> APP'(app'(map, f), xs) The graph contains the following edges 1 >= 1, 2 > 2 *APP'(app'(filter, f), app'(app'(add, x), xs)) -> APP'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) The graph contains the following edges 2 > 2 *APP'(app'(app'(app'(filter2, true), f), x), xs) -> APP'(app'(filter, f), xs) The graph contains the following edges 2 >= 2 *APP'(app'(app'(app'(filter2, false), f), x), xs) -> APP'(app'(filter, f), xs) The graph contains the following edges 2 >= 2 ---------------------------------------- (71) YES