7.81/3.23 YES 7.81/3.25 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 7.81/3.25 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.81/3.25 7.81/3.25 7.81/3.25 Termination of the given ETRS could be proven: 7.81/3.25 7.81/3.25 (0) ETRS 7.81/3.25 (1) EquationalDependencyPairsProof [EQUIVALENT, 0 ms] 7.81/3.25 (2) EDP 7.81/3.25 (3) EDependencyGraphProof [EQUIVALENT, 0 ms] 7.81/3.25 (4) AND 7.81/3.25 (5) EDP 7.81/3.25 (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 7.81/3.25 (7) EDP 7.81/3.25 (8) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 7.81/3.25 (9) EDP 7.81/3.25 (10) PisEmptyProof [EQUIVALENT, 0 ms] 7.81/3.25 (11) YES 7.81/3.25 (12) EDP 7.81/3.25 (13) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 7.81/3.25 (14) EDP 7.81/3.25 (15) ERuleRemovalProof [EQUIVALENT, 0 ms] 7.81/3.25 (16) EDP 7.81/3.25 (17) EDPPoloProof [EQUIVALENT, 10 ms] 7.81/3.25 (18) EDP 7.81/3.25 (19) PisEmptyProof [EQUIVALENT, 0 ms] 7.81/3.25 (20) YES 7.81/3.25 (21) EDP 7.81/3.25 (22) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 7.81/3.25 (23) EDP 7.81/3.25 (24) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 7.81/3.25 (25) EDP 7.81/3.25 (26) PisEmptyProof [EQUIVALENT, 0 ms] 7.81/3.25 (27) YES 7.81/3.25 (28) EDP 7.81/3.25 (29) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 7.81/3.25 (30) EDP 7.81/3.25 (31) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 7.81/3.25 (32) EDP 7.81/3.25 (33) ERuleRemovalProof [EQUIVALENT, 17 ms] 7.81/3.25 (34) EDP 7.81/3.25 (35) ERuleRemovalProof [EQUIVALENT, 0 ms] 7.81/3.25 (36) EDP 7.81/3.25 (37) EUsableRulesReductionPairsProof [EQUIVALENT, 8 ms] 7.81/3.25 (38) EDP 7.81/3.25 (39) EDPProblemToQDPProblemProof [EQUIVALENT, 0 ms] 7.81/3.25 (40) QDP 7.81/3.25 (41) UsableRulesProof [EQUIVALENT, 0 ms] 7.81/3.25 (42) QDP 7.81/3.25 (43) MRRProof [EQUIVALENT, 9 ms] 7.81/3.25 (44) QDP 7.81/3.25 (45) DependencyGraphProof [EQUIVALENT, 0 ms] 7.81/3.25 (46) TRUE 7.81/3.25 (47) EDP 7.81/3.25 (48) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 7.81/3.25 (49) EDP 7.81/3.25 (50) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 7.81/3.25 (51) EDP 7.81/3.25 (52) PisEmptyProof [EQUIVALENT, 0 ms] 7.81/3.25 (53) YES 7.81/3.25 (54) EDP 7.81/3.25 (55) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 7.81/3.25 (56) EDP 7.81/3.25 (57) EDPPoloProof [EQUIVALENT, 0 ms] 7.81/3.25 (58) EDP 7.81/3.25 (59) PisEmptyProof [EQUIVALENT, 0 ms] 7.81/3.25 (60) YES 7.81/3.25 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (0) 7.81/3.25 Obligation: 7.81/3.25 Equational rewrite system: 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (1) EquationalDependencyPairsProof (EQUIVALENT) 7.81/3.25 Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 MINUS(s(x), s(y)) -> MINUS(x, y) 7.81/3.25 MINUS(minus(x, y), z) -> MINUS(x, plus(y, z)) 7.81/3.25 MINUS(minus(x, y), z) -> PLUS(y, z) 7.81/3.25 QUOT(s(x), s(y)) -> QUOT(minus(x, y), s(y)) 7.81/3.25 QUOT(s(x), s(y)) -> MINUS(x, y) 7.81/3.25 PLUS(s(x), y) -> PLUS(x, y) 7.81/3.25 APP(cons(x, l), k) -> APP(l, k) 7.81/3.25 SUM(cons(x, cons(y, l))) -> SUM(cons(plus(x, y), l)) 7.81/3.25 SUM(cons(x, cons(y, l))) -> PLUS(x, y) 7.81/3.25 SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 SUM(app(l, cons(x, cons(y, k)))) -> APP(l, sum(cons(x, cons(y, k)))) 7.81/3.25 SUM(app(l, cons(x, cons(y, k)))) -> SUM(cons(x, cons(y, k))) 7.81/3.25 PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext) 7.81/3.25 PLUS(plus(s(x), y), ext) -> PLUS(x, y) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 The set E# consists of the following equations: 7.81/3.25 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (2) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 MINUS(s(x), s(y)) -> MINUS(x, y) 7.81/3.25 MINUS(minus(x, y), z) -> MINUS(x, plus(y, z)) 7.81/3.25 MINUS(minus(x, y), z) -> PLUS(y, z) 7.81/3.25 QUOT(s(x), s(y)) -> QUOT(minus(x, y), s(y)) 7.81/3.25 QUOT(s(x), s(y)) -> MINUS(x, y) 7.81/3.25 PLUS(s(x), y) -> PLUS(x, y) 7.81/3.25 APP(cons(x, l), k) -> APP(l, k) 7.81/3.25 SUM(cons(x, cons(y, l))) -> SUM(cons(plus(x, y), l)) 7.81/3.25 SUM(cons(x, cons(y, l))) -> PLUS(x, y) 7.81/3.25 SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 SUM(app(l, cons(x, cons(y, k)))) -> APP(l, sum(cons(x, cons(y, k)))) 7.81/3.25 SUM(app(l, cons(x, cons(y, k)))) -> SUM(cons(x, cons(y, k))) 7.81/3.25 PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext) 7.81/3.25 PLUS(plus(s(x), y), ext) -> PLUS(x, y) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 The set E# consists of the following equations: 7.81/3.25 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (3) EDependencyGraphProof (EQUIVALENT) 7.81/3.25 The approximation of the Equational Dependency Graph [DA_STEIN] contains 6 SCCs with 5 less nodes. 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (4) 7.81/3.25 Complex Obligation (AND) 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (5) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 APP(cons(x, l), k) -> APP(l, k) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 The set E# consists of the following equations: 7.81/3.25 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (6) ESharpUsableEquationsProof (EQUIVALENT) 7.81/3.25 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (7) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 APP(cons(x, l), k) -> APP(l, k) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 E# is empty. 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (8) EUsableRulesReductionPairsProof (EQUIVALENT) 7.81/3.25 By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 7.81/3.25 7.81/3.25 The following dependency pairs can be deleted: 7.81/3.25 7.81/3.25 APP(cons(x, l), k) -> APP(l, k) 7.81/3.25 The following rules are removed from R: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 The following equations are removed from E: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 Used ordering: POLO with Polynomial interpretation [POLO]: 7.81/3.25 7.81/3.25 POL(APP(x_1, x_2)) = 3*x_1 + x_2 7.81/3.25 POL(cons(x_1, x_2)) = x_1 + 3*x_2 7.81/3.25 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (9) 7.81/3.25 Obligation: 7.81/3.25 P is empty. 7.81/3.25 R is empty. 7.81/3.25 E is empty. 7.81/3.25 E# is empty. 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (10) PisEmptyProof (EQUIVALENT) 7.81/3.25 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (11) 7.81/3.25 YES 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (12) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext) 7.81/3.25 PLUS(s(x), y) -> PLUS(x, y) 7.81/3.25 PLUS(plus(s(x), y), ext) -> PLUS(x, y) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 The set E# consists of the following equations: 7.81/3.25 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (13) EUsableRulesReductionPairsProof (EQUIVALENT) 7.81/3.25 By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 7.81/3.25 7.81/3.25 No dependency pairs are removed. 7.81/3.25 7.81/3.25 The following rules are removed from R: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 No equations are removed from E. 7.81/3.25 7.81/3.25 Used ordering: POLO with Polynomial interpretation [POLO]: 7.81/3.25 7.81/3.25 POL(0) = 0 7.81/3.25 POL(PLUS(x_1, x_2)) = x_1 + x_2 7.81/3.25 POL(plus(x_1, x_2)) = x_1 + x_2 7.81/3.25 POL(s(x_1)) = x_1 7.81/3.25 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (14) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext) 7.81/3.25 PLUS(s(x), y) -> PLUS(x, y) 7.81/3.25 PLUS(plus(s(x), y), ext) -> PLUS(x, y) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 The set E# consists of the following equations: 7.81/3.25 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (15) ERuleRemovalProof (EQUIVALENT) 7.81/3.25 By using the rule removal processor [DA_STEIN] with the following polynomial ordering [POLO], at least one Dependency Pair or term rewrite system rule of this EDP problem can be strictly oriented. 7.81/3.25 7.81/3.25 Strictly oriented dependency pairs: 7.81/3.25 7.81/3.25 PLUS(s(x), y) -> PLUS(x, y) 7.81/3.25 PLUS(plus(s(x), y), ext) -> PLUS(x, y) 7.81/3.25 7.81/3.25 7.81/3.25 Used ordering: POLO with Polynomial interpretation [POLO]: 7.81/3.25 7.81/3.25 POL(PLUS(x_1, x_2)) = 2*x_1 + 2*x_2 7.81/3.25 POL(plus(x_1, x_2)) = x_1 + x_2 7.81/3.25 POL(s(x_1)) = 1 + x_1 7.81/3.25 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (16) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 The set E# consists of the following equations: 7.81/3.25 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (17) EDPPoloProof (EQUIVALENT) 7.81/3.25 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. 7.81/3.25 7.81/3.25 7.81/3.25 PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext) 7.81/3.25 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 7.81/3.25 7.81/3.25 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 We had to orient the following equations of E# equivalently. 7.81/3.25 7.81/3.25 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 With the implicit AFS we had to orient the following usable equations of E equivalently. 7.81/3.25 7.81/3.25 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 Used ordering: POLO with Polynomial interpretation [POLO]: 7.81/3.25 7.81/3.25 POL(PLUS(x_1, x_2)) = x_1 + x_2 7.81/3.25 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 7.81/3.25 POL(s(x_1)) = 0 7.81/3.25 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (18) 7.81/3.25 Obligation: 7.81/3.25 P is empty. 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 The set E# consists of the following equations: 7.81/3.25 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (19) PisEmptyProof (EQUIVALENT) 7.81/3.25 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (20) 7.81/3.25 YES 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (21) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 SUM(cons(x, cons(y, l))) -> SUM(cons(plus(x, y), l)) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 The set E# consists of the following equations: 7.81/3.25 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (22) ESharpUsableEquationsProof (EQUIVALENT) 7.81/3.25 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (23) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 SUM(cons(x, cons(y, l))) -> SUM(cons(plus(x, y), l)) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 E# is empty. 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (24) EUsableRulesReductionPairsProof (EQUIVALENT) 7.81/3.25 By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 7.81/3.25 7.81/3.25 The following dependency pairs can be deleted: 7.81/3.25 7.81/3.25 SUM(cons(x, cons(y, l))) -> SUM(cons(plus(x, y), l)) 7.81/3.25 The following rules are removed from R: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 No equations are removed from E. 7.81/3.25 7.81/3.25 Used ordering: POLO with Polynomial interpretation [POLO]: 7.81/3.25 7.81/3.25 POL(0) = 0 7.81/3.25 POL(SUM(x_1)) = x_1 7.81/3.25 POL(cons(x_1, x_2)) = 2 + x_1 + x_2 7.81/3.25 POL(plus(x_1, x_2)) = x_1 + x_2 7.81/3.25 POL(s(x_1)) = 3 + x_1 7.81/3.25 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (25) 7.81/3.25 Obligation: 7.81/3.25 P is empty. 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 E# is empty. 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (26) PisEmptyProof (EQUIVALENT) 7.81/3.25 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (27) 7.81/3.25 YES 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (28) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 The set E# consists of the following equations: 7.81/3.25 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (29) ESharpUsableEquationsProof (EQUIVALENT) 7.81/3.25 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (30) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 E# is empty. 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (31) EUsableRulesReductionPairsProof (EQUIVALENT) 7.81/3.25 By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 7.81/3.25 7.81/3.25 No dependency pairs are removed. 7.81/3.25 7.81/3.25 The following rules are removed from R: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 No equations are removed from E. 7.81/3.25 7.81/3.25 Used ordering: POLO with Polynomial interpretation [POLO]: 7.81/3.25 7.81/3.25 POL(0) = 0 7.81/3.25 POL(SUM(x_1)) = x_1 7.81/3.25 POL(app(x_1, x_2)) = 2*x_1 + x_2 7.81/3.25 POL(cons(x_1, x_2)) = x_1 + x_2 7.81/3.25 POL(nil) = 0 7.81/3.25 POL(plus(x_1, x_2)) = x_1 + x_2 7.81/3.25 POL(s(x_1)) = 1 + x_1 7.81/3.25 POL(sum(x_1)) = x_1 7.81/3.25 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (32) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 E# is empty. 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (33) ERuleRemovalProof (EQUIVALENT) 7.81/3.25 By using the rule removal processor [DA_STEIN] with the following polynomial ordering [POLO], at least one Dependency Pair or term rewrite system rule of this EDP problem can be strictly oriented. 7.81/3.25 7.81/3.25 7.81/3.25 Strictly oriented rules of the TRS R: 7.81/3.25 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 7.81/3.25 Used ordering: POLO with Polynomial interpretation [POLO]: 7.81/3.25 7.81/3.25 POL(SUM(x_1)) = 2*x_1 7.81/3.25 POL(app(x_1, x_2)) = 2*x_1 + 2*x_2 7.81/3.25 POL(cons(x_1, x_2)) = x_1 + x_2 7.81/3.25 POL(nil) = 2 7.81/3.25 POL(plus(x_1, x_2)) = x_1 + x_2 7.81/3.25 POL(s(x_1)) = x_1 7.81/3.25 POL(sum(x_1)) = x_1 7.81/3.25 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (34) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 E# is empty. 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (35) ERuleRemovalProof (EQUIVALENT) 7.81/3.25 By using the rule removal processor [DA_STEIN] with the following polynomial ordering [POLO], at least one Dependency Pair or term rewrite system rule of this EDP problem can be strictly oriented. 7.81/3.25 7.81/3.25 7.81/3.25 Strictly oriented rules of the TRS R: 7.81/3.25 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 7.81/3.25 Used ordering: POLO with Polynomial interpretation [POLO]: 7.81/3.25 7.81/3.25 POL(SUM(x_1)) = 2*x_1 7.81/3.25 POL(app(x_1, x_2)) = x_1 + 2*x_2 7.81/3.25 POL(cons(x_1, x_2)) = 2 + x_1 + x_2 7.81/3.25 POL(nil) = 0 7.81/3.25 POL(plus(x_1, x_2)) = x_1 + x_2 7.81/3.25 POL(s(x_1)) = x_1 7.81/3.25 POL(sum(x_1)) = x_1 7.81/3.25 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (36) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 E# is empty. 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (37) EUsableRulesReductionPairsProof (EQUIVALENT) 7.81/3.25 By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 7.81/3.25 7.81/3.25 No dependency pairs are removed. 7.81/3.25 7.81/3.25 The following rules are removed from R: 7.81/3.25 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 The following equations are removed from E: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 Used ordering: POLO with Polynomial interpretation [POLO]: 7.81/3.25 7.81/3.25 POL(SUM(x_1)) = 2*x_1 7.81/3.25 POL(app(x_1, x_2)) = 2*x_1 + 2*x_2 7.81/3.25 POL(cons(x_1, x_2)) = 2*x_1 + x_2 7.81/3.25 POL(nil) = 0 7.81/3.25 POL(sum(x_1)) = x_1 7.81/3.25 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (38) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 7.81/3.25 E is empty. 7.81/3.25 E# is empty. 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (39) EDPProblemToQDPProblemProof (EQUIVALENT) 7.81/3.25 The EDP problem does not contain equations anymore, so we can transform it with the EDP to QDP problem processor [DA_STEIN] into a QDP problem. 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (40) 7.81/3.25 Obligation: 7.81/3.25 Q DP problem: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 7.81/3.25 Q is empty. 7.81/3.25 We have to consider all minimal (P,Q,R)-chains. 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (41) UsableRulesProof (EQUIVALENT) 7.81/3.25 We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (42) 7.81/3.25 Obligation: 7.81/3.25 Q DP problem: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 7.81/3.25 Q is empty. 7.81/3.25 We have to consider all minimal (P,Q,R)-chains. 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (43) MRRProof (EQUIVALENT) 7.81/3.25 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 7.81/3.25 7.81/3.25 7.81/3.25 Strictly oriented rules of the TRS R: 7.81/3.25 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 7.81/3.25 Used ordering: Polynomial interpretation [POLO]: 7.81/3.25 7.81/3.25 POL(SUM(x_1)) = 2*x_1 7.81/3.25 POL(app(x_1, x_2)) = 1 + 2*x_1 + x_2 7.81/3.25 POL(cons(x_1, x_2)) = 1 + x_1 + x_2 7.81/3.25 POL(sum(x_1)) = x_1 7.81/3.25 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (44) 7.81/3.25 Obligation: 7.81/3.25 Q DP problem: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 7.81/3.25 R is empty. 7.81/3.25 Q is empty. 7.81/3.25 We have to consider all minimal (P,Q,R)-chains. 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (45) DependencyGraphProof (EQUIVALENT) 7.81/3.25 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (46) 7.81/3.25 TRUE 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (47) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 MINUS(minus(x, y), z) -> MINUS(x, plus(y, z)) 7.81/3.25 MINUS(s(x), s(y)) -> MINUS(x, y) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 The set E# consists of the following equations: 7.81/3.25 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (48) ESharpUsableEquationsProof (EQUIVALENT) 7.81/3.25 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (49) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 MINUS(minus(x, y), z) -> MINUS(x, plus(y, z)) 7.81/3.25 MINUS(s(x), s(y)) -> MINUS(x, y) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 E# is empty. 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (50) EUsableRulesReductionPairsProof (EQUIVALENT) 7.81/3.25 By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 7.81/3.25 7.81/3.25 The following dependency pairs can be deleted: 7.81/3.25 7.81/3.25 MINUS(minus(x, y), z) -> MINUS(x, plus(y, z)) 7.81/3.25 MINUS(s(x), s(y)) -> MINUS(x, y) 7.81/3.25 The following rules are removed from R: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 No equations are removed from E. 7.81/3.25 7.81/3.25 Used ordering: POLO with Polynomial interpretation [POLO]: 7.81/3.25 7.81/3.25 POL(0) = 0 7.81/3.25 POL(MINUS(x_1, x_2)) = 3*x_1 + 2*x_2 7.81/3.25 POL(minus(x_1, x_2)) = 2 + 3*x_1 + 3*x_2 7.81/3.25 POL(plus(x_1, x_2)) = x_1 + x_2 7.81/3.25 POL(s(x_1)) = 3 + x_1 7.81/3.25 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (51) 7.81/3.25 Obligation: 7.81/3.25 P is empty. 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 E# is empty. 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (52) PisEmptyProof (EQUIVALENT) 7.81/3.25 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (53) 7.81/3.25 YES 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (54) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 QUOT(s(x), s(y)) -> QUOT(minus(x, y), s(y)) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 The set E# consists of the following equations: 7.81/3.25 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (55) ESharpUsableEquationsProof (EQUIVALENT) 7.81/3.25 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 7.81/3.25 PLUS(x, y) == PLUS(y, x) 7.81/3.25 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (56) 7.81/3.25 Obligation: 7.81/3.25 The TRS P consists of the following rules: 7.81/3.25 7.81/3.25 QUOT(s(x), s(y)) -> QUOT(minus(x, y), s(y)) 7.81/3.25 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 E# is empty. 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (57) EDPPoloProof (EQUIVALENT) 7.81/3.25 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. 7.81/3.25 7.81/3.25 7.81/3.25 QUOT(s(x), s(y)) -> QUOT(minus(x, y), s(y)) 7.81/3.25 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 7.81/3.25 7.81/3.25 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(x, 0) -> x 7.81/3.25 There is no equation of E#. 7.81/3.25 7.81/3.25 7.81/3.25 With the implicit AFS there is no usable equation of E. 7.81/3.25 7.81/3.25 7.81/3.25 Used ordering: POLO with Polynomial interpretation [POLO]: 7.81/3.25 7.81/3.25 POL(0) = 0 7.81/3.25 POL(QUOT(x_1, x_2)) = x_1 7.81/3.25 POL(minus(x_1, x_2)) = x_1 7.81/3.25 POL(plus(x_1, x_2)) = 0 7.81/3.25 POL(s(x_1)) = 1 + 2*x_1 7.81/3.25 7.81/3.25 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (58) 7.81/3.25 Obligation: 7.81/3.25 P is empty. 7.81/3.25 The TRS R consists of the following rules: 7.81/3.25 7.81/3.25 minus(x, 0) -> x 7.81/3.25 minus(s(x), s(y)) -> minus(x, y) 7.81/3.25 minus(minus(x, y), z) -> minus(x, plus(y, z)) 7.81/3.25 quot(0, s(y)) -> 0 7.81/3.25 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 7.81/3.25 plus(0, y) -> y 7.81/3.25 plus(s(x), y) -> s(plus(x, y)) 7.81/3.25 app(nil, k) -> k 7.81/3.25 app(l, nil) -> l 7.81/3.25 app(cons(x, l), k) -> cons(x, app(l, k)) 7.81/3.25 sum(cons(x, nil)) -> cons(x, nil) 7.81/3.25 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.81/3.25 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.81/3.25 plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) 7.81/3.25 7.81/3.25 The set E consists of the following equations: 7.81/3.25 7.81/3.25 plus(x, y) == plus(y, x) 7.81/3.25 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.81/3.25 7.81/3.25 E# is empty. 7.81/3.25 We have to consider all minimal (P,E#,R,E)-chains 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (59) PisEmptyProof (EQUIVALENT) 7.81/3.25 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 7.81/3.25 ---------------------------------------- 7.81/3.25 7.81/3.25 (60) 7.81/3.25 YES 8.09/3.36 EOF