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