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, 1634 ms] (2) ETRS (3) RRRPoloETRSProof [EQUIVALENT, 773 ms] (4) ETRS (5) RRRPoloETRSProof [EQUIVALENT, 636 ms] (6) ETRS (7) EquationalDependencyPairsProof [EQUIVALENT, 0 ms] (8) EDP (9) EDependencyGraphProof [EQUIVALENT, 0 ms] (10) EDP (11) EUsableRulesReductionPairsProof [EQUIVALENT, 2 ms] (12) EDP (13) PisEmptyProof [EQUIVALENT, 0 ms] (14) YES ---------------------------------------- (0) Obligation: Equational rewrite system: The TRS R consists of the following rules: union(empty, X) -> X max(singl(x)) -> x max(union(singl(x), singl(0))) -> x max(union(singl(s(x)), singl(s(y)))) -> s(max(union(singl(x), singl(y)))) max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) The set E consists of the following equations: union(x, y) == union(y, x) union(union(x, y), z) == union(x, union(y, z)) ---------------------------------------- (1) RRRPoloETRSProof (EQUIVALENT) The following E TRS is given: Equational rewrite system: The TRS R consists of the following rules: union(empty, X) -> X max(singl(x)) -> x max(union(singl(x), singl(0))) -> x max(union(singl(s(x)), singl(s(y)))) -> s(max(union(singl(x), singl(y)))) max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) The set E consists of the following equations: union(x, y) == union(y, x) union(union(x, y), z) == union(x, union(y, z)) The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: union(empty, X) -> X Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(empty) = 1 POL(max(x_1)) = x_1 POL(s(x_1)) = x_1 POL(singl(x_1)) = x_1 POL(union(x_1, x_2)) = x_1 + x_2 ---------------------------------------- (2) Obligation: Equational rewrite system: The TRS R consists of the following rules: max(singl(x)) -> x max(union(singl(x), singl(0))) -> x max(union(singl(s(x)), singl(s(y)))) -> s(max(union(singl(x), singl(y)))) max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) The set E consists of the following equations: union(x, y) == union(y, x) union(union(x, y), z) == union(x, union(y, z)) ---------------------------------------- (3) RRRPoloETRSProof (EQUIVALENT) The following E TRS is given: Equational rewrite system: The TRS R consists of the following rules: max(singl(x)) -> x max(union(singl(x), singl(0))) -> x max(union(singl(s(x)), singl(s(y)))) -> s(max(union(singl(x), singl(y)))) max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) The set E consists of the following equations: union(x, y) == union(y, x) union(union(x, y), z) == union(x, union(y, z)) The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: max(union(singl(x), singl(0))) -> x Used ordering: Polynomial interpretation [POLO]: POL(0) = 3 POL(max(x_1)) = x_1 POL(s(x_1)) = x_1 POL(singl(x_1)) = x_1 POL(union(x_1, x_2)) = x_1 + x_2 ---------------------------------------- (4) Obligation: Equational rewrite system: The TRS R consists of the following rules: max(singl(x)) -> x max(union(singl(s(x)), singl(s(y)))) -> s(max(union(singl(x), singl(y)))) max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) The set E consists of the following equations: union(x, y) == union(y, x) union(union(x, y), z) == union(x, union(y, z)) ---------------------------------------- (5) RRRPoloETRSProof (EQUIVALENT) The following E TRS is given: Equational rewrite system: The TRS R consists of the following rules: max(singl(x)) -> x max(union(singl(s(x)), singl(s(y)))) -> s(max(union(singl(x), singl(y)))) max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) The set E consists of the following equations: union(x, y) == union(y, x) union(union(x, y), z) == union(x, union(y, z)) The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: max(union(singl(s(x)), singl(s(y)))) -> s(max(union(singl(x), singl(y)))) Used ordering: Polynomial interpretation [POLO]: POL(max(x_1)) = x_1 POL(s(x_1)) = 1 + x_1 POL(singl(x_1)) = x_1 POL(union(x_1, x_2)) = 2 + 2*x_1 + x_1*x_2 + 2*x_2 ---------------------------------------- (6) Obligation: Equational rewrite system: The TRS R consists of the following rules: max(singl(x)) -> x max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) The set E consists of the following equations: union(x, y) == union(y, x) union(union(x, y), z) == union(x, union(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: MAX(union(singl(x), union(Y, Z))) -> MAX(union(singl(x), singl(max(union(Y, Z))))) MAX(union(singl(x), union(Y, Z))) -> MAX(union(Y, Z)) The TRS R consists of the following rules: max(singl(x)) -> x max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) The set E consists of the following equations: union(x, y) == union(y, x) union(union(x, y), z) == union(x, union(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (8) Obligation: The TRS P consists of the following rules: MAX(union(singl(x), union(Y, Z))) -> MAX(union(singl(x), singl(max(union(Y, Z))))) MAX(union(singl(x), union(Y, Z))) -> MAX(union(Y, Z)) The TRS R consists of the following rules: max(singl(x)) -> x max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) The set E consists of the following equations: union(x, y) == union(y, x) union(union(x, y), z) == union(x, union(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (9) EDependencyGraphProof (EQUIVALENT) The approximation of the Equational Dependency Graph [DA_STEIN] contains 1 SCC with 1 less node. ---------------------------------------- (10) Obligation: The TRS P consists of the following rules: MAX(union(singl(x), union(Y, Z))) -> MAX(union(Y, Z)) The TRS R consists of the following rules: max(singl(x)) -> x max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) The set E consists of the following equations: union(x, y) == union(y, x) union(union(x, y), z) == union(x, union(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (11) 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. The following dependency pairs can be deleted: MAX(union(singl(x), union(Y, Z))) -> MAX(union(Y, Z)) The following rules are removed from R: max(singl(x)) -> x max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) No equations are removed from E. Used ordering: POLO with Polynomial interpretation [POLO]: POL(MAX(x_1)) = 3*x_1 POL(singl(x_1)) = x_1 POL(union(x_1, x_2)) = x_1 + x_2 ---------------------------------------- (12) Obligation: P is empty. R is empty. The set E consists of the following equations: union(x, y) == union(y, x) union(union(x, y), z) == union(x, union(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (13) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,E#,R,E) chain. ---------------------------------------- (14) YES