319.59/291.48 WORST_CASE(Omega(n^2), ?) 319.69/291.49 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 319.69/291.49 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 319.69/291.49 319.69/291.49 319.69/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 319.69/291.49 319.69/291.49 (0) CpxTRS 319.69/291.49 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 319.69/291.49 (2) CpxTRS 319.69/291.49 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 319.69/291.49 (4) typed CpxTrs 319.69/291.49 (5) OrderProof [LOWER BOUND(ID), 0 ms] 319.69/291.49 (6) typed CpxTrs 319.69/291.49 (7) RewriteLemmaProof [LOWER BOUND(ID), 218 ms] 319.69/291.49 (8) BEST 319.69/291.49 (9) proven lower bound 319.69/291.49 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 319.69/291.49 (11) BOUNDS(n^1, INF) 319.69/291.49 (12) typed CpxTrs 319.69/291.49 (13) RewriteLemmaProof [LOWER BOUND(ID), 74 ms] 319.69/291.49 (14) typed CpxTrs 319.69/291.49 (15) RewriteLemmaProof [LOWER BOUND(ID), 46 ms] 319.69/291.49 (16) typed CpxTrs 319.69/291.49 (17) RewriteLemmaProof [LOWER BOUND(ID), 247 ms] 319.69/291.49 (18) proven lower bound 319.69/291.49 (19) LowerBoundPropagationProof [FINISHED, 0 ms] 319.69/291.49 (20) BOUNDS(n^2, INF) 319.69/291.49 319.69/291.49 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (0) 319.69/291.49 Obligation: 319.69/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 319.69/291.49 319.69/291.49 319.69/291.49 The TRS R consists of the following rules: 319.69/291.49 319.69/291.49 isEmpty(nil) -> true 319.69/291.49 isEmpty(cons(x, xs)) -> false 319.69/291.49 last(cons(x, nil)) -> x 319.69/291.49 last(cons(x, cons(y, ys))) -> last(cons(y, ys)) 319.69/291.49 dropLast(nil) -> nil 319.69/291.49 dropLast(cons(x, nil)) -> nil 319.69/291.49 dropLast(cons(x, cons(y, ys))) -> cons(x, dropLast(cons(y, ys))) 319.69/291.49 append(nil, ys) -> ys 319.69/291.49 append(cons(x, xs), ys) -> cons(x, append(xs, ys)) 319.69/291.49 reverse(xs) -> rev(xs, nil) 319.69/291.49 rev(xs, ys) -> if(isEmpty(xs), dropLast(xs), append(ys, last(xs)), ys) 319.69/291.49 if(true, xs, ys, zs) -> zs 319.69/291.49 if(false, xs, ys, zs) -> rev(xs, ys) 319.69/291.49 319.69/291.49 S is empty. 319.69/291.49 Rewrite Strategy: FULL 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 319.69/291.49 Renamed function symbols to avoid clashes with predefined symbol. 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (2) 319.69/291.49 Obligation: 319.69/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 319.69/291.49 319.69/291.49 319.69/291.49 The TRS R consists of the following rules: 319.69/291.49 319.69/291.49 isEmpty(nil) -> true 319.69/291.49 isEmpty(cons(x, xs)) -> false 319.69/291.49 last(cons(x, nil)) -> x 319.69/291.49 last(cons(x, cons(y, ys))) -> last(cons(y, ys)) 319.69/291.49 dropLast(nil) -> nil 319.69/291.49 dropLast(cons(x, nil)) -> nil 319.69/291.49 dropLast(cons(x, cons(y, ys))) -> cons(x, dropLast(cons(y, ys))) 319.69/291.49 append(nil, ys) -> ys 319.69/291.49 append(cons(x, xs), ys) -> cons(x, append(xs, ys)) 319.69/291.49 reverse(xs) -> rev(xs, nil) 319.69/291.49 rev(xs, ys) -> if(isEmpty(xs), dropLast(xs), append(ys, last(xs)), ys) 319.69/291.49 if(true, xs, ys, zs) -> zs 319.69/291.49 if(false, xs, ys, zs) -> rev(xs, ys) 319.69/291.49 319.69/291.49 S is empty. 319.69/291.49 Rewrite Strategy: FULL 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 319.69/291.49 Infered types. 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (4) 319.69/291.49 Obligation: 319.69/291.49 TRS: 319.69/291.49 Rules: 319.69/291.49 isEmpty(nil) -> true 319.69/291.49 isEmpty(cons(x, xs)) -> false 319.69/291.49 last(cons(x, nil)) -> x 319.69/291.49 last(cons(x, cons(y, ys))) -> last(cons(y, ys)) 319.69/291.49 dropLast(nil) -> nil 319.69/291.49 dropLast(cons(x, nil)) -> nil 319.69/291.49 dropLast(cons(x, cons(y, ys))) -> cons(x, dropLast(cons(y, ys))) 319.69/291.49 append(nil, ys) -> ys 319.69/291.49 append(cons(x, xs), ys) -> cons(x, append(xs, ys)) 319.69/291.49 reverse(xs) -> rev(xs, nil) 319.69/291.49 rev(xs, ys) -> if(isEmpty(xs), dropLast(xs), append(ys, last(xs)), ys) 319.69/291.49 if(true, xs, ys, zs) -> zs 319.69/291.49 if(false, xs, ys, zs) -> rev(xs, ys) 319.69/291.49 319.69/291.49 Types: 319.69/291.49 isEmpty :: nil:cons -> true:false 319.69/291.49 nil :: nil:cons 319.69/291.49 true :: true:false 319.69/291.49 cons :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 false :: true:false 319.69/291.49 last :: nil:cons -> nil:cons 319.69/291.49 dropLast :: nil:cons -> nil:cons 319.69/291.49 append :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 reverse :: nil:cons -> nil:cons 319.69/291.49 rev :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 if :: true:false -> nil:cons -> nil:cons -> nil:cons -> nil:cons 319.69/291.49 hole_true:false1_0 :: true:false 319.69/291.49 hole_nil:cons2_0 :: nil:cons 319.69/291.49 gen_nil:cons3_0 :: Nat -> nil:cons 319.69/291.49 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (5) OrderProof (LOWER BOUND(ID)) 319.69/291.49 Heuristically decided to analyse the following defined symbols: 319.69/291.49 last, dropLast, append, rev 319.69/291.49 319.69/291.49 They will be analysed ascendingly in the following order: 319.69/291.49 last < rev 319.69/291.49 dropLast < rev 319.69/291.49 append < rev 319.69/291.49 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (6) 319.69/291.49 Obligation: 319.69/291.49 TRS: 319.69/291.49 Rules: 319.69/291.49 isEmpty(nil) -> true 319.69/291.49 isEmpty(cons(x, xs)) -> false 319.69/291.49 last(cons(x, nil)) -> x 319.69/291.49 last(cons(x, cons(y, ys))) -> last(cons(y, ys)) 319.69/291.49 dropLast(nil) -> nil 319.69/291.49 dropLast(cons(x, nil)) -> nil 319.69/291.49 dropLast(cons(x, cons(y, ys))) -> cons(x, dropLast(cons(y, ys))) 319.69/291.49 append(nil, ys) -> ys 319.69/291.49 append(cons(x, xs), ys) -> cons(x, append(xs, ys)) 319.69/291.49 reverse(xs) -> rev(xs, nil) 319.69/291.49 rev(xs, ys) -> if(isEmpty(xs), dropLast(xs), append(ys, last(xs)), ys) 319.69/291.49 if(true, xs, ys, zs) -> zs 319.69/291.49 if(false, xs, ys, zs) -> rev(xs, ys) 319.69/291.49 319.69/291.49 Types: 319.69/291.49 isEmpty :: nil:cons -> true:false 319.69/291.49 nil :: nil:cons 319.69/291.49 true :: true:false 319.69/291.49 cons :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 false :: true:false 319.69/291.49 last :: nil:cons -> nil:cons 319.69/291.49 dropLast :: nil:cons -> nil:cons 319.69/291.49 append :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 reverse :: nil:cons -> nil:cons 319.69/291.49 rev :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 if :: true:false -> nil:cons -> nil:cons -> nil:cons -> nil:cons 319.69/291.49 hole_true:false1_0 :: true:false 319.69/291.49 hole_nil:cons2_0 :: nil:cons 319.69/291.49 gen_nil:cons3_0 :: Nat -> nil:cons 319.69/291.49 319.69/291.49 319.69/291.49 Generator Equations: 319.69/291.49 gen_nil:cons3_0(0) <=> nil 319.69/291.49 gen_nil:cons3_0(+(x, 1)) <=> cons(nil, gen_nil:cons3_0(x)) 319.69/291.49 319.69/291.49 319.69/291.49 The following defined symbols remain to be analysed: 319.69/291.49 last, dropLast, append, rev 319.69/291.49 319.69/291.49 They will be analysed ascendingly in the following order: 319.69/291.49 last < rev 319.69/291.49 dropLast < rev 319.69/291.49 append < rev 319.69/291.49 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (7) RewriteLemmaProof (LOWER BOUND(ID)) 319.69/291.49 Proved the following rewrite lemma: 319.69/291.49 last(gen_nil:cons3_0(+(1, n5_0))) -> gen_nil:cons3_0(0), rt in Omega(1 + n5_0) 319.69/291.49 319.69/291.49 Induction Base: 319.69/291.49 last(gen_nil:cons3_0(+(1, 0))) ->_R^Omega(1) 319.69/291.49 nil 319.69/291.49 319.69/291.49 Induction Step: 319.69/291.49 last(gen_nil:cons3_0(+(1, +(n5_0, 1)))) ->_R^Omega(1) 319.69/291.49 last(cons(nil, gen_nil:cons3_0(n5_0))) ->_IH 319.69/291.49 gen_nil:cons3_0(0) 319.69/291.49 319.69/291.49 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (8) 319.69/291.49 Complex Obligation (BEST) 319.69/291.49 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (9) 319.69/291.49 Obligation: 319.69/291.49 Proved the lower bound n^1 for the following obligation: 319.69/291.49 319.69/291.49 TRS: 319.69/291.49 Rules: 319.69/291.49 isEmpty(nil) -> true 319.69/291.49 isEmpty(cons(x, xs)) -> false 319.69/291.49 last(cons(x, nil)) -> x 319.69/291.49 last(cons(x, cons(y, ys))) -> last(cons(y, ys)) 319.69/291.49 dropLast(nil) -> nil 319.69/291.49 dropLast(cons(x, nil)) -> nil 319.69/291.49 dropLast(cons(x, cons(y, ys))) -> cons(x, dropLast(cons(y, ys))) 319.69/291.49 append(nil, ys) -> ys 319.69/291.49 append(cons(x, xs), ys) -> cons(x, append(xs, ys)) 319.69/291.49 reverse(xs) -> rev(xs, nil) 319.69/291.49 rev(xs, ys) -> if(isEmpty(xs), dropLast(xs), append(ys, last(xs)), ys) 319.69/291.49 if(true, xs, ys, zs) -> zs 319.69/291.49 if(false, xs, ys, zs) -> rev(xs, ys) 319.69/291.49 319.69/291.49 Types: 319.69/291.49 isEmpty :: nil:cons -> true:false 319.69/291.49 nil :: nil:cons 319.69/291.49 true :: true:false 319.69/291.49 cons :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 false :: true:false 319.69/291.49 last :: nil:cons -> nil:cons 319.69/291.49 dropLast :: nil:cons -> nil:cons 319.69/291.49 append :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 reverse :: nil:cons -> nil:cons 319.69/291.49 rev :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 if :: true:false -> nil:cons -> nil:cons -> nil:cons -> nil:cons 319.69/291.49 hole_true:false1_0 :: true:false 319.69/291.49 hole_nil:cons2_0 :: nil:cons 319.69/291.49 gen_nil:cons3_0 :: Nat -> nil:cons 319.69/291.49 319.69/291.49 319.69/291.49 Generator Equations: 319.69/291.49 gen_nil:cons3_0(0) <=> nil 319.69/291.49 gen_nil:cons3_0(+(x, 1)) <=> cons(nil, gen_nil:cons3_0(x)) 319.69/291.49 319.69/291.49 319.69/291.49 The following defined symbols remain to be analysed: 319.69/291.49 last, dropLast, append, rev 319.69/291.49 319.69/291.49 They will be analysed ascendingly in the following order: 319.69/291.49 last < rev 319.69/291.49 dropLast < rev 319.69/291.49 append < rev 319.69/291.49 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (10) LowerBoundPropagationProof (FINISHED) 319.69/291.49 Propagated lower bound. 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (11) 319.69/291.49 BOUNDS(n^1, INF) 319.69/291.49 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (12) 319.69/291.49 Obligation: 319.69/291.49 TRS: 319.69/291.49 Rules: 319.69/291.49 isEmpty(nil) -> true 319.69/291.49 isEmpty(cons(x, xs)) -> false 319.69/291.49 last(cons(x, nil)) -> x 319.69/291.49 last(cons(x, cons(y, ys))) -> last(cons(y, ys)) 319.69/291.49 dropLast(nil) -> nil 319.69/291.49 dropLast(cons(x, nil)) -> nil 319.69/291.49 dropLast(cons(x, cons(y, ys))) -> cons(x, dropLast(cons(y, ys))) 319.69/291.49 append(nil, ys) -> ys 319.69/291.49 append(cons(x, xs), ys) -> cons(x, append(xs, ys)) 319.69/291.49 reverse(xs) -> rev(xs, nil) 319.69/291.49 rev(xs, ys) -> if(isEmpty(xs), dropLast(xs), append(ys, last(xs)), ys) 319.69/291.49 if(true, xs, ys, zs) -> zs 319.69/291.49 if(false, xs, ys, zs) -> rev(xs, ys) 319.69/291.49 319.69/291.49 Types: 319.69/291.49 isEmpty :: nil:cons -> true:false 319.69/291.49 nil :: nil:cons 319.69/291.49 true :: true:false 319.69/291.49 cons :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 false :: true:false 319.69/291.49 last :: nil:cons -> nil:cons 319.69/291.49 dropLast :: nil:cons -> nil:cons 319.69/291.49 append :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 reverse :: nil:cons -> nil:cons 319.69/291.49 rev :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 if :: true:false -> nil:cons -> nil:cons -> nil:cons -> nil:cons 319.69/291.49 hole_true:false1_0 :: true:false 319.69/291.49 hole_nil:cons2_0 :: nil:cons 319.69/291.49 gen_nil:cons3_0 :: Nat -> nil:cons 319.69/291.49 319.69/291.49 319.69/291.49 Lemmas: 319.69/291.49 last(gen_nil:cons3_0(+(1, n5_0))) -> gen_nil:cons3_0(0), rt in Omega(1 + n5_0) 319.69/291.49 319.69/291.49 319.69/291.49 Generator Equations: 319.69/291.49 gen_nil:cons3_0(0) <=> nil 319.69/291.49 gen_nil:cons3_0(+(x, 1)) <=> cons(nil, gen_nil:cons3_0(x)) 319.69/291.49 319.69/291.49 319.69/291.49 The following defined symbols remain to be analysed: 319.69/291.49 dropLast, append, rev 319.69/291.49 319.69/291.49 They will be analysed ascendingly in the following order: 319.69/291.49 dropLast < rev 319.69/291.49 append < rev 319.69/291.49 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (13) RewriteLemmaProof (LOWER BOUND(ID)) 319.69/291.49 Proved the following rewrite lemma: 319.69/291.49 dropLast(gen_nil:cons3_0(+(1, n198_0))) -> gen_nil:cons3_0(n198_0), rt in Omega(1 + n198_0) 319.69/291.49 319.69/291.49 Induction Base: 319.69/291.49 dropLast(gen_nil:cons3_0(+(1, 0))) ->_R^Omega(1) 319.69/291.49 nil 319.69/291.49 319.69/291.49 Induction Step: 319.69/291.49 dropLast(gen_nil:cons3_0(+(1, +(n198_0, 1)))) ->_R^Omega(1) 319.69/291.49 cons(nil, dropLast(cons(nil, gen_nil:cons3_0(n198_0)))) ->_IH 319.69/291.49 cons(nil, gen_nil:cons3_0(c199_0)) 319.69/291.49 319.69/291.49 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (14) 319.69/291.49 Obligation: 319.69/291.49 TRS: 319.69/291.49 Rules: 319.69/291.49 isEmpty(nil) -> true 319.69/291.49 isEmpty(cons(x, xs)) -> false 319.69/291.49 last(cons(x, nil)) -> x 319.69/291.49 last(cons(x, cons(y, ys))) -> last(cons(y, ys)) 319.69/291.49 dropLast(nil) -> nil 319.69/291.49 dropLast(cons(x, nil)) -> nil 319.69/291.49 dropLast(cons(x, cons(y, ys))) -> cons(x, dropLast(cons(y, ys))) 319.69/291.49 append(nil, ys) -> ys 319.69/291.49 append(cons(x, xs), ys) -> cons(x, append(xs, ys)) 319.69/291.49 reverse(xs) -> rev(xs, nil) 319.69/291.49 rev(xs, ys) -> if(isEmpty(xs), dropLast(xs), append(ys, last(xs)), ys) 319.69/291.49 if(true, xs, ys, zs) -> zs 319.69/291.49 if(false, xs, ys, zs) -> rev(xs, ys) 319.69/291.49 319.69/291.49 Types: 319.69/291.49 isEmpty :: nil:cons -> true:false 319.69/291.49 nil :: nil:cons 319.69/291.49 true :: true:false 319.69/291.49 cons :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 false :: true:false 319.69/291.49 last :: nil:cons -> nil:cons 319.69/291.49 dropLast :: nil:cons -> nil:cons 319.69/291.49 append :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 reverse :: nil:cons -> nil:cons 319.69/291.49 rev :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 if :: true:false -> nil:cons -> nil:cons -> nil:cons -> nil:cons 319.69/291.49 hole_true:false1_0 :: true:false 319.69/291.49 hole_nil:cons2_0 :: nil:cons 319.69/291.49 gen_nil:cons3_0 :: Nat -> nil:cons 319.69/291.49 319.69/291.49 319.69/291.49 Lemmas: 319.69/291.49 last(gen_nil:cons3_0(+(1, n5_0))) -> gen_nil:cons3_0(0), rt in Omega(1 + n5_0) 319.69/291.49 dropLast(gen_nil:cons3_0(+(1, n198_0))) -> gen_nil:cons3_0(n198_0), rt in Omega(1 + n198_0) 319.69/291.49 319.69/291.49 319.69/291.49 Generator Equations: 319.69/291.49 gen_nil:cons3_0(0) <=> nil 319.69/291.49 gen_nil:cons3_0(+(x, 1)) <=> cons(nil, gen_nil:cons3_0(x)) 319.69/291.49 319.69/291.49 319.69/291.49 The following defined symbols remain to be analysed: 319.69/291.49 append, rev 319.69/291.49 319.69/291.49 They will be analysed ascendingly in the following order: 319.69/291.49 append < rev 319.69/291.49 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (15) RewriteLemmaProof (LOWER BOUND(ID)) 319.69/291.49 Proved the following rewrite lemma: 319.69/291.49 append(gen_nil:cons3_0(n545_0), gen_nil:cons3_0(b)) -> gen_nil:cons3_0(+(n545_0, b)), rt in Omega(1 + n545_0) 319.69/291.49 319.69/291.49 Induction Base: 319.69/291.49 append(gen_nil:cons3_0(0), gen_nil:cons3_0(b)) ->_R^Omega(1) 319.69/291.49 gen_nil:cons3_0(b) 319.69/291.49 319.69/291.49 Induction Step: 319.69/291.49 append(gen_nil:cons3_0(+(n545_0, 1)), gen_nil:cons3_0(b)) ->_R^Omega(1) 319.69/291.49 cons(nil, append(gen_nil:cons3_0(n545_0), gen_nil:cons3_0(b))) ->_IH 319.69/291.49 cons(nil, gen_nil:cons3_0(+(b, c546_0))) 319.69/291.49 319.69/291.49 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (16) 319.69/291.49 Obligation: 319.69/291.49 TRS: 319.69/291.49 Rules: 319.69/291.49 isEmpty(nil) -> true 319.69/291.49 isEmpty(cons(x, xs)) -> false 319.69/291.49 last(cons(x, nil)) -> x 319.69/291.49 last(cons(x, cons(y, ys))) -> last(cons(y, ys)) 319.69/291.49 dropLast(nil) -> nil 319.69/291.49 dropLast(cons(x, nil)) -> nil 319.69/291.49 dropLast(cons(x, cons(y, ys))) -> cons(x, dropLast(cons(y, ys))) 319.69/291.49 append(nil, ys) -> ys 319.69/291.49 append(cons(x, xs), ys) -> cons(x, append(xs, ys)) 319.69/291.49 reverse(xs) -> rev(xs, nil) 319.69/291.49 rev(xs, ys) -> if(isEmpty(xs), dropLast(xs), append(ys, last(xs)), ys) 319.69/291.49 if(true, xs, ys, zs) -> zs 319.69/291.49 if(false, xs, ys, zs) -> rev(xs, ys) 319.69/291.49 319.69/291.49 Types: 319.69/291.49 isEmpty :: nil:cons -> true:false 319.69/291.49 nil :: nil:cons 319.69/291.49 true :: true:false 319.69/291.49 cons :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 false :: true:false 319.69/291.49 last :: nil:cons -> nil:cons 319.69/291.49 dropLast :: nil:cons -> nil:cons 319.69/291.49 append :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 reverse :: nil:cons -> nil:cons 319.69/291.49 rev :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 if :: true:false -> nil:cons -> nil:cons -> nil:cons -> nil:cons 319.69/291.49 hole_true:false1_0 :: true:false 319.69/291.49 hole_nil:cons2_0 :: nil:cons 319.69/291.49 gen_nil:cons3_0 :: Nat -> nil:cons 319.69/291.49 319.69/291.49 319.69/291.49 Lemmas: 319.69/291.49 last(gen_nil:cons3_0(+(1, n5_0))) -> gen_nil:cons3_0(0), rt in Omega(1 + n5_0) 319.69/291.49 dropLast(gen_nil:cons3_0(+(1, n198_0))) -> gen_nil:cons3_0(n198_0), rt in Omega(1 + n198_0) 319.69/291.49 append(gen_nil:cons3_0(n545_0), gen_nil:cons3_0(b)) -> gen_nil:cons3_0(+(n545_0, b)), rt in Omega(1 + n545_0) 319.69/291.49 319.69/291.49 319.69/291.49 Generator Equations: 319.69/291.49 gen_nil:cons3_0(0) <=> nil 319.69/291.49 gen_nil:cons3_0(+(x, 1)) <=> cons(nil, gen_nil:cons3_0(x)) 319.69/291.49 319.69/291.49 319.69/291.49 The following defined symbols remain to be analysed: 319.69/291.49 rev 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (17) RewriteLemmaProof (LOWER BOUND(ID)) 319.69/291.49 Proved the following rewrite lemma: 319.69/291.49 rev(gen_nil:cons3_0(n1160_0), gen_nil:cons3_0(0)) -> gen_nil:cons3_0(0), rt in Omega(1 + n1160_0 + n1160_0^2) 319.69/291.49 319.69/291.49 Induction Base: 319.69/291.49 rev(gen_nil:cons3_0(0), gen_nil:cons3_0(0)) ->_R^Omega(1) 319.69/291.49 if(isEmpty(gen_nil:cons3_0(0)), dropLast(gen_nil:cons3_0(0)), append(gen_nil:cons3_0(0), last(gen_nil:cons3_0(0))), gen_nil:cons3_0(0)) ->_R^Omega(1) 319.69/291.49 if(true, dropLast(gen_nil:cons3_0(0)), append(gen_nil:cons3_0(0), last(gen_nil:cons3_0(0))), gen_nil:cons3_0(0)) ->_R^Omega(1) 319.69/291.49 if(true, nil, append(gen_nil:cons3_0(0), last(gen_nil:cons3_0(0))), gen_nil:cons3_0(0)) ->_R^Omega(1) 319.69/291.49 if(true, nil, last(gen_nil:cons3_0(0)), gen_nil:cons3_0(0)) ->_R^Omega(1) 319.69/291.49 gen_nil:cons3_0(0) 319.69/291.49 319.69/291.49 Induction Step: 319.69/291.49 rev(gen_nil:cons3_0(+(n1160_0, 1)), gen_nil:cons3_0(0)) ->_R^Omega(1) 319.69/291.49 if(isEmpty(gen_nil:cons3_0(+(n1160_0, 1))), dropLast(gen_nil:cons3_0(+(n1160_0, 1))), append(gen_nil:cons3_0(0), last(gen_nil:cons3_0(+(n1160_0, 1)))), gen_nil:cons3_0(0)) ->_R^Omega(1) 319.69/291.49 if(false, dropLast(gen_nil:cons3_0(+(1, n1160_0))), append(gen_nil:cons3_0(0), last(gen_nil:cons3_0(+(1, n1160_0)))), gen_nil:cons3_0(0)) ->_L^Omega(1 + n1160_0) 319.69/291.49 if(false, gen_nil:cons3_0(n1160_0), append(gen_nil:cons3_0(0), last(gen_nil:cons3_0(+(1, n1160_0)))), gen_nil:cons3_0(0)) ->_L^Omega(1 + n1160_0) 319.69/291.49 if(false, gen_nil:cons3_0(n1160_0), append(gen_nil:cons3_0(0), gen_nil:cons3_0(0)), gen_nil:cons3_0(0)) ->_L^Omega(1) 319.69/291.49 if(false, gen_nil:cons3_0(n1160_0), gen_nil:cons3_0(+(0, 0)), gen_nil:cons3_0(0)) ->_R^Omega(1) 319.69/291.49 rev(gen_nil:cons3_0(n1160_0), gen_nil:cons3_0(0)) ->_IH 319.69/291.49 gen_nil:cons3_0(0) 319.69/291.49 319.69/291.49 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (18) 319.69/291.49 Obligation: 319.69/291.49 Proved the lower bound n^2 for the following obligation: 319.69/291.49 319.69/291.49 TRS: 319.69/291.49 Rules: 319.69/291.49 isEmpty(nil) -> true 319.69/291.49 isEmpty(cons(x, xs)) -> false 319.69/291.49 last(cons(x, nil)) -> x 319.69/291.49 last(cons(x, cons(y, ys))) -> last(cons(y, ys)) 319.69/291.49 dropLast(nil) -> nil 319.69/291.49 dropLast(cons(x, nil)) -> nil 319.69/291.49 dropLast(cons(x, cons(y, ys))) -> cons(x, dropLast(cons(y, ys))) 319.69/291.49 append(nil, ys) -> ys 319.69/291.49 append(cons(x, xs), ys) -> cons(x, append(xs, ys)) 319.69/291.49 reverse(xs) -> rev(xs, nil) 319.69/291.49 rev(xs, ys) -> if(isEmpty(xs), dropLast(xs), append(ys, last(xs)), ys) 319.69/291.49 if(true, xs, ys, zs) -> zs 319.69/291.49 if(false, xs, ys, zs) -> rev(xs, ys) 319.69/291.49 319.69/291.49 Types: 319.69/291.49 isEmpty :: nil:cons -> true:false 319.69/291.49 nil :: nil:cons 319.69/291.49 true :: true:false 319.69/291.49 cons :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 false :: true:false 319.69/291.49 last :: nil:cons -> nil:cons 319.69/291.49 dropLast :: nil:cons -> nil:cons 319.69/291.49 append :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 reverse :: nil:cons -> nil:cons 319.69/291.49 rev :: nil:cons -> nil:cons -> nil:cons 319.69/291.49 if :: true:false -> nil:cons -> nil:cons -> nil:cons -> nil:cons 319.69/291.49 hole_true:false1_0 :: true:false 319.69/291.49 hole_nil:cons2_0 :: nil:cons 319.69/291.49 gen_nil:cons3_0 :: Nat -> nil:cons 319.69/291.49 319.69/291.49 319.69/291.49 Lemmas: 319.69/291.49 last(gen_nil:cons3_0(+(1, n5_0))) -> gen_nil:cons3_0(0), rt in Omega(1 + n5_0) 319.69/291.49 dropLast(gen_nil:cons3_0(+(1, n198_0))) -> gen_nil:cons3_0(n198_0), rt in Omega(1 + n198_0) 319.69/291.49 append(gen_nil:cons3_0(n545_0), gen_nil:cons3_0(b)) -> gen_nil:cons3_0(+(n545_0, b)), rt in Omega(1 + n545_0) 319.69/291.49 319.69/291.49 319.69/291.49 Generator Equations: 319.69/291.49 gen_nil:cons3_0(0) <=> nil 319.69/291.49 gen_nil:cons3_0(+(x, 1)) <=> cons(nil, gen_nil:cons3_0(x)) 319.69/291.49 319.69/291.49 319.69/291.49 The following defined symbols remain to be analysed: 319.69/291.49 rev 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (19) LowerBoundPropagationProof (FINISHED) 319.69/291.49 Propagated lower bound. 319.69/291.49 ---------------------------------------- 319.69/291.49 319.69/291.49 (20) 319.69/291.49 BOUNDS(n^2, INF) 319.71/291.51 EOF