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