13.45/5.64 YES 13.45/5.65 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 13.45/5.65 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 13.45/5.65 13.45/5.65 13.45/5.65 Termination of the given ETRS could be proven: 13.45/5.65 13.45/5.65 (0) ETRS 13.45/5.65 (1) RRRPoloETRSProof [EQUIVALENT, 1420 ms] 13.45/5.65 (2) ETRS 13.45/5.65 (3) RRRPoloETRSProof [EQUIVALENT, 907 ms] 13.45/5.65 (4) ETRS 13.45/5.65 (5) RRRPoloETRSProof [EQUIVALENT, 647 ms] 13.45/5.65 (6) ETRS 13.45/5.65 (7) EquationalDependencyPairsProof [EQUIVALENT, 24 ms] 13.45/5.65 (8) EDP 13.45/5.65 (9) EDependencyGraphProof [EQUIVALENT, 0 ms] 13.45/5.65 (10) EDP 13.45/5.65 (11) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 13.45/5.65 (12) EDP 13.45/5.65 (13) PisEmptyProof [EQUIVALENT, 0 ms] 13.45/5.65 (14) YES 13.45/5.65 13.45/5.65 13.45/5.65 ---------------------------------------- 13.45/5.65 13.45/5.65 (0) 13.45/5.65 Obligation: 13.45/5.65 Equational rewrite system: 13.45/5.65 The TRS R consists of the following rules: 13.45/5.65 13.45/5.65 union(empty, X) -> X 13.45/5.65 max(singl(x)) -> x 13.45/5.65 max(union(singl(x), singl(0))) -> x 13.45/5.65 max(union(singl(s(x)), singl(s(y)))) -> s(max(union(singl(x), singl(y)))) 13.45/5.65 max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) 13.45/5.65 13.45/5.65 The set E consists of the following equations: 13.45/5.65 13.45/5.65 union(x, y) == union(y, x) 13.45/5.65 union(union(x, y), z) == union(x, union(y, z)) 13.45/5.65 13.45/5.65 13.45/5.65 ---------------------------------------- 13.45/5.65 13.45/5.65 (1) RRRPoloETRSProof (EQUIVALENT) 13.45/5.65 The following E TRS is given: Equational rewrite system: 13.45/5.65 The TRS R consists of the following rules: 13.45/5.65 13.45/5.65 union(empty, X) -> X 13.45/5.65 max(singl(x)) -> x 13.45/5.65 max(union(singl(x), singl(0))) -> x 13.45/5.65 max(union(singl(s(x)), singl(s(y)))) -> s(max(union(singl(x), singl(y)))) 13.45/5.65 max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) 13.45/5.65 13.45/5.65 The set E consists of the following equations: 13.45/5.65 13.45/5.65 union(x, y) == union(y, x) 13.45/5.65 union(union(x, y), z) == union(x, union(y, z)) 13.45/5.65 13.45/5.65 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 13.45/5.65 13.45/5.65 union(empty, X) -> X 13.45/5.65 Used ordering: 13.45/5.65 Polynomial interpretation [POLO]: 13.45/5.65 13.45/5.65 POL(0) = 0 13.45/5.65 POL(empty) = 1 13.45/5.65 POL(max(x_1)) = x_1 13.45/5.65 POL(s(x_1)) = x_1 13.45/5.65 POL(singl(x_1)) = x_1 13.45/5.65 POL(union(x_1, x_2)) = x_1 + x_2 13.45/5.65 13.45/5.65 13.45/5.65 13.45/5.65 13.45/5.65 ---------------------------------------- 13.45/5.65 13.45/5.65 (2) 13.45/5.65 Obligation: 13.45/5.65 Equational rewrite system: 13.45/5.65 The TRS R consists of the following rules: 13.45/5.65 13.45/5.65 max(singl(x)) -> x 13.45/5.65 max(union(singl(x), singl(0))) -> x 13.45/5.65 max(union(singl(s(x)), singl(s(y)))) -> s(max(union(singl(x), singl(y)))) 13.45/5.65 max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) 13.45/5.65 13.45/5.65 The set E consists of the following equations: 13.45/5.65 13.45/5.65 union(x, y) == union(y, x) 13.45/5.65 union(union(x, y), z) == union(x, union(y, z)) 13.45/5.65 13.45/5.65 13.45/5.65 ---------------------------------------- 13.45/5.65 13.45/5.65 (3) RRRPoloETRSProof (EQUIVALENT) 13.45/5.65 The following E TRS is given: Equational rewrite system: 13.45/5.65 The TRS R consists of the following rules: 13.45/5.65 13.45/5.65 max(singl(x)) -> x 13.45/5.65 max(union(singl(x), singl(0))) -> x 13.45/5.65 max(union(singl(s(x)), singl(s(y)))) -> s(max(union(singl(x), singl(y)))) 13.45/5.65 max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) 13.45/5.65 13.45/5.65 The set E consists of the following equations: 13.45/5.65 13.45/5.65 union(x, y) == union(y, x) 13.45/5.65 union(union(x, y), z) == union(x, union(y, z)) 13.45/5.65 13.45/5.65 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 13.45/5.65 13.45/5.65 max(union(singl(x), singl(0))) -> x 13.45/5.65 Used ordering: 13.45/5.65 Polynomial interpretation [POLO]: 13.45/5.65 13.45/5.65 POL(0) = 3 13.45/5.65 POL(max(x_1)) = x_1 13.45/5.65 POL(s(x_1)) = x_1 13.45/5.65 POL(singl(x_1)) = x_1 13.45/5.65 POL(union(x_1, x_2)) = x_1 + x_2 13.45/5.65 13.45/5.65 13.45/5.65 13.45/5.65 13.45/5.65 ---------------------------------------- 13.45/5.65 13.45/5.65 (4) 13.45/5.65 Obligation: 13.45/5.65 Equational rewrite system: 13.45/5.65 The TRS R consists of the following rules: 13.45/5.65 13.45/5.65 max(singl(x)) -> x 13.45/5.65 max(union(singl(s(x)), singl(s(y)))) -> s(max(union(singl(x), singl(y)))) 13.45/5.65 max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) 13.45/5.65 13.45/5.65 The set E consists of the following equations: 13.45/5.65 13.45/5.65 union(x, y) == union(y, x) 13.45/5.65 union(union(x, y), z) == union(x, union(y, z)) 13.45/5.65 13.45/5.65 13.45/5.65 ---------------------------------------- 13.45/5.65 13.45/5.65 (5) RRRPoloETRSProof (EQUIVALENT) 13.45/5.65 The following E TRS is given: Equational rewrite system: 13.45/5.65 The TRS R consists of the following rules: 13.45/5.65 13.45/5.65 max(singl(x)) -> x 13.45/5.65 max(union(singl(s(x)), singl(s(y)))) -> s(max(union(singl(x), singl(y)))) 13.45/5.65 max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) 13.45/5.65 13.45/5.65 The set E consists of the following equations: 13.45/5.65 13.45/5.65 union(x, y) == union(y, x) 13.45/5.65 union(union(x, y), z) == union(x, union(y, z)) 13.45/5.65 13.45/5.65 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 13.45/5.65 13.45/5.65 max(union(singl(s(x)), singl(s(y)))) -> s(max(union(singl(x), singl(y)))) 13.45/5.65 Used ordering: 13.45/5.65 Polynomial interpretation [POLO]: 13.45/5.65 13.45/5.65 POL(max(x_1)) = x_1 13.45/5.65 POL(s(x_1)) = 1 + x_1 13.45/5.65 POL(singl(x_1)) = x_1 13.45/5.65 POL(union(x_1, x_2)) = 2 + 2*x_1 + x_1*x_2 + 2*x_2 13.45/5.65 13.45/5.65 13.45/5.65 13.45/5.65 13.45/5.65 ---------------------------------------- 13.45/5.65 13.45/5.65 (6) 13.45/5.65 Obligation: 13.45/5.65 Equational rewrite system: 13.45/5.65 The TRS R consists of the following rules: 13.45/5.65 13.45/5.65 max(singl(x)) -> x 13.45/5.65 max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) 13.45/5.65 13.45/5.65 The set E consists of the following equations: 13.45/5.65 13.45/5.65 union(x, y) == union(y, x) 13.45/5.65 union(union(x, y), z) == union(x, union(y, z)) 13.45/5.65 13.45/5.65 13.45/5.65 ---------------------------------------- 13.45/5.65 13.45/5.65 (7) EquationalDependencyPairsProof (EQUIVALENT) 13.45/5.65 Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: 13.45/5.65 The TRS P consists of the following rules: 13.45/5.65 13.45/5.65 MAX(union(singl(x), union(Y, Z))) -> MAX(union(singl(x), singl(max(union(Y, Z))))) 13.45/5.65 MAX(union(singl(x), union(Y, Z))) -> MAX(union(Y, Z)) 13.45/5.65 13.45/5.65 The TRS R consists of the following rules: 13.45/5.65 13.45/5.65 max(singl(x)) -> x 13.45/5.65 max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) 13.45/5.65 13.45/5.65 The set E consists of the following equations: 13.45/5.65 13.45/5.65 union(x, y) == union(y, x) 13.45/5.65 union(union(x, y), z) == union(x, union(y, z)) 13.45/5.65 13.45/5.65 E# is empty. 13.45/5.65 We have to consider all minimal (P,E#,R,E)-chains 13.45/5.65 13.45/5.65 ---------------------------------------- 13.45/5.65 13.45/5.65 (8) 13.45/5.65 Obligation: 13.45/5.65 The TRS P consists of the following rules: 13.45/5.65 13.45/5.65 MAX(union(singl(x), union(Y, Z))) -> MAX(union(singl(x), singl(max(union(Y, Z))))) 13.45/5.65 MAX(union(singl(x), union(Y, Z))) -> MAX(union(Y, Z)) 13.45/5.65 13.45/5.65 The TRS R consists of the following rules: 13.45/5.65 13.45/5.65 max(singl(x)) -> x 13.45/5.65 max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) 13.45/5.65 13.45/5.65 The set E consists of the following equations: 13.45/5.65 13.45/5.65 union(x, y) == union(y, x) 13.45/5.65 union(union(x, y), z) == union(x, union(y, z)) 13.45/5.65 13.45/5.65 E# is empty. 13.45/5.65 We have to consider all minimal (P,E#,R,E)-chains 13.45/5.65 ---------------------------------------- 13.45/5.65 13.45/5.65 (9) EDependencyGraphProof (EQUIVALENT) 13.45/5.65 The approximation of the Equational Dependency Graph [DA_STEIN] contains 1 SCC with 1 less node. 13.45/5.65 ---------------------------------------- 13.45/5.65 13.45/5.65 (10) 13.45/5.65 Obligation: 13.45/5.65 The TRS P consists of the following rules: 13.45/5.65 13.45/5.65 MAX(union(singl(x), union(Y, Z))) -> MAX(union(Y, Z)) 13.45/5.65 13.45/5.65 The TRS R consists of the following rules: 13.45/5.65 13.45/5.65 max(singl(x)) -> x 13.45/5.65 max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) 13.45/5.65 13.45/5.65 The set E consists of the following equations: 13.45/5.65 13.45/5.65 union(x, y) == union(y, x) 13.45/5.65 union(union(x, y), z) == union(x, union(y, z)) 13.45/5.65 13.45/5.65 E# is empty. 13.45/5.65 We have to consider all minimal (P,E#,R,E)-chains 13.45/5.65 ---------------------------------------- 13.45/5.65 13.45/5.65 (11) EUsableRulesReductionPairsProof (EQUIVALENT) 13.45/5.65 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. 13.45/5.65 13.45/5.65 The following dependency pairs can be deleted: 13.45/5.65 13.45/5.65 MAX(union(singl(x), union(Y, Z))) -> MAX(union(Y, Z)) 13.45/5.65 The following rules are removed from R: 13.45/5.65 13.45/5.65 max(singl(x)) -> x 13.45/5.65 max(union(singl(x), union(Y, Z))) -> max(union(singl(x), singl(max(union(Y, Z))))) 13.45/5.65 No equations are removed from E. 13.45/5.65 13.45/5.65 Used ordering: POLO with Polynomial interpretation [POLO]: 13.45/5.65 13.45/5.65 POL(MAX(x_1)) = 3*x_1 13.45/5.65 POL(singl(x_1)) = x_1 13.45/5.65 POL(union(x_1, x_2)) = x_1 + x_2 13.45/5.65 13.45/5.65 13.45/5.65 ---------------------------------------- 13.45/5.65 13.45/5.65 (12) 13.45/5.65 Obligation: 13.45/5.65 P is empty. 13.45/5.65 R is empty. 13.45/5.65 The set E consists of the following equations: 13.45/5.65 13.45/5.65 union(x, y) == union(y, x) 13.45/5.65 union(union(x, y), z) == union(x, union(y, z)) 13.45/5.65 13.45/5.65 E# is empty. 13.45/5.65 We have to consider all minimal (P,E#,R,E)-chains 13.45/5.65 ---------------------------------------- 13.45/5.65 13.45/5.65 (13) PisEmptyProof (EQUIVALENT) 13.45/5.65 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 13.45/5.65 ---------------------------------------- 13.45/5.65 13.45/5.65 (14) 13.45/5.65 YES 13.52/5.68 EOF