1108.10/291.47 WORST_CASE(Omega(n^2), ?) 1111.46/292.29 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 1111.46/292.29 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1111.46/292.29 1111.46/292.29 1111.46/292.29 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1111.46/292.29 1111.46/292.29 (0) CpxTRS 1111.46/292.29 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1111.46/292.29 (2) CpxTRS 1111.46/292.29 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1111.46/292.29 (4) typed CpxTrs 1111.46/292.29 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1111.46/292.29 (6) typed CpxTrs 1111.46/292.29 (7) RewriteLemmaProof [LOWER BOUND(ID), 253 ms] 1111.46/292.29 (8) BEST 1111.46/292.29 (9) proven lower bound 1111.46/292.29 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1111.46/292.29 (11) BOUNDS(n^1, INF) 1111.46/292.29 (12) typed CpxTrs 1111.46/292.29 (13) RewriteLemmaProof [LOWER BOUND(ID), 93 ms] 1111.46/292.29 (14) typed CpxTrs 1111.46/292.29 (15) RewriteLemmaProof [LOWER BOUND(ID), 83 ms] 1111.46/292.29 (16) proven lower bound 1111.46/292.29 (17) LowerBoundPropagationProof [FINISHED, 0 ms] 1111.46/292.29 (18) BOUNDS(n^2, INF) 1111.46/292.29 1111.46/292.29 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (0) 1111.46/292.29 Obligation: 1111.46/292.29 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1111.46/292.29 1111.46/292.29 1111.46/292.29 The TRS R consists of the following rules: 1111.46/292.29 1111.46/292.29 last(nil) -> 0 1111.46/292.29 last(cons(x, nil)) -> x 1111.46/292.29 last(cons(x, cons(y, xs))) -> last(cons(y, xs)) 1111.46/292.29 del(x, nil) -> nil 1111.46/292.29 del(x, cons(y, xs)) -> if(eq(x, y), x, y, xs) 1111.46/292.29 if(true, x, y, xs) -> xs 1111.46/292.29 if(false, x, y, xs) -> cons(y, del(x, xs)) 1111.46/292.29 eq(0, 0) -> true 1111.46/292.29 eq(0, s(y)) -> false 1111.46/292.29 eq(s(x), 0) -> false 1111.46/292.29 eq(s(x), s(y)) -> eq(x, y) 1111.46/292.29 reverse(nil) -> nil 1111.46/292.29 reverse(cons(x, xs)) -> cons(last(cons(x, xs)), reverse(del(last(cons(x, xs)), cons(x, xs)))) 1111.46/292.29 1111.46/292.29 S is empty. 1111.46/292.29 Rewrite Strategy: INNERMOST 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1111.46/292.29 Renamed function symbols to avoid clashes with predefined symbol. 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (2) 1111.46/292.29 Obligation: 1111.46/292.29 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1111.46/292.29 1111.46/292.29 1111.46/292.29 The TRS R consists of the following rules: 1111.46/292.29 1111.46/292.29 last(nil) -> 0' 1111.46/292.29 last(cons(x, nil)) -> x 1111.46/292.29 last(cons(x, cons(y, xs))) -> last(cons(y, xs)) 1111.46/292.29 del(x, nil) -> nil 1111.46/292.29 del(x, cons(y, xs)) -> if(eq(x, y), x, y, xs) 1111.46/292.29 if(true, x, y, xs) -> xs 1111.46/292.29 if(false, x, y, xs) -> cons(y, del(x, xs)) 1111.46/292.29 eq(0', 0') -> true 1111.46/292.29 eq(0', s(y)) -> false 1111.46/292.29 eq(s(x), 0') -> false 1111.46/292.29 eq(s(x), s(y)) -> eq(x, y) 1111.46/292.29 reverse(nil) -> nil 1111.46/292.29 reverse(cons(x, xs)) -> cons(last(cons(x, xs)), reverse(del(last(cons(x, xs)), cons(x, xs)))) 1111.46/292.29 1111.46/292.29 S is empty. 1111.46/292.29 Rewrite Strategy: INNERMOST 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1111.46/292.29 Infered types. 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (4) 1111.46/292.29 Obligation: 1111.46/292.29 Innermost TRS: 1111.46/292.29 Rules: 1111.46/292.29 last(nil) -> 0' 1111.46/292.29 last(cons(x, nil)) -> x 1111.46/292.29 last(cons(x, cons(y, xs))) -> last(cons(y, xs)) 1111.46/292.29 del(x, nil) -> nil 1111.46/292.29 del(x, cons(y, xs)) -> if(eq(x, y), x, y, xs) 1111.46/292.29 if(true, x, y, xs) -> xs 1111.46/292.29 if(false, x, y, xs) -> cons(y, del(x, xs)) 1111.46/292.29 eq(0', 0') -> true 1111.46/292.29 eq(0', s(y)) -> false 1111.46/292.29 eq(s(x), 0') -> false 1111.46/292.29 eq(s(x), s(y)) -> eq(x, y) 1111.46/292.29 reverse(nil) -> nil 1111.46/292.29 reverse(cons(x, xs)) -> cons(last(cons(x, xs)), reverse(del(last(cons(x, xs)), cons(x, xs)))) 1111.46/292.29 1111.46/292.29 Types: 1111.46/292.29 last :: nil:cons -> 0':s 1111.46/292.29 nil :: nil:cons 1111.46/292.29 0' :: 0':s 1111.46/292.29 cons :: 0':s -> nil:cons -> nil:cons 1111.46/292.29 del :: 0':s -> nil:cons -> nil:cons 1111.46/292.29 if :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 1111.46/292.29 eq :: 0':s -> 0':s -> true:false 1111.46/292.29 true :: true:false 1111.46/292.29 false :: true:false 1111.46/292.29 s :: 0':s -> 0':s 1111.46/292.29 reverse :: nil:cons -> nil:cons 1111.46/292.29 hole_0':s1_0 :: 0':s 1111.46/292.29 hole_nil:cons2_0 :: nil:cons 1111.46/292.29 hole_true:false3_0 :: true:false 1111.46/292.29 gen_0':s4_0 :: Nat -> 0':s 1111.46/292.29 gen_nil:cons5_0 :: Nat -> nil:cons 1111.46/292.29 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (5) OrderProof (LOWER BOUND(ID)) 1111.46/292.29 Heuristically decided to analyse the following defined symbols: 1111.46/292.29 last, del, eq, reverse 1111.46/292.29 1111.46/292.29 They will be analysed ascendingly in the following order: 1111.46/292.29 last < reverse 1111.46/292.29 eq < del 1111.46/292.29 del < reverse 1111.46/292.29 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (6) 1111.46/292.29 Obligation: 1111.46/292.29 Innermost TRS: 1111.46/292.29 Rules: 1111.46/292.29 last(nil) -> 0' 1111.46/292.29 last(cons(x, nil)) -> x 1111.46/292.29 last(cons(x, cons(y, xs))) -> last(cons(y, xs)) 1111.46/292.29 del(x, nil) -> nil 1111.46/292.29 del(x, cons(y, xs)) -> if(eq(x, y), x, y, xs) 1111.46/292.29 if(true, x, y, xs) -> xs 1111.46/292.29 if(false, x, y, xs) -> cons(y, del(x, xs)) 1111.46/292.29 eq(0', 0') -> true 1111.46/292.29 eq(0', s(y)) -> false 1111.46/292.29 eq(s(x), 0') -> false 1111.46/292.29 eq(s(x), s(y)) -> eq(x, y) 1111.46/292.29 reverse(nil) -> nil 1111.46/292.29 reverse(cons(x, xs)) -> cons(last(cons(x, xs)), reverse(del(last(cons(x, xs)), cons(x, xs)))) 1111.46/292.29 1111.46/292.29 Types: 1111.46/292.29 last :: nil:cons -> 0':s 1111.46/292.29 nil :: nil:cons 1111.46/292.29 0' :: 0':s 1111.46/292.29 cons :: 0':s -> nil:cons -> nil:cons 1111.46/292.29 del :: 0':s -> nil:cons -> nil:cons 1111.46/292.29 if :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 1111.46/292.29 eq :: 0':s -> 0':s -> true:false 1111.46/292.29 true :: true:false 1111.46/292.29 false :: true:false 1111.46/292.29 s :: 0':s -> 0':s 1111.46/292.29 reverse :: nil:cons -> nil:cons 1111.46/292.29 hole_0':s1_0 :: 0':s 1111.46/292.29 hole_nil:cons2_0 :: nil:cons 1111.46/292.29 hole_true:false3_0 :: true:false 1111.46/292.29 gen_0':s4_0 :: Nat -> 0':s 1111.46/292.29 gen_nil:cons5_0 :: Nat -> nil:cons 1111.46/292.29 1111.46/292.29 1111.46/292.29 Generator Equations: 1111.46/292.29 gen_0':s4_0(0) <=> 0' 1111.46/292.29 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1111.46/292.29 gen_nil:cons5_0(0) <=> nil 1111.46/292.29 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 1111.46/292.29 1111.46/292.29 1111.46/292.29 The following defined symbols remain to be analysed: 1111.46/292.29 last, del, eq, reverse 1111.46/292.29 1111.46/292.29 They will be analysed ascendingly in the following order: 1111.46/292.29 last < reverse 1111.46/292.29 eq < del 1111.46/292.29 del < reverse 1111.46/292.29 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1111.46/292.29 Proved the following rewrite lemma: 1111.46/292.29 last(gen_nil:cons5_0(+(1, n7_0))) -> gen_0':s4_0(0), rt in Omega(1 + n7_0) 1111.46/292.29 1111.46/292.29 Induction Base: 1111.46/292.29 last(gen_nil:cons5_0(+(1, 0))) ->_R^Omega(1) 1111.46/292.29 0' 1111.46/292.29 1111.46/292.29 Induction Step: 1111.46/292.29 last(gen_nil:cons5_0(+(1, +(n7_0, 1)))) ->_R^Omega(1) 1111.46/292.29 last(cons(0', gen_nil:cons5_0(n7_0))) ->_IH 1111.46/292.29 gen_0':s4_0(0) 1111.46/292.29 1111.46/292.29 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (8) 1111.46/292.29 Complex Obligation (BEST) 1111.46/292.29 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (9) 1111.46/292.29 Obligation: 1111.46/292.29 Proved the lower bound n^1 for the following obligation: 1111.46/292.29 1111.46/292.29 Innermost TRS: 1111.46/292.29 Rules: 1111.46/292.29 last(nil) -> 0' 1111.46/292.29 last(cons(x, nil)) -> x 1111.46/292.29 last(cons(x, cons(y, xs))) -> last(cons(y, xs)) 1111.46/292.29 del(x, nil) -> nil 1111.46/292.29 del(x, cons(y, xs)) -> if(eq(x, y), x, y, xs) 1111.46/292.29 if(true, x, y, xs) -> xs 1111.46/292.29 if(false, x, y, xs) -> cons(y, del(x, xs)) 1111.46/292.29 eq(0', 0') -> true 1111.46/292.29 eq(0', s(y)) -> false 1111.46/292.29 eq(s(x), 0') -> false 1111.46/292.29 eq(s(x), s(y)) -> eq(x, y) 1111.46/292.29 reverse(nil) -> nil 1111.46/292.29 reverse(cons(x, xs)) -> cons(last(cons(x, xs)), reverse(del(last(cons(x, xs)), cons(x, xs)))) 1111.46/292.29 1111.46/292.29 Types: 1111.46/292.29 last :: nil:cons -> 0':s 1111.46/292.29 nil :: nil:cons 1111.46/292.29 0' :: 0':s 1111.46/292.29 cons :: 0':s -> nil:cons -> nil:cons 1111.46/292.29 del :: 0':s -> nil:cons -> nil:cons 1111.46/292.29 if :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 1111.46/292.29 eq :: 0':s -> 0':s -> true:false 1111.46/292.29 true :: true:false 1111.46/292.29 false :: true:false 1111.46/292.29 s :: 0':s -> 0':s 1111.46/292.29 reverse :: nil:cons -> nil:cons 1111.46/292.29 hole_0':s1_0 :: 0':s 1111.46/292.29 hole_nil:cons2_0 :: nil:cons 1111.46/292.29 hole_true:false3_0 :: true:false 1111.46/292.29 gen_0':s4_0 :: Nat -> 0':s 1111.46/292.29 gen_nil:cons5_0 :: Nat -> nil:cons 1111.46/292.29 1111.46/292.29 1111.46/292.29 Generator Equations: 1111.46/292.29 gen_0':s4_0(0) <=> 0' 1111.46/292.29 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1111.46/292.29 gen_nil:cons5_0(0) <=> nil 1111.46/292.29 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 1111.46/292.29 1111.46/292.29 1111.46/292.29 The following defined symbols remain to be analysed: 1111.46/292.29 last, del, eq, reverse 1111.46/292.29 1111.46/292.29 They will be analysed ascendingly in the following order: 1111.46/292.29 last < reverse 1111.46/292.29 eq < del 1111.46/292.29 del < reverse 1111.46/292.29 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (10) LowerBoundPropagationProof (FINISHED) 1111.46/292.29 Propagated lower bound. 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (11) 1111.46/292.29 BOUNDS(n^1, INF) 1111.46/292.29 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (12) 1111.46/292.29 Obligation: 1111.46/292.29 Innermost TRS: 1111.46/292.29 Rules: 1111.46/292.29 last(nil) -> 0' 1111.46/292.29 last(cons(x, nil)) -> x 1111.46/292.29 last(cons(x, cons(y, xs))) -> last(cons(y, xs)) 1111.46/292.29 del(x, nil) -> nil 1111.46/292.29 del(x, cons(y, xs)) -> if(eq(x, y), x, y, xs) 1111.46/292.29 if(true, x, y, xs) -> xs 1111.46/292.29 if(false, x, y, xs) -> cons(y, del(x, xs)) 1111.46/292.29 eq(0', 0') -> true 1111.46/292.29 eq(0', s(y)) -> false 1111.46/292.29 eq(s(x), 0') -> false 1111.46/292.29 eq(s(x), s(y)) -> eq(x, y) 1111.46/292.29 reverse(nil) -> nil 1111.46/292.29 reverse(cons(x, xs)) -> cons(last(cons(x, xs)), reverse(del(last(cons(x, xs)), cons(x, xs)))) 1111.46/292.29 1111.46/292.29 Types: 1111.46/292.29 last :: nil:cons -> 0':s 1111.46/292.29 nil :: nil:cons 1111.46/292.29 0' :: 0':s 1111.46/292.29 cons :: 0':s -> nil:cons -> nil:cons 1111.46/292.29 del :: 0':s -> nil:cons -> nil:cons 1111.46/292.29 if :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 1111.46/292.29 eq :: 0':s -> 0':s -> true:false 1111.46/292.29 true :: true:false 1111.46/292.29 false :: true:false 1111.46/292.29 s :: 0':s -> 0':s 1111.46/292.29 reverse :: nil:cons -> nil:cons 1111.46/292.29 hole_0':s1_0 :: 0':s 1111.46/292.29 hole_nil:cons2_0 :: nil:cons 1111.46/292.29 hole_true:false3_0 :: true:false 1111.46/292.29 gen_0':s4_0 :: Nat -> 0':s 1111.46/292.29 gen_nil:cons5_0 :: Nat -> nil:cons 1111.46/292.29 1111.46/292.29 1111.46/292.29 Lemmas: 1111.46/292.29 last(gen_nil:cons5_0(+(1, n7_0))) -> gen_0':s4_0(0), rt in Omega(1 + n7_0) 1111.46/292.29 1111.46/292.29 1111.46/292.29 Generator Equations: 1111.46/292.29 gen_0':s4_0(0) <=> 0' 1111.46/292.29 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1111.46/292.29 gen_nil:cons5_0(0) <=> nil 1111.46/292.29 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 1111.46/292.29 1111.46/292.29 1111.46/292.29 The following defined symbols remain to be analysed: 1111.46/292.29 eq, del, reverse 1111.46/292.29 1111.46/292.29 They will be analysed ascendingly in the following order: 1111.46/292.29 eq < del 1111.46/292.29 del < reverse 1111.46/292.29 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (13) RewriteLemmaProof (LOWER BOUND(ID)) 1111.46/292.29 Proved the following rewrite lemma: 1111.46/292.29 eq(gen_0':s4_0(n356_0), gen_0':s4_0(n356_0)) -> true, rt in Omega(1 + n356_0) 1111.46/292.29 1111.46/292.29 Induction Base: 1111.46/292.29 eq(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 1111.46/292.29 true 1111.46/292.29 1111.46/292.29 Induction Step: 1111.46/292.29 eq(gen_0':s4_0(+(n356_0, 1)), gen_0':s4_0(+(n356_0, 1))) ->_R^Omega(1) 1111.46/292.29 eq(gen_0':s4_0(n356_0), gen_0':s4_0(n356_0)) ->_IH 1111.46/292.29 true 1111.46/292.29 1111.46/292.29 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (14) 1111.46/292.29 Obligation: 1111.46/292.29 Innermost TRS: 1111.46/292.29 Rules: 1111.46/292.29 last(nil) -> 0' 1111.46/292.29 last(cons(x, nil)) -> x 1111.46/292.29 last(cons(x, cons(y, xs))) -> last(cons(y, xs)) 1111.46/292.29 del(x, nil) -> nil 1111.46/292.29 del(x, cons(y, xs)) -> if(eq(x, y), x, y, xs) 1111.46/292.29 if(true, x, y, xs) -> xs 1111.46/292.29 if(false, x, y, xs) -> cons(y, del(x, xs)) 1111.46/292.29 eq(0', 0') -> true 1111.46/292.29 eq(0', s(y)) -> false 1111.46/292.29 eq(s(x), 0') -> false 1111.46/292.29 eq(s(x), s(y)) -> eq(x, y) 1111.46/292.29 reverse(nil) -> nil 1111.46/292.29 reverse(cons(x, xs)) -> cons(last(cons(x, xs)), reverse(del(last(cons(x, xs)), cons(x, xs)))) 1111.46/292.29 1111.46/292.29 Types: 1111.46/292.29 last :: nil:cons -> 0':s 1111.46/292.29 nil :: nil:cons 1111.46/292.29 0' :: 0':s 1111.46/292.29 cons :: 0':s -> nil:cons -> nil:cons 1111.46/292.29 del :: 0':s -> nil:cons -> nil:cons 1111.46/292.29 if :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 1111.46/292.29 eq :: 0':s -> 0':s -> true:false 1111.46/292.29 true :: true:false 1111.46/292.29 false :: true:false 1111.46/292.29 s :: 0':s -> 0':s 1111.46/292.29 reverse :: nil:cons -> nil:cons 1111.46/292.29 hole_0':s1_0 :: 0':s 1111.46/292.29 hole_nil:cons2_0 :: nil:cons 1111.46/292.29 hole_true:false3_0 :: true:false 1111.46/292.29 gen_0':s4_0 :: Nat -> 0':s 1111.46/292.29 gen_nil:cons5_0 :: Nat -> nil:cons 1111.46/292.29 1111.46/292.29 1111.46/292.29 Lemmas: 1111.46/292.29 last(gen_nil:cons5_0(+(1, n7_0))) -> gen_0':s4_0(0), rt in Omega(1 + n7_0) 1111.46/292.29 eq(gen_0':s4_0(n356_0), gen_0':s4_0(n356_0)) -> true, rt in Omega(1 + n356_0) 1111.46/292.29 1111.46/292.29 1111.46/292.29 Generator Equations: 1111.46/292.29 gen_0':s4_0(0) <=> 0' 1111.46/292.29 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1111.46/292.29 gen_nil:cons5_0(0) <=> nil 1111.46/292.29 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 1111.46/292.29 1111.46/292.29 1111.46/292.29 The following defined symbols remain to be analysed: 1111.46/292.29 del, reverse 1111.46/292.29 1111.46/292.29 They will be analysed ascendingly in the following order: 1111.46/292.29 del < reverse 1111.46/292.29 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (15) RewriteLemmaProof (LOWER BOUND(ID)) 1111.46/292.29 Proved the following rewrite lemma: 1111.46/292.29 reverse(gen_nil:cons5_0(n1023_0)) -> gen_nil:cons5_0(n1023_0), rt in Omega(1 + n1023_0 + n1023_0^2) 1111.46/292.29 1111.46/292.29 Induction Base: 1111.46/292.29 reverse(gen_nil:cons5_0(0)) ->_R^Omega(1) 1111.46/292.29 nil 1111.46/292.29 1111.46/292.29 Induction Step: 1111.46/292.29 reverse(gen_nil:cons5_0(+(n1023_0, 1))) ->_R^Omega(1) 1111.46/292.29 cons(last(cons(0', gen_nil:cons5_0(n1023_0))), reverse(del(last(cons(0', gen_nil:cons5_0(n1023_0))), cons(0', gen_nil:cons5_0(n1023_0))))) ->_L^Omega(1 + n1023_0) 1111.46/292.29 cons(gen_0':s4_0(0), reverse(del(last(cons(0', gen_nil:cons5_0(n1023_0))), cons(0', gen_nil:cons5_0(n1023_0))))) ->_L^Omega(1 + n1023_0) 1111.46/292.29 cons(gen_0':s4_0(0), reverse(del(gen_0':s4_0(0), cons(0', gen_nil:cons5_0(n1023_0))))) ->_R^Omega(1) 1111.46/292.29 cons(gen_0':s4_0(0), reverse(if(eq(gen_0':s4_0(0), 0'), gen_0':s4_0(0), 0', gen_nil:cons5_0(n1023_0)))) ->_L^Omega(1) 1111.46/292.29 cons(gen_0':s4_0(0), reverse(if(true, gen_0':s4_0(0), 0', gen_nil:cons5_0(n1023_0)))) ->_R^Omega(1) 1111.46/292.29 cons(gen_0':s4_0(0), reverse(gen_nil:cons5_0(n1023_0))) ->_IH 1111.46/292.29 cons(gen_0':s4_0(0), gen_nil:cons5_0(c1024_0)) 1111.46/292.29 1111.46/292.29 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (16) 1111.46/292.29 Obligation: 1111.46/292.29 Proved the lower bound n^2 for the following obligation: 1111.46/292.29 1111.46/292.29 Innermost TRS: 1111.46/292.29 Rules: 1111.46/292.29 last(nil) -> 0' 1111.46/292.29 last(cons(x, nil)) -> x 1111.46/292.29 last(cons(x, cons(y, xs))) -> last(cons(y, xs)) 1111.46/292.29 del(x, nil) -> nil 1111.46/292.29 del(x, cons(y, xs)) -> if(eq(x, y), x, y, xs) 1111.46/292.29 if(true, x, y, xs) -> xs 1111.46/292.29 if(false, x, y, xs) -> cons(y, del(x, xs)) 1111.46/292.29 eq(0', 0') -> true 1111.46/292.29 eq(0', s(y)) -> false 1111.46/292.29 eq(s(x), 0') -> false 1111.46/292.29 eq(s(x), s(y)) -> eq(x, y) 1111.46/292.29 reverse(nil) -> nil 1111.46/292.29 reverse(cons(x, xs)) -> cons(last(cons(x, xs)), reverse(del(last(cons(x, xs)), cons(x, xs)))) 1111.46/292.29 1111.46/292.29 Types: 1111.46/292.29 last :: nil:cons -> 0':s 1111.46/292.29 nil :: nil:cons 1111.46/292.29 0' :: 0':s 1111.46/292.29 cons :: 0':s -> nil:cons -> nil:cons 1111.46/292.29 del :: 0':s -> nil:cons -> nil:cons 1111.46/292.29 if :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons 1111.46/292.29 eq :: 0':s -> 0':s -> true:false 1111.46/292.29 true :: true:false 1111.46/292.29 false :: true:false 1111.46/292.29 s :: 0':s -> 0':s 1111.46/292.29 reverse :: nil:cons -> nil:cons 1111.46/292.29 hole_0':s1_0 :: 0':s 1111.46/292.29 hole_nil:cons2_0 :: nil:cons 1111.46/292.29 hole_true:false3_0 :: true:false 1111.46/292.29 gen_0':s4_0 :: Nat -> 0':s 1111.46/292.29 gen_nil:cons5_0 :: Nat -> nil:cons 1111.46/292.29 1111.46/292.29 1111.46/292.29 Lemmas: 1111.46/292.29 last(gen_nil:cons5_0(+(1, n7_0))) -> gen_0':s4_0(0), rt in Omega(1 + n7_0) 1111.46/292.29 eq(gen_0':s4_0(n356_0), gen_0':s4_0(n356_0)) -> true, rt in Omega(1 + n356_0) 1111.46/292.29 1111.46/292.29 1111.46/292.29 Generator Equations: 1111.46/292.29 gen_0':s4_0(0) <=> 0' 1111.46/292.29 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1111.46/292.29 gen_nil:cons5_0(0) <=> nil 1111.46/292.29 gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x)) 1111.46/292.29 1111.46/292.29 1111.46/292.29 The following defined symbols remain to be analysed: 1111.46/292.29 reverse 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (17) LowerBoundPropagationProof (FINISHED) 1111.46/292.29 Propagated lower bound. 1111.46/292.29 ---------------------------------------- 1111.46/292.29 1111.46/292.29 (18) 1111.46/292.29 BOUNDS(n^2, INF) 1111.58/292.36 EOF