8.66/3.80 YES 8.66/3.80 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 8.66/3.80 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.66/3.80 8.66/3.80 8.66/3.80 Termination of the given ETRS could be proven: 8.66/3.80 8.66/3.80 (0) ETRS 8.66/3.80 (1) RRRPoloETRSProof [EQUIVALENT, 219 ms] 8.66/3.80 (2) ETRS 8.66/3.80 (3) RRRPoloETRSProof [EQUIVALENT, 63 ms] 8.66/3.80 (4) ETRS 8.66/3.80 (5) RRRPoloETRSProof [EQUIVALENT, 50 ms] 8.66/3.80 (6) ETRS 8.66/3.80 (7) EquationalDependencyPairsProof [EQUIVALENT, 107 ms] 8.66/3.80 (8) EDP 8.66/3.80 (9) EUsableRulesReductionPairsProof [EQUIVALENT, 25 ms] 8.66/3.80 (10) EDP 8.66/3.80 (11) ERuleRemovalProof [EQUIVALENT, 20 ms] 8.66/3.80 (12) EDP 8.66/3.80 (13) EDPPoloProof [EQUIVALENT, 3 ms] 8.66/3.80 (14) EDP 8.66/3.80 (15) PisEmptyProof [EQUIVALENT, 0 ms] 8.66/3.80 (16) YES 8.66/3.80 8.66/3.80 8.66/3.80 ---------------------------------------- 8.66/3.80 8.66/3.80 (0) 8.66/3.80 Obligation: 8.66/3.80 Equational rewrite system: 8.66/3.80 The TRS R consists of the following rules: 8.66/3.80 8.66/3.80 zero(0) -> 0 8.66/3.80 plus(x, 0) -> x 8.66/3.80 plus(zero(x), zero(y)) -> zero(plus(x, y)) 8.66/3.80 plus(zero(x), un(y)) -> un(plus(x, y)) 8.66/3.80 plus(zero(x), j(y)) -> j(plus(x, y)) 8.66/3.80 plus(un(x), j(y)) -> zero(plus(x, y)) 8.66/3.80 plus(un(x), un(y)) -> j(plus(x, plus(y, un(0)))) 8.66/3.80 plus(j(x), j(y)) -> un(plus(x, plus(y, j(0)))) 8.66/3.80 minus(x, y) -> plus(x, neg(y)) 8.66/3.80 neg(0) -> 0 8.66/3.80 neg(zero(x)) -> zero(neg(x)) 8.66/3.80 neg(un(x)) -> j(neg(x)) 8.66/3.80 neg(j(x)) -> un(neg(x)) 8.66/3.80 times(x, 0) -> 0 8.66/3.80 times(x, times(0, z)) -> times(0, z) 8.66/3.80 times(x, zero(y)) -> zero(times(x, y)) 8.66/3.80 times(x, times(zero(y), z)) -> times(zero(times(x, y)), z) 8.66/3.80 times(x, un(y)) -> plus(x, zero(times(x, y))) 8.66/3.80 times(x, times(un(y), z)) -> times(plus(x, zero(times(x, y))), z) 8.66/3.80 times(x, j(y)) -> plus(zero(times(x, y)), neg(x)) 8.66/3.80 times(x, times(j(y), z)) -> times(plus(zero(times(x, y)), neg(x)), z) 8.66/3.80 8.66/3.80 The set E consists of the following equations: 8.66/3.80 8.66/3.80 plus(x, y) == plus(y, x) 8.66/3.80 times(x, y) == times(y, x) 8.66/3.80 plus(plus(x, y), z) == plus(x, plus(y, z)) 8.66/3.80 times(times(x, y), z) == times(x, times(y, z)) 8.66/3.80 8.66/3.80 8.66/3.80 ---------------------------------------- 8.66/3.80 8.66/3.80 (1) RRRPoloETRSProof (EQUIVALENT) 8.66/3.80 The following E TRS is given: Equational rewrite system: 8.66/3.80 The TRS R consists of the following rules: 8.66/3.80 8.66/3.80 zero(0) -> 0 8.66/3.80 plus(x, 0) -> x 8.66/3.80 plus(zero(x), zero(y)) -> zero(plus(x, y)) 8.66/3.80 plus(zero(x), un(y)) -> un(plus(x, y)) 8.66/3.80 plus(zero(x), j(y)) -> j(plus(x, y)) 8.66/3.80 plus(un(x), j(y)) -> zero(plus(x, y)) 8.66/3.80 plus(un(x), un(y)) -> j(plus(x, plus(y, un(0)))) 8.66/3.80 plus(j(x), j(y)) -> un(plus(x, plus(y, j(0)))) 8.66/3.80 minus(x, y) -> plus(x, neg(y)) 8.66/3.80 neg(0) -> 0 8.66/3.80 neg(zero(x)) -> zero(neg(x)) 8.66/3.80 neg(un(x)) -> j(neg(x)) 8.66/3.80 neg(j(x)) -> un(neg(x)) 8.66/3.80 times(x, 0) -> 0 8.66/3.80 times(x, times(0, z)) -> times(0, z) 8.66/3.80 times(x, zero(y)) -> zero(times(x, y)) 8.66/3.80 times(x, times(zero(y), z)) -> times(zero(times(x, y)), z) 8.66/3.80 times(x, un(y)) -> plus(x, zero(times(x, y))) 8.66/3.80 times(x, times(un(y), z)) -> times(plus(x, zero(times(x, y))), z) 8.66/3.80 times(x, j(y)) -> plus(zero(times(x, y)), neg(x)) 8.66/3.80 times(x, times(j(y), z)) -> times(plus(zero(times(x, y)), neg(x)), z) 8.66/3.80 8.66/3.80 The set E consists of the following equations: 8.66/3.80 8.66/3.80 plus(x, y) == plus(y, x) 8.66/3.80 times(x, y) == times(y, x) 8.66/3.80 plus(plus(x, y), z) == plus(x, plus(y, z)) 8.66/3.80 times(times(x, y), z) == times(x, times(y, z)) 8.66/3.80 8.66/3.80 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 8.66/3.80 8.66/3.80 plus(un(x), j(y)) -> zero(plus(x, y)) 8.66/3.80 times(x, un(y)) -> plus(x, zero(times(x, y))) 8.66/3.80 times(x, times(un(y), z)) -> times(plus(x, zero(times(x, y))), z) 8.66/3.80 times(x, j(y)) -> plus(zero(times(x, y)), neg(x)) 8.66/3.80 times(x, times(j(y), z)) -> times(plus(zero(times(x, y)), neg(x)), z) 8.66/3.80 Used ordering: 8.66/3.80 Polynomial interpretation [POLO]: 8.66/3.80 8.66/3.80 POL(0) = 0 8.66/3.80 POL(j(x_1)) = 1 + x_1 8.66/3.80 POL(minus(x_1, x_2)) = x_1 + x_2 8.66/3.80 POL(neg(x_1)) = x_1 8.66/3.80 POL(plus(x_1, x_2)) = x_1 + x_2 8.66/3.80 POL(times(x_1, x_2)) = x_1 + 2*x_1*x_2 + x_2 8.66/3.80 POL(un(x_1)) = 1 + x_1 8.66/3.80 POL(zero(x_1)) = x_1 8.66/3.80 8.66/3.80 8.66/3.80 8.66/3.80 8.66/3.80 ---------------------------------------- 8.66/3.80 8.66/3.80 (2) 8.66/3.80 Obligation: 8.66/3.80 Equational rewrite system: 8.66/3.80 The TRS R consists of the following rules: 8.66/3.80 8.66/3.80 zero(0) -> 0 8.66/3.80 plus(x, 0) -> x 8.66/3.80 plus(zero(x), zero(y)) -> zero(plus(x, y)) 8.66/3.80 plus(zero(x), un(y)) -> un(plus(x, y)) 8.66/3.80 plus(zero(x), j(y)) -> j(plus(x, y)) 8.66/3.80 plus(un(x), un(y)) -> j(plus(x, plus(y, un(0)))) 8.66/3.81 plus(j(x), j(y)) -> un(plus(x, plus(y, j(0)))) 8.66/3.81 minus(x, y) -> plus(x, neg(y)) 8.66/3.81 neg(0) -> 0 8.66/3.81 neg(zero(x)) -> zero(neg(x)) 8.66/3.81 neg(un(x)) -> j(neg(x)) 8.66/3.81 neg(j(x)) -> un(neg(x)) 8.66/3.81 times(x, 0) -> 0 8.66/3.81 times(x, times(0, z)) -> times(0, z) 8.66/3.81 times(x, zero(y)) -> zero(times(x, y)) 8.66/3.81 times(x, times(zero(y), z)) -> times(zero(times(x, y)), z) 8.66/3.81 8.66/3.81 The set E consists of the following equations: 8.66/3.81 8.66/3.81 plus(x, y) == plus(y, x) 8.66/3.81 times(x, y) == times(y, x) 8.66/3.81 plus(plus(x, y), z) == plus(x, plus(y, z)) 8.66/3.81 times(times(x, y), z) == times(x, times(y, z)) 8.66/3.81 8.66/3.81 8.66/3.81 ---------------------------------------- 8.66/3.81 8.66/3.81 (3) RRRPoloETRSProof (EQUIVALENT) 8.66/3.81 The following E TRS is given: Equational rewrite system: 8.66/3.81 The TRS R consists of the following rules: 8.66/3.81 8.66/3.81 zero(0) -> 0 8.66/3.81 plus(x, 0) -> x 8.66/3.81 plus(zero(x), zero(y)) -> zero(plus(x, y)) 8.66/3.81 plus(zero(x), un(y)) -> un(plus(x, y)) 8.66/3.81 plus(zero(x), j(y)) -> j(plus(x, y)) 8.66/3.81 plus(un(x), un(y)) -> j(plus(x, plus(y, un(0)))) 8.66/3.81 plus(j(x), j(y)) -> un(plus(x, plus(y, j(0)))) 8.66/3.81 minus(x, y) -> plus(x, neg(y)) 8.66/3.81 neg(0) -> 0 8.66/3.81 neg(zero(x)) -> zero(neg(x)) 8.66/3.81 neg(un(x)) -> j(neg(x)) 8.66/3.81 neg(j(x)) -> un(neg(x)) 8.66/3.81 times(x, 0) -> 0 8.66/3.81 times(x, times(0, z)) -> times(0, z) 8.66/3.81 times(x, zero(y)) -> zero(times(x, y)) 8.66/3.81 times(x, times(zero(y), z)) -> times(zero(times(x, y)), z) 8.66/3.81 8.66/3.81 The set E consists of the following equations: 8.66/3.81 8.66/3.81 plus(x, y) == plus(y, x) 8.66/3.81 times(x, y) == times(y, x) 8.66/3.81 plus(plus(x, y), z) == plus(x, plus(y, z)) 8.66/3.81 times(times(x, y), z) == times(x, times(y, z)) 8.66/3.81 8.66/3.81 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 8.66/3.81 8.66/3.81 minus(x, y) -> plus(x, neg(y)) 8.66/3.81 neg(un(x)) -> j(neg(x)) 8.66/3.81 neg(j(x)) -> un(neg(x)) 8.66/3.81 Used ordering: 8.66/3.81 Polynomial interpretation [POLO]: 8.66/3.81 8.66/3.81 POL(0) = 0 8.66/3.81 POL(j(x_1)) = 1 + 2*x_1 8.66/3.81 POL(minus(x_1, x_2)) = 3 + x_1 + 3*x_1*x_2 + 3*x_2 8.66/3.81 POL(neg(x_1)) = 2*x_1 8.66/3.81 POL(plus(x_1, x_2)) = x_1 + x_1*x_2 + x_2 8.66/3.81 POL(times(x_1, x_2)) = x_1 + x_2 8.66/3.81 POL(un(x_1)) = 1 + 2*x_1 8.66/3.81 POL(zero(x_1)) = x_1 8.66/3.81 8.66/3.81 8.66/3.81 8.66/3.81 8.66/3.81 ---------------------------------------- 8.66/3.81 8.66/3.81 (4) 8.66/3.81 Obligation: 8.66/3.81 Equational rewrite system: 8.66/3.81 The TRS R consists of the following rules: 8.66/3.81 8.66/3.81 zero(0) -> 0 8.66/3.81 plus(x, 0) -> x 8.66/3.81 plus(zero(x), zero(y)) -> zero(plus(x, y)) 8.66/3.81 plus(zero(x), un(y)) -> un(plus(x, y)) 8.66/3.81 plus(zero(x), j(y)) -> j(plus(x, y)) 8.66/3.81 plus(un(x), un(y)) -> j(plus(x, plus(y, un(0)))) 8.66/3.81 plus(j(x), j(y)) -> un(plus(x, plus(y, j(0)))) 8.66/3.81 neg(0) -> 0 8.66/3.81 neg(zero(x)) -> zero(neg(x)) 8.66/3.81 times(x, 0) -> 0 8.66/3.81 times(x, times(0, z)) -> times(0, z) 8.66/3.81 times(x, zero(y)) -> zero(times(x, y)) 8.66/3.81 times(x, times(zero(y), z)) -> times(zero(times(x, y)), z) 8.66/3.81 8.66/3.81 The set E consists of the following equations: 8.66/3.81 8.66/3.81 plus(x, y) == plus(y, x) 8.66/3.81 times(x, y) == times(y, x) 8.66/3.81 plus(plus(x, y), z) == plus(x, plus(y, z)) 8.66/3.81 times(times(x, y), z) == times(x, times(y, z)) 8.66/3.81 8.66/3.81 8.66/3.81 ---------------------------------------- 8.66/3.81 8.66/3.81 (5) RRRPoloETRSProof (EQUIVALENT) 8.66/3.81 The following E TRS is given: Equational rewrite system: 8.66/3.81 The TRS R consists of the following rules: 8.66/3.81 8.66/3.81 zero(0) -> 0 8.66/3.81 plus(x, 0) -> x 8.66/3.81 plus(zero(x), zero(y)) -> zero(plus(x, y)) 8.66/3.81 plus(zero(x), un(y)) -> un(plus(x, y)) 8.66/3.81 plus(zero(x), j(y)) -> j(plus(x, y)) 8.66/3.81 plus(un(x), un(y)) -> j(plus(x, plus(y, un(0)))) 8.66/3.81 plus(j(x), j(y)) -> un(plus(x, plus(y, j(0)))) 8.66/3.81 neg(0) -> 0 8.66/3.81 neg(zero(x)) -> zero(neg(x)) 8.66/3.81 times(x, 0) -> 0 8.66/3.81 times(x, times(0, z)) -> times(0, z) 8.66/3.81 times(x, zero(y)) -> zero(times(x, y)) 8.66/3.81 times(x, times(zero(y), z)) -> times(zero(times(x, y)), z) 8.66/3.81 8.66/3.81 The set E consists of the following equations: 8.66/3.81 8.66/3.81 plus(x, y) == plus(y, x) 8.66/3.81 times(x, y) == times(y, x) 8.66/3.81 plus(plus(x, y), z) == plus(x, plus(y, z)) 8.66/3.81 times(times(x, y), z) == times(x, times(y, z)) 8.66/3.81 8.66/3.81 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 8.66/3.81 8.66/3.81 zero(0) -> 0 8.66/3.81 plus(zero(x), zero(y)) -> zero(plus(x, y)) 8.66/3.81 plus(zero(x), un(y)) -> un(plus(x, y)) 8.66/3.81 plus(zero(x), j(y)) -> j(plus(x, y)) 8.66/3.81 neg(0) -> 0 8.66/3.81 neg(zero(x)) -> zero(neg(x)) 8.66/3.81 times(x, 0) -> 0 8.66/3.81 times(x, times(0, z)) -> times(0, z) 8.66/3.81 times(x, zero(y)) -> zero(times(x, y)) 8.66/3.81 times(x, times(zero(y), z)) -> times(zero(times(x, y)), z) 8.66/3.81 Used ordering: 8.66/3.81 Polynomial interpretation [POLO]: 8.66/3.81 8.66/3.81 POL(0) = 0 8.66/3.81 POL(j(x_1)) = x_1 8.66/3.81 POL(neg(x_1)) = 3 + 3*x_1^2 8.66/3.81 POL(plus(x_1, x_2)) = x_1 + x_2 8.66/3.81 POL(times(x_1, x_2)) = 2 + 2*x_1 + x_1*x_2 + 2*x_2 8.66/3.81 POL(un(x_1)) = x_1 8.66/3.81 POL(zero(x_1)) = 1 + x_1 8.66/3.81 8.66/3.81 8.66/3.81 8.66/3.81 8.66/3.81 ---------------------------------------- 8.66/3.81 8.66/3.81 (6) 8.66/3.81 Obligation: 8.66/3.81 Equational rewrite system: 8.66/3.81 The TRS R consists of the following rules: 8.66/3.81 8.66/3.81 plus(x, 0) -> x 8.66/3.81 plus(un(x), un(y)) -> j(plus(x, plus(y, un(0)))) 8.66/3.81 plus(j(x), j(y)) -> un(plus(x, plus(y, j(0)))) 8.66/3.81 8.66/3.81 The set E consists of the following equations: 8.66/3.81 8.66/3.81 plus(x, y) == plus(y, x) 8.66/3.81 times(x, y) == times(y, x) 8.66/3.81 plus(plus(x, y), z) == plus(x, plus(y, z)) 8.66/3.81 times(times(x, y), z) == times(x, times(y, z)) 8.66/3.81 8.66/3.81 8.66/3.81 ---------------------------------------- 8.66/3.81 8.66/3.81 (7) EquationalDependencyPairsProof (EQUIVALENT) 8.66/3.81 Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: 8.66/3.81 The TRS P consists of the following rules: 8.66/3.81 8.66/3.81 PLUS(un(x), un(y)) -> PLUS(x, plus(y, un(0))) 8.66/3.81 PLUS(un(x), un(y)) -> PLUS(y, un(0)) 8.66/3.81 PLUS(j(x), j(y)) -> PLUS(x, plus(y, j(0))) 8.66/3.81 PLUS(j(x), j(y)) -> PLUS(y, j(0)) 8.66/3.81 PLUS(plus(un(x), un(y)), ext) -> PLUS(j(plus(x, plus(y, un(0)))), ext) 8.66/3.81 PLUS(plus(un(x), un(y)), ext) -> PLUS(x, plus(y, un(0))) 8.66/3.81 PLUS(plus(un(x), un(y)), ext) -> PLUS(y, un(0)) 8.66/3.81 PLUS(plus(j(x), j(y)), ext) -> PLUS(un(plus(x, plus(y, j(0)))), ext) 8.66/3.81 PLUS(plus(j(x), j(y)), ext) -> PLUS(x, plus(y, j(0))) 8.66/3.81 PLUS(plus(j(x), j(y)), ext) -> PLUS(y, j(0)) 8.66/3.81 8.66/3.81 The TRS R consists of the following rules: 8.66/3.81 8.66/3.81 plus(x, 0) -> x 8.66/3.81 plus(un(x), un(y)) -> j(plus(x, plus(y, un(0)))) 8.66/3.81 plus(j(x), j(y)) -> un(plus(x, plus(y, j(0)))) 8.66/3.81 plus(plus(un(x), un(y)), ext) -> plus(j(plus(x, plus(y, un(0)))), ext) 8.66/3.81 plus(plus(j(x), j(y)), ext) -> plus(un(plus(x, plus(y, j(0)))), ext) 8.66/3.81 8.66/3.81 The set E consists of the following equations: 8.66/3.81 8.66/3.81 plus(x, y) == plus(y, x) 8.66/3.81 times(x, y) == times(y, x) 8.66/3.81 plus(plus(x, y), z) == plus(x, plus(y, z)) 8.66/3.81 times(times(x, y), z) == times(x, times(y, z)) 8.66/3.81 8.66/3.81 The set E# consists of the following equations: 8.66/3.81 8.66/3.81 PLUS(x, y) == PLUS(y, x) 8.66/3.81 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 8.66/3.81 8.66/3.81 We have to consider all minimal (P,E#,R,E)-chains 8.66/3.81 8.66/3.81 ---------------------------------------- 8.66/3.81 8.66/3.81 (8) 8.66/3.81 Obligation: 8.66/3.81 The TRS P consists of the following rules: 8.66/3.81 8.66/3.81 PLUS(un(x), un(y)) -> PLUS(x, plus(y, un(0))) 8.66/3.81 PLUS(un(x), un(y)) -> PLUS(y, un(0)) 8.66/3.81 PLUS(j(x), j(y)) -> PLUS(x, plus(y, j(0))) 8.66/3.81 PLUS(j(x), j(y)) -> PLUS(y, j(0)) 8.66/3.81 PLUS(plus(un(x), un(y)), ext) -> PLUS(j(plus(x, plus(y, un(0)))), ext) 8.66/3.81 PLUS(plus(un(x), un(y)), ext) -> PLUS(x, plus(y, un(0))) 8.66/3.81 PLUS(plus(un(x), un(y)), ext) -> PLUS(y, un(0)) 8.66/3.81 PLUS(plus(j(x), j(y)), ext) -> PLUS(un(plus(x, plus(y, j(0)))), ext) 8.66/3.81 PLUS(plus(j(x), j(y)), ext) -> PLUS(x, plus(y, j(0))) 8.66/3.81 PLUS(plus(j(x), j(y)), ext) -> PLUS(y, j(0)) 8.66/3.81 8.66/3.81 The TRS R consists of the following rules: 8.66/3.81 8.66/3.81 plus(x, 0) -> x 8.66/3.81 plus(un(x), un(y)) -> j(plus(x, plus(y, un(0)))) 8.66/3.81 plus(j(x), j(y)) -> un(plus(x, plus(y, j(0)))) 8.66/3.81 plus(plus(un(x), un(y)), ext) -> plus(j(plus(x, plus(y, un(0)))), ext) 8.66/3.81 plus(plus(j(x), j(y)), ext) -> plus(un(plus(x, plus(y, j(0)))), ext) 8.66/3.81 8.66/3.81 The set E consists of the following equations: 8.66/3.81 8.66/3.81 plus(x, y) == plus(y, x) 8.66/3.81 times(x, y) == times(y, x) 8.66/3.81 plus(plus(x, y), z) == plus(x, plus(y, z)) 8.66/3.81 times(times(x, y), z) == times(x, times(y, z)) 8.66/3.81 8.66/3.81 The set E# consists of the following equations: 8.66/3.81 8.66/3.81 PLUS(x, y) == PLUS(y, x) 8.66/3.81 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 8.66/3.81 8.66/3.81 We have to consider all minimal (P,E#,R,E)-chains 8.66/3.81 ---------------------------------------- 8.66/3.81 8.66/3.81 (9) EUsableRulesReductionPairsProof (EQUIVALENT) 8.66/3.81 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. 8.66/3.81 8.66/3.81 No dependency pairs are removed. 8.66/3.81 8.66/3.81 No rules are removed from R. 8.66/3.81 8.66/3.81 The following equations are removed from E: 8.66/3.81 8.66/3.81 times(x, y) == times(y, x) 8.66/3.81 times(times(x, y), z) == times(x, times(y, z)) 8.66/3.81 Used ordering: POLO with Polynomial interpretation [POLO]: 8.66/3.81 8.66/3.81 POL(0) = 0 8.66/3.81 POL(PLUS(x_1, x_2)) = x_1 + x_2 8.66/3.81 POL(j(x_1)) = x_1 8.66/3.81 POL(plus(x_1, x_2)) = x_1 + x_2 8.66/3.81 POL(un(x_1)) = x_1 8.66/3.81 8.66/3.81 8.66/3.81 ---------------------------------------- 8.66/3.81 8.66/3.81 (10) 8.66/3.81 Obligation: 8.66/3.81 The TRS P consists of the following rules: 8.66/3.81 8.66/3.81 PLUS(un(x), un(y)) -> PLUS(x, plus(y, un(0))) 8.66/3.81 PLUS(un(x), un(y)) -> PLUS(y, un(0)) 8.66/3.81 PLUS(j(x), j(y)) -> PLUS(x, plus(y, j(0))) 8.66/3.81 PLUS(j(x), j(y)) -> PLUS(y, j(0)) 8.66/3.81 PLUS(plus(un(x), un(y)), ext) -> PLUS(j(plus(x, plus(y, un(0)))), ext) 8.66/3.81 PLUS(plus(un(x), un(y)), ext) -> PLUS(x, plus(y, un(0))) 8.66/3.81 PLUS(plus(un(x), un(y)), ext) -> PLUS(y, un(0)) 8.66/3.81 PLUS(plus(j(x), j(y)), ext) -> PLUS(un(plus(x, plus(y, j(0)))), ext) 8.66/3.81 PLUS(plus(j(x), j(y)), ext) -> PLUS(x, plus(y, j(0))) 8.66/3.81 PLUS(plus(j(x), j(y)), ext) -> PLUS(y, j(0)) 8.66/3.81 8.66/3.81 The TRS R consists of the following rules: 8.66/3.81 8.66/3.81 plus(x, 0) -> x 8.66/3.81 plus(un(x), un(y)) -> j(plus(x, plus(y, un(0)))) 8.66/3.81 plus(j(x), j(y)) -> un(plus(x, plus(y, j(0)))) 8.66/3.81 plus(plus(un(x), un(y)), ext) -> plus(j(plus(x, plus(y, un(0)))), ext) 8.66/3.81 plus(plus(j(x), j(y)), ext) -> plus(un(plus(x, plus(y, j(0)))), ext) 8.66/3.81 8.66/3.81 The set E consists of the following equations: 8.66/3.81 8.66/3.81 plus(plus(x, y), z) == plus(x, plus(y, z)) 8.66/3.81 plus(x, y) == plus(y, x) 8.66/3.81 8.66/3.81 The set E# consists of the following equations: 8.66/3.81 8.66/3.81 PLUS(x, y) == PLUS(y, x) 8.66/3.81 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 8.66/3.81 8.66/3.81 We have to consider all minimal (P,E#,R,E)-chains 8.66/3.81 ---------------------------------------- 8.66/3.81 8.66/3.81 (11) ERuleRemovalProof (EQUIVALENT) 8.66/3.81 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. 8.66/3.81 8.66/3.81 Strictly oriented dependency pairs: 8.66/3.81 8.66/3.81 PLUS(un(x), un(y)) -> PLUS(x, plus(y, un(0))) 8.66/3.81 PLUS(un(x), un(y)) -> PLUS(y, un(0)) 8.66/3.81 PLUS(j(x), j(y)) -> PLUS(x, plus(y, j(0))) 8.66/3.81 PLUS(j(x), j(y)) -> PLUS(y, j(0)) 8.66/3.81 PLUS(plus(un(x), un(y)), ext) -> PLUS(x, plus(y, un(0))) 8.66/3.81 PLUS(plus(un(x), un(y)), ext) -> PLUS(y, un(0)) 8.66/3.81 PLUS(plus(j(x), j(y)), ext) -> PLUS(x, plus(y, j(0))) 8.66/3.81 PLUS(plus(j(x), j(y)), ext) -> PLUS(y, j(0)) 8.66/3.81 8.66/3.81 8.66/3.81 Used ordering: POLO with Polynomial interpretation [POLO]: 8.66/3.81 8.66/3.81 POL(0) = 0 8.66/3.81 POL(PLUS(x_1, x_2)) = x_1 + x_2 8.66/3.81 POL(j(x_1)) = 3 + x_1 8.66/3.81 POL(plus(x_1, x_2)) = x_1 + x_2 8.66/3.81 POL(un(x_1)) = 3 + x_1 8.66/3.81 8.66/3.81 8.66/3.81 ---------------------------------------- 8.66/3.81 8.66/3.81 (12) 8.66/3.81 Obligation: 8.66/3.81 The TRS P consists of the following rules: 8.66/3.81 8.66/3.81 PLUS(plus(un(x), un(y)), ext) -> PLUS(j(plus(x, plus(y, un(0)))), ext) 8.66/3.81 PLUS(plus(j(x), j(y)), ext) -> PLUS(un(plus(x, plus(y, j(0)))), ext) 8.66/3.81 8.66/3.81 The TRS R consists of the following rules: 8.66/3.81 8.66/3.81 plus(x, 0) -> x 8.66/3.81 plus(un(x), un(y)) -> j(plus(x, plus(y, un(0)))) 8.66/3.81 plus(j(x), j(y)) -> un(plus(x, plus(y, j(0)))) 8.66/3.81 plus(plus(un(x), un(y)), ext) -> plus(j(plus(x, plus(y, un(0)))), ext) 8.66/3.81 plus(plus(j(x), j(y)), ext) -> plus(un(plus(x, plus(y, j(0)))), ext) 8.66/3.81 8.66/3.81 The set E consists of the following equations: 8.66/3.81 8.66/3.81 plus(plus(x, y), z) == plus(x, plus(y, z)) 8.66/3.81 plus(x, y) == plus(y, x) 8.66/3.81 8.66/3.81 The set E# consists of the following equations: 8.66/3.81 8.66/3.81 PLUS(x, y) == PLUS(y, x) 8.66/3.81 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 8.66/3.81 8.66/3.81 We have to consider all minimal (P,E#,R,E)-chains 8.66/3.81 ---------------------------------------- 8.66/3.81 8.66/3.81 (13) EDPPoloProof (EQUIVALENT) 8.66/3.81 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. 8.66/3.81 8.66/3.81 8.66/3.81 PLUS(plus(un(x), un(y)), ext) -> PLUS(j(plus(x, plus(y, un(0)))), ext) 8.66/3.81 PLUS(plus(j(x), j(y)), ext) -> PLUS(un(plus(x, plus(y, j(0)))), ext) 8.66/3.81 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 8.66/3.81 8.66/3.81 8.66/3.81 plus(j(x), j(y)) -> un(plus(x, plus(y, j(0)))) 8.66/3.81 plus(un(x), un(y)) -> j(plus(x, plus(y, un(0)))) 8.66/3.81 plus(x, 0) -> x 8.66/3.81 plus(plus(un(x), un(y)), ext) -> plus(j(plus(x, plus(y, un(0)))), ext) 8.66/3.81 plus(plus(j(x), j(y)), ext) -> plus(un(plus(x, plus(y, j(0)))), ext) 8.66/3.81 We had to orient the following equations of E# equivalently. 8.66/3.81 8.66/3.81 8.66/3.81 PLUS(x, y) == PLUS(y, x) 8.66/3.81 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 8.66/3.81 With the implicit AFS we had to orient the following usable equations of E equivalently. 8.66/3.81 8.66/3.81 8.66/3.81 plus(plus(x, y), z) == plus(x, plus(y, z)) 8.66/3.81 plus(x, y) == plus(y, x) 8.66/3.81 Used ordering: POLO with Polynomial interpretation [POLO]: 8.66/3.81 8.66/3.81 POL(0) = 0 8.66/3.81 POL(PLUS(x_1, x_2)) = x_1 + x_2 8.66/3.81 POL(j(x_1)) = 0 8.66/3.81 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 8.66/3.81 POL(un(x_1)) = 0 8.66/3.81 8.66/3.81 8.66/3.81 ---------------------------------------- 8.66/3.81 8.66/3.81 (14) 8.66/3.81 Obligation: 8.66/3.81 P is empty. 8.66/3.81 The TRS R consists of the following rules: 8.66/3.81 8.66/3.81 plus(x, 0) -> x 8.66/3.81 plus(un(x), un(y)) -> j(plus(x, plus(y, un(0)))) 8.66/3.81 plus(j(x), j(y)) -> un(plus(x, plus(y, j(0)))) 8.66/3.81 plus(plus(un(x), un(y)), ext) -> plus(j(plus(x, plus(y, un(0)))), ext) 8.66/3.81 plus(plus(j(x), j(y)), ext) -> plus(un(plus(x, plus(y, j(0)))), ext) 8.66/3.81 8.66/3.81 The set E consists of the following equations: 8.66/3.81 8.66/3.81 plus(plus(x, y), z) == plus(x, plus(y, z)) 8.66/3.81 plus(x, y) == plus(y, x) 8.66/3.81 8.66/3.81 The set E# consists of the following equations: 8.66/3.81 8.66/3.81 PLUS(x, y) == PLUS(y, x) 8.66/3.81 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 8.66/3.81 8.66/3.81 We have to consider all minimal (P,E#,R,E)-chains 8.66/3.81 ---------------------------------------- 8.66/3.81 8.66/3.81 (15) PisEmptyProof (EQUIVALENT) 8.66/3.81 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 8.66/3.81 ---------------------------------------- 8.66/3.81 8.66/3.81 (16) 8.66/3.81 YES 8.66/3.83 EOF