7.49/3.54 YES 7.71/3.55 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 7.71/3.55 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.71/3.55 7.71/3.55 7.71/3.55 Termination of the given ETRS could be proven: 7.71/3.55 7.71/3.55 (0) ETRS 7.71/3.55 (1) RRRPoloETRSProof [EQUIVALENT, 938 ms] 7.71/3.55 (2) ETRS 7.71/3.55 (3) EquationalDependencyPairsProof [EQUIVALENT, 0 ms] 7.71/3.55 (4) EDP 7.71/3.55 (5) EDependencyGraphProof [EQUIVALENT, 0 ms] 7.71/3.55 (6) TRUE 7.71/3.55 7.71/3.55 7.71/3.55 ---------------------------------------- 7.71/3.55 7.71/3.55 (0) 7.71/3.55 Obligation: 7.71/3.55 Equational rewrite system: 7.71/3.55 The TRS R consists of the following rules: 7.71/3.55 7.71/3.55 app(nil, k) -> k 7.71/3.55 app(l, nil) -> l 7.71/3.55 app(cons(x, l), k) -> cons(x, app(l, k)) 7.71/3.55 sum(cons(x, nil)) -> cons(x, nil) 7.71/3.55 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.71/3.55 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.71/3.55 sum(cons(0, cons(plus(x, y), l))) -> pred(sum(cons(s(x), cons(y, l)))) 7.71/3.55 plus(0, y) -> y 7.71/3.55 plus(s(x), y) -> s(plus(x, y)) 7.71/3.55 pred(cons(s(x), nil)) -> cons(x, nil) 7.71/3.55 7.71/3.55 The set E consists of the following equations: 7.71/3.55 7.71/3.55 plus(x, y) == plus(y, x) 7.71/3.55 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.71/3.55 7.71/3.55 7.71/3.55 ---------------------------------------- 7.71/3.55 7.71/3.55 (1) RRRPoloETRSProof (EQUIVALENT) 7.71/3.55 The following E TRS is given: Equational rewrite system: 7.71/3.55 The TRS R consists of the following rules: 7.71/3.55 7.71/3.55 app(nil, k) -> k 7.71/3.55 app(l, nil) -> l 7.71/3.55 app(cons(x, l), k) -> cons(x, app(l, k)) 7.71/3.55 sum(cons(x, nil)) -> cons(x, nil) 7.71/3.55 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.71/3.55 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.71/3.55 sum(cons(0, cons(plus(x, y), l))) -> pred(sum(cons(s(x), cons(y, l)))) 7.71/3.55 plus(0, y) -> y 7.71/3.55 plus(s(x), y) -> s(plus(x, y)) 7.71/3.55 pred(cons(s(x), nil)) -> cons(x, nil) 7.71/3.55 7.71/3.55 The set E consists of the following equations: 7.71/3.55 7.71/3.55 plus(x, y) == plus(y, x) 7.71/3.55 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.71/3.55 7.71/3.55 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 7.71/3.55 7.71/3.55 app(nil, k) -> k 7.71/3.55 app(l, nil) -> l 7.71/3.55 app(cons(x, l), k) -> cons(x, app(l, k)) 7.71/3.55 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 7.71/3.55 sum(cons(0, cons(plus(x, y), l))) -> pred(sum(cons(s(x), cons(y, l)))) 7.71/3.55 plus(0, y) -> y 7.71/3.55 plus(s(x), y) -> s(plus(x, y)) 7.71/3.55 pred(cons(s(x), nil)) -> cons(x, nil) 7.71/3.55 Used ordering: 7.71/3.55 Polynomial interpretation [POLO]: 7.71/3.55 7.71/3.55 POL(0) = 2 7.71/3.55 POL(app(x_1, x_2)) = 1 + 3*x_1 + 2*x_1*x_2 + x_2 7.71/3.55 POL(cons(x_1, x_2)) = 3 + 2*x_1 + x_1*x_2 + 2*x_2 7.71/3.55 POL(nil) = 0 7.71/3.55 POL(plus(x_1, x_2)) = 2 + 2*x_1 + x_1*x_2 + 2*x_2 7.71/3.55 POL(pred(x_1)) = 1 + x_1 7.71/3.55 POL(s(x_1)) = 3 + x_1 7.71/3.55 POL(sum(x_1)) = x_1 7.71/3.55 7.71/3.55 7.71/3.55 7.71/3.55 7.71/3.55 ---------------------------------------- 7.71/3.55 7.71/3.55 (2) 7.71/3.55 Obligation: 7.71/3.55 Equational rewrite system: 7.71/3.55 The TRS R consists of the following rules: 7.71/3.55 7.71/3.55 sum(cons(x, nil)) -> cons(x, nil) 7.71/3.55 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.71/3.55 7.71/3.55 The set E consists of the following equations: 7.71/3.55 7.71/3.55 plus(x, y) == plus(y, x) 7.71/3.55 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.71/3.55 7.71/3.55 7.71/3.55 ---------------------------------------- 7.71/3.55 7.71/3.55 (3) EquationalDependencyPairsProof (EQUIVALENT) 7.71/3.55 Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: 7.71/3.55 The TRS P consists of the following rules: 7.71/3.55 7.71/3.55 SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) 7.71/3.55 SUM(app(l, cons(x, cons(y, k)))) -> SUM(cons(x, cons(y, k))) 7.71/3.55 7.71/3.55 The TRS R consists of the following rules: 7.71/3.55 7.71/3.55 sum(cons(x, nil)) -> cons(x, nil) 7.71/3.55 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.71/3.55 7.71/3.55 The set E consists of the following equations: 7.71/3.55 7.71/3.55 plus(x, y) == plus(y, x) 7.71/3.55 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.71/3.55 7.71/3.55 E# is empty. 7.71/3.55 We have to consider all minimal (P,E#,R,E)-chains 7.71/3.55 7.71/3.55 ---------------------------------------- 7.71/3.55 7.71/3.55 (4) 7.71/3.55 Obligation: 7.71/3.55 The TRS P consists of the following rules: 7.71/3.55 7.71/3.55 SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) 7.71/3.55 SUM(app(l, cons(x, cons(y, k)))) -> SUM(cons(x, cons(y, k))) 7.71/3.55 7.71/3.55 The TRS R consists of the following rules: 7.71/3.55 7.71/3.55 sum(cons(x, nil)) -> cons(x, nil) 7.71/3.55 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 7.71/3.55 7.71/3.55 The set E consists of the following equations: 7.71/3.55 7.71/3.55 plus(x, y) == plus(y, x) 7.71/3.55 plus(plus(x, y), z) == plus(x, plus(y, z)) 7.71/3.55 7.71/3.55 E# is empty. 7.71/3.55 We have to consider all minimal (P,E#,R,E)-chains 7.71/3.55 ---------------------------------------- 7.71/3.55 7.71/3.55 (5) EDependencyGraphProof (EQUIVALENT) 7.71/3.55 The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 2 less nodes. 7.71/3.55 ---------------------------------------- 7.71/3.55 7.71/3.55 (6) 7.71/3.55 TRUE 7.73/3.58 EOF