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