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