1115.67/291.81 WORST_CASE(Omega(n^2), ?) 1131.81/295.89 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1131.81/295.89 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1131.81/295.89 1131.81/295.89 1131.81/295.89 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1131.81/295.89 1131.81/295.89 (0) CpxTRS 1131.81/295.89 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1131.81/295.89 (2) CpxTRS 1131.81/295.89 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1131.81/295.89 (4) typed CpxTrs 1131.81/295.89 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1131.81/295.89 (6) typed CpxTrs 1131.81/295.89 (7) RewriteLemmaProof [LOWER BOUND(ID), 237 ms] 1131.81/295.89 (8) BEST 1131.81/295.89 (9) proven lower bound 1131.81/295.89 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1131.81/295.89 (11) BOUNDS(n^1, INF) 1131.81/295.89 (12) typed CpxTrs 1131.81/295.89 (13) RewriteLemmaProof [LOWER BOUND(ID), 146 ms] 1131.81/295.89 (14) proven lower bound 1131.81/295.89 (15) LowerBoundPropagationProof [FINISHED, 0 ms] 1131.81/295.89 (16) BOUNDS(n^2, INF) 1131.81/295.89 1131.81/295.89 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (0) 1131.81/295.89 Obligation: 1131.81/295.89 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1131.81/295.89 1131.81/295.89 1131.81/295.89 The TRS R consists of the following rules: 1131.81/295.89 1131.81/295.89 sum(cons(s(n), x), cons(m, y)) -> sum(cons(n, x), cons(s(m), y)) 1131.81/295.89 sum(cons(0, x), y) -> sum(x, y) 1131.81/295.89 sum(nil, y) -> y 1131.81/295.89 empty(nil) -> true 1131.81/295.89 empty(cons(n, x)) -> false 1131.81/295.89 tail(nil) -> nil 1131.81/295.89 tail(cons(n, x)) -> x 1131.81/295.89 head(cons(n, x)) -> n 1131.81/295.89 weight(x) -> if(empty(x), empty(tail(x)), x) 1131.81/295.89 if(true, b, x) -> weight_undefined_error 1131.81/295.89 if(false, b, x) -> if2(b, x) 1131.81/295.89 if2(true, x) -> head(x) 1131.81/295.89 if2(false, x) -> weight(sum(x, cons(0, tail(tail(x))))) 1131.81/295.89 1131.81/295.89 S is empty. 1131.81/295.89 Rewrite Strategy: INNERMOST 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1131.81/295.89 Renamed function symbols to avoid clashes with predefined symbol. 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (2) 1131.81/295.89 Obligation: 1131.81/295.89 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1131.81/295.89 1131.81/295.89 1131.81/295.89 The TRS R consists of the following rules: 1131.81/295.89 1131.81/295.89 sum(cons(s(n), x), cons(m, y)) -> sum(cons(n, x), cons(s(m), y)) 1131.81/295.89 sum(cons(0', x), y) -> sum(x, y) 1131.81/295.89 sum(nil, y) -> y 1131.81/295.89 empty(nil) -> true 1131.81/295.89 empty(cons(n, x)) -> false 1131.81/295.89 tail(nil) -> nil 1131.81/295.89 tail(cons(n, x)) -> x 1131.81/295.89 head(cons(n, x)) -> n 1131.81/295.89 weight(x) -> if(empty(x), empty(tail(x)), x) 1131.81/295.89 if(true, b, x) -> weight_undefined_error 1131.81/295.89 if(false, b, x) -> if2(b, x) 1131.81/295.89 if2(true, x) -> head(x) 1131.81/295.89 if2(false, x) -> weight(sum(x, cons(0', tail(tail(x))))) 1131.81/295.89 1131.81/295.89 S is empty. 1131.81/295.89 Rewrite Strategy: INNERMOST 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1131.81/295.89 Infered types. 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (4) 1131.81/295.89 Obligation: 1131.81/295.89 Innermost TRS: 1131.81/295.89 Rules: 1131.81/295.89 sum(cons(s(n), x), cons(m, y)) -> sum(cons(n, x), cons(s(m), y)) 1131.81/295.89 sum(cons(0', x), y) -> sum(x, y) 1131.81/295.89 sum(nil, y) -> y 1131.81/295.89 empty(nil) -> true 1131.81/295.89 empty(cons(n, x)) -> false 1131.81/295.89 tail(nil) -> nil 1131.81/295.89 tail(cons(n, x)) -> x 1131.81/295.89 head(cons(n, x)) -> n 1131.81/295.89 weight(x) -> if(empty(x), empty(tail(x)), x) 1131.81/295.89 if(true, b, x) -> weight_undefined_error 1131.81/295.89 if(false, b, x) -> if2(b, x) 1131.81/295.89 if2(true, x) -> head(x) 1131.81/295.89 if2(false, x) -> weight(sum(x, cons(0', tail(tail(x))))) 1131.81/295.89 1131.81/295.89 Types: 1131.81/295.89 sum :: cons:nil -> cons:nil -> cons:nil 1131.81/295.89 cons :: s:0':weight_undefined_error -> cons:nil -> cons:nil 1131.81/295.89 s :: s:0':weight_undefined_error -> s:0':weight_undefined_error 1131.81/295.89 0' :: s:0':weight_undefined_error 1131.81/295.89 nil :: cons:nil 1131.81/295.89 empty :: cons:nil -> true:false 1131.81/295.89 true :: true:false 1131.81/295.89 false :: true:false 1131.81/295.89 tail :: cons:nil -> cons:nil 1131.81/295.89 head :: cons:nil -> s:0':weight_undefined_error 1131.81/295.89 weight :: cons:nil -> s:0':weight_undefined_error 1131.81/295.89 if :: true:false -> true:false -> cons:nil -> s:0':weight_undefined_error 1131.81/295.89 weight_undefined_error :: s:0':weight_undefined_error 1131.81/295.89 if2 :: true:false -> cons:nil -> s:0':weight_undefined_error 1131.81/295.89 hole_cons:nil1_0 :: cons:nil 1131.81/295.89 hole_s:0':weight_undefined_error2_0 :: s:0':weight_undefined_error 1131.81/295.89 hole_true:false3_0 :: true:false 1131.81/295.89 gen_cons:nil4_0 :: Nat -> cons:nil 1131.81/295.89 gen_s:0':weight_undefined_error5_0 :: Nat -> s:0':weight_undefined_error 1131.81/295.89 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (5) OrderProof (LOWER BOUND(ID)) 1131.81/295.89 Heuristically decided to analyse the following defined symbols: 1131.81/295.89 sum, weight 1131.81/295.89 1131.81/295.89 They will be analysed ascendingly in the following order: 1131.81/295.89 sum < weight 1131.81/295.89 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (6) 1131.81/295.89 Obligation: 1131.81/295.89 Innermost TRS: 1131.81/295.89 Rules: 1131.81/295.89 sum(cons(s(n), x), cons(m, y)) -> sum(cons(n, x), cons(s(m), y)) 1131.81/295.89 sum(cons(0', x), y) -> sum(x, y) 1131.81/295.89 sum(nil, y) -> y 1131.81/295.89 empty(nil) -> true 1131.81/295.89 empty(cons(n, x)) -> false 1131.81/295.89 tail(nil) -> nil 1131.81/295.89 tail(cons(n, x)) -> x 1131.81/295.89 head(cons(n, x)) -> n 1131.81/295.89 weight(x) -> if(empty(x), empty(tail(x)), x) 1131.81/295.89 if(true, b, x) -> weight_undefined_error 1131.81/295.89 if(false, b, x) -> if2(b, x) 1131.81/295.89 if2(true, x) -> head(x) 1131.81/295.89 if2(false, x) -> weight(sum(x, cons(0', tail(tail(x))))) 1131.81/295.89 1131.81/295.89 Types: 1131.81/295.89 sum :: cons:nil -> cons:nil -> cons:nil 1131.81/295.89 cons :: s:0':weight_undefined_error -> cons:nil -> cons:nil 1131.81/295.89 s :: s:0':weight_undefined_error -> s:0':weight_undefined_error 1131.81/295.89 0' :: s:0':weight_undefined_error 1131.81/295.89 nil :: cons:nil 1131.81/295.89 empty :: cons:nil -> true:false 1131.81/295.89 true :: true:false 1131.81/295.89 false :: true:false 1131.81/295.89 tail :: cons:nil -> cons:nil 1131.81/295.89 head :: cons:nil -> s:0':weight_undefined_error 1131.81/295.89 weight :: cons:nil -> s:0':weight_undefined_error 1131.81/295.89 if :: true:false -> true:false -> cons:nil -> s:0':weight_undefined_error 1131.81/295.89 weight_undefined_error :: s:0':weight_undefined_error 1131.81/295.89 if2 :: true:false -> cons:nil -> s:0':weight_undefined_error 1131.81/295.89 hole_cons:nil1_0 :: cons:nil 1131.81/295.89 hole_s:0':weight_undefined_error2_0 :: s:0':weight_undefined_error 1131.81/295.89 hole_true:false3_0 :: true:false 1131.81/295.89 gen_cons:nil4_0 :: Nat -> cons:nil 1131.81/295.89 gen_s:0':weight_undefined_error5_0 :: Nat -> s:0':weight_undefined_error 1131.81/295.89 1131.81/295.89 1131.81/295.89 Generator Equations: 1131.81/295.89 gen_cons:nil4_0(0) <=> nil 1131.81/295.89 gen_cons:nil4_0(+(x, 1)) <=> cons(0', gen_cons:nil4_0(x)) 1131.81/295.89 gen_s:0':weight_undefined_error5_0(0) <=> 0' 1131.81/295.89 gen_s:0':weight_undefined_error5_0(+(x, 1)) <=> s(gen_s:0':weight_undefined_error5_0(x)) 1131.81/295.89 1131.81/295.89 1131.81/295.89 The following defined symbols remain to be analysed: 1131.81/295.89 sum, weight 1131.81/295.89 1131.81/295.89 They will be analysed ascendingly in the following order: 1131.81/295.89 sum < weight 1131.81/295.89 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1131.81/295.89 Proved the following rewrite lemma: 1131.81/295.89 sum(gen_cons:nil4_0(n7_0), gen_cons:nil4_0(b)) -> gen_cons:nil4_0(b), rt in Omega(1 + n7_0) 1131.81/295.89 1131.81/295.89 Induction Base: 1131.81/295.89 sum(gen_cons:nil4_0(0), gen_cons:nil4_0(b)) ->_R^Omega(1) 1131.81/295.89 gen_cons:nil4_0(b) 1131.81/295.89 1131.81/295.89 Induction Step: 1131.81/295.89 sum(gen_cons:nil4_0(+(n7_0, 1)), gen_cons:nil4_0(b)) ->_R^Omega(1) 1131.81/295.89 sum(gen_cons:nil4_0(n7_0), gen_cons:nil4_0(b)) ->_IH 1131.81/295.89 gen_cons:nil4_0(b) 1131.81/295.89 1131.81/295.89 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (8) 1131.81/295.89 Complex Obligation (BEST) 1131.81/295.89 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (9) 1131.81/295.89 Obligation: 1131.81/295.89 Proved the lower bound n^1 for the following obligation: 1131.81/295.89 1131.81/295.89 Innermost TRS: 1131.81/295.89 Rules: 1131.81/295.89 sum(cons(s(n), x), cons(m, y)) -> sum(cons(n, x), cons(s(m), y)) 1131.81/295.89 sum(cons(0', x), y) -> sum(x, y) 1131.81/295.89 sum(nil, y) -> y 1131.81/295.89 empty(nil) -> true 1131.81/295.89 empty(cons(n, x)) -> false 1131.81/295.89 tail(nil) -> nil 1131.81/295.89 tail(cons(n, x)) -> x 1131.81/295.89 head(cons(n, x)) -> n 1131.81/295.89 weight(x) -> if(empty(x), empty(tail(x)), x) 1131.81/295.89 if(true, b, x) -> weight_undefined_error 1131.81/295.89 if(false, b, x) -> if2(b, x) 1131.81/295.89 if2(true, x) -> head(x) 1131.81/295.89 if2(false, x) -> weight(sum(x, cons(0', tail(tail(x))))) 1131.81/295.89 1131.81/295.89 Types: 1131.81/295.89 sum :: cons:nil -> cons:nil -> cons:nil 1131.81/295.89 cons :: s:0':weight_undefined_error -> cons:nil -> cons:nil 1131.81/295.89 s :: s:0':weight_undefined_error -> s:0':weight_undefined_error 1131.81/295.89 0' :: s:0':weight_undefined_error 1131.81/295.89 nil :: cons:nil 1131.81/295.89 empty :: cons:nil -> true:false 1131.81/295.89 true :: true:false 1131.81/295.89 false :: true:false 1131.81/295.89 tail :: cons:nil -> cons:nil 1131.81/295.89 head :: cons:nil -> s:0':weight_undefined_error 1131.81/295.89 weight :: cons:nil -> s:0':weight_undefined_error 1131.81/295.89 if :: true:false -> true:false -> cons:nil -> s:0':weight_undefined_error 1131.81/295.89 weight_undefined_error :: s:0':weight_undefined_error 1131.81/295.89 if2 :: true:false -> cons:nil -> s:0':weight_undefined_error 1131.81/295.89 hole_cons:nil1_0 :: cons:nil 1131.81/295.89 hole_s:0':weight_undefined_error2_0 :: s:0':weight_undefined_error 1131.81/295.89 hole_true:false3_0 :: true:false 1131.81/295.89 gen_cons:nil4_0 :: Nat -> cons:nil 1131.81/295.89 gen_s:0':weight_undefined_error5_0 :: Nat -> s:0':weight_undefined_error 1131.81/295.89 1131.81/295.89 1131.81/295.89 Generator Equations: 1131.81/295.89 gen_cons:nil4_0(0) <=> nil 1131.81/295.89 gen_cons:nil4_0(+(x, 1)) <=> cons(0', gen_cons:nil4_0(x)) 1131.81/295.89 gen_s:0':weight_undefined_error5_0(0) <=> 0' 1131.81/295.89 gen_s:0':weight_undefined_error5_0(+(x, 1)) <=> s(gen_s:0':weight_undefined_error5_0(x)) 1131.81/295.89 1131.81/295.89 1131.81/295.89 The following defined symbols remain to be analysed: 1131.81/295.89 sum, weight 1131.81/295.89 1131.81/295.89 They will be analysed ascendingly in the following order: 1131.81/295.89 sum < weight 1131.81/295.89 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (10) LowerBoundPropagationProof (FINISHED) 1131.81/295.89 Propagated lower bound. 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (11) 1131.81/295.89 BOUNDS(n^1, INF) 1131.81/295.89 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (12) 1131.81/295.89 Obligation: 1131.81/295.89 Innermost TRS: 1131.81/295.89 Rules: 1131.81/295.89 sum(cons(s(n), x), cons(m, y)) -> sum(cons(n, x), cons(s(m), y)) 1131.81/295.89 sum(cons(0', x), y) -> sum(x, y) 1131.81/295.89 sum(nil, y) -> y 1131.81/295.89 empty(nil) -> true 1131.81/295.89 empty(cons(n, x)) -> false 1131.81/295.89 tail(nil) -> nil 1131.81/295.89 tail(cons(n, x)) -> x 1131.81/295.89 head(cons(n, x)) -> n 1131.81/295.89 weight(x) -> if(empty(x), empty(tail(x)), x) 1131.81/295.89 if(true, b, x) -> weight_undefined_error 1131.81/295.89 if(false, b, x) -> if2(b, x) 1131.81/295.89 if2(true, x) -> head(x) 1131.81/295.89 if2(false, x) -> weight(sum(x, cons(0', tail(tail(x))))) 1131.81/295.89 1131.81/295.89 Types: 1131.81/295.89 sum :: cons:nil -> cons:nil -> cons:nil 1131.81/295.89 cons :: s:0':weight_undefined_error -> cons:nil -> cons:nil 1131.81/295.89 s :: s:0':weight_undefined_error -> s:0':weight_undefined_error 1131.81/295.89 0' :: s:0':weight_undefined_error 1131.81/295.89 nil :: cons:nil 1131.81/295.89 empty :: cons:nil -> true:false 1131.81/295.89 true :: true:false 1131.81/295.89 false :: true:false 1131.81/295.89 tail :: cons:nil -> cons:nil 1131.81/295.89 head :: cons:nil -> s:0':weight_undefined_error 1131.81/295.89 weight :: cons:nil -> s:0':weight_undefined_error 1131.81/295.89 if :: true:false -> true:false -> cons:nil -> s:0':weight_undefined_error 1131.81/295.89 weight_undefined_error :: s:0':weight_undefined_error 1131.81/295.89 if2 :: true:false -> cons:nil -> s:0':weight_undefined_error 1131.81/295.89 hole_cons:nil1_0 :: cons:nil 1131.81/295.89 hole_s:0':weight_undefined_error2_0 :: s:0':weight_undefined_error 1131.81/295.89 hole_true:false3_0 :: true:false 1131.81/295.89 gen_cons:nil4_0 :: Nat -> cons:nil 1131.81/295.89 gen_s:0':weight_undefined_error5_0 :: Nat -> s:0':weight_undefined_error 1131.81/295.89 1131.81/295.89 1131.81/295.89 Lemmas: 1131.81/295.89 sum(gen_cons:nil4_0(n7_0), gen_cons:nil4_0(b)) -> gen_cons:nil4_0(b), rt in Omega(1 + n7_0) 1131.81/295.89 1131.81/295.89 1131.81/295.89 Generator Equations: 1131.81/295.89 gen_cons:nil4_0(0) <=> nil 1131.81/295.89 gen_cons:nil4_0(+(x, 1)) <=> cons(0', gen_cons:nil4_0(x)) 1131.81/295.89 gen_s:0':weight_undefined_error5_0(0) <=> 0' 1131.81/295.89 gen_s:0':weight_undefined_error5_0(+(x, 1)) <=> s(gen_s:0':weight_undefined_error5_0(x)) 1131.81/295.89 1131.81/295.89 1131.81/295.89 The following defined symbols remain to be analysed: 1131.81/295.89 weight 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (13) RewriteLemmaProof (LOWER BOUND(ID)) 1131.81/295.89 Proved the following rewrite lemma: 1131.81/295.89 weight(gen_cons:nil4_0(+(1, n680_0))) -> gen_s:0':weight_undefined_error5_0(0), rt in Omega(1 + n680_0 + n680_0^2) 1131.81/295.89 1131.81/295.89 Induction Base: 1131.81/295.89 weight(gen_cons:nil4_0(+(1, 0))) ->_R^Omega(1) 1131.81/295.89 if(empty(gen_cons:nil4_0(+(1, 0))), empty(tail(gen_cons:nil4_0(+(1, 0)))), gen_cons:nil4_0(+(1, 0))) ->_R^Omega(1) 1131.81/295.89 if(false, empty(tail(gen_cons:nil4_0(1))), gen_cons:nil4_0(1)) ->_R^Omega(1) 1131.81/295.89 if(false, empty(gen_cons:nil4_0(0)), gen_cons:nil4_0(1)) ->_R^Omega(1) 1131.81/295.89 if(false, true, gen_cons:nil4_0(1)) ->_R^Omega(1) 1131.81/295.89 if2(true, gen_cons:nil4_0(1)) ->_R^Omega(1) 1131.81/295.89 head(gen_cons:nil4_0(1)) ->_R^Omega(1) 1131.81/295.89 0' 1131.81/295.89 1131.81/295.89 Induction Step: 1131.81/295.89 weight(gen_cons:nil4_0(+(1, +(n680_0, 1)))) ->_R^Omega(1) 1131.81/295.89 if(empty(gen_cons:nil4_0(+(1, +(n680_0, 1)))), empty(tail(gen_cons:nil4_0(+(1, +(n680_0, 1))))), gen_cons:nil4_0(+(1, +(n680_0, 1)))) ->_R^Omega(1) 1131.81/295.89 if(false, empty(tail(gen_cons:nil4_0(+(2, n680_0)))), gen_cons:nil4_0(+(2, n680_0))) ->_R^Omega(1) 1131.81/295.89 if(false, empty(gen_cons:nil4_0(+(1, n680_0))), gen_cons:nil4_0(+(2, n680_0))) ->_R^Omega(1) 1131.81/295.89 if(false, false, gen_cons:nil4_0(+(2, n680_0))) ->_R^Omega(1) 1131.81/295.89 if2(false, gen_cons:nil4_0(+(2, n680_0))) ->_R^Omega(1) 1131.81/295.89 weight(sum(gen_cons:nil4_0(+(2, n680_0)), cons(0', tail(tail(gen_cons:nil4_0(+(2, n680_0))))))) ->_R^Omega(1) 1131.81/295.89 weight(sum(gen_cons:nil4_0(+(2, n680_0)), cons(0', tail(gen_cons:nil4_0(+(1, n680_0)))))) ->_R^Omega(1) 1131.81/295.89 weight(sum(gen_cons:nil4_0(+(2, n680_0)), cons(0', gen_cons:nil4_0(n680_0)))) ->_L^Omega(3 + n680_0) 1131.81/295.89 weight(gen_cons:nil4_0(+(n680_0, 1))) ->_IH 1131.81/295.89 gen_s:0':weight_undefined_error5_0(0) 1131.81/295.89 1131.81/295.89 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (14) 1131.81/295.89 Obligation: 1131.81/295.89 Proved the lower bound n^2 for the following obligation: 1131.81/295.89 1131.81/295.89 Innermost TRS: 1131.81/295.89 Rules: 1131.81/295.89 sum(cons(s(n), x), cons(m, y)) -> sum(cons(n, x), cons(s(m), y)) 1131.81/295.89 sum(cons(0', x), y) -> sum(x, y) 1131.81/295.89 sum(nil, y) -> y 1131.81/295.89 empty(nil) -> true 1131.81/295.89 empty(cons(n, x)) -> false 1131.81/295.89 tail(nil) -> nil 1131.81/295.89 tail(cons(n, x)) -> x 1131.81/295.89 head(cons(n, x)) -> n 1131.81/295.89 weight(x) -> if(empty(x), empty(tail(x)), x) 1131.81/295.89 if(true, b, x) -> weight_undefined_error 1131.81/295.89 if(false, b, x) -> if2(b, x) 1131.81/295.89 if2(true, x) -> head(x) 1131.81/295.89 if2(false, x) -> weight(sum(x, cons(0', tail(tail(x))))) 1131.81/295.89 1131.81/295.89 Types: 1131.81/295.89 sum :: cons:nil -> cons:nil -> cons:nil 1131.81/295.89 cons :: s:0':weight_undefined_error -> cons:nil -> cons:nil 1131.81/295.89 s :: s:0':weight_undefined_error -> s:0':weight_undefined_error 1131.81/295.89 0' :: s:0':weight_undefined_error 1131.81/295.89 nil :: cons:nil 1131.81/295.89 empty :: cons:nil -> true:false 1131.81/295.89 true :: true:false 1131.81/295.89 false :: true:false 1131.81/295.89 tail :: cons:nil -> cons:nil 1131.81/295.89 head :: cons:nil -> s:0':weight_undefined_error 1131.81/295.89 weight :: cons:nil -> s:0':weight_undefined_error 1131.81/295.89 if :: true:false -> true:false -> cons:nil -> s:0':weight_undefined_error 1131.81/295.89 weight_undefined_error :: s:0':weight_undefined_error 1131.81/295.89 if2 :: true:false -> cons:nil -> s:0':weight_undefined_error 1131.81/295.89 hole_cons:nil1_0 :: cons:nil 1131.81/295.89 hole_s:0':weight_undefined_error2_0 :: s:0':weight_undefined_error 1131.81/295.89 hole_true:false3_0 :: true:false 1131.81/295.89 gen_cons:nil4_0 :: Nat -> cons:nil 1131.81/295.89 gen_s:0':weight_undefined_error5_0 :: Nat -> s:0':weight_undefined_error 1131.81/295.89 1131.81/295.89 1131.81/295.89 Lemmas: 1131.81/295.89 sum(gen_cons:nil4_0(n7_0), gen_cons:nil4_0(b)) -> gen_cons:nil4_0(b), rt in Omega(1 + n7_0) 1131.81/295.89 1131.81/295.89 1131.81/295.89 Generator Equations: 1131.81/295.89 gen_cons:nil4_0(0) <=> nil 1131.81/295.89 gen_cons:nil4_0(+(x, 1)) <=> cons(0', gen_cons:nil4_0(x)) 1131.81/295.89 gen_s:0':weight_undefined_error5_0(0) <=> 0' 1131.81/295.89 gen_s:0':weight_undefined_error5_0(+(x, 1)) <=> s(gen_s:0':weight_undefined_error5_0(x)) 1131.81/295.89 1131.81/295.89 1131.81/295.89 The following defined symbols remain to be analysed: 1131.81/295.89 weight 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (15) LowerBoundPropagationProof (FINISHED) 1131.81/295.89 Propagated lower bound. 1131.81/295.89 ---------------------------------------- 1131.81/295.89 1131.81/295.89 (16) 1131.81/295.89 BOUNDS(n^2, INF) 1131.96/295.97 EOF