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