5.85/2.55 YES 5.85/2.57 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 5.85/2.57 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.85/2.57 5.85/2.57 5.85/2.57 Termination of the given ETRS could be proven: 5.85/2.57 5.85/2.57 (0) ETRS 5.85/2.57 (1) EquationalDependencyPairsProof [EQUIVALENT, 0 ms] 5.85/2.57 (2) EDP 5.85/2.57 (3) EDependencyGraphProof [EQUIVALENT, 0 ms] 5.85/2.57 (4) AND 5.85/2.57 (5) EDP 5.85/2.57 (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 5.85/2.57 (7) EDP 5.85/2.57 (8) EUsableRulesReductionPairsProof [EQUIVALENT, 9 ms] 5.85/2.57 (9) EDP 5.85/2.57 (10) PisEmptyProof [EQUIVALENT, 0 ms] 5.85/2.57 (11) YES 5.85/2.57 (12) EDP 5.85/2.57 (13) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 5.85/2.57 (14) EDP 5.85/2.57 (15) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 5.85/2.57 (16) EDP 5.85/2.57 (17) PisEmptyProof [EQUIVALENT, 0 ms] 5.85/2.57 (18) YES 5.85/2.57 (19) EDP 5.85/2.57 (20) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 5.85/2.57 (21) EDP 5.85/2.57 (22) EDPPoloProof [EQUIVALENT, 0 ms] 5.85/2.57 (23) EDP 5.85/2.57 (24) PisEmptyProof [EQUIVALENT, 0 ms] 5.85/2.57 (25) YES 5.85/2.57 (26) EDP 5.85/2.57 (27) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 5.85/2.57 (28) EDP 5.85/2.57 (29) PisEmptyProof [EQUIVALENT, 0 ms] 5.85/2.57 (30) YES 5.85/2.57 (31) EDP 5.85/2.57 (32) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 5.85/2.57 (33) EDP 5.85/2.57 (34) EDPPoloProof [EQUIVALENT, 0 ms] 5.85/2.57 (35) EDP 5.85/2.57 (36) PisEmptyProof [EQUIVALENT, 0 ms] 5.85/2.57 (37) YES 5.85/2.57 (38) EDP 5.85/2.57 (39) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 5.85/2.57 (40) EDP 5.85/2.57 (41) EDPPoloProof [EQUIVALENT, 0 ms] 5.85/2.57 (42) EDP 5.85/2.57 (43) EDPPoloProof [EQUIVALENT, 15 ms] 5.85/2.57 (44) EDP 5.85/2.57 (45) EDependencyGraphProof [EQUIVALENT, 0 ms] 5.85/2.57 (46) TRUE 5.85/2.57 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (0) 5.85/2.57 Obligation: 5.85/2.57 Equational rewrite system: 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (1) EquationalDependencyPairsProof (EQUIVALENT) 5.85/2.57 Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: 5.85/2.57 The TRS P consists of the following rules: 5.85/2.57 5.85/2.57 EQ(s(x), s(y)) -> EQ(x, y) 5.85/2.57 LE(s(x), s(y)) -> LE(x, y) 5.85/2.57 APP(add(n, x), y) -> APP(x, y) 5.85/2.57 MIN(add(n, add(m, x))) -> IF_MIN(le(n, m), add(n, add(m, x))) 5.85/2.57 MIN(add(n, add(m, x))) -> LE(n, m) 5.85/2.57 IF_MIN(true, add(n, add(m, x))) -> MIN(add(n, x)) 5.85/2.57 IF_MIN(false, add(n, add(m, x))) -> MIN(add(m, x)) 5.85/2.57 RM(n, add(m, x)) -> IF_RM(eq(n, m), n, add(m, x)) 5.85/2.57 RM(n, add(m, x)) -> EQ(n, m) 5.85/2.57 IF_RM(true, n, add(m, x)) -> RM(n, x) 5.85/2.57 IF_RM(false, n, add(m, x)) -> RM(n, x) 5.85/2.57 MINSORT(add(n, x), y) -> IF_MINSORT(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 MINSORT(add(n, x), y) -> EQ(n, min(add(n, x))) 5.85/2.57 MINSORT(add(n, x), y) -> MIN(add(n, x)) 5.85/2.57 IF_MINSORT(true, add(n, x), y) -> MINSORT(app(rm(n, x), y), nil) 5.85/2.57 IF_MINSORT(true, add(n, x), y) -> APP(rm(n, x), y) 5.85/2.57 IF_MINSORT(true, add(n, x), y) -> RM(n, x) 5.85/2.57 IF_MINSORT(false, add(n, x), y) -> MINSORT(x, add(n, y)) 5.85/2.57 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 The set E# consists of the following equations: 5.85/2.57 5.85/2.57 EQ(x, y) == EQ(y, x) 5.85/2.57 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (2) 5.85/2.57 Obligation: 5.85/2.57 The TRS P consists of the following rules: 5.85/2.57 5.85/2.57 EQ(s(x), s(y)) -> EQ(x, y) 5.85/2.57 LE(s(x), s(y)) -> LE(x, y) 5.85/2.57 APP(add(n, x), y) -> APP(x, y) 5.85/2.57 MIN(add(n, add(m, x))) -> IF_MIN(le(n, m), add(n, add(m, x))) 5.85/2.57 MIN(add(n, add(m, x))) -> LE(n, m) 5.85/2.57 IF_MIN(true, add(n, add(m, x))) -> MIN(add(n, x)) 5.85/2.57 IF_MIN(false, add(n, add(m, x))) -> MIN(add(m, x)) 5.85/2.57 RM(n, add(m, x)) -> IF_RM(eq(n, m), n, add(m, x)) 5.85/2.57 RM(n, add(m, x)) -> EQ(n, m) 5.85/2.57 IF_RM(true, n, add(m, x)) -> RM(n, x) 5.85/2.57 IF_RM(false, n, add(m, x)) -> RM(n, x) 5.85/2.57 MINSORT(add(n, x), y) -> IF_MINSORT(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 MINSORT(add(n, x), y) -> EQ(n, min(add(n, x))) 5.85/2.57 MINSORT(add(n, x), y) -> MIN(add(n, x)) 5.85/2.57 IF_MINSORT(true, add(n, x), y) -> MINSORT(app(rm(n, x), y), nil) 5.85/2.57 IF_MINSORT(true, add(n, x), y) -> APP(rm(n, x), y) 5.85/2.57 IF_MINSORT(true, add(n, x), y) -> RM(n, x) 5.85/2.57 IF_MINSORT(false, add(n, x), y) -> MINSORT(x, add(n, y)) 5.85/2.57 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 The set E# consists of the following equations: 5.85/2.57 5.85/2.57 EQ(x, y) == EQ(y, x) 5.85/2.57 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (3) EDependencyGraphProof (EQUIVALENT) 5.85/2.57 The approximation of the Equational Dependency Graph [DA_STEIN] contains 6 SCCs with 6 less nodes. 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (4) 5.85/2.57 Complex Obligation (AND) 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (5) 5.85/2.57 Obligation: 5.85/2.57 The TRS P consists of the following rules: 5.85/2.57 5.85/2.57 APP(add(n, x), y) -> APP(x, y) 5.85/2.57 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 The set E# consists of the following equations: 5.85/2.57 5.85/2.57 EQ(x, y) == EQ(y, x) 5.85/2.57 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (6) ESharpUsableEquationsProof (EQUIVALENT) 5.85/2.57 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 5.85/2.57 EQ(x, y) == EQ(y, x) 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (7) 5.85/2.57 Obligation: 5.85/2.57 The TRS P consists of the following rules: 5.85/2.57 5.85/2.57 APP(add(n, x), y) -> APP(x, y) 5.85/2.57 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 E# is empty. 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (8) EUsableRulesReductionPairsProof (EQUIVALENT) 5.85/2.57 By using the improved usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding improved usable rules can be oriented non-strictly, the improved usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and improved usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 5.85/2.57 5.85/2.57 The following dependency pairs can be deleted: 5.85/2.57 5.85/2.57 APP(add(n, x), y) -> APP(x, y) 5.85/2.57 The following rules are removed from R: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 The following equations are removed from E: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 Used ordering: POLO with Polynomial interpretation [POLO]: 5.85/2.57 5.85/2.57 POL(APP(x_1, x_2)) = 3*x_1 + x_2 5.85/2.57 POL(add(x_1, x_2)) = x_1 + 3*x_2 5.85/2.57 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (9) 5.85/2.57 Obligation: 5.85/2.57 P is empty. 5.85/2.57 R is empty. 5.85/2.57 E is empty. 5.85/2.57 E# is empty. 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (10) PisEmptyProof (EQUIVALENT) 5.85/2.57 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (11) 5.85/2.57 YES 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (12) 5.85/2.57 Obligation: 5.85/2.57 The TRS P consists of the following rules: 5.85/2.57 5.85/2.57 LE(s(x), s(y)) -> LE(x, y) 5.85/2.57 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 The set E# consists of the following equations: 5.85/2.57 5.85/2.57 EQ(x, y) == EQ(y, x) 5.85/2.57 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (13) ESharpUsableEquationsProof (EQUIVALENT) 5.85/2.57 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 5.85/2.57 EQ(x, y) == EQ(y, x) 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (14) 5.85/2.57 Obligation: 5.85/2.57 The TRS P consists of the following rules: 5.85/2.57 5.85/2.57 LE(s(x), s(y)) -> LE(x, y) 5.85/2.57 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 E# is empty. 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (15) EUsableRulesReductionPairsProof (EQUIVALENT) 5.85/2.57 By using the improved usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding improved usable rules can be oriented non-strictly, the improved usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and improved usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 5.85/2.57 5.85/2.57 The following dependency pairs can be deleted: 5.85/2.57 5.85/2.57 LE(s(x), s(y)) -> LE(x, y) 5.85/2.57 The following rules are removed from R: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 The following equations are removed from E: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 Used ordering: POLO with Polynomial interpretation [POLO]: 5.85/2.57 5.85/2.57 POL(LE(x_1, x_2)) = 3*x_1 + 3*x_2 5.85/2.57 POL(s(x_1)) = x_1 5.85/2.57 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (16) 5.85/2.57 Obligation: 5.85/2.57 P is empty. 5.85/2.57 R is empty. 5.85/2.57 E is empty. 5.85/2.57 E# is empty. 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (17) PisEmptyProof (EQUIVALENT) 5.85/2.57 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (18) 5.85/2.57 YES 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (19) 5.85/2.57 Obligation: 5.85/2.57 The TRS P consists of the following rules: 5.85/2.57 5.85/2.57 IF_MIN(true, add(n, add(m, x))) -> MIN(add(n, x)) 5.85/2.57 IF_MIN(false, add(n, add(m, x))) -> MIN(add(m, x)) 5.85/2.57 MIN(add(n, add(m, x))) -> IF_MIN(le(n, m), add(n, add(m, x))) 5.85/2.57 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 The set E# consists of the following equations: 5.85/2.57 5.85/2.57 EQ(x, y) == EQ(y, x) 5.85/2.57 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (20) ESharpUsableEquationsProof (EQUIVALENT) 5.85/2.57 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 5.85/2.57 EQ(x, y) == EQ(y, x) 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (21) 5.85/2.57 Obligation: 5.85/2.57 The TRS P consists of the following rules: 5.85/2.57 5.85/2.57 IF_MIN(true, add(n, add(m, x))) -> MIN(add(n, x)) 5.85/2.57 IF_MIN(false, add(n, add(m, x))) -> MIN(add(m, x)) 5.85/2.57 MIN(add(n, add(m, x))) -> IF_MIN(le(n, m), add(n, add(m, x))) 5.85/2.57 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 E# is empty. 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (22) EDPPoloProof (EQUIVALENT) 5.85/2.57 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. 5.85/2.57 5.85/2.57 5.85/2.57 IF_MIN(true, add(n, add(m, x))) -> MIN(add(n, x)) 5.85/2.57 IF_MIN(false, add(n, add(m, x))) -> MIN(add(m, x)) 5.85/2.57 MIN(add(n, add(m, x))) -> IF_MIN(le(n, m), add(n, add(m, x))) 5.85/2.57 With the implicit AFS there is no usable rule of R. 5.85/2.57 5.85/2.57 5.85/2.57 There is no equation of E#. 5.85/2.57 5.85/2.57 5.85/2.57 With the implicit AFS there is no usable equation of E. 5.85/2.57 5.85/2.57 5.85/2.57 Used ordering: POLO with Polynomial interpretation [POLO]: 5.85/2.57 5.85/2.57 POL(0) = 0 5.85/2.57 POL(IF_MIN(x_1, x_2)) = 2*x_2 5.85/2.57 POL(MIN(x_1)) = 3 + 3*x_1 5.85/2.57 POL(add(x_1, x_2)) = 3 + 3*x_2 5.85/2.57 POL(false) = 0 5.85/2.57 POL(le(x_1, x_2)) = 0 5.85/2.57 POL(s(x_1)) = 3*x_1 5.85/2.57 POL(true) = 0 5.85/2.57 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (23) 5.85/2.57 Obligation: 5.85/2.57 P is empty. 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 E# is empty. 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (24) PisEmptyProof (EQUIVALENT) 5.85/2.57 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (25) 5.85/2.57 YES 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (26) 5.85/2.57 Obligation: 5.85/2.57 The TRS P consists of the following rules: 5.85/2.57 5.85/2.57 EQ(s(x), s(y)) -> EQ(x, y) 5.85/2.57 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 The set E# consists of the following equations: 5.85/2.57 5.85/2.57 EQ(x, y) == EQ(y, x) 5.85/2.57 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (27) EUsableRulesReductionPairsProof (EQUIVALENT) 5.85/2.57 By using the improved usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding improved usable rules can be oriented non-strictly, the improved usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and improved usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 5.85/2.57 5.85/2.57 The following dependency pairs can be deleted: 5.85/2.57 5.85/2.57 EQ(s(x), s(y)) -> EQ(x, y) 5.85/2.57 The following rules are removed from R: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 The following equations are removed from E: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 Used ordering: POLO with Polynomial interpretation [POLO]: 5.85/2.57 5.85/2.57 POL(EQ(x_1, x_2)) = 3*x_1 + 3*x_2 5.85/2.57 POL(s(x_1)) = 3*x_1 5.85/2.57 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (28) 5.85/2.57 Obligation: 5.85/2.57 P is empty. 5.85/2.57 R is empty. 5.85/2.57 E is empty. 5.85/2.57 The set E# consists of the following equations: 5.85/2.57 5.85/2.57 EQ(x, y) == EQ(y, x) 5.85/2.57 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (29) PisEmptyProof (EQUIVALENT) 5.85/2.57 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (30) 5.85/2.57 YES 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (31) 5.85/2.57 Obligation: 5.85/2.57 The TRS P consists of the following rules: 5.85/2.57 5.85/2.57 IF_RM(true, n, add(m, x)) -> RM(n, x) 5.85/2.57 RM(n, add(m, x)) -> IF_RM(eq(n, m), n, add(m, x)) 5.85/2.57 IF_RM(false, n, add(m, x)) -> RM(n, x) 5.85/2.57 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 The set E# consists of the following equations: 5.85/2.57 5.85/2.57 EQ(x, y) == EQ(y, x) 5.85/2.57 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (32) ESharpUsableEquationsProof (EQUIVALENT) 5.85/2.57 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 5.85/2.57 EQ(x, y) == EQ(y, x) 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (33) 5.85/2.57 Obligation: 5.85/2.57 The TRS P consists of the following rules: 5.85/2.57 5.85/2.57 IF_RM(true, n, add(m, x)) -> RM(n, x) 5.85/2.57 RM(n, add(m, x)) -> IF_RM(eq(n, m), n, add(m, x)) 5.85/2.57 IF_RM(false, n, add(m, x)) -> RM(n, x) 5.85/2.57 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 E# is empty. 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (34) EDPPoloProof (EQUIVALENT) 5.85/2.57 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. 5.85/2.57 5.85/2.57 5.85/2.57 IF_RM(true, n, add(m, x)) -> RM(n, x) 5.85/2.57 RM(n, add(m, x)) -> IF_RM(eq(n, m), n, add(m, x)) 5.85/2.57 IF_RM(false, n, add(m, x)) -> RM(n, x) 5.85/2.57 With the implicit AFS there is no usable rule of R. 5.85/2.57 5.85/2.57 5.85/2.57 There is no equation of E#. 5.85/2.57 5.85/2.57 5.85/2.57 With the implicit AFS there is no usable equation of E. 5.85/2.57 5.85/2.57 5.85/2.57 Used ordering: POLO with Polynomial interpretation [POLO]: 5.85/2.57 5.85/2.57 POL(0) = 0 5.85/2.57 POL(IF_RM(x_1, x_2, x_3)) = 3*x_2 + 2*x_3 5.85/2.57 POL(RM(x_1, x_2)) = 3 + 3*x_1 + 2*x_2 5.85/2.57 POL(add(x_1, x_2)) = 2 + x_2 5.85/2.57 POL(eq(x_1, x_2)) = 0 5.85/2.57 POL(false) = 0 5.85/2.57 POL(s(x_1)) = 0 5.85/2.57 POL(true) = 0 5.85/2.57 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (35) 5.85/2.57 Obligation: 5.85/2.57 P is empty. 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 E# is empty. 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (36) PisEmptyProof (EQUIVALENT) 5.85/2.57 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (37) 5.85/2.57 YES 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (38) 5.85/2.57 Obligation: 5.85/2.57 The TRS P consists of the following rules: 5.85/2.57 5.85/2.57 IF_MINSORT(true, add(n, x), y) -> MINSORT(app(rm(n, x), y), nil) 5.85/2.57 MINSORT(add(n, x), y) -> IF_MINSORT(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 IF_MINSORT(false, add(n, x), y) -> MINSORT(x, add(n, y)) 5.85/2.57 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 The set E# consists of the following equations: 5.85/2.57 5.85/2.57 EQ(x, y) == EQ(y, x) 5.85/2.57 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (39) ESharpUsableEquationsProof (EQUIVALENT) 5.85/2.57 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 5.85/2.57 EQ(x, y) == EQ(y, x) 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (40) 5.85/2.57 Obligation: 5.85/2.57 The TRS P consists of the following rules: 5.85/2.57 5.85/2.57 IF_MINSORT(true, add(n, x), y) -> MINSORT(app(rm(n, x), y), nil) 5.85/2.57 MINSORT(add(n, x), y) -> IF_MINSORT(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 IF_MINSORT(false, add(n, x), y) -> MINSORT(x, add(n, y)) 5.85/2.57 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 E# is empty. 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (41) EDPPoloProof (EQUIVALENT) 5.85/2.57 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented. 5.85/2.57 5.85/2.57 5.85/2.57 IF_MINSORT(true, add(n, x), y) -> MINSORT(app(rm(n, x), y), nil) 5.85/2.57 The remaining Dependency Pairs were at least non-strictly oriented. 5.85/2.57 5.85/2.57 5.85/2.57 MINSORT(add(n, x), y) -> IF_MINSORT(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 IF_MINSORT(false, add(n, x), y) -> MINSORT(x, add(n, y)) 5.85/2.57 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 5.85/2.57 5.85/2.57 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 app(nil, y) -> y 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 There is no equation of E#. 5.85/2.57 5.85/2.57 5.85/2.57 With the implicit AFS there is no usable equation of E. 5.85/2.57 5.85/2.57 5.85/2.57 Used ordering: POLO with Polynomial interpretation [POLO]: 5.85/2.57 5.85/2.57 POL(0) = 0 5.85/2.57 POL(IF_MINSORT(x_1, x_2, x_3)) = x_2 + x_3 5.85/2.57 POL(MINSORT(x_1, x_2)) = x_1 + x_2 5.85/2.57 POL(add(x_1, x_2)) = 2 + x_2 5.85/2.57 POL(app(x_1, x_2)) = x_1 + x_2 5.85/2.57 POL(eq(x_1, x_2)) = 0 5.85/2.57 POL(false) = 0 5.85/2.57 POL(if_min(x_1, x_2)) = 2 5.85/2.57 POL(if_rm(x_1, x_2, x_3)) = x_3 5.85/2.57 POL(le(x_1, x_2)) = 0 5.85/2.57 POL(min(x_1)) = 0 5.85/2.57 POL(nil) = 0 5.85/2.57 POL(rm(x_1, x_2)) = x_2 5.85/2.57 POL(s(x_1)) = 0 5.85/2.57 POL(true) = 0 5.85/2.57 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (42) 5.85/2.57 Obligation: 5.85/2.57 The TRS P consists of the following rules: 5.85/2.57 5.85/2.57 MINSORT(add(n, x), y) -> IF_MINSORT(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 IF_MINSORT(false, add(n, x), y) -> MINSORT(x, add(n, y)) 5.85/2.57 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 E# is empty. 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (43) EDPPoloProof (EQUIVALENT) 5.85/2.57 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented. 5.85/2.57 5.85/2.57 5.85/2.57 IF_MINSORT(false, add(n, x), y) -> MINSORT(x, add(n, y)) 5.85/2.57 The remaining Dependency Pairs were at least non-strictly oriented. 5.85/2.57 5.85/2.57 5.85/2.57 MINSORT(add(n, x), y) -> IF_MINSORT(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 With the implicit AFS there is no usable rule of R. 5.85/2.57 5.85/2.57 5.85/2.57 There is no equation of E#. 5.85/2.57 5.85/2.57 5.85/2.57 With the implicit AFS there is no usable equation of E. 5.85/2.57 5.85/2.57 5.85/2.57 Used ordering: POLO with Polynomial interpretation [POLO]: 5.85/2.57 5.85/2.57 POL(0) = 0 5.85/2.57 POL(IF_MINSORT(x_1, x_2, x_3)) = 2*x_2 5.85/2.57 POL(MINSORT(x_1, x_2)) = 2*x_1 5.85/2.57 POL(add(x_1, x_2)) = 2 + 2*x_1 + x_2 5.85/2.57 POL(eq(x_1, x_2)) = 0 5.85/2.57 POL(false) = 0 5.85/2.57 POL(if_min(x_1, x_2)) = 2 5.85/2.57 POL(le(x_1, x_2)) = 0 5.85/2.57 POL(min(x_1)) = 0 5.85/2.57 POL(nil) = 0 5.85/2.57 POL(s(x_1)) = 0 5.85/2.57 POL(true) = 0 5.85/2.57 5.85/2.57 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (44) 5.85/2.57 Obligation: 5.85/2.57 The TRS P consists of the following rules: 5.85/2.57 5.85/2.57 MINSORT(add(n, x), y) -> IF_MINSORT(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 5.85/2.57 The TRS R consists of the following rules: 5.85/2.57 5.85/2.57 eq(0, 0) -> true 5.85/2.57 eq(0, s(x)) -> false 5.85/2.57 eq(s(x), 0) -> false 5.85/2.57 eq(s(x), s(y)) -> eq(x, y) 5.85/2.57 le(0, y) -> true 5.85/2.57 le(s(x), 0) -> false 5.85/2.57 le(s(x), s(y)) -> le(x, y) 5.85/2.57 app(nil, y) -> y 5.85/2.57 app(add(n, x), y) -> add(n, app(x, y)) 5.85/2.57 min(add(n, nil)) -> n 5.85/2.57 min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x))) 5.85/2.57 if_min(true, add(n, add(m, x))) -> min(add(n, x)) 5.85/2.57 if_min(false, add(n, add(m, x))) -> min(add(m, x)) 5.85/2.57 rm(n, nil) -> nil 5.85/2.57 rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x)) 5.85/2.57 if_rm(true, n, add(m, x)) -> rm(n, x) 5.85/2.57 if_rm(false, n, add(m, x)) -> add(m, rm(n, x)) 5.85/2.57 minsort(nil, nil) -> nil 5.85/2.57 minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y) 5.85/2.57 if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil)) 5.85/2.57 if_minsort(false, add(n, x), y) -> minsort(x, add(n, y)) 5.85/2.57 5.85/2.57 The set E consists of the following equations: 5.85/2.57 5.85/2.57 eq(x, y) == eq(y, x) 5.85/2.57 5.85/2.57 E# is empty. 5.85/2.57 We have to consider all minimal (P,E#,R,E)-chains 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (45) EDependencyGraphProof (EQUIVALENT) 5.85/2.57 The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 1 less node. 5.85/2.57 ---------------------------------------- 5.85/2.57 5.85/2.57 (46) 5.85/2.57 TRUE 6.20/2.63 EOF