341.56/291.77 WORST_CASE(Omega(n^2), ?) 341.56/291.78 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 341.56/291.78 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 341.56/291.78 341.56/291.78 341.56/291.78 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 341.56/291.78 341.56/291.78 (0) CpxTRS 341.56/291.78 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 341.56/291.78 (2) CpxTRS 341.56/291.78 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 341.56/291.78 (4) typed CpxTrs 341.56/291.78 (5) OrderProof [LOWER BOUND(ID), 0 ms] 341.56/291.78 (6) typed CpxTrs 341.56/291.78 (7) RewriteLemmaProof [LOWER BOUND(ID), 359 ms] 341.56/291.78 (8) BEST 341.56/291.78 (9) proven lower bound 341.56/291.78 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 341.56/291.78 (11) BOUNDS(n^1, INF) 341.56/291.78 (12) typed CpxTrs 341.56/291.78 (13) RewriteLemmaProof [LOWER BOUND(ID), 4078 ms] 341.56/291.78 (14) BEST 341.56/291.78 (15) proven lower bound 341.56/291.78 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 341.56/291.78 (17) BOUNDS(n^2, INF) 341.56/291.78 (18) typed CpxTrs 341.56/291.78 (19) RewriteLemmaProof [LOWER BOUND(ID), 14 ms] 341.56/291.78 (20) typed CpxTrs 341.56/291.78 (21) RewriteLemmaProof [LOWER BOUND(ID), 455 ms] 341.56/291.78 (22) BOUNDS(1, INF) 341.56/291.78 341.56/291.78 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (0) 341.56/291.78 Obligation: 341.56/291.78 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 341.56/291.78 341.56/291.78 341.56/291.78 The TRS R consists of the following rules: 341.56/291.78 341.56/291.78 +(x, 0) -> x 341.56/291.78 +(0, x) -> x 341.56/291.78 +(s(x), s(y)) -> s(s(+(x, y))) 341.56/291.78 +(+(x, y), z) -> +(x, +(y, z)) 341.56/291.78 *(x, 0) -> 0 341.56/291.78 *(0, x) -> 0 341.56/291.78 *(s(x), s(y)) -> s(+(*(x, y), +(x, y))) 341.56/291.78 *(*(x, y), z) -> *(x, *(y, z)) 341.56/291.78 sum(nil) -> 0 341.56/291.78 sum(cons(x, l)) -> +(x, sum(l)) 341.56/291.78 prod(nil) -> s(0) 341.56/291.78 prod(cons(x, l)) -> *(x, prod(l)) 341.56/291.78 341.56/291.78 S is empty. 341.56/291.78 Rewrite Strategy: FULL 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 341.56/291.78 Renamed function symbols to avoid clashes with predefined symbol. 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (2) 341.56/291.78 Obligation: 341.56/291.78 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 341.56/291.78 341.56/291.78 341.56/291.78 The TRS R consists of the following rules: 341.56/291.78 341.56/291.78 +'(x, 0') -> x 341.56/291.78 +'(0', x) -> x 341.56/291.78 +'(s(x), s(y)) -> s(s(+'(x, y))) 341.56/291.78 +'(+'(x, y), z) -> +'(x, +'(y, z)) 341.56/291.78 *'(x, 0') -> 0' 341.56/291.78 *'(0', x) -> 0' 341.56/291.78 *'(s(x), s(y)) -> s(+'(*'(x, y), +'(x, y))) 341.56/291.78 *'(*'(x, y), z) -> *'(x, *'(y, z)) 341.56/291.78 sum(nil) -> 0' 341.56/291.78 sum(cons(x, l)) -> +'(x, sum(l)) 341.56/291.78 prod(nil) -> s(0') 341.56/291.78 prod(cons(x, l)) -> *'(x, prod(l)) 341.56/291.78 341.56/291.78 S is empty. 341.56/291.78 Rewrite Strategy: FULL 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 341.56/291.78 Infered types. 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (4) 341.56/291.78 Obligation: 341.56/291.78 TRS: 341.56/291.78 Rules: 341.56/291.78 +'(x, 0') -> x 341.56/291.78 +'(0', x) -> x 341.56/291.78 +'(s(x), s(y)) -> s(s(+'(x, y))) 341.56/291.78 +'(+'(x, y), z) -> +'(x, +'(y, z)) 341.56/291.78 *'(x, 0') -> 0' 341.56/291.78 *'(0', x) -> 0' 341.56/291.78 *'(s(x), s(y)) -> s(+'(*'(x, y), +'(x, y))) 341.56/291.78 *'(*'(x, y), z) -> *'(x, *'(y, z)) 341.56/291.78 sum(nil) -> 0' 341.56/291.78 sum(cons(x, l)) -> +'(x, sum(l)) 341.56/291.78 prod(nil) -> s(0') 341.56/291.78 prod(cons(x, l)) -> *'(x, prod(l)) 341.56/291.78 341.56/291.78 Types: 341.56/291.78 +' :: 0':s -> 0':s -> 0':s 341.56/291.78 0' :: 0':s 341.56/291.78 s :: 0':s -> 0':s 341.56/291.78 *' :: 0':s -> 0':s -> 0':s 341.56/291.78 sum :: nil:cons -> 0':s 341.56/291.78 nil :: nil:cons 341.56/291.78 cons :: 0':s -> nil:cons -> nil:cons 341.56/291.78 prod :: nil:cons -> 0':s 341.56/291.78 hole_0':s1_0 :: 0':s 341.56/291.78 hole_nil:cons2_0 :: nil:cons 341.56/291.78 gen_0':s3_0 :: Nat -> 0':s 341.56/291.78 gen_nil:cons4_0 :: Nat -> nil:cons 341.56/291.78 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (5) OrderProof (LOWER BOUND(ID)) 341.56/291.78 Heuristically decided to analyse the following defined symbols: 341.56/291.78 +', *', sum, prod 341.56/291.78 341.56/291.78 They will be analysed ascendingly in the following order: 341.56/291.78 +' < *' 341.56/291.78 +' < sum 341.56/291.78 *' < prod 341.56/291.78 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (6) 341.56/291.78 Obligation: 341.56/291.78 TRS: 341.56/291.78 Rules: 341.56/291.78 +'(x, 0') -> x 341.56/291.78 +'(0', x) -> x 341.56/291.78 +'(s(x), s(y)) -> s(s(+'(x, y))) 341.56/291.78 +'(+'(x, y), z) -> +'(x, +'(y, z)) 341.56/291.78 *'(x, 0') -> 0' 341.56/291.78 *'(0', x) -> 0' 341.56/291.78 *'(s(x), s(y)) -> s(+'(*'(x, y), +'(x, y))) 341.56/291.78 *'(*'(x, y), z) -> *'(x, *'(y, z)) 341.56/291.78 sum(nil) -> 0' 341.56/291.78 sum(cons(x, l)) -> +'(x, sum(l)) 341.56/291.78 prod(nil) -> s(0') 341.56/291.78 prod(cons(x, l)) -> *'(x, prod(l)) 341.56/291.78 341.56/291.78 Types: 341.56/291.78 +' :: 0':s -> 0':s -> 0':s 341.56/291.78 0' :: 0':s 341.56/291.78 s :: 0':s -> 0':s 341.56/291.78 *' :: 0':s -> 0':s -> 0':s 341.56/291.78 sum :: nil:cons -> 0':s 341.56/291.78 nil :: nil:cons 341.56/291.78 cons :: 0':s -> nil:cons -> nil:cons 341.56/291.78 prod :: nil:cons -> 0':s 341.56/291.78 hole_0':s1_0 :: 0':s 341.56/291.78 hole_nil:cons2_0 :: nil:cons 341.56/291.78 gen_0':s3_0 :: Nat -> 0':s 341.56/291.78 gen_nil:cons4_0 :: Nat -> nil:cons 341.56/291.78 341.56/291.78 341.56/291.78 Generator Equations: 341.56/291.78 gen_0':s3_0(0) <=> 0' 341.56/291.78 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 341.56/291.78 gen_nil:cons4_0(0) <=> nil 341.56/291.78 gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x)) 341.56/291.78 341.56/291.78 341.56/291.78 The following defined symbols remain to be analysed: 341.56/291.78 +', *', sum, prod 341.56/291.78 341.56/291.78 They will be analysed ascendingly in the following order: 341.56/291.78 +' < *' 341.56/291.78 +' < sum 341.56/291.78 *' < prod 341.56/291.78 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (7) RewriteLemmaProof (LOWER BOUND(ID)) 341.56/291.78 Proved the following rewrite lemma: 341.56/291.78 +'(gen_0':s3_0(n6_0), gen_0':s3_0(n6_0)) -> gen_0':s3_0(*(2, n6_0)), rt in Omega(1 + n6_0) 341.56/291.78 341.56/291.78 Induction Base: 341.56/291.78 +'(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1) 341.56/291.78 gen_0':s3_0(0) 341.56/291.78 341.56/291.78 Induction Step: 341.56/291.78 +'(gen_0':s3_0(+(n6_0, 1)), gen_0':s3_0(+(n6_0, 1))) ->_R^Omega(1) 341.56/291.78 s(s(+'(gen_0':s3_0(n6_0), gen_0':s3_0(n6_0)))) ->_IH 341.56/291.78 s(s(gen_0':s3_0(*(2, c7_0)))) 341.56/291.78 341.56/291.78 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (8) 341.56/291.78 Complex Obligation (BEST) 341.56/291.78 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (9) 341.56/291.78 Obligation: 341.56/291.78 Proved the lower bound n^1 for the following obligation: 341.56/291.78 341.56/291.78 TRS: 341.56/291.78 Rules: 341.56/291.78 +'(x, 0') -> x 341.56/291.78 +'(0', x) -> x 341.56/291.78 +'(s(x), s(y)) -> s(s(+'(x, y))) 341.56/291.78 +'(+'(x, y), z) -> +'(x, +'(y, z)) 341.56/291.78 *'(x, 0') -> 0' 341.56/291.78 *'(0', x) -> 0' 341.56/291.78 *'(s(x), s(y)) -> s(+'(*'(x, y), +'(x, y))) 341.56/291.78 *'(*'(x, y), z) -> *'(x, *'(y, z)) 341.56/291.78 sum(nil) -> 0' 341.56/291.78 sum(cons(x, l)) -> +'(x, sum(l)) 341.56/291.78 prod(nil) -> s(0') 341.56/291.78 prod(cons(x, l)) -> *'(x, prod(l)) 341.56/291.78 341.56/291.78 Types: 341.56/291.78 +' :: 0':s -> 0':s -> 0':s 341.56/291.78 0' :: 0':s 341.56/291.78 s :: 0':s -> 0':s 341.56/291.78 *' :: 0':s -> 0':s -> 0':s 341.56/291.78 sum :: nil:cons -> 0':s 341.56/291.78 nil :: nil:cons 341.56/291.78 cons :: 0':s -> nil:cons -> nil:cons 341.56/291.78 prod :: nil:cons -> 0':s 341.56/291.78 hole_0':s1_0 :: 0':s 341.56/291.78 hole_nil:cons2_0 :: nil:cons 341.56/291.78 gen_0':s3_0 :: Nat -> 0':s 341.56/291.78 gen_nil:cons4_0 :: Nat -> nil:cons 341.56/291.78 341.56/291.78 341.56/291.78 Generator Equations: 341.56/291.78 gen_0':s3_0(0) <=> 0' 341.56/291.78 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 341.56/291.78 gen_nil:cons4_0(0) <=> nil 341.56/291.78 gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x)) 341.56/291.78 341.56/291.78 341.56/291.78 The following defined symbols remain to be analysed: 341.56/291.78 +', *', sum, prod 341.56/291.78 341.56/291.78 They will be analysed ascendingly in the following order: 341.56/291.78 +' < *' 341.56/291.78 +' < sum 341.56/291.78 *' < prod 341.56/291.78 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (10) LowerBoundPropagationProof (FINISHED) 341.56/291.78 Propagated lower bound. 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (11) 341.56/291.78 BOUNDS(n^1, INF) 341.56/291.78 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (12) 341.56/291.78 Obligation: 341.56/291.78 TRS: 341.56/291.78 Rules: 341.56/291.78 +'(x, 0') -> x 341.56/291.78 +'(0', x) -> x 341.56/291.78 +'(s(x), s(y)) -> s(s(+'(x, y))) 341.56/291.78 +'(+'(x, y), z) -> +'(x, +'(y, z)) 341.56/291.78 *'(x, 0') -> 0' 341.56/291.78 *'(0', x) -> 0' 341.56/291.78 *'(s(x), s(y)) -> s(+'(*'(x, y), +'(x, y))) 341.56/291.78 *'(*'(x, y), z) -> *'(x, *'(y, z)) 341.56/291.78 sum(nil) -> 0' 341.56/291.78 sum(cons(x, l)) -> +'(x, sum(l)) 341.56/291.78 prod(nil) -> s(0') 341.56/291.78 prod(cons(x, l)) -> *'(x, prod(l)) 341.56/291.78 341.56/291.78 Types: 341.56/291.78 +' :: 0':s -> 0':s -> 0':s 341.56/291.78 0' :: 0':s 341.56/291.78 s :: 0':s -> 0':s 341.56/291.78 *' :: 0':s -> 0':s -> 0':s 341.56/291.78 sum :: nil:cons -> 0':s 341.56/291.78 nil :: nil:cons 341.56/291.78 cons :: 0':s -> nil:cons -> nil:cons 341.56/291.78 prod :: nil:cons -> 0':s 341.56/291.78 hole_0':s1_0 :: 0':s 341.56/291.78 hole_nil:cons2_0 :: nil:cons 341.56/291.78 gen_0':s3_0 :: Nat -> 0':s 341.56/291.78 gen_nil:cons4_0 :: Nat -> nil:cons 341.56/291.78 341.56/291.78 341.56/291.78 Lemmas: 341.56/291.78 +'(gen_0':s3_0(n6_0), gen_0':s3_0(n6_0)) -> gen_0':s3_0(*(2, n6_0)), rt in Omega(1 + n6_0) 341.56/291.78 341.56/291.78 341.56/291.78 Generator Equations: 341.56/291.78 gen_0':s3_0(0) <=> 0' 341.56/291.78 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 341.56/291.78 gen_nil:cons4_0(0) <=> nil 341.56/291.78 gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x)) 341.56/291.78 341.56/291.78 341.56/291.78 The following defined symbols remain to be analysed: 341.56/291.78 *', sum, prod 341.56/291.78 341.56/291.78 They will be analysed ascendingly in the following order: 341.56/291.78 *' < prod 341.56/291.78 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (13) RewriteLemmaProof (LOWER BOUND(ID)) 341.56/291.78 Proved the following rewrite lemma: 341.56/291.78 *'(gen_0':s3_0(n683_0), gen_0':s3_0(n683_0)) -> *5_0, rt in Omega(n683_0 + n683_0^2) 341.56/291.78 341.56/291.78 Induction Base: 341.56/291.78 *'(gen_0':s3_0(0), gen_0':s3_0(0)) 341.56/291.78 341.56/291.78 Induction Step: 341.56/291.78 *'(gen_0':s3_0(+(n683_0, 1)), gen_0':s3_0(+(n683_0, 1))) ->_R^Omega(1) 341.56/291.78 s(+'(*'(gen_0':s3_0(n683_0), gen_0':s3_0(n683_0)), +'(gen_0':s3_0(n683_0), gen_0':s3_0(n683_0)))) ->_IH 341.56/291.78 s(+'(*5_0, +'(gen_0':s3_0(n683_0), gen_0':s3_0(n683_0)))) ->_L^Omega(1 + n683_0) 341.56/291.78 s(+'(*5_0, gen_0':s3_0(*(2, n683_0)))) 341.56/291.78 341.56/291.78 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (14) 341.56/291.78 Complex Obligation (BEST) 341.56/291.78 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (15) 341.56/291.78 Obligation: 341.56/291.78 Proved the lower bound n^2 for the following obligation: 341.56/291.78 341.56/291.78 TRS: 341.56/291.78 Rules: 341.56/291.78 +'(x, 0') -> x 341.56/291.78 +'(0', x) -> x 341.56/291.78 +'(s(x), s(y)) -> s(s(+'(x, y))) 341.56/291.78 +'(+'(x, y), z) -> +'(x, +'(y, z)) 341.56/291.78 *'(x, 0') -> 0' 341.56/291.78 *'(0', x) -> 0' 341.56/291.78 *'(s(x), s(y)) -> s(+'(*'(x, y), +'(x, y))) 341.56/291.78 *'(*'(x, y), z) -> *'(x, *'(y, z)) 341.56/291.78 sum(nil) -> 0' 341.56/291.78 sum(cons(x, l)) -> +'(x, sum(l)) 341.56/291.78 prod(nil) -> s(0') 341.56/291.78 prod(cons(x, l)) -> *'(x, prod(l)) 341.56/291.78 341.56/291.78 Types: 341.56/291.78 +' :: 0':s -> 0':s -> 0':s 341.56/291.78 0' :: 0':s 341.56/291.78 s :: 0':s -> 0':s 341.56/291.78 *' :: 0':s -> 0':s -> 0':s 341.56/291.78 sum :: nil:cons -> 0':s 341.56/291.78 nil :: nil:cons 341.56/291.78 cons :: 0':s -> nil:cons -> nil:cons 341.56/291.78 prod :: nil:cons -> 0':s 341.56/291.78 hole_0':s1_0 :: 0':s 341.56/291.78 hole_nil:cons2_0 :: nil:cons 341.56/291.78 gen_0':s3_0 :: Nat -> 0':s 341.56/291.78 gen_nil:cons4_0 :: Nat -> nil:cons 341.56/291.78 341.56/291.78 341.56/291.78 Lemmas: 341.56/291.78 +'(gen_0':s3_0(n6_0), gen_0':s3_0(n6_0)) -> gen_0':s3_0(*(2, n6_0)), rt in Omega(1 + n6_0) 341.56/291.78 341.56/291.78 341.56/291.78 Generator Equations: 341.56/291.78 gen_0':s3_0(0) <=> 0' 341.56/291.78 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 341.56/291.78 gen_nil:cons4_0(0) <=> nil 341.56/291.78 gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x)) 341.56/291.78 341.56/291.78 341.56/291.78 The following defined symbols remain to be analysed: 341.56/291.78 *', sum, prod 341.56/291.78 341.56/291.78 They will be analysed ascendingly in the following order: 341.56/291.78 *' < prod 341.56/291.78 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (16) LowerBoundPropagationProof (FINISHED) 341.56/291.78 Propagated lower bound. 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (17) 341.56/291.78 BOUNDS(n^2, INF) 341.56/291.78 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (18) 341.56/291.78 Obligation: 341.56/291.78 TRS: 341.56/291.78 Rules: 341.56/291.78 +'(x, 0') -> x 341.56/291.78 +'(0', x) -> x 341.56/291.78 +'(s(x), s(y)) -> s(s(+'(x, y))) 341.56/291.78 +'(+'(x, y), z) -> +'(x, +'(y, z)) 341.56/291.78 *'(x, 0') -> 0' 341.56/291.78 *'(0', x) -> 0' 341.56/291.78 *'(s(x), s(y)) -> s(+'(*'(x, y), +'(x, y))) 341.56/291.78 *'(*'(x, y), z) -> *'(x, *'(y, z)) 341.56/291.78 sum(nil) -> 0' 341.56/291.78 sum(cons(x, l)) -> +'(x, sum(l)) 341.56/291.78 prod(nil) -> s(0') 341.56/291.78 prod(cons(x, l)) -> *'(x, prod(l)) 341.56/291.78 341.56/291.78 Types: 341.56/291.78 +' :: 0':s -> 0':s -> 0':s 341.56/291.78 0' :: 0':s 341.56/291.78 s :: 0':s -> 0':s 341.56/291.78 *' :: 0':s -> 0':s -> 0':s 341.56/291.78 sum :: nil:cons -> 0':s 341.56/291.78 nil :: nil:cons 341.56/291.78 cons :: 0':s -> nil:cons -> nil:cons 341.56/291.78 prod :: nil:cons -> 0':s 341.56/291.78 hole_0':s1_0 :: 0':s 341.56/291.78 hole_nil:cons2_0 :: nil:cons 341.56/291.78 gen_0':s3_0 :: Nat -> 0':s 341.56/291.78 gen_nil:cons4_0 :: Nat -> nil:cons 341.56/291.78 341.56/291.78 341.56/291.78 Lemmas: 341.56/291.78 +'(gen_0':s3_0(n6_0), gen_0':s3_0(n6_0)) -> gen_0':s3_0(*(2, n6_0)), rt in Omega(1 + n6_0) 341.56/291.78 *'(gen_0':s3_0(n683_0), gen_0':s3_0(n683_0)) -> *5_0, rt in Omega(n683_0 + n683_0^2) 341.56/291.78 341.56/291.78 341.56/291.78 Generator Equations: 341.56/291.78 gen_0':s3_0(0) <=> 0' 341.56/291.78 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 341.56/291.78 gen_nil:cons4_0(0) <=> nil 341.56/291.78 gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x)) 341.56/291.78 341.56/291.78 341.56/291.78 The following defined symbols remain to be analysed: 341.56/291.78 sum, prod 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (19) RewriteLemmaProof (LOWER BOUND(ID)) 341.56/291.78 Proved the following rewrite lemma: 341.56/291.78 sum(gen_nil:cons4_0(n13075_0)) -> gen_0':s3_0(0), rt in Omega(1 + n13075_0) 341.56/291.78 341.56/291.78 Induction Base: 341.56/291.78 sum(gen_nil:cons4_0(0)) ->_R^Omega(1) 341.56/291.78 0' 341.56/291.78 341.56/291.78 Induction Step: 341.56/291.78 sum(gen_nil:cons4_0(+(n13075_0, 1))) ->_R^Omega(1) 341.56/291.78 +'(0', sum(gen_nil:cons4_0(n13075_0))) ->_IH 341.56/291.78 +'(0', gen_0':s3_0(0)) ->_L^Omega(1) 341.56/291.78 gen_0':s3_0(*(2, 0)) 341.56/291.78 341.56/291.78 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (20) 341.56/291.78 Obligation: 341.56/291.78 TRS: 341.56/291.78 Rules: 341.56/291.78 +'(x, 0') -> x 341.56/291.78 +'(0', x) -> x 341.56/291.78 +'(s(x), s(y)) -> s(s(+'(x, y))) 341.56/291.78 +'(+'(x, y), z) -> +'(x, +'(y, z)) 341.56/291.78 *'(x, 0') -> 0' 341.56/291.78 *'(0', x) -> 0' 341.56/291.78 *'(s(x), s(y)) -> s(+'(*'(x, y), +'(x, y))) 341.56/291.78 *'(*'(x, y), z) -> *'(x, *'(y, z)) 341.56/291.78 sum(nil) -> 0' 341.56/291.78 sum(cons(x, l)) -> +'(x, sum(l)) 341.56/291.78 prod(nil) -> s(0') 341.56/291.78 prod(cons(x, l)) -> *'(x, prod(l)) 341.56/291.78 341.56/291.78 Types: 341.56/291.78 +' :: 0':s -> 0':s -> 0':s 341.56/291.78 0' :: 0':s 341.56/291.78 s :: 0':s -> 0':s 341.56/291.78 *' :: 0':s -> 0':s -> 0':s 341.56/291.78 sum :: nil:cons -> 0':s 341.56/291.78 nil :: nil:cons 341.56/291.78 cons :: 0':s -> nil:cons -> nil:cons 341.56/291.78 prod :: nil:cons -> 0':s 341.56/291.78 hole_0':s1_0 :: 0':s 341.56/291.78 hole_nil:cons2_0 :: nil:cons 341.56/291.78 gen_0':s3_0 :: Nat -> 0':s 341.56/291.78 gen_nil:cons4_0 :: Nat -> nil:cons 341.56/291.78 341.56/291.78 341.56/291.78 Lemmas: 341.56/291.78 +'(gen_0':s3_0(n6_0), gen_0':s3_0(n6_0)) -> gen_0':s3_0(*(2, n6_0)), rt in Omega(1 + n6_0) 341.56/291.78 *'(gen_0':s3_0(n683_0), gen_0':s3_0(n683_0)) -> *5_0, rt in Omega(n683_0 + n683_0^2) 341.56/291.78 sum(gen_nil:cons4_0(n13075_0)) -> gen_0':s3_0(0), rt in Omega(1 + n13075_0) 341.56/291.78 341.56/291.78 341.56/291.78 Generator Equations: 341.56/291.78 gen_0':s3_0(0) <=> 0' 341.56/291.78 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 341.56/291.78 gen_nil:cons4_0(0) <=> nil 341.56/291.78 gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x)) 341.56/291.78 341.56/291.78 341.56/291.78 The following defined symbols remain to be analysed: 341.56/291.78 prod 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (21) RewriteLemmaProof (LOWER BOUND(ID)) 341.56/291.78 Proved the following rewrite lemma: 341.56/291.78 prod(gen_nil:cons4_0(n13524_0)) -> *5_0, rt in Omega(n13524_0) 341.56/291.78 341.56/291.78 Induction Base: 341.56/291.78 prod(gen_nil:cons4_0(0)) 341.56/291.78 341.56/291.78 Induction Step: 341.56/291.78 prod(gen_nil:cons4_0(+(n13524_0, 1))) ->_R^Omega(1) 341.56/291.78 *'(0', prod(gen_nil:cons4_0(n13524_0))) ->_IH 341.56/291.78 *'(0', *5_0) 341.56/291.78 341.56/291.78 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 341.56/291.78 ---------------------------------------- 341.56/291.78 341.56/291.78 (22) 341.56/291.78 BOUNDS(1, INF) 341.62/291.83 EOF