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