6.31/2.64 YES 6.64/2.66 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 6.64/2.66 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.64/2.66 6.64/2.66 6.64/2.66 Termination w.r.t. Q of the given QTRS could be proven: 6.64/2.66 6.64/2.66 (0) QTRS 6.64/2.66 (1) DependencyPairsProof [EQUIVALENT, 90 ms] 6.64/2.66 (2) QDP 6.64/2.66 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 6.64/2.66 (4) AND 6.64/2.66 (5) QDP 6.64/2.66 (6) UsableRulesProof [EQUIVALENT, 0 ms] 6.64/2.66 (7) QDP 6.64/2.66 (8) ATransformationProof [EQUIVALENT, 0 ms] 6.64/2.66 (9) QDP 6.64/2.66 (10) QReductionProof [EQUIVALENT, 0 ms] 6.64/2.66 (11) QDP 6.64/2.66 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 6.64/2.66 (13) YES 6.64/2.66 (14) QDP 6.64/2.66 (15) UsableRulesProof [EQUIVALENT, 0 ms] 6.64/2.66 (16) QDP 6.64/2.66 (17) ATransformationProof [EQUIVALENT, 0 ms] 6.64/2.66 (18) QDP 6.64/2.66 (19) QReductionProof [EQUIVALENT, 0 ms] 6.64/2.66 (20) QDP 6.64/2.66 (21) QDPOrderProof [EQUIVALENT, 27 ms] 6.64/2.66 (22) QDP 6.64/2.66 (23) DependencyGraphProof [EQUIVALENT, 0 ms] 6.64/2.66 (24) TRUE 6.64/2.66 (25) QDP 6.64/2.66 (26) UsableRulesProof [EQUIVALENT, 0 ms] 6.64/2.66 (27) QDP 6.64/2.66 (28) ATransformationProof [EQUIVALENT, 0 ms] 6.64/2.66 (29) QDP 6.64/2.66 (30) QReductionProof [EQUIVALENT, 0 ms] 6.64/2.66 (31) QDP 6.64/2.66 (32) QDPSizeChangeProof [EQUIVALENT, 0 ms] 6.64/2.66 (33) YES 6.64/2.66 (34) QDP 6.64/2.66 (35) UsableRulesProof [EQUIVALENT, 0 ms] 6.64/2.66 (36) QDP 6.64/2.66 (37) ATransformationProof [EQUIVALENT, 0 ms] 6.64/2.66 (38) QDP 6.64/2.66 (39) QReductionProof [EQUIVALENT, 0 ms] 6.64/2.66 (40) QDP 6.64/2.66 (41) QDPSizeChangeProof [EQUIVALENT, 0 ms] 6.64/2.66 (42) YES 6.64/2.66 (43) QDP 6.64/2.66 (44) UsableRulesProof [EQUIVALENT, 0 ms] 6.64/2.66 (45) QDP 6.64/2.66 (46) ATransformationProof [EQUIVALENT, 0 ms] 6.64/2.66 (47) QDP 6.64/2.66 (48) QReductionProof [EQUIVALENT, 0 ms] 6.64/2.66 (49) QDP 6.64/2.66 (50) QDPOrderProof [EQUIVALENT, 45 ms] 6.64/2.66 (51) QDP 6.64/2.66 (52) PisEmptyProof [EQUIVALENT, 0 ms] 6.64/2.66 (53) YES 6.64/2.66 (54) QDP 6.64/2.66 (55) QDPSizeChangeProof [EQUIVALENT, 0 ms] 6.64/2.66 (56) YES 6.64/2.66 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (0) 6.64/2.66 Obligation: 6.64/2.66 Q restricted rewrite system: 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) -> true 6.64/2.66 app(app(eq, 0), app(s, m)) -> false 6.64/2.66 app(app(eq, app(s, n)), 0) -> false 6.64/2.66 app(app(eq, app(s, n)), app(s, m)) -> app(app(eq, n), m) 6.64/2.66 app(app(le, 0), m) -> true 6.64/2.66 app(app(le, app(s, n)), 0) -> false 6.64/2.66 app(app(le, app(s, n)), app(s, m)) -> app(app(le, n), m) 6.64/2.66 app(min, app(app(cons, 0), nil)) -> 0 6.64/2.66 app(min, app(app(cons, app(s, n)), nil)) -> app(s, n) 6.64/2.66 app(min, app(app(cons, n), app(app(cons, m), x))) -> app(app(if_min, app(app(le, n), m)), app(app(cons, n), app(app(cons, m), x))) 6.64/2.66 app(app(if_min, true), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, n), x)) 6.64/2.66 app(app(if_min, false), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, m), x)) 6.64/2.66 app(app(app(replace, n), m), nil) -> nil 6.64/2.66 app(app(app(replace, n), m), app(app(cons, k), x)) -> app(app(app(app(if_replace, app(app(eq, n), k)), n), m), app(app(cons, k), x)) 6.64/2.66 app(app(app(app(if_replace, true), n), m), app(app(cons, k), x)) -> app(app(cons, m), x) 6.64/2.66 app(app(app(app(if_replace, false), n), m), app(app(cons, k), x)) -> app(app(cons, k), app(app(app(replace, n), m), x)) 6.64/2.66 app(sort, nil) -> nil 6.64/2.66 app(sort, app(app(cons, n), x)) -> app(app(cons, app(min, app(app(cons, n), x))), app(sort, app(app(app(replace, app(min, app(app(cons, n), x))), n), x))) 6.64/2.66 app(app(map, f), nil) -> nil 6.64/2.66 app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs)) 6.64/2.66 app(app(filter, f), nil) -> nil 6.64/2.66 app(app(filter, f), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(f, x)), f), x), xs) 6.64/2.66 app(app(app(app(filter2, true), f), x), xs) -> app(app(cons, x), app(app(filter, f), xs)) 6.64/2.66 app(app(app(app(filter2, false), f), x), xs) -> app(app(filter, f), xs) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) 6.64/2.66 app(app(eq, 0), app(s, x0)) 6.64/2.66 app(app(eq, app(s, x0)), 0) 6.64/2.66 app(app(eq, app(s, x0)), app(s, x1)) 6.64/2.66 app(app(le, 0), x0) 6.64/2.66 app(app(le, app(s, x0)), 0) 6.64/2.66 app(app(le, app(s, x0)), app(s, x1)) 6.64/2.66 app(min, app(app(cons, 0), nil)) 6.64/2.66 app(min, app(app(cons, app(s, x0)), nil)) 6.64/2.66 app(min, app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, true), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, false), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(app(replace, x0), x1), nil) 6.64/2.66 app(app(app(replace, x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, true), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, false), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(sort, nil) 6.64/2.66 app(sort, app(app(cons, x0), x1)) 6.64/2.66 app(app(map, x0), nil) 6.64/2.66 app(app(map, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(filter, x0), nil) 6.64/2.66 app(app(filter, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(app(app(filter2, true), x0), x1), x2) 6.64/2.66 app(app(app(app(filter2, false), x0), x1), x2) 6.64/2.66 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (1) DependencyPairsProof (EQUIVALENT) 6.64/2.66 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (2) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 APP(app(eq, app(s, n)), app(s, m)) -> APP(app(eq, n), m) 6.64/2.66 APP(app(eq, app(s, n)), app(s, m)) -> APP(eq, n) 6.64/2.66 APP(app(le, app(s, n)), app(s, m)) -> APP(app(le, n), m) 6.64/2.66 APP(app(le, app(s, n)), app(s, m)) -> APP(le, n) 6.64/2.66 APP(min, app(app(cons, n), app(app(cons, m), x))) -> APP(app(if_min, app(app(le, n), m)), app(app(cons, n), app(app(cons, m), x))) 6.64/2.66 APP(min, app(app(cons, n), app(app(cons, m), x))) -> APP(if_min, app(app(le, n), m)) 6.64/2.66 APP(min, app(app(cons, n), app(app(cons, m), x))) -> APP(app(le, n), m) 6.64/2.66 APP(min, app(app(cons, n), app(app(cons, m), x))) -> APP(le, n) 6.64/2.66 APP(app(if_min, true), app(app(cons, n), app(app(cons, m), x))) -> APP(min, app(app(cons, n), x)) 6.64/2.66 APP(app(if_min, true), app(app(cons, n), app(app(cons, m), x))) -> APP(app(cons, n), x) 6.64/2.66 APP(app(if_min, false), app(app(cons, n), app(app(cons, m), x))) -> APP(min, app(app(cons, m), x)) 6.64/2.66 APP(app(app(replace, n), m), app(app(cons, k), x)) -> APP(app(app(app(if_replace, app(app(eq, n), k)), n), m), app(app(cons, k), x)) 6.64/2.66 APP(app(app(replace, n), m), app(app(cons, k), x)) -> APP(app(app(if_replace, app(app(eq, n), k)), n), m) 6.64/2.66 APP(app(app(replace, n), m), app(app(cons, k), x)) -> APP(app(if_replace, app(app(eq, n), k)), n) 6.64/2.66 APP(app(app(replace, n), m), app(app(cons, k), x)) -> APP(if_replace, app(app(eq, n), k)) 6.64/2.66 APP(app(app(replace, n), m), app(app(cons, k), x)) -> APP(app(eq, n), k) 6.64/2.66 APP(app(app(replace, n), m), app(app(cons, k), x)) -> APP(eq, n) 6.64/2.66 APP(app(app(app(if_replace, true), n), m), app(app(cons, k), x)) -> APP(app(cons, m), x) 6.64/2.66 APP(app(app(app(if_replace, true), n), m), app(app(cons, k), x)) -> APP(cons, m) 6.64/2.66 APP(app(app(app(if_replace, false), n), m), app(app(cons, k), x)) -> APP(app(cons, k), app(app(app(replace, n), m), x)) 6.64/2.66 APP(app(app(app(if_replace, false), n), m), app(app(cons, k), x)) -> APP(app(app(replace, n), m), x) 6.64/2.66 APP(app(app(app(if_replace, false), n), m), app(app(cons, k), x)) -> APP(app(replace, n), m) 6.64/2.66 APP(app(app(app(if_replace, false), n), m), app(app(cons, k), x)) -> APP(replace, n) 6.64/2.66 APP(sort, app(app(cons, n), x)) -> APP(app(cons, app(min, app(app(cons, n), x))), app(sort, app(app(app(replace, app(min, app(app(cons, n), x))), n), x))) 6.64/2.66 APP(sort, app(app(cons, n), x)) -> APP(cons, app(min, app(app(cons, n), x))) 6.64/2.66 APP(sort, app(app(cons, n), x)) -> APP(min, app(app(cons, n), x)) 6.64/2.66 APP(sort, app(app(cons, n), x)) -> APP(sort, app(app(app(replace, app(min, app(app(cons, n), x))), n), x)) 6.64/2.66 APP(sort, app(app(cons, n), x)) -> APP(app(app(replace, app(min, app(app(cons, n), x))), n), x) 6.64/2.66 APP(sort, app(app(cons, n), x)) -> APP(app(replace, app(min, app(app(cons, n), x))), n) 6.64/2.66 APP(sort, app(app(cons, n), x)) -> APP(replace, app(min, app(app(cons, n), x))) 6.64/2.66 APP(app(map, f), app(app(cons, x), xs)) -> APP(app(cons, app(f, x)), app(app(map, f), xs)) 6.64/2.66 APP(app(map, f), app(app(cons, x), xs)) -> APP(cons, app(f, x)) 6.64/2.66 APP(app(map, f), app(app(cons, x), xs)) -> APP(f, x) 6.64/2.66 APP(app(map, f), app(app(cons, x), xs)) -> APP(app(map, f), xs) 6.64/2.66 APP(app(filter, f), app(app(cons, x), xs)) -> APP(app(app(app(filter2, app(f, x)), f), x), xs) 6.64/2.66 APP(app(filter, f), app(app(cons, x), xs)) -> APP(app(app(filter2, app(f, x)), f), x) 6.64/2.66 APP(app(filter, f), app(app(cons, x), xs)) -> APP(app(filter2, app(f, x)), f) 6.64/2.66 APP(app(filter, f), app(app(cons, x), xs)) -> APP(filter2, app(f, x)) 6.64/2.66 APP(app(filter, f), app(app(cons, x), xs)) -> APP(f, x) 6.64/2.66 APP(app(app(app(filter2, true), f), x), xs) -> APP(app(cons, x), app(app(filter, f), xs)) 6.64/2.66 APP(app(app(app(filter2, true), f), x), xs) -> APP(cons, x) 6.64/2.66 APP(app(app(app(filter2, true), f), x), xs) -> APP(app(filter, f), xs) 6.64/2.66 APP(app(app(app(filter2, true), f), x), xs) -> APP(filter, f) 6.64/2.66 APP(app(app(app(filter2, false), f), x), xs) -> APP(app(filter, f), xs) 6.64/2.66 APP(app(app(app(filter2, false), f), x), xs) -> APP(filter, f) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) -> true 6.64/2.66 app(app(eq, 0), app(s, m)) -> false 6.64/2.66 app(app(eq, app(s, n)), 0) -> false 6.64/2.66 app(app(eq, app(s, n)), app(s, m)) -> app(app(eq, n), m) 6.64/2.66 app(app(le, 0), m) -> true 6.64/2.66 app(app(le, app(s, n)), 0) -> false 6.64/2.66 app(app(le, app(s, n)), app(s, m)) -> app(app(le, n), m) 6.64/2.66 app(min, app(app(cons, 0), nil)) -> 0 6.64/2.66 app(min, app(app(cons, app(s, n)), nil)) -> app(s, n) 6.64/2.66 app(min, app(app(cons, n), app(app(cons, m), x))) -> app(app(if_min, app(app(le, n), m)), app(app(cons, n), app(app(cons, m), x))) 6.64/2.66 app(app(if_min, true), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, n), x)) 6.64/2.66 app(app(if_min, false), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, m), x)) 6.64/2.66 app(app(app(replace, n), m), nil) -> nil 6.64/2.66 app(app(app(replace, n), m), app(app(cons, k), x)) -> app(app(app(app(if_replace, app(app(eq, n), k)), n), m), app(app(cons, k), x)) 6.64/2.66 app(app(app(app(if_replace, true), n), m), app(app(cons, k), x)) -> app(app(cons, m), x) 6.64/2.66 app(app(app(app(if_replace, false), n), m), app(app(cons, k), x)) -> app(app(cons, k), app(app(app(replace, n), m), x)) 6.64/2.66 app(sort, nil) -> nil 6.64/2.66 app(sort, app(app(cons, n), x)) -> app(app(cons, app(min, app(app(cons, n), x))), app(sort, app(app(app(replace, app(min, app(app(cons, n), x))), n), x))) 6.64/2.66 app(app(map, f), nil) -> nil 6.64/2.66 app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs)) 6.64/2.66 app(app(filter, f), nil) -> nil 6.64/2.66 app(app(filter, f), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(f, x)), f), x), xs) 6.64/2.66 app(app(app(app(filter2, true), f), x), xs) -> app(app(cons, x), app(app(filter, f), xs)) 6.64/2.66 app(app(app(app(filter2, false), f), x), xs) -> app(app(filter, f), xs) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) 6.64/2.66 app(app(eq, 0), app(s, x0)) 6.64/2.66 app(app(eq, app(s, x0)), 0) 6.64/2.66 app(app(eq, app(s, x0)), app(s, x1)) 6.64/2.66 app(app(le, 0), x0) 6.64/2.66 app(app(le, app(s, x0)), 0) 6.64/2.66 app(app(le, app(s, x0)), app(s, x1)) 6.64/2.66 app(min, app(app(cons, 0), nil)) 6.64/2.66 app(min, app(app(cons, app(s, x0)), nil)) 6.64/2.66 app(min, app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, true), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, false), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(app(replace, x0), x1), nil) 6.64/2.66 app(app(app(replace, x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, true), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, false), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(sort, nil) 6.64/2.66 app(sort, app(app(cons, x0), x1)) 6.64/2.66 app(app(map, x0), nil) 6.64/2.66 app(app(map, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(filter, x0), nil) 6.64/2.66 app(app(filter, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(app(app(filter2, true), x0), x1), x2) 6.64/2.66 app(app(app(app(filter2, false), x0), x1), x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (3) DependencyGraphProof (EQUIVALENT) 6.64/2.66 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 6 SCCs with 31 less nodes. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (4) 6.64/2.66 Complex Obligation (AND) 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (5) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 APP(app(le, app(s, n)), app(s, m)) -> APP(app(le, n), m) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) -> true 6.64/2.66 app(app(eq, 0), app(s, m)) -> false 6.64/2.66 app(app(eq, app(s, n)), 0) -> false 6.64/2.66 app(app(eq, app(s, n)), app(s, m)) -> app(app(eq, n), m) 6.64/2.66 app(app(le, 0), m) -> true 6.64/2.66 app(app(le, app(s, n)), 0) -> false 6.64/2.66 app(app(le, app(s, n)), app(s, m)) -> app(app(le, n), m) 6.64/2.66 app(min, app(app(cons, 0), nil)) -> 0 6.64/2.66 app(min, app(app(cons, app(s, n)), nil)) -> app(s, n) 6.64/2.66 app(min, app(app(cons, n), app(app(cons, m), x))) -> app(app(if_min, app(app(le, n), m)), app(app(cons, n), app(app(cons, m), x))) 6.64/2.66 app(app(if_min, true), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, n), x)) 6.64/2.66 app(app(if_min, false), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, m), x)) 6.64/2.66 app(app(app(replace, n), m), nil) -> nil 6.64/2.66 app(app(app(replace, n), m), app(app(cons, k), x)) -> app(app(app(app(if_replace, app(app(eq, n), k)), n), m), app(app(cons, k), x)) 6.64/2.66 app(app(app(app(if_replace, true), n), m), app(app(cons, k), x)) -> app(app(cons, m), x) 6.64/2.66 app(app(app(app(if_replace, false), n), m), app(app(cons, k), x)) -> app(app(cons, k), app(app(app(replace, n), m), x)) 6.64/2.66 app(sort, nil) -> nil 6.64/2.66 app(sort, app(app(cons, n), x)) -> app(app(cons, app(min, app(app(cons, n), x))), app(sort, app(app(app(replace, app(min, app(app(cons, n), x))), n), x))) 6.64/2.66 app(app(map, f), nil) -> nil 6.64/2.66 app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs)) 6.64/2.66 app(app(filter, f), nil) -> nil 6.64/2.66 app(app(filter, f), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(f, x)), f), x), xs) 6.64/2.66 app(app(app(app(filter2, true), f), x), xs) -> app(app(cons, x), app(app(filter, f), xs)) 6.64/2.66 app(app(app(app(filter2, false), f), x), xs) -> app(app(filter, f), xs) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) 6.64/2.66 app(app(eq, 0), app(s, x0)) 6.64/2.66 app(app(eq, app(s, x0)), 0) 6.64/2.66 app(app(eq, app(s, x0)), app(s, x1)) 6.64/2.66 app(app(le, 0), x0) 6.64/2.66 app(app(le, app(s, x0)), 0) 6.64/2.66 app(app(le, app(s, x0)), app(s, x1)) 6.64/2.66 app(min, app(app(cons, 0), nil)) 6.64/2.66 app(min, app(app(cons, app(s, x0)), nil)) 6.64/2.66 app(min, app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, true), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, false), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(app(replace, x0), x1), nil) 6.64/2.66 app(app(app(replace, x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, true), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, false), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(sort, nil) 6.64/2.66 app(sort, app(app(cons, x0), x1)) 6.64/2.66 app(app(map, x0), nil) 6.64/2.66 app(app(map, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(filter, x0), nil) 6.64/2.66 app(app(filter, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(app(app(filter2, true), x0), x1), x2) 6.64/2.66 app(app(app(app(filter2, false), x0), x1), x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (6) UsableRulesProof (EQUIVALENT) 6.64/2.66 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. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (7) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 APP(app(le, app(s, n)), app(s, m)) -> APP(app(le, n), m) 6.64/2.66 6.64/2.66 R is empty. 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) 6.64/2.66 app(app(eq, 0), app(s, x0)) 6.64/2.66 app(app(eq, app(s, x0)), 0) 6.64/2.66 app(app(eq, app(s, x0)), app(s, x1)) 6.64/2.66 app(app(le, 0), x0) 6.64/2.66 app(app(le, app(s, x0)), 0) 6.64/2.66 app(app(le, app(s, x0)), app(s, x1)) 6.64/2.66 app(min, app(app(cons, 0), nil)) 6.64/2.66 app(min, app(app(cons, app(s, x0)), nil)) 6.64/2.66 app(min, app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, true), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, false), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(app(replace, x0), x1), nil) 6.64/2.66 app(app(app(replace, x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, true), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, false), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(sort, nil) 6.64/2.66 app(sort, app(app(cons, x0), x1)) 6.64/2.66 app(app(map, x0), nil) 6.64/2.66 app(app(map, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(filter, x0), nil) 6.64/2.66 app(app(filter, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(app(app(filter2, true), x0), x1), x2) 6.64/2.66 app(app(app(app(filter2, false), x0), x1), x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (8) ATransformationProof (EQUIVALENT) 6.64/2.66 We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (9) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 le1(s(n), s(m)) -> le1(n, m) 6.64/2.66 6.64/2.66 R is empty. 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 eq(0, 0) 6.64/2.66 eq(0, s(x0)) 6.64/2.66 eq(s(x0), 0) 6.64/2.66 eq(s(x0), s(x1)) 6.64/2.66 le(0, x0) 6.64/2.66 le(s(x0), 0) 6.64/2.66 le(s(x0), s(x1)) 6.64/2.66 min(cons(0, nil)) 6.64/2.66 min(cons(s(x0), nil)) 6.64/2.66 min(cons(x0, cons(x1, x2))) 6.64/2.66 if_min(true, cons(x0, cons(x1, x2))) 6.64/2.66 if_min(false, cons(x0, cons(x1, x2))) 6.64/2.66 replace(x0, x1, nil) 6.64/2.66 replace(x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(true, x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(false, x0, x1, cons(x2, x3)) 6.64/2.66 sort(nil) 6.64/2.66 sort(cons(x0, x1)) 6.64/2.66 map(x0, nil) 6.64/2.66 map(x0, cons(x1, x2)) 6.64/2.66 filter(x0, nil) 6.64/2.66 filter(x0, cons(x1, x2)) 6.64/2.66 filter2(true, x0, x1, x2) 6.64/2.66 filter2(false, x0, x1, x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (10) QReductionProof (EQUIVALENT) 6.64/2.66 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 6.64/2.66 6.64/2.66 eq(0, 0) 6.64/2.66 eq(0, s(x0)) 6.64/2.66 eq(s(x0), 0) 6.64/2.66 eq(s(x0), s(x1)) 6.64/2.66 le(0, x0) 6.64/2.66 le(s(x0), 0) 6.64/2.66 le(s(x0), s(x1)) 6.64/2.66 min(cons(0, nil)) 6.64/2.66 min(cons(s(x0), nil)) 6.64/2.66 min(cons(x0, cons(x1, x2))) 6.64/2.66 if_min(true, cons(x0, cons(x1, x2))) 6.64/2.66 if_min(false, cons(x0, cons(x1, x2))) 6.64/2.66 replace(x0, x1, nil) 6.64/2.66 replace(x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(true, x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(false, x0, x1, cons(x2, x3)) 6.64/2.66 sort(nil) 6.64/2.66 sort(cons(x0, x1)) 6.64/2.66 map(x0, nil) 6.64/2.66 map(x0, cons(x1, x2)) 6.64/2.66 filter(x0, nil) 6.64/2.66 filter(x0, cons(x1, x2)) 6.64/2.66 filter2(true, x0, x1, x2) 6.64/2.66 filter2(false, x0, x1, x2) 6.64/2.66 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (11) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 le1(s(n), s(m)) -> le1(n, m) 6.64/2.66 6.64/2.66 R is empty. 6.64/2.66 Q is empty. 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (12) QDPSizeChangeProof (EQUIVALENT) 6.64/2.66 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. 6.64/2.66 6.64/2.66 From the DPs we obtained the following set of size-change graphs: 6.64/2.66 *le1(s(n), s(m)) -> le1(n, m) 6.64/2.66 The graph contains the following edges 1 > 1, 2 > 2 6.64/2.66 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (13) 6.64/2.66 YES 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (14) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 APP(min, app(app(cons, n), app(app(cons, m), x))) -> APP(app(if_min, app(app(le, n), m)), app(app(cons, n), app(app(cons, m), x))) 6.64/2.66 APP(app(if_min, true), app(app(cons, n), app(app(cons, m), x))) -> APP(min, app(app(cons, n), x)) 6.64/2.66 APP(app(if_min, false), app(app(cons, n), app(app(cons, m), x))) -> APP(min, app(app(cons, m), x)) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) -> true 6.64/2.66 app(app(eq, 0), app(s, m)) -> false 6.64/2.66 app(app(eq, app(s, n)), 0) -> false 6.64/2.66 app(app(eq, app(s, n)), app(s, m)) -> app(app(eq, n), m) 6.64/2.66 app(app(le, 0), m) -> true 6.64/2.66 app(app(le, app(s, n)), 0) -> false 6.64/2.66 app(app(le, app(s, n)), app(s, m)) -> app(app(le, n), m) 6.64/2.66 app(min, app(app(cons, 0), nil)) -> 0 6.64/2.66 app(min, app(app(cons, app(s, n)), nil)) -> app(s, n) 6.64/2.66 app(min, app(app(cons, n), app(app(cons, m), x))) -> app(app(if_min, app(app(le, n), m)), app(app(cons, n), app(app(cons, m), x))) 6.64/2.66 app(app(if_min, true), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, n), x)) 6.64/2.66 app(app(if_min, false), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, m), x)) 6.64/2.66 app(app(app(replace, n), m), nil) -> nil 6.64/2.66 app(app(app(replace, n), m), app(app(cons, k), x)) -> app(app(app(app(if_replace, app(app(eq, n), k)), n), m), app(app(cons, k), x)) 6.64/2.66 app(app(app(app(if_replace, true), n), m), app(app(cons, k), x)) -> app(app(cons, m), x) 6.64/2.66 app(app(app(app(if_replace, false), n), m), app(app(cons, k), x)) -> app(app(cons, k), app(app(app(replace, n), m), x)) 6.64/2.66 app(sort, nil) -> nil 6.64/2.66 app(sort, app(app(cons, n), x)) -> app(app(cons, app(min, app(app(cons, n), x))), app(sort, app(app(app(replace, app(min, app(app(cons, n), x))), n), x))) 6.64/2.66 app(app(map, f), nil) -> nil 6.64/2.66 app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs)) 6.64/2.66 app(app(filter, f), nil) -> nil 6.64/2.66 app(app(filter, f), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(f, x)), f), x), xs) 6.64/2.66 app(app(app(app(filter2, true), f), x), xs) -> app(app(cons, x), app(app(filter, f), xs)) 6.64/2.66 app(app(app(app(filter2, false), f), x), xs) -> app(app(filter, f), xs) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) 6.64/2.66 app(app(eq, 0), app(s, x0)) 6.64/2.66 app(app(eq, app(s, x0)), 0) 6.64/2.66 app(app(eq, app(s, x0)), app(s, x1)) 6.64/2.66 app(app(le, 0), x0) 6.64/2.66 app(app(le, app(s, x0)), 0) 6.64/2.66 app(app(le, app(s, x0)), app(s, x1)) 6.64/2.66 app(min, app(app(cons, 0), nil)) 6.64/2.66 app(min, app(app(cons, app(s, x0)), nil)) 6.64/2.66 app(min, app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, true), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, false), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(app(replace, x0), x1), nil) 6.64/2.66 app(app(app(replace, x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, true), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, false), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(sort, nil) 6.64/2.66 app(sort, app(app(cons, x0), x1)) 6.64/2.66 app(app(map, x0), nil) 6.64/2.66 app(app(map, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(filter, x0), nil) 6.64/2.66 app(app(filter, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(app(app(filter2, true), x0), x1), x2) 6.64/2.66 app(app(app(app(filter2, false), x0), x1), x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (15) UsableRulesProof (EQUIVALENT) 6.64/2.66 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. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (16) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 APP(min, app(app(cons, n), app(app(cons, m), x))) -> APP(app(if_min, app(app(le, n), m)), app(app(cons, n), app(app(cons, m), x))) 6.64/2.66 APP(app(if_min, true), app(app(cons, n), app(app(cons, m), x))) -> APP(min, app(app(cons, n), x)) 6.64/2.66 APP(app(if_min, false), app(app(cons, n), app(app(cons, m), x))) -> APP(min, app(app(cons, m), x)) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 app(app(le, 0), m) -> true 6.64/2.66 app(app(le, app(s, n)), 0) -> false 6.64/2.66 app(app(le, app(s, n)), app(s, m)) -> app(app(le, n), m) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) 6.64/2.66 app(app(eq, 0), app(s, x0)) 6.64/2.66 app(app(eq, app(s, x0)), 0) 6.64/2.66 app(app(eq, app(s, x0)), app(s, x1)) 6.64/2.66 app(app(le, 0), x0) 6.64/2.66 app(app(le, app(s, x0)), 0) 6.64/2.66 app(app(le, app(s, x0)), app(s, x1)) 6.64/2.66 app(min, app(app(cons, 0), nil)) 6.64/2.66 app(min, app(app(cons, app(s, x0)), nil)) 6.64/2.66 app(min, app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, true), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, false), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(app(replace, x0), x1), nil) 6.64/2.66 app(app(app(replace, x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, true), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, false), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(sort, nil) 6.64/2.66 app(sort, app(app(cons, x0), x1)) 6.64/2.66 app(app(map, x0), nil) 6.64/2.66 app(app(map, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(filter, x0), nil) 6.64/2.66 app(app(filter, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(app(app(filter2, true), x0), x1), x2) 6.64/2.66 app(app(app(app(filter2, false), x0), x1), x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (17) ATransformationProof (EQUIVALENT) 6.64/2.66 We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (18) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 min1(cons(n, cons(m, x))) -> if_min1(le(n, m), cons(n, cons(m, x))) 6.64/2.66 if_min1(true, cons(n, cons(m, x))) -> min1(cons(n, x)) 6.64/2.66 if_min1(false, cons(n, cons(m, x))) -> min1(cons(m, x)) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 le(0, m) -> true 6.64/2.66 le(s(n), 0) -> false 6.64/2.66 le(s(n), s(m)) -> le(n, m) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 eq(0, 0) 6.64/2.66 eq(0, s(x0)) 6.64/2.66 eq(s(x0), 0) 6.64/2.66 eq(s(x0), s(x1)) 6.64/2.66 le(0, x0) 6.64/2.66 le(s(x0), 0) 6.64/2.66 le(s(x0), s(x1)) 6.64/2.66 min(cons(0, nil)) 6.64/2.66 min(cons(s(x0), nil)) 6.64/2.66 min(cons(x0, cons(x1, x2))) 6.64/2.66 if_min(true, cons(x0, cons(x1, x2))) 6.64/2.66 if_min(false, cons(x0, cons(x1, x2))) 6.64/2.66 replace(x0, x1, nil) 6.64/2.66 replace(x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(true, x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(false, x0, x1, cons(x2, x3)) 6.64/2.66 sort(nil) 6.64/2.66 sort(cons(x0, x1)) 6.64/2.66 map(x0, nil) 6.64/2.66 map(x0, cons(x1, x2)) 6.64/2.66 filter(x0, nil) 6.64/2.66 filter(x0, cons(x1, x2)) 6.64/2.66 filter2(true, x0, x1, x2) 6.64/2.66 filter2(false, x0, x1, x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (19) QReductionProof (EQUIVALENT) 6.64/2.66 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 6.64/2.66 6.64/2.66 eq(0, 0) 6.64/2.66 eq(0, s(x0)) 6.64/2.66 eq(s(x0), 0) 6.64/2.66 eq(s(x0), s(x1)) 6.64/2.66 min(cons(0, nil)) 6.64/2.66 min(cons(s(x0), nil)) 6.64/2.66 min(cons(x0, cons(x1, x2))) 6.64/2.66 if_min(true, cons(x0, cons(x1, x2))) 6.64/2.66 if_min(false, cons(x0, cons(x1, x2))) 6.64/2.66 replace(x0, x1, nil) 6.64/2.66 replace(x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(true, x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(false, x0, x1, cons(x2, x3)) 6.64/2.66 sort(nil) 6.64/2.66 sort(cons(x0, x1)) 6.64/2.66 map(x0, nil) 6.64/2.66 map(x0, cons(x1, x2)) 6.64/2.66 filter(x0, nil) 6.64/2.66 filter(x0, cons(x1, x2)) 6.64/2.66 filter2(true, x0, x1, x2) 6.64/2.66 filter2(false, x0, x1, x2) 6.64/2.66 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (20) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 min1(cons(n, cons(m, x))) -> if_min1(le(n, m), cons(n, cons(m, x))) 6.64/2.66 if_min1(true, cons(n, cons(m, x))) -> min1(cons(n, x)) 6.64/2.66 if_min1(false, cons(n, cons(m, x))) -> min1(cons(m, x)) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 le(0, m) -> true 6.64/2.66 le(s(n), 0) -> false 6.64/2.66 le(s(n), s(m)) -> le(n, m) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 le(0, x0) 6.64/2.66 le(s(x0), 0) 6.64/2.66 le(s(x0), s(x1)) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (21) QDPOrderProof (EQUIVALENT) 6.64/2.66 We use the reduction pair processor [LPAR04,JAR06]. 6.64/2.66 6.64/2.66 6.64/2.66 The following pairs can be oriented strictly and are deleted. 6.64/2.66 6.64/2.66 if_min1(true, cons(n, cons(m, x))) -> min1(cons(n, x)) 6.64/2.66 if_min1(false, cons(n, cons(m, x))) -> min1(cons(m, x)) 6.64/2.66 The remaining pairs can at least be oriented weakly. 6.64/2.66 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 6.64/2.66 6.64/2.66 POL( if_min1_2(x_1, x_2) ) = 2x_2 + 2 6.64/2.66 POL( le_2(x_1, x_2) ) = 0 6.64/2.66 POL( 0 ) = 0 6.64/2.66 POL( true ) = 2 6.64/2.66 POL( s_1(x_1) ) = 2x_1 + 2 6.64/2.66 POL( false ) = 2 6.64/2.66 POL( min1_1(x_1) ) = 2x_1 + 2 6.64/2.66 POL( cons_2(x_1, x_2) ) = 2x_2 + 2 6.64/2.66 6.64/2.66 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 6.64/2.66 none 6.64/2.66 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (22) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 min1(cons(n, cons(m, x))) -> if_min1(le(n, m), cons(n, cons(m, x))) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 le(0, m) -> true 6.64/2.66 le(s(n), 0) -> false 6.64/2.66 le(s(n), s(m)) -> le(n, m) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 le(0, x0) 6.64/2.66 le(s(x0), 0) 6.64/2.66 le(s(x0), s(x1)) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (23) DependencyGraphProof (EQUIVALENT) 6.64/2.66 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (24) 6.64/2.66 TRUE 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (25) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 APP(app(eq, app(s, n)), app(s, m)) -> APP(app(eq, n), m) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) -> true 6.64/2.66 app(app(eq, 0), app(s, m)) -> false 6.64/2.66 app(app(eq, app(s, n)), 0) -> false 6.64/2.66 app(app(eq, app(s, n)), app(s, m)) -> app(app(eq, n), m) 6.64/2.66 app(app(le, 0), m) -> true 6.64/2.66 app(app(le, app(s, n)), 0) -> false 6.64/2.66 app(app(le, app(s, n)), app(s, m)) -> app(app(le, n), m) 6.64/2.66 app(min, app(app(cons, 0), nil)) -> 0 6.64/2.66 app(min, app(app(cons, app(s, n)), nil)) -> app(s, n) 6.64/2.66 app(min, app(app(cons, n), app(app(cons, m), x))) -> app(app(if_min, app(app(le, n), m)), app(app(cons, n), app(app(cons, m), x))) 6.64/2.66 app(app(if_min, true), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, n), x)) 6.64/2.66 app(app(if_min, false), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, m), x)) 6.64/2.66 app(app(app(replace, n), m), nil) -> nil 6.64/2.66 app(app(app(replace, n), m), app(app(cons, k), x)) -> app(app(app(app(if_replace, app(app(eq, n), k)), n), m), app(app(cons, k), x)) 6.64/2.66 app(app(app(app(if_replace, true), n), m), app(app(cons, k), x)) -> app(app(cons, m), x) 6.64/2.66 app(app(app(app(if_replace, false), n), m), app(app(cons, k), x)) -> app(app(cons, k), app(app(app(replace, n), m), x)) 6.64/2.66 app(sort, nil) -> nil 6.64/2.66 app(sort, app(app(cons, n), x)) -> app(app(cons, app(min, app(app(cons, n), x))), app(sort, app(app(app(replace, app(min, app(app(cons, n), x))), n), x))) 6.64/2.66 app(app(map, f), nil) -> nil 6.64/2.66 app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs)) 6.64/2.66 app(app(filter, f), nil) -> nil 6.64/2.66 app(app(filter, f), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(f, x)), f), x), xs) 6.64/2.66 app(app(app(app(filter2, true), f), x), xs) -> app(app(cons, x), app(app(filter, f), xs)) 6.64/2.66 app(app(app(app(filter2, false), f), x), xs) -> app(app(filter, f), xs) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) 6.64/2.66 app(app(eq, 0), app(s, x0)) 6.64/2.66 app(app(eq, app(s, x0)), 0) 6.64/2.66 app(app(eq, app(s, x0)), app(s, x1)) 6.64/2.66 app(app(le, 0), x0) 6.64/2.66 app(app(le, app(s, x0)), 0) 6.64/2.66 app(app(le, app(s, x0)), app(s, x1)) 6.64/2.66 app(min, app(app(cons, 0), nil)) 6.64/2.66 app(min, app(app(cons, app(s, x0)), nil)) 6.64/2.66 app(min, app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, true), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, false), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(app(replace, x0), x1), nil) 6.64/2.66 app(app(app(replace, x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, true), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, false), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(sort, nil) 6.64/2.66 app(sort, app(app(cons, x0), x1)) 6.64/2.66 app(app(map, x0), nil) 6.64/2.66 app(app(map, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(filter, x0), nil) 6.64/2.66 app(app(filter, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(app(app(filter2, true), x0), x1), x2) 6.64/2.66 app(app(app(app(filter2, false), x0), x1), x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (26) UsableRulesProof (EQUIVALENT) 6.64/2.66 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. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (27) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 APP(app(eq, app(s, n)), app(s, m)) -> APP(app(eq, n), m) 6.64/2.66 6.64/2.66 R is empty. 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) 6.64/2.66 app(app(eq, 0), app(s, x0)) 6.64/2.66 app(app(eq, app(s, x0)), 0) 6.64/2.66 app(app(eq, app(s, x0)), app(s, x1)) 6.64/2.66 app(app(le, 0), x0) 6.64/2.66 app(app(le, app(s, x0)), 0) 6.64/2.66 app(app(le, app(s, x0)), app(s, x1)) 6.64/2.66 app(min, app(app(cons, 0), nil)) 6.64/2.66 app(min, app(app(cons, app(s, x0)), nil)) 6.64/2.66 app(min, app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, true), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, false), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(app(replace, x0), x1), nil) 6.64/2.66 app(app(app(replace, x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, true), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, false), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(sort, nil) 6.64/2.66 app(sort, app(app(cons, x0), x1)) 6.64/2.66 app(app(map, x0), nil) 6.64/2.66 app(app(map, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(filter, x0), nil) 6.64/2.66 app(app(filter, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(app(app(filter2, true), x0), x1), x2) 6.64/2.66 app(app(app(app(filter2, false), x0), x1), x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (28) ATransformationProof (EQUIVALENT) 6.64/2.66 We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (29) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 eq1(s(n), s(m)) -> eq1(n, m) 6.64/2.66 6.64/2.66 R is empty. 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 eq(0, 0) 6.64/2.66 eq(0, s(x0)) 6.64/2.66 eq(s(x0), 0) 6.64/2.66 eq(s(x0), s(x1)) 6.64/2.66 le(0, x0) 6.64/2.66 le(s(x0), 0) 6.64/2.66 le(s(x0), s(x1)) 6.64/2.66 min(cons(0, nil)) 6.64/2.66 min(cons(s(x0), nil)) 6.64/2.66 min(cons(x0, cons(x1, x2))) 6.64/2.66 if_min(true, cons(x0, cons(x1, x2))) 6.64/2.66 if_min(false, cons(x0, cons(x1, x2))) 6.64/2.66 replace(x0, x1, nil) 6.64/2.66 replace(x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(true, x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(false, x0, x1, cons(x2, x3)) 6.64/2.66 sort(nil) 6.64/2.66 sort(cons(x0, x1)) 6.64/2.66 map(x0, nil) 6.64/2.66 map(x0, cons(x1, x2)) 6.64/2.66 filter(x0, nil) 6.64/2.66 filter(x0, cons(x1, x2)) 6.64/2.66 filter2(true, x0, x1, x2) 6.64/2.66 filter2(false, x0, x1, x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (30) QReductionProof (EQUIVALENT) 6.64/2.66 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 6.64/2.66 6.64/2.66 eq(0, 0) 6.64/2.66 eq(0, s(x0)) 6.64/2.66 eq(s(x0), 0) 6.64/2.66 eq(s(x0), s(x1)) 6.64/2.66 le(0, x0) 6.64/2.66 le(s(x0), 0) 6.64/2.66 le(s(x0), s(x1)) 6.64/2.66 min(cons(0, nil)) 6.64/2.66 min(cons(s(x0), nil)) 6.64/2.66 min(cons(x0, cons(x1, x2))) 6.64/2.66 if_min(true, cons(x0, cons(x1, x2))) 6.64/2.66 if_min(false, cons(x0, cons(x1, x2))) 6.64/2.66 replace(x0, x1, nil) 6.64/2.66 replace(x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(true, x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(false, x0, x1, cons(x2, x3)) 6.64/2.66 sort(nil) 6.64/2.66 sort(cons(x0, x1)) 6.64/2.66 map(x0, nil) 6.64/2.66 map(x0, cons(x1, x2)) 6.64/2.66 filter(x0, nil) 6.64/2.66 filter(x0, cons(x1, x2)) 6.64/2.66 filter2(true, x0, x1, x2) 6.64/2.66 filter2(false, x0, x1, x2) 6.64/2.66 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (31) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 eq1(s(n), s(m)) -> eq1(n, m) 6.64/2.66 6.64/2.66 R is empty. 6.64/2.66 Q is empty. 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (32) QDPSizeChangeProof (EQUIVALENT) 6.64/2.66 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. 6.64/2.66 6.64/2.66 From the DPs we obtained the following set of size-change graphs: 6.64/2.66 *eq1(s(n), s(m)) -> eq1(n, m) 6.64/2.66 The graph contains the following edges 1 > 1, 2 > 2 6.64/2.66 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (33) 6.64/2.66 YES 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (34) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 APP(app(app(replace, n), m), app(app(cons, k), x)) -> APP(app(app(app(if_replace, app(app(eq, n), k)), n), m), app(app(cons, k), x)) 6.64/2.66 APP(app(app(app(if_replace, false), n), m), app(app(cons, k), x)) -> APP(app(app(replace, n), m), x) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) -> true 6.64/2.66 app(app(eq, 0), app(s, m)) -> false 6.64/2.66 app(app(eq, app(s, n)), 0) -> false 6.64/2.66 app(app(eq, app(s, n)), app(s, m)) -> app(app(eq, n), m) 6.64/2.66 app(app(le, 0), m) -> true 6.64/2.66 app(app(le, app(s, n)), 0) -> false 6.64/2.66 app(app(le, app(s, n)), app(s, m)) -> app(app(le, n), m) 6.64/2.66 app(min, app(app(cons, 0), nil)) -> 0 6.64/2.66 app(min, app(app(cons, app(s, n)), nil)) -> app(s, n) 6.64/2.66 app(min, app(app(cons, n), app(app(cons, m), x))) -> app(app(if_min, app(app(le, n), m)), app(app(cons, n), app(app(cons, m), x))) 6.64/2.66 app(app(if_min, true), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, n), x)) 6.64/2.66 app(app(if_min, false), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, m), x)) 6.64/2.66 app(app(app(replace, n), m), nil) -> nil 6.64/2.66 app(app(app(replace, n), m), app(app(cons, k), x)) -> app(app(app(app(if_replace, app(app(eq, n), k)), n), m), app(app(cons, k), x)) 6.64/2.66 app(app(app(app(if_replace, true), n), m), app(app(cons, k), x)) -> app(app(cons, m), x) 6.64/2.66 app(app(app(app(if_replace, false), n), m), app(app(cons, k), x)) -> app(app(cons, k), app(app(app(replace, n), m), x)) 6.64/2.66 app(sort, nil) -> nil 6.64/2.66 app(sort, app(app(cons, n), x)) -> app(app(cons, app(min, app(app(cons, n), x))), app(sort, app(app(app(replace, app(min, app(app(cons, n), x))), n), x))) 6.64/2.66 app(app(map, f), nil) -> nil 6.64/2.66 app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs)) 6.64/2.66 app(app(filter, f), nil) -> nil 6.64/2.66 app(app(filter, f), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(f, x)), f), x), xs) 6.64/2.66 app(app(app(app(filter2, true), f), x), xs) -> app(app(cons, x), app(app(filter, f), xs)) 6.64/2.66 app(app(app(app(filter2, false), f), x), xs) -> app(app(filter, f), xs) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) 6.64/2.66 app(app(eq, 0), app(s, x0)) 6.64/2.66 app(app(eq, app(s, x0)), 0) 6.64/2.66 app(app(eq, app(s, x0)), app(s, x1)) 6.64/2.66 app(app(le, 0), x0) 6.64/2.66 app(app(le, app(s, x0)), 0) 6.64/2.66 app(app(le, app(s, x0)), app(s, x1)) 6.64/2.66 app(min, app(app(cons, 0), nil)) 6.64/2.66 app(min, app(app(cons, app(s, x0)), nil)) 6.64/2.66 app(min, app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, true), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, false), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(app(replace, x0), x1), nil) 6.64/2.66 app(app(app(replace, x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, true), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, false), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(sort, nil) 6.64/2.66 app(sort, app(app(cons, x0), x1)) 6.64/2.66 app(app(map, x0), nil) 6.64/2.66 app(app(map, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(filter, x0), nil) 6.64/2.66 app(app(filter, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(app(app(filter2, true), x0), x1), x2) 6.64/2.66 app(app(app(app(filter2, false), x0), x1), x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (35) UsableRulesProof (EQUIVALENT) 6.64/2.66 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. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (36) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 APP(app(app(replace, n), m), app(app(cons, k), x)) -> APP(app(app(app(if_replace, app(app(eq, n), k)), n), m), app(app(cons, k), x)) 6.64/2.66 APP(app(app(app(if_replace, false), n), m), app(app(cons, k), x)) -> APP(app(app(replace, n), m), x) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) -> true 6.64/2.66 app(app(eq, 0), app(s, m)) -> false 6.64/2.66 app(app(eq, app(s, n)), 0) -> false 6.64/2.66 app(app(eq, app(s, n)), app(s, m)) -> app(app(eq, n), m) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) 6.64/2.66 app(app(eq, 0), app(s, x0)) 6.64/2.66 app(app(eq, app(s, x0)), 0) 6.64/2.66 app(app(eq, app(s, x0)), app(s, x1)) 6.64/2.66 app(app(le, 0), x0) 6.64/2.66 app(app(le, app(s, x0)), 0) 6.64/2.66 app(app(le, app(s, x0)), app(s, x1)) 6.64/2.66 app(min, app(app(cons, 0), nil)) 6.64/2.66 app(min, app(app(cons, app(s, x0)), nil)) 6.64/2.66 app(min, app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, true), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, false), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(app(replace, x0), x1), nil) 6.64/2.66 app(app(app(replace, x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, true), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, false), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(sort, nil) 6.64/2.66 app(sort, app(app(cons, x0), x1)) 6.64/2.66 app(app(map, x0), nil) 6.64/2.66 app(app(map, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(filter, x0), nil) 6.64/2.66 app(app(filter, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(app(app(filter2, true), x0), x1), x2) 6.64/2.66 app(app(app(app(filter2, false), x0), x1), x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (37) ATransformationProof (EQUIVALENT) 6.64/2.66 We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (38) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 replace1(n, m, cons(k, x)) -> if_replace1(eq(n, k), n, m, cons(k, x)) 6.64/2.66 if_replace1(false, n, m, cons(k, x)) -> replace1(n, m, x) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 eq(0, 0) -> true 6.64/2.66 eq(0, s(m)) -> false 6.64/2.66 eq(s(n), 0) -> false 6.64/2.66 eq(s(n), s(m)) -> eq(n, m) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 eq(0, 0) 6.64/2.66 eq(0, s(x0)) 6.64/2.66 eq(s(x0), 0) 6.64/2.66 eq(s(x0), s(x1)) 6.64/2.66 le(0, x0) 6.64/2.66 le(s(x0), 0) 6.64/2.66 le(s(x0), s(x1)) 6.64/2.66 min(cons(0, nil)) 6.64/2.66 min(cons(s(x0), nil)) 6.64/2.66 min(cons(x0, cons(x1, x2))) 6.64/2.66 if_min(true, cons(x0, cons(x1, x2))) 6.64/2.66 if_min(false, cons(x0, cons(x1, x2))) 6.64/2.66 replace(x0, x1, nil) 6.64/2.66 replace(x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(true, x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(false, x0, x1, cons(x2, x3)) 6.64/2.66 sort(nil) 6.64/2.66 sort(cons(x0, x1)) 6.64/2.66 map(x0, nil) 6.64/2.66 map(x0, cons(x1, x2)) 6.64/2.66 filter(x0, nil) 6.64/2.66 filter(x0, cons(x1, x2)) 6.64/2.66 filter2(true, x0, x1, x2) 6.64/2.66 filter2(false, x0, x1, x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (39) QReductionProof (EQUIVALENT) 6.64/2.66 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 6.64/2.66 6.64/2.66 le(0, x0) 6.64/2.66 le(s(x0), 0) 6.64/2.66 le(s(x0), s(x1)) 6.64/2.66 min(cons(0, nil)) 6.64/2.66 min(cons(s(x0), nil)) 6.64/2.66 min(cons(x0, cons(x1, x2))) 6.64/2.66 if_min(true, cons(x0, cons(x1, x2))) 6.64/2.66 if_min(false, cons(x0, cons(x1, x2))) 6.64/2.66 replace(x0, x1, nil) 6.64/2.66 replace(x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(true, x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(false, x0, x1, cons(x2, x3)) 6.64/2.66 sort(nil) 6.64/2.66 sort(cons(x0, x1)) 6.64/2.66 map(x0, nil) 6.64/2.66 map(x0, cons(x1, x2)) 6.64/2.66 filter(x0, nil) 6.64/2.66 filter(x0, cons(x1, x2)) 6.64/2.66 filter2(true, x0, x1, x2) 6.64/2.66 filter2(false, x0, x1, x2) 6.64/2.66 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (40) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 replace1(n, m, cons(k, x)) -> if_replace1(eq(n, k), n, m, cons(k, x)) 6.64/2.66 if_replace1(false, n, m, cons(k, x)) -> replace1(n, m, x) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 eq(0, 0) -> true 6.64/2.66 eq(0, s(m)) -> false 6.64/2.66 eq(s(n), 0) -> false 6.64/2.66 eq(s(n), s(m)) -> eq(n, m) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 eq(0, 0) 6.64/2.66 eq(0, s(x0)) 6.64/2.66 eq(s(x0), 0) 6.64/2.66 eq(s(x0), s(x1)) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (41) QDPSizeChangeProof (EQUIVALENT) 6.64/2.66 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. 6.64/2.66 6.64/2.66 From the DPs we obtained the following set of size-change graphs: 6.64/2.66 *if_replace1(false, n, m, cons(k, x)) -> replace1(n, m, x) 6.64/2.66 The graph contains the following edges 2 >= 1, 3 >= 2, 4 > 3 6.64/2.66 6.64/2.66 6.64/2.66 *replace1(n, m, cons(k, x)) -> if_replace1(eq(n, k), n, m, cons(k, x)) 6.64/2.66 The graph contains the following edges 1 >= 2, 2 >= 3, 3 >= 4 6.64/2.66 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (42) 6.64/2.66 YES 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (43) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 APP(sort, app(app(cons, n), x)) -> APP(sort, app(app(app(replace, app(min, app(app(cons, n), x))), n), x)) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) -> true 6.64/2.66 app(app(eq, 0), app(s, m)) -> false 6.64/2.66 app(app(eq, app(s, n)), 0) -> false 6.64/2.66 app(app(eq, app(s, n)), app(s, m)) -> app(app(eq, n), m) 6.64/2.66 app(app(le, 0), m) -> true 6.64/2.66 app(app(le, app(s, n)), 0) -> false 6.64/2.66 app(app(le, app(s, n)), app(s, m)) -> app(app(le, n), m) 6.64/2.66 app(min, app(app(cons, 0), nil)) -> 0 6.64/2.66 app(min, app(app(cons, app(s, n)), nil)) -> app(s, n) 6.64/2.66 app(min, app(app(cons, n), app(app(cons, m), x))) -> app(app(if_min, app(app(le, n), m)), app(app(cons, n), app(app(cons, m), x))) 6.64/2.66 app(app(if_min, true), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, n), x)) 6.64/2.66 app(app(if_min, false), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, m), x)) 6.64/2.66 app(app(app(replace, n), m), nil) -> nil 6.64/2.66 app(app(app(replace, n), m), app(app(cons, k), x)) -> app(app(app(app(if_replace, app(app(eq, n), k)), n), m), app(app(cons, k), x)) 6.64/2.66 app(app(app(app(if_replace, true), n), m), app(app(cons, k), x)) -> app(app(cons, m), x) 6.64/2.66 app(app(app(app(if_replace, false), n), m), app(app(cons, k), x)) -> app(app(cons, k), app(app(app(replace, n), m), x)) 6.64/2.66 app(sort, nil) -> nil 6.64/2.66 app(sort, app(app(cons, n), x)) -> app(app(cons, app(min, app(app(cons, n), x))), app(sort, app(app(app(replace, app(min, app(app(cons, n), x))), n), x))) 6.64/2.66 app(app(map, f), nil) -> nil 6.64/2.66 app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs)) 6.64/2.66 app(app(filter, f), nil) -> nil 6.64/2.66 app(app(filter, f), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(f, x)), f), x), xs) 6.64/2.66 app(app(app(app(filter2, true), f), x), xs) -> app(app(cons, x), app(app(filter, f), xs)) 6.64/2.66 app(app(app(app(filter2, false), f), x), xs) -> app(app(filter, f), xs) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) 6.64/2.66 app(app(eq, 0), app(s, x0)) 6.64/2.66 app(app(eq, app(s, x0)), 0) 6.64/2.66 app(app(eq, app(s, x0)), app(s, x1)) 6.64/2.66 app(app(le, 0), x0) 6.64/2.66 app(app(le, app(s, x0)), 0) 6.64/2.66 app(app(le, app(s, x0)), app(s, x1)) 6.64/2.66 app(min, app(app(cons, 0), nil)) 6.64/2.66 app(min, app(app(cons, app(s, x0)), nil)) 6.64/2.66 app(min, app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, true), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, false), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(app(replace, x0), x1), nil) 6.64/2.66 app(app(app(replace, x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, true), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, false), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(sort, nil) 6.64/2.66 app(sort, app(app(cons, x0), x1)) 6.64/2.66 app(app(map, x0), nil) 6.64/2.66 app(app(map, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(filter, x0), nil) 6.64/2.66 app(app(filter, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(app(app(filter2, true), x0), x1), x2) 6.64/2.66 app(app(app(app(filter2, false), x0), x1), x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (44) UsableRulesProof (EQUIVALENT) 6.64/2.66 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. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (45) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 APP(sort, app(app(cons, n), x)) -> APP(sort, app(app(app(replace, app(min, app(app(cons, n), x))), n), x)) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 app(min, app(app(cons, 0), nil)) -> 0 6.64/2.66 app(min, app(app(cons, app(s, n)), nil)) -> app(s, n) 6.64/2.66 app(min, app(app(cons, n), app(app(cons, m), x))) -> app(app(if_min, app(app(le, n), m)), app(app(cons, n), app(app(cons, m), x))) 6.64/2.66 app(app(if_min, true), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, n), x)) 6.64/2.66 app(app(if_min, false), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, m), x)) 6.64/2.66 app(app(app(replace, n), m), nil) -> nil 6.64/2.66 app(app(app(replace, n), m), app(app(cons, k), x)) -> app(app(app(app(if_replace, app(app(eq, n), k)), n), m), app(app(cons, k), x)) 6.64/2.66 app(app(eq, 0), 0) -> true 6.64/2.66 app(app(eq, 0), app(s, m)) -> false 6.64/2.66 app(app(eq, app(s, n)), 0) -> false 6.64/2.66 app(app(eq, app(s, n)), app(s, m)) -> app(app(eq, n), m) 6.64/2.66 app(app(app(app(if_replace, true), n), m), app(app(cons, k), x)) -> app(app(cons, m), x) 6.64/2.66 app(app(app(app(if_replace, false), n), m), app(app(cons, k), x)) -> app(app(cons, k), app(app(app(replace, n), m), x)) 6.64/2.66 app(app(le, 0), m) -> true 6.64/2.66 app(app(le, app(s, n)), 0) -> false 6.64/2.66 app(app(le, app(s, n)), app(s, m)) -> app(app(le, n), m) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) 6.64/2.66 app(app(eq, 0), app(s, x0)) 6.64/2.66 app(app(eq, app(s, x0)), 0) 6.64/2.66 app(app(eq, app(s, x0)), app(s, x1)) 6.64/2.66 app(app(le, 0), x0) 6.64/2.66 app(app(le, app(s, x0)), 0) 6.64/2.66 app(app(le, app(s, x0)), app(s, x1)) 6.64/2.66 app(min, app(app(cons, 0), nil)) 6.64/2.66 app(min, app(app(cons, app(s, x0)), nil)) 6.64/2.66 app(min, app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, true), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, false), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(app(replace, x0), x1), nil) 6.64/2.66 app(app(app(replace, x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, true), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, false), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(sort, nil) 6.64/2.66 app(sort, app(app(cons, x0), x1)) 6.64/2.66 app(app(map, x0), nil) 6.64/2.66 app(app(map, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(filter, x0), nil) 6.64/2.66 app(app(filter, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(app(app(filter2, true), x0), x1), x2) 6.64/2.66 app(app(app(app(filter2, false), x0), x1), x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (46) ATransformationProof (EQUIVALENT) 6.64/2.66 We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (47) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 sort1(cons(n, x)) -> sort1(replace(min(cons(n, x)), n, x)) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 min(cons(0, nil)) -> 0 6.64/2.66 min(cons(s(n), nil)) -> s(n) 6.64/2.66 min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) 6.64/2.66 if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) 6.64/2.66 if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) 6.64/2.66 replace(n, m, nil) -> nil 6.64/2.66 replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) 6.64/2.66 eq(0, 0) -> true 6.64/2.66 eq(0, s(m)) -> false 6.64/2.66 eq(s(n), 0) -> false 6.64/2.66 eq(s(n), s(m)) -> eq(n, m) 6.64/2.66 if_replace(true, n, m, cons(k, x)) -> cons(m, x) 6.64/2.66 if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) 6.64/2.66 le(0, m) -> true 6.64/2.66 le(s(n), 0) -> false 6.64/2.66 le(s(n), s(m)) -> le(n, m) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 eq(0, 0) 6.64/2.66 eq(0, s(x0)) 6.64/2.66 eq(s(x0), 0) 6.64/2.66 eq(s(x0), s(x1)) 6.64/2.66 le(0, x0) 6.64/2.66 le(s(x0), 0) 6.64/2.66 le(s(x0), s(x1)) 6.64/2.66 min(cons(0, nil)) 6.64/2.66 min(cons(s(x0), nil)) 6.64/2.66 min(cons(x0, cons(x1, x2))) 6.64/2.66 if_min(true, cons(x0, cons(x1, x2))) 6.64/2.66 if_min(false, cons(x0, cons(x1, x2))) 6.64/2.66 replace(x0, x1, nil) 6.64/2.66 replace(x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(true, x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(false, x0, x1, cons(x2, x3)) 6.64/2.66 sort(nil) 6.64/2.66 sort(cons(x0, x1)) 6.64/2.66 map(x0, nil) 6.64/2.66 map(x0, cons(x1, x2)) 6.64/2.66 filter(x0, nil) 6.64/2.66 filter(x0, cons(x1, x2)) 6.64/2.66 filter2(true, x0, x1, x2) 6.64/2.66 filter2(false, x0, x1, x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (48) QReductionProof (EQUIVALENT) 6.64/2.66 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 6.64/2.66 6.64/2.66 sort(nil) 6.64/2.66 sort(cons(x0, x1)) 6.64/2.66 map(x0, nil) 6.64/2.66 map(x0, cons(x1, x2)) 6.64/2.66 filter(x0, nil) 6.64/2.66 filter(x0, cons(x1, x2)) 6.64/2.66 filter2(true, x0, x1, x2) 6.64/2.66 filter2(false, x0, x1, x2) 6.64/2.66 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (49) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 sort1(cons(n, x)) -> sort1(replace(min(cons(n, x)), n, x)) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 min(cons(0, nil)) -> 0 6.64/2.66 min(cons(s(n), nil)) -> s(n) 6.64/2.66 min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) 6.64/2.66 if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) 6.64/2.66 if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) 6.64/2.66 replace(n, m, nil) -> nil 6.64/2.66 replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) 6.64/2.66 eq(0, 0) -> true 6.64/2.66 eq(0, s(m)) -> false 6.64/2.66 eq(s(n), 0) -> false 6.64/2.66 eq(s(n), s(m)) -> eq(n, m) 6.64/2.66 if_replace(true, n, m, cons(k, x)) -> cons(m, x) 6.64/2.66 if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) 6.64/2.66 le(0, m) -> true 6.64/2.66 le(s(n), 0) -> false 6.64/2.66 le(s(n), s(m)) -> le(n, m) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 eq(0, 0) 6.64/2.66 eq(0, s(x0)) 6.64/2.66 eq(s(x0), 0) 6.64/2.66 eq(s(x0), s(x1)) 6.64/2.66 le(0, x0) 6.64/2.66 le(s(x0), 0) 6.64/2.66 le(s(x0), s(x1)) 6.64/2.66 min(cons(0, nil)) 6.64/2.66 min(cons(s(x0), nil)) 6.64/2.66 min(cons(x0, cons(x1, x2))) 6.64/2.66 if_min(true, cons(x0, cons(x1, x2))) 6.64/2.66 if_min(false, cons(x0, cons(x1, x2))) 6.64/2.66 replace(x0, x1, nil) 6.64/2.66 replace(x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(true, x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(false, x0, x1, cons(x2, x3)) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (50) QDPOrderProof (EQUIVALENT) 6.64/2.66 We use the reduction pair processor [LPAR04,JAR06]. 6.64/2.66 6.64/2.66 6.64/2.66 The following pairs can be oriented strictly and are deleted. 6.64/2.66 6.64/2.66 sort1(cons(n, x)) -> sort1(replace(min(cons(n, x)), n, x)) 6.64/2.66 The remaining pairs can at least be oriented weakly. 6.64/2.66 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 6.64/2.66 6.64/2.66 POL( replace_3(x_1, ..., x_3) ) = max{0, 2x_3 - 2} 6.64/2.66 POL( sort1_1(x_1) ) = max{0, x_1 - 1} 6.64/2.66 POL( min_1(x_1) ) = max{0, -2} 6.64/2.66 POL( cons_2(x_1, x_2) ) = 2x_2 + 2 6.64/2.66 POL( 0 ) = 2 6.64/2.66 POL( nil ) = 0 6.64/2.66 POL( s_1(x_1) ) = 2 6.64/2.66 POL( if_min_2(x_1, x_2) ) = 2x_1 6.64/2.66 POL( le_2(x_1, x_2) ) = 0 6.64/2.66 POL( true ) = 1 6.64/2.66 POL( false ) = 0 6.64/2.66 POL( if_replace_4(x_1, ..., x_4) ) = max{0, 2x_4 - 2} 6.64/2.66 POL( eq_2(x_1, x_2) ) = 0 6.64/2.66 6.64/2.66 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 6.64/2.66 6.64/2.66 replace(n, m, nil) -> nil 6.64/2.66 replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) 6.64/2.66 if_replace(true, n, m, cons(k, x)) -> cons(m, x) 6.64/2.66 if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) 6.64/2.66 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (51) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 P is empty. 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 min(cons(0, nil)) -> 0 6.64/2.66 min(cons(s(n), nil)) -> s(n) 6.64/2.66 min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) 6.64/2.66 if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) 6.64/2.66 if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) 6.64/2.66 replace(n, m, nil) -> nil 6.64/2.66 replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) 6.64/2.66 eq(0, 0) -> true 6.64/2.66 eq(0, s(m)) -> false 6.64/2.66 eq(s(n), 0) -> false 6.64/2.66 eq(s(n), s(m)) -> eq(n, m) 6.64/2.66 if_replace(true, n, m, cons(k, x)) -> cons(m, x) 6.64/2.66 if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) 6.64/2.66 le(0, m) -> true 6.64/2.66 le(s(n), 0) -> false 6.64/2.66 le(s(n), s(m)) -> le(n, m) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 eq(0, 0) 6.64/2.66 eq(0, s(x0)) 6.64/2.66 eq(s(x0), 0) 6.64/2.66 eq(s(x0), s(x1)) 6.64/2.66 le(0, x0) 6.64/2.66 le(s(x0), 0) 6.64/2.66 le(s(x0), s(x1)) 6.64/2.66 min(cons(0, nil)) 6.64/2.66 min(cons(s(x0), nil)) 6.64/2.66 min(cons(x0, cons(x1, x2))) 6.64/2.66 if_min(true, cons(x0, cons(x1, x2))) 6.64/2.66 if_min(false, cons(x0, cons(x1, x2))) 6.64/2.66 replace(x0, x1, nil) 6.64/2.66 replace(x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(true, x0, x1, cons(x2, x3)) 6.64/2.66 if_replace(false, x0, x1, cons(x2, x3)) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (52) PisEmptyProof (EQUIVALENT) 6.64/2.66 The TRS P is empty. Hence, there is no (P,Q,R) chain. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (53) 6.64/2.66 YES 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (54) 6.64/2.66 Obligation: 6.64/2.66 Q DP problem: 6.64/2.66 The TRS P consists of the following rules: 6.64/2.66 6.64/2.66 APP(app(map, f), app(app(cons, x), xs)) -> APP(app(map, f), xs) 6.64/2.66 APP(app(map, f), app(app(cons, x), xs)) -> APP(f, x) 6.64/2.66 APP(app(filter, f), app(app(cons, x), xs)) -> APP(app(app(app(filter2, app(f, x)), f), x), xs) 6.64/2.66 APP(app(app(app(filter2, true), f), x), xs) -> APP(app(filter, f), xs) 6.64/2.66 APP(app(filter, f), app(app(cons, x), xs)) -> APP(f, x) 6.64/2.66 APP(app(app(app(filter2, false), f), x), xs) -> APP(app(filter, f), xs) 6.64/2.66 6.64/2.66 The TRS R consists of the following rules: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) -> true 6.64/2.66 app(app(eq, 0), app(s, m)) -> false 6.64/2.66 app(app(eq, app(s, n)), 0) -> false 6.64/2.66 app(app(eq, app(s, n)), app(s, m)) -> app(app(eq, n), m) 6.64/2.66 app(app(le, 0), m) -> true 6.64/2.66 app(app(le, app(s, n)), 0) -> false 6.64/2.66 app(app(le, app(s, n)), app(s, m)) -> app(app(le, n), m) 6.64/2.66 app(min, app(app(cons, 0), nil)) -> 0 6.64/2.66 app(min, app(app(cons, app(s, n)), nil)) -> app(s, n) 6.64/2.66 app(min, app(app(cons, n), app(app(cons, m), x))) -> app(app(if_min, app(app(le, n), m)), app(app(cons, n), app(app(cons, m), x))) 6.64/2.66 app(app(if_min, true), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, n), x)) 6.64/2.66 app(app(if_min, false), app(app(cons, n), app(app(cons, m), x))) -> app(min, app(app(cons, m), x)) 6.64/2.66 app(app(app(replace, n), m), nil) -> nil 6.64/2.66 app(app(app(replace, n), m), app(app(cons, k), x)) -> app(app(app(app(if_replace, app(app(eq, n), k)), n), m), app(app(cons, k), x)) 6.64/2.66 app(app(app(app(if_replace, true), n), m), app(app(cons, k), x)) -> app(app(cons, m), x) 6.64/2.66 app(app(app(app(if_replace, false), n), m), app(app(cons, k), x)) -> app(app(cons, k), app(app(app(replace, n), m), x)) 6.64/2.66 app(sort, nil) -> nil 6.64/2.66 app(sort, app(app(cons, n), x)) -> app(app(cons, app(min, app(app(cons, n), x))), app(sort, app(app(app(replace, app(min, app(app(cons, n), x))), n), x))) 6.64/2.66 app(app(map, f), nil) -> nil 6.64/2.66 app(app(map, f), app(app(cons, x), xs)) -> app(app(cons, app(f, x)), app(app(map, f), xs)) 6.64/2.66 app(app(filter, f), nil) -> nil 6.64/2.66 app(app(filter, f), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(f, x)), f), x), xs) 6.64/2.66 app(app(app(app(filter2, true), f), x), xs) -> app(app(cons, x), app(app(filter, f), xs)) 6.64/2.66 app(app(app(app(filter2, false), f), x), xs) -> app(app(filter, f), xs) 6.64/2.66 6.64/2.66 The set Q consists of the following terms: 6.64/2.66 6.64/2.66 app(app(eq, 0), 0) 6.64/2.66 app(app(eq, 0), app(s, x0)) 6.64/2.66 app(app(eq, app(s, x0)), 0) 6.64/2.66 app(app(eq, app(s, x0)), app(s, x1)) 6.64/2.66 app(app(le, 0), x0) 6.64/2.66 app(app(le, app(s, x0)), 0) 6.64/2.66 app(app(le, app(s, x0)), app(s, x1)) 6.64/2.66 app(min, app(app(cons, 0), nil)) 6.64/2.66 app(min, app(app(cons, app(s, x0)), nil)) 6.64/2.66 app(min, app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, true), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(if_min, false), app(app(cons, x0), app(app(cons, x1), x2))) 6.64/2.66 app(app(app(replace, x0), x1), nil) 6.64/2.66 app(app(app(replace, x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, true), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(app(app(app(if_replace, false), x0), x1), app(app(cons, x2), x3)) 6.64/2.66 app(sort, nil) 6.64/2.66 app(sort, app(app(cons, x0), x1)) 6.64/2.66 app(app(map, x0), nil) 6.64/2.66 app(app(map, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(filter, x0), nil) 6.64/2.66 app(app(filter, x0), app(app(cons, x1), x2)) 6.64/2.66 app(app(app(app(filter2, true), x0), x1), x2) 6.64/2.66 app(app(app(app(filter2, false), x0), x1), x2) 6.64/2.66 6.64/2.66 We have to consider all minimal (P,Q,R)-chains. 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (55) QDPSizeChangeProof (EQUIVALENT) 6.64/2.66 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. 6.64/2.66 6.64/2.66 From the DPs we obtained the following set of size-change graphs: 6.64/2.66 *APP(app(filter, f), app(app(cons, x), xs)) -> APP(f, x) 6.64/2.66 The graph contains the following edges 1 > 1, 2 > 2 6.64/2.66 6.64/2.66 6.64/2.66 *APP(app(map, f), app(app(cons, x), xs)) -> APP(f, x) 6.64/2.66 The graph contains the following edges 1 > 1, 2 > 2 6.64/2.66 6.64/2.66 6.64/2.66 *APP(app(map, f), app(app(cons, x), xs)) -> APP(app(map, f), xs) 6.64/2.66 The graph contains the following edges 1 >= 1, 2 > 2 6.64/2.66 6.64/2.66 6.64/2.66 *APP(app(filter, f), app(app(cons, x), xs)) -> APP(app(app(app(filter2, app(f, x)), f), x), xs) 6.64/2.66 The graph contains the following edges 2 > 2 6.64/2.66 6.64/2.66 6.64/2.66 *APP(app(app(app(filter2, true), f), x), xs) -> APP(app(filter, f), xs) 6.64/2.66 The graph contains the following edges 2 >= 2 6.64/2.66 6.64/2.66 6.64/2.66 *APP(app(app(app(filter2, false), f), x), xs) -> APP(app(filter, f), xs) 6.64/2.66 The graph contains the following edges 2 >= 2 6.64/2.66 6.64/2.66 6.64/2.66 ---------------------------------------- 6.64/2.66 6.64/2.66 (56) 6.64/2.66 YES 6.71/2.69 EOF