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