4.67/2.15 YES 4.67/2.16 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.67/2.16 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.67/2.16 4.67/2.16 4.67/2.16 Termination of the given ETRS could be proven: 4.67/2.16 4.67/2.16 (0) ETRS 4.67/2.16 (1) RRRPoloETRSProof [EQUIVALENT, 166 ms] 4.67/2.16 (2) ETRS 4.67/2.16 (3) RRRPoloETRSProof [EQUIVALENT, 46 ms] 4.67/2.16 (4) ETRS 4.67/2.16 (5) EquationalDependencyPairsProof [EQUIVALENT, 0 ms] 4.67/2.16 (6) EDP 4.67/2.16 (7) EDependencyGraphProof [EQUIVALENT, 0 ms] 4.67/2.16 (8) AND 4.67/2.16 (9) EDP 4.67/2.16 (10) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 4.67/2.16 (11) EDP 4.67/2.16 (12) EUsableRulesReductionPairsProof [EQUIVALENT, 5 ms] 4.67/2.16 (13) EDP 4.67/2.16 (14) PisEmptyProof [EQUIVALENT, 0 ms] 4.67/2.16 (15) YES 4.67/2.16 (16) EDP 4.67/2.16 (17) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 4.67/2.16 (18) EDP 4.67/2.16 (19) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 4.67/2.16 (20) EDP 4.67/2.16 (21) EDPProblemToQDPProblemProof [EQUIVALENT, 0 ms] 4.67/2.16 (22) QDP 4.67/2.16 (23) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.67/2.16 (24) YES 4.67/2.16 (25) EDP 4.67/2.16 (26) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 4.67/2.16 (27) EDP 4.67/2.16 (28) ERuleRemovalProof [EQUIVALENT, 11 ms] 4.67/2.16 (29) EDP 4.67/2.16 (30) EDPPoloProof [EQUIVALENT, 0 ms] 4.67/2.16 (31) EDP 4.67/2.16 (32) PisEmptyProof [EQUIVALENT, 0 ms] 4.67/2.16 (33) YES 4.67/2.16 (34) EDP 4.67/2.16 (35) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 4.67/2.16 (36) EDP 4.67/2.16 (37) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 4.67/2.16 (38) EDP 4.67/2.16 (39) PisEmptyProof [EQUIVALENT, 0 ms] 4.67/2.16 (40) YES 4.67/2.16 4.67/2.16 4.67/2.16 ---------------------------------------- 4.67/2.16 4.67/2.16 (0) 4.67/2.16 Obligation: 4.67/2.16 Equational rewrite system: 4.67/2.16 The TRS R consists of the following rules: 4.67/2.16 4.67/2.16 sum(x, y) -> S(int(x, y)) 4.67/2.16 S(nil) -> 0 4.67/2.16 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.16 plus(x, 0) -> x 4.67/2.16 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.16 int(0, 0) -> cons(0, nil) 4.67/2.16 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.16 int(s(x), 0) -> nil 4.67/2.16 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.16 intlist(nil) -> nil 4.67/2.16 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.16 4.67/2.16 The set E consists of the following equations: 4.67/2.16 4.67/2.16 plus(x, y) == plus(y, x) 4.67/2.16 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.16 4.67/2.16 4.67/2.16 ---------------------------------------- 4.67/2.16 4.67/2.16 (1) RRRPoloETRSProof (EQUIVALENT) 4.67/2.16 The following E TRS is given: Equational rewrite system: 4.67/2.16 The TRS R consists of the following rules: 4.67/2.16 4.67/2.16 sum(x, y) -> S(int(x, y)) 4.67/2.16 S(nil) -> 0 4.67/2.16 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.16 plus(x, 0) -> x 4.67/2.16 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.16 int(0, 0) -> cons(0, nil) 4.67/2.16 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.16 int(s(x), 0) -> nil 4.67/2.16 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.16 intlist(nil) -> nil 4.67/2.16 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.16 4.67/2.16 The set E consists of the following equations: 4.67/2.16 4.67/2.16 plus(x, y) == plus(y, x) 4.67/2.16 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.16 4.67/2.16 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 4.67/2.16 4.67/2.16 sum(x, y) -> S(int(x, y)) 4.67/2.16 int(0, 0) -> cons(0, nil) 4.67/2.16 int(s(x), 0) -> nil 4.67/2.16 Used ordering: 4.67/2.16 Polynomial interpretation [POLO]: 4.67/2.16 4.67/2.16 POL(0) = 0 4.67/2.16 POL(S(x_1)) = x_1 4.67/2.16 POL(cons(x_1, x_2)) = 2*x_1 + x_2 4.67/2.16 POL(int(x_1, x_2)) = 1 + x_1 + x_2 4.67/2.16 POL(intlist(x_1)) = x_1 4.67/2.16 POL(nil) = 0 4.67/2.16 POL(plus(x_1, x_2)) = x_1 + x_2 4.67/2.16 POL(s(x_1)) = x_1 4.67/2.16 POL(sum(x_1, x_2)) = 2 + x_1 + x_1*x_2 + x_2 4.67/2.16 4.67/2.16 4.67/2.16 4.67/2.16 4.67/2.16 ---------------------------------------- 4.67/2.16 4.67/2.16 (2) 4.67/2.16 Obligation: 4.67/2.16 Equational rewrite system: 4.67/2.16 The TRS R consists of the following rules: 4.67/2.16 4.67/2.16 S(nil) -> 0 4.67/2.16 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.16 plus(x, 0) -> x 4.67/2.16 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.16 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.16 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.16 intlist(nil) -> nil 4.67/2.16 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.16 4.67/2.16 The set E consists of the following equations: 4.67/2.16 4.67/2.16 plus(x, y) == plus(y, x) 4.67/2.16 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.16 4.67/2.16 4.67/2.16 ---------------------------------------- 4.67/2.16 4.67/2.16 (3) RRRPoloETRSProof (EQUIVALENT) 4.67/2.16 The following E TRS is given: Equational rewrite system: 4.67/2.16 The TRS R consists of the following rules: 4.67/2.16 4.67/2.16 S(nil) -> 0 4.67/2.16 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.16 plus(x, 0) -> x 4.67/2.16 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.16 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.16 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.16 intlist(nil) -> nil 4.67/2.16 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.16 4.67/2.16 The set E consists of the following equations: 4.67/2.16 4.67/2.16 plus(x, y) == plus(y, x) 4.67/2.16 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.16 4.67/2.16 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 4.67/2.16 4.67/2.16 S(nil) -> 0 4.67/2.16 Used ordering: 4.67/2.16 Polynomial interpretation [POLO]: 4.67/2.16 4.67/2.16 POL(0) = 0 4.67/2.16 POL(S(x_1)) = 2*x_1 4.67/2.16 POL(cons(x_1, x_2)) = 2*x_1 + x_2 4.67/2.16 POL(int(x_1, x_2)) = 2*x_1 + x_2 4.67/2.16 POL(intlist(x_1)) = x_1 4.67/2.16 POL(nil) = 1 4.67/2.16 POL(plus(x_1, x_2)) = x_1 + x_2 4.67/2.16 POL(s(x_1)) = x_1 4.67/2.16 4.67/2.16 4.67/2.16 4.67/2.16 4.67/2.16 ---------------------------------------- 4.67/2.16 4.67/2.16 (4) 4.67/2.16 Obligation: 4.67/2.16 Equational rewrite system: 4.67/2.16 The TRS R consists of the following rules: 4.67/2.16 4.67/2.16 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.16 plus(x, 0) -> x 4.67/2.16 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.16 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.16 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.16 intlist(nil) -> nil 4.67/2.16 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.16 4.67/2.16 The set E consists of the following equations: 4.67/2.16 4.67/2.16 plus(x, y) == plus(y, x) 4.67/2.16 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.16 4.67/2.16 4.67/2.16 ---------------------------------------- 4.67/2.16 4.67/2.16 (5) EquationalDependencyPairsProof (EQUIVALENT) 4.67/2.16 Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: 4.67/2.16 The TRS P consists of the following rules: 4.67/2.16 4.67/2.16 S^1(cons(x, xs)) -> PLUS(x, S(xs)) 4.67/2.16 S^1(cons(x, xs)) -> S^1(xs) 4.67/2.16 PLUS(x, s(y)) -> PLUS(x, y) 4.67/2.16 INT(0, s(y)) -> INT(s(0), s(y)) 4.67/2.16 INT(s(x), s(y)) -> INTLIST(int(x, y)) 4.67/2.16 INT(s(x), s(y)) -> INT(x, y) 4.67/2.16 INTLIST(cons(x, y)) -> INTLIST(y) 4.67/2.16 PLUS(plus(x, s(y)), ext) -> PLUS(s(plus(x, y)), ext) 4.67/2.16 PLUS(plus(x, s(y)), ext) -> PLUS(x, y) 4.67/2.16 4.67/2.16 The TRS R consists of the following rules: 4.67/2.16 4.67/2.16 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.16 plus(x, 0) -> x 4.67/2.16 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.16 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.16 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.16 intlist(nil) -> nil 4.67/2.16 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.16 plus(plus(x, s(y)), ext) -> plus(s(plus(x, y)), ext) 4.67/2.16 4.67/2.16 The set E consists of the following equations: 4.67/2.16 4.67/2.16 plus(x, y) == plus(y, x) 4.67/2.16 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.16 4.67/2.16 The set E# consists of the following equations: 4.67/2.16 4.67/2.16 PLUS(x, y) == PLUS(y, x) 4.67/2.16 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 4.67/2.16 4.67/2.16 We have to consider all minimal (P,E#,R,E)-chains 4.67/2.16 4.67/2.16 ---------------------------------------- 4.67/2.16 4.67/2.16 (6) 4.67/2.16 Obligation: 4.67/2.16 The TRS P consists of the following rules: 4.67/2.16 4.67/2.16 S^1(cons(x, xs)) -> PLUS(x, S(xs)) 4.67/2.16 S^1(cons(x, xs)) -> S^1(xs) 4.67/2.16 PLUS(x, s(y)) -> PLUS(x, y) 4.67/2.16 INT(0, s(y)) -> INT(s(0), s(y)) 4.67/2.16 INT(s(x), s(y)) -> INTLIST(int(x, y)) 4.67/2.16 INT(s(x), s(y)) -> INT(x, y) 4.67/2.16 INTLIST(cons(x, y)) -> INTLIST(y) 4.67/2.16 PLUS(plus(x, s(y)), ext) -> PLUS(s(plus(x, y)), ext) 4.67/2.16 PLUS(plus(x, s(y)), ext) -> PLUS(x, y) 4.67/2.16 4.67/2.16 The TRS R consists of the following rules: 4.67/2.16 4.67/2.16 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.16 plus(x, 0) -> x 4.67/2.16 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.16 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.16 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.16 intlist(nil) -> nil 4.67/2.16 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.16 plus(plus(x, s(y)), ext) -> plus(s(plus(x, y)), ext) 4.67/2.16 4.67/2.16 The set E consists of the following equations: 4.67/2.16 4.67/2.16 plus(x, y) == plus(y, x) 4.67/2.16 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.16 4.67/2.16 The set E# consists of the following equations: 4.67/2.16 4.67/2.16 PLUS(x, y) == PLUS(y, x) 4.67/2.16 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 4.67/2.16 4.67/2.16 We have to consider all minimal (P,E#,R,E)-chains 4.67/2.16 ---------------------------------------- 4.67/2.16 4.67/2.16 (7) EDependencyGraphProof (EQUIVALENT) 4.67/2.16 The approximation of the Equational Dependency Graph [DA_STEIN] contains 4 SCCs with 2 less nodes. 4.67/2.16 ---------------------------------------- 4.67/2.16 4.67/2.16 (8) 4.67/2.16 Complex Obligation (AND) 4.67/2.16 4.67/2.16 ---------------------------------------- 4.67/2.16 4.67/2.16 (9) 4.67/2.16 Obligation: 4.67/2.16 The TRS P consists of the following rules: 4.67/2.16 4.67/2.16 INTLIST(cons(x, y)) -> INTLIST(y) 4.67/2.16 4.67/2.16 The TRS R consists of the following rules: 4.67/2.16 4.67/2.16 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.16 plus(x, 0) -> x 4.67/2.16 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.16 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.16 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.16 intlist(nil) -> nil 4.67/2.16 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.17 plus(plus(x, s(y)), ext) -> plus(s(plus(x, y)), ext) 4.67/2.17 4.67/2.17 The set E consists of the following equations: 4.67/2.17 4.67/2.17 plus(x, y) == plus(y, x) 4.67/2.17 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.17 4.67/2.17 The set E# consists of the following equations: 4.67/2.17 4.67/2.17 PLUS(x, y) == PLUS(y, x) 4.67/2.17 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 4.67/2.17 4.67/2.17 We have to consider all minimal (P,E#,R,E)-chains 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (10) ESharpUsableEquationsProof (EQUIVALENT) 4.67/2.17 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 4.67/2.17 PLUS(x, y) == PLUS(y, x) 4.67/2.17 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 4.67/2.17 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (11) 4.67/2.17 Obligation: 4.67/2.17 The TRS P consists of the following rules: 4.67/2.17 4.67/2.17 INTLIST(cons(x, y)) -> INTLIST(y) 4.67/2.17 4.67/2.17 The TRS R consists of the following rules: 4.67/2.17 4.67/2.17 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.17 plus(x, 0) -> x 4.67/2.17 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.17 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.17 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.17 intlist(nil) -> nil 4.67/2.17 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.17 plus(plus(x, s(y)), ext) -> plus(s(plus(x, y)), ext) 4.67/2.17 4.67/2.17 The set E consists of the following equations: 4.67/2.17 4.67/2.17 plus(x, y) == plus(y, x) 4.67/2.17 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.17 4.67/2.17 E# is empty. 4.67/2.17 We have to consider all minimal (P,E#,R,E)-chains 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (12) EUsableRulesReductionPairsProof (EQUIVALENT) 4.67/2.17 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. 4.67/2.17 4.67/2.17 The following dependency pairs can be deleted: 4.67/2.17 4.67/2.17 INTLIST(cons(x, y)) -> INTLIST(y) 4.67/2.17 The following rules are removed from R: 4.67/2.17 4.67/2.17 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.17 plus(x, 0) -> x 4.67/2.17 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.17 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.17 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.17 intlist(nil) -> nil 4.67/2.17 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.17 plus(plus(x, s(y)), ext) -> plus(s(plus(x, y)), ext) 4.67/2.17 The following equations are removed from E: 4.67/2.17 4.67/2.17 plus(x, y) == plus(y, x) 4.67/2.17 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.17 Used ordering: POLO with Polynomial interpretation [POLO]: 4.67/2.17 4.67/2.17 POL(INTLIST(x_1)) = 3*x_1 4.67/2.17 POL(cons(x_1, x_2)) = x_1 + 3*x_2 4.67/2.17 4.67/2.17 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (13) 4.67/2.17 Obligation: 4.67/2.17 P is empty. 4.67/2.17 R is empty. 4.67/2.17 E is empty. 4.67/2.17 E# is empty. 4.67/2.17 We have to consider all minimal (P,E#,R,E)-chains 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (14) PisEmptyProof (EQUIVALENT) 4.67/2.17 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (15) 4.67/2.17 YES 4.67/2.17 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (16) 4.67/2.17 Obligation: 4.67/2.17 The TRS P consists of the following rules: 4.67/2.17 4.67/2.17 INT(0, s(y)) -> INT(s(0), s(y)) 4.67/2.17 INT(s(x), s(y)) -> INT(x, y) 4.67/2.17 4.67/2.17 The TRS R consists of the following rules: 4.67/2.17 4.67/2.17 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.17 plus(x, 0) -> x 4.67/2.17 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.17 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.17 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.17 intlist(nil) -> nil 4.67/2.17 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.17 plus(plus(x, s(y)), ext) -> plus(s(plus(x, y)), ext) 4.67/2.17 4.67/2.17 The set E consists of the following equations: 4.67/2.17 4.67/2.17 plus(x, y) == plus(y, x) 4.67/2.17 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.17 4.67/2.17 The set E# consists of the following equations: 4.67/2.17 4.67/2.17 PLUS(x, y) == PLUS(y, x) 4.67/2.17 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 4.67/2.17 4.67/2.17 We have to consider all minimal (P,E#,R,E)-chains 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (17) ESharpUsableEquationsProof (EQUIVALENT) 4.67/2.17 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 4.67/2.17 PLUS(x, y) == PLUS(y, x) 4.67/2.17 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 4.67/2.17 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (18) 4.67/2.17 Obligation: 4.67/2.17 The TRS P consists of the following rules: 4.67/2.17 4.67/2.17 INT(0, s(y)) -> INT(s(0), s(y)) 4.67/2.17 INT(s(x), s(y)) -> INT(x, y) 4.67/2.17 4.67/2.17 The TRS R consists of the following rules: 4.67/2.17 4.67/2.17 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.17 plus(x, 0) -> x 4.67/2.17 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.17 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.17 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.17 intlist(nil) -> nil 4.67/2.17 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.17 plus(plus(x, s(y)), ext) -> plus(s(plus(x, y)), ext) 4.67/2.17 4.67/2.17 The set E consists of the following equations: 4.67/2.17 4.67/2.17 plus(x, y) == plus(y, x) 4.67/2.17 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.17 4.67/2.17 E# is empty. 4.67/2.17 We have to consider all minimal (P,E#,R,E)-chains 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (19) EUsableRulesReductionPairsProof (EQUIVALENT) 4.67/2.17 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. 4.67/2.17 4.67/2.17 No dependency pairs are removed. 4.67/2.17 4.67/2.17 The following rules are removed from R: 4.67/2.17 4.67/2.17 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.17 plus(x, 0) -> x 4.67/2.17 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.17 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.17 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.17 intlist(nil) -> nil 4.67/2.17 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.17 plus(plus(x, s(y)), ext) -> plus(s(plus(x, y)), ext) 4.67/2.17 The following equations are removed from E: 4.67/2.17 4.67/2.17 plus(x, y) == plus(y, x) 4.67/2.17 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.17 Used ordering: POLO with Polynomial interpretation [POLO]: 4.67/2.17 4.67/2.17 POL(0) = 0 4.67/2.17 POL(INT(x_1, x_2)) = x_1 + 3*x_2 4.67/2.17 POL(s(x_1)) = x_1 4.67/2.17 4.67/2.17 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (20) 4.67/2.17 Obligation: 4.67/2.17 The TRS P consists of the following rules: 4.67/2.17 4.67/2.17 INT(0, s(y)) -> INT(s(0), s(y)) 4.67/2.17 INT(s(x), s(y)) -> INT(x, y) 4.67/2.17 4.67/2.17 R is empty. 4.67/2.17 E is empty. 4.67/2.17 E# is empty. 4.67/2.17 We have to consider all minimal (P,E#,R,E)-chains 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (21) EDPProblemToQDPProblemProof (EQUIVALENT) 4.67/2.17 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. 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (22) 4.67/2.17 Obligation: 4.67/2.17 Q DP problem: 4.67/2.17 The TRS P consists of the following rules: 4.67/2.17 4.67/2.17 INT(0, s(y)) -> INT(s(0), s(y)) 4.67/2.17 INT(s(x), s(y)) -> INT(x, y) 4.67/2.17 4.67/2.17 R is empty. 4.67/2.17 Q is empty. 4.67/2.17 We have to consider all minimal (P,Q,R)-chains. 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (23) QDPSizeChangeProof (EQUIVALENT) 4.67/2.17 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.67/2.17 4.67/2.17 From the DPs we obtained the following set of size-change graphs: 4.67/2.17 *INT(s(x), s(y)) -> INT(x, y) 4.67/2.17 The graph contains the following edges 1 > 1, 2 > 2 4.67/2.17 4.67/2.17 4.67/2.17 *INT(0, s(y)) -> INT(s(0), s(y)) 4.67/2.17 The graph contains the following edges 2 >= 2 4.67/2.17 4.67/2.17 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (24) 4.67/2.17 YES 4.67/2.17 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (25) 4.67/2.17 Obligation: 4.67/2.17 The TRS P consists of the following rules: 4.67/2.17 4.67/2.17 PLUS(plus(x, s(y)), ext) -> PLUS(s(plus(x, y)), ext) 4.67/2.17 PLUS(plus(x, s(y)), ext) -> PLUS(x, y) 4.67/2.17 PLUS(x, s(y)) -> PLUS(x, y) 4.67/2.17 4.67/2.17 The TRS R consists of the following rules: 4.67/2.17 4.67/2.17 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.17 plus(x, 0) -> x 4.67/2.17 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.17 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.17 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.17 intlist(nil) -> nil 4.67/2.17 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.17 plus(plus(x, s(y)), ext) -> plus(s(plus(x, y)), ext) 4.67/2.17 4.67/2.17 The set E consists of the following equations: 4.67/2.17 4.67/2.17 plus(x, y) == plus(y, x) 4.67/2.17 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.17 4.67/2.17 The set E# consists of the following equations: 4.67/2.17 4.67/2.17 PLUS(x, y) == PLUS(y, x) 4.67/2.17 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 4.67/2.17 4.67/2.17 We have to consider all minimal (P,E#,R,E)-chains 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (26) EUsableRulesReductionPairsProof (EQUIVALENT) 4.67/2.17 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. 4.67/2.17 4.67/2.17 No dependency pairs are removed. 4.67/2.17 4.67/2.17 The following rules are removed from R: 4.67/2.17 4.67/2.17 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.17 plus(x, 0) -> x 4.67/2.17 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.17 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.17 intlist(nil) -> nil 4.67/2.17 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.17 No equations are removed from E. 4.67/2.17 4.67/2.17 Used ordering: POLO with Polynomial interpretation [POLO]: 4.67/2.17 4.67/2.17 POL(0) = 0 4.67/2.17 POL(PLUS(x_1, x_2)) = x_1 + x_2 4.67/2.17 POL(plus(x_1, x_2)) = x_1 + x_2 4.67/2.17 POL(s(x_1)) = x_1 4.67/2.17 4.67/2.17 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (27) 4.67/2.17 Obligation: 4.67/2.17 The TRS P consists of the following rules: 4.67/2.17 4.67/2.17 PLUS(plus(x, s(y)), ext) -> PLUS(s(plus(x, y)), ext) 4.67/2.17 PLUS(plus(x, s(y)), ext) -> PLUS(x, y) 4.67/2.17 PLUS(x, s(y)) -> PLUS(x, y) 4.67/2.17 4.67/2.17 The TRS R consists of the following rules: 4.67/2.17 4.67/2.17 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.17 plus(plus(x, s(y)), ext) -> plus(s(plus(x, y)), ext) 4.67/2.17 4.67/2.17 The set E consists of the following equations: 4.67/2.17 4.67/2.17 plus(x, y) == plus(y, x) 4.67/2.17 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.17 4.67/2.17 The set E# consists of the following equations: 4.67/2.17 4.67/2.17 PLUS(x, y) == PLUS(y, x) 4.67/2.17 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 4.67/2.17 4.67/2.17 We have to consider all minimal (P,E#,R,E)-chains 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (28) ERuleRemovalProof (EQUIVALENT) 4.67/2.17 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. 4.67/2.17 4.67/2.17 Strictly oriented dependency pairs: 4.67/2.17 4.67/2.17 PLUS(plus(x, s(y)), ext) -> PLUS(x, y) 4.67/2.17 PLUS(x, s(y)) -> PLUS(x, y) 4.67/2.17 4.67/2.17 4.67/2.17 Used ordering: POLO with Polynomial interpretation [POLO]: 4.67/2.17 4.67/2.17 POL(PLUS(x_1, x_2)) = x_1 + x_2 4.67/2.17 POL(plus(x_1, x_2)) = 2 + x_1 + x_2 4.67/2.17 POL(s(x_1)) = 2 + x_1 4.67/2.17 4.67/2.17 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (29) 4.67/2.17 Obligation: 4.67/2.17 The TRS P consists of the following rules: 4.67/2.17 4.67/2.17 PLUS(plus(x, s(y)), ext) -> PLUS(s(plus(x, y)), ext) 4.67/2.17 4.67/2.17 The TRS R consists of the following rules: 4.67/2.17 4.67/2.17 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.17 plus(plus(x, s(y)), ext) -> plus(s(plus(x, y)), ext) 4.67/2.17 4.67/2.17 The set E consists of the following equations: 4.67/2.17 4.67/2.17 plus(x, y) == plus(y, x) 4.67/2.17 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.17 4.67/2.17 The set E# consists of the following equations: 4.67/2.17 4.67/2.17 PLUS(x, y) == PLUS(y, x) 4.67/2.17 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 4.67/2.17 4.67/2.17 We have to consider all minimal (P,E#,R,E)-chains 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (30) EDPPoloProof (EQUIVALENT) 4.67/2.17 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. 4.67/2.17 4.67/2.17 4.67/2.17 PLUS(plus(x, s(y)), ext) -> PLUS(s(plus(x, y)), ext) 4.67/2.17 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 4.67/2.17 4.67/2.17 4.67/2.17 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.17 plus(plus(x, s(y)), ext) -> plus(s(plus(x, y)), ext) 4.67/2.17 We had to orient the following equations of E# equivalently. 4.67/2.17 4.67/2.17 4.67/2.17 PLUS(x, y) == PLUS(y, x) 4.67/2.17 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 4.67/2.17 With the implicit AFS we had to orient the following usable equations of E equivalently. 4.67/2.17 4.67/2.17 4.67/2.17 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.17 plus(x, y) == plus(y, x) 4.67/2.17 Used ordering: POLO with Polynomial interpretation [POLO]: 4.67/2.17 4.67/2.17 POL(PLUS(x_1, x_2)) = x_1 + x_2 4.67/2.17 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 4.67/2.17 POL(s(x_1)) = 0 4.67/2.17 4.67/2.17 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (31) 4.67/2.17 Obligation: 4.67/2.17 P is empty. 4.67/2.17 The TRS R consists of the following rules: 4.67/2.17 4.67/2.17 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.17 plus(plus(x, s(y)), ext) -> plus(s(plus(x, y)), ext) 4.67/2.17 4.67/2.17 The set E consists of the following equations: 4.67/2.17 4.67/2.17 plus(x, y) == plus(y, x) 4.67/2.17 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.17 4.67/2.17 The set E# consists of the following equations: 4.67/2.17 4.67/2.17 PLUS(x, y) == PLUS(y, x) 4.67/2.17 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 4.67/2.17 4.67/2.17 We have to consider all minimal (P,E#,R,E)-chains 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (32) PisEmptyProof (EQUIVALENT) 4.67/2.17 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (33) 4.67/2.17 YES 4.67/2.17 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (34) 4.67/2.17 Obligation: 4.67/2.17 The TRS P consists of the following rules: 4.67/2.17 4.67/2.17 S^1(cons(x, xs)) -> S^1(xs) 4.67/2.17 4.67/2.17 The TRS R consists of the following rules: 4.67/2.17 4.67/2.17 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.17 plus(x, 0) -> x 4.67/2.17 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.17 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.17 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.17 intlist(nil) -> nil 4.67/2.17 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.17 plus(plus(x, s(y)), ext) -> plus(s(plus(x, y)), ext) 4.67/2.17 4.67/2.17 The set E consists of the following equations: 4.67/2.17 4.67/2.17 plus(x, y) == plus(y, x) 4.67/2.17 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.17 4.67/2.17 The set E# consists of the following equations: 4.67/2.17 4.67/2.17 PLUS(x, y) == PLUS(y, x) 4.67/2.17 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 4.67/2.17 4.67/2.17 We have to consider all minimal (P,E#,R,E)-chains 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (35) ESharpUsableEquationsProof (EQUIVALENT) 4.67/2.17 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 4.67/2.17 PLUS(x, y) == PLUS(y, x) 4.67/2.17 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 4.67/2.17 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (36) 4.67/2.17 Obligation: 4.67/2.17 The TRS P consists of the following rules: 4.67/2.17 4.67/2.17 S^1(cons(x, xs)) -> S^1(xs) 4.67/2.17 4.67/2.17 The TRS R consists of the following rules: 4.67/2.17 4.67/2.17 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.17 plus(x, 0) -> x 4.67/2.17 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.17 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.17 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.17 intlist(nil) -> nil 4.67/2.17 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.17 plus(plus(x, s(y)), ext) -> plus(s(plus(x, y)), ext) 4.67/2.17 4.67/2.17 The set E consists of the following equations: 4.67/2.17 4.67/2.17 plus(x, y) == plus(y, x) 4.67/2.17 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.17 4.67/2.17 E# is empty. 4.67/2.17 We have to consider all minimal (P,E#,R,E)-chains 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (37) EUsableRulesReductionPairsProof (EQUIVALENT) 4.67/2.17 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. 4.67/2.17 4.67/2.17 The following dependency pairs can be deleted: 4.67/2.17 4.67/2.17 S^1(cons(x, xs)) -> S^1(xs) 4.67/2.17 The following rules are removed from R: 4.67/2.17 4.67/2.17 S(cons(x, xs)) -> plus(x, S(xs)) 4.67/2.17 plus(x, 0) -> x 4.67/2.17 plus(x, s(y)) -> s(plus(x, y)) 4.67/2.17 int(0, s(y)) -> cons(0, int(s(0), s(y))) 4.67/2.17 int(s(x), s(y)) -> intlist(int(x, y)) 4.67/2.17 intlist(nil) -> nil 4.67/2.17 intlist(cons(x, y)) -> cons(s(x), intlist(y)) 4.67/2.17 plus(plus(x, s(y)), ext) -> plus(s(plus(x, y)), ext) 4.67/2.17 The following equations are removed from E: 4.67/2.17 4.67/2.17 plus(x, y) == plus(y, x) 4.67/2.17 plus(plus(x, y), z) == plus(x, plus(y, z)) 4.67/2.17 Used ordering: POLO with Polynomial interpretation [POLO]: 4.67/2.17 4.67/2.17 POL(S^1(x_1)) = 3*x_1 4.67/2.17 POL(cons(x_1, x_2)) = x_1 + 3*x_2 4.67/2.17 4.67/2.17 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (38) 4.67/2.17 Obligation: 4.67/2.17 P is empty. 4.67/2.17 R is empty. 4.67/2.17 E is empty. 4.67/2.17 E# is empty. 4.67/2.17 We have to consider all minimal (P,E#,R,E)-chains 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (39) PisEmptyProof (EQUIVALENT) 4.67/2.17 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 4.67/2.17 ---------------------------------------- 4.67/2.17 4.67/2.17 (40) 4.67/2.17 YES 4.67/2.19 EOF