1105.39/291.54 WORST_CASE(Omega(n^2), ?) 1105.99/291.67 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1105.99/291.67 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1105.99/291.67 1105.99/291.67 1105.99/291.67 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1105.99/291.67 1105.99/291.67 (0) CpxTRS 1105.99/291.67 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1105.99/291.67 (2) CpxTRS 1105.99/291.67 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1105.99/291.67 (4) typed CpxTrs 1105.99/291.67 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1105.99/291.67 (6) typed CpxTrs 1105.99/291.67 (7) RewriteLemmaProof [LOWER BOUND(ID), 297 ms] 1105.99/291.67 (8) BEST 1105.99/291.67 (9) proven lower bound 1105.99/291.67 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1105.99/291.67 (11) BOUNDS(n^1, INF) 1105.99/291.67 (12) typed CpxTrs 1105.99/291.67 (13) RewriteLemmaProof [LOWER BOUND(ID), 74 ms] 1105.99/291.67 (14) typed CpxTrs 1105.99/291.67 (15) RewriteLemmaProof [LOWER BOUND(ID), 40 ms] 1105.99/291.67 (16) typed CpxTrs 1105.99/291.67 (17) RewriteLemmaProof [LOWER BOUND(ID), 19 ms] 1105.99/291.67 (18) proven lower bound 1105.99/291.67 (19) LowerBoundPropagationProof [FINISHED, 0 ms] 1105.99/291.67 (20) BOUNDS(n^2, INF) 1105.99/291.67 1105.99/291.67 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (0) 1105.99/291.67 Obligation: 1105.99/291.67 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1105.99/291.67 1105.99/291.67 1105.99/291.67 The TRS R consists of the following rules: 1105.99/291.67 1105.99/291.67 le(0, y) -> true 1105.99/291.67 le(s(x), 0) -> false 1105.99/291.67 le(s(x), s(y)) -> le(x, y) 1105.99/291.67 eq(0, 0) -> true 1105.99/291.67 eq(0, s(y)) -> false 1105.99/291.67 eq(s(x), 0) -> false 1105.99/291.67 eq(s(x), s(y)) -> eq(x, y) 1105.99/291.67 if1(true, x, y, xs) -> min(x, xs) 1105.99/291.67 if1(false, x, y, xs) -> min(y, xs) 1105.99/291.67 if2(true, x, y, xs) -> xs 1105.99/291.67 if2(false, x, y, xs) -> cons(y, del(x, xs)) 1105.99/291.67 minsort(nil) -> nil 1105.99/291.67 minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) 1105.99/291.67 min(x, nil) -> x 1105.99/291.67 min(x, cons(y, z)) -> if1(le(x, y), x, y, z) 1105.99/291.67 del(x, nil) -> nil 1105.99/291.67 del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) 1105.99/291.67 1105.99/291.67 S is empty. 1105.99/291.67 Rewrite Strategy: INNERMOST 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1105.99/291.67 Renamed function symbols to avoid clashes with predefined symbol. 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (2) 1105.99/291.67 Obligation: 1105.99/291.67 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1105.99/291.67 1105.99/291.67 1105.99/291.67 The TRS R consists of the following rules: 1105.99/291.67 1105.99/291.67 le(0', y) -> true 1105.99/291.67 le(s(x), 0') -> false 1105.99/291.67 le(s(x), s(y)) -> le(x, y) 1105.99/291.67 eq(0', 0') -> true 1105.99/291.67 eq(0', s(y)) -> false 1105.99/291.67 eq(s(x), 0') -> false 1105.99/291.67 eq(s(x), s(y)) -> eq(x, y) 1105.99/291.67 if1(true, x, y, xs) -> min(x, xs) 1105.99/291.67 if1(false, x, y, xs) -> min(y, xs) 1105.99/291.67 if2(true, x, y, xs) -> xs 1105.99/291.67 if2(false, x, y, xs) -> cons(y, del(x, xs)) 1105.99/291.67 minsort(nil) -> nil 1105.99/291.67 minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) 1105.99/291.67 min(x, nil) -> x 1105.99/291.67 min(x, cons(y, z)) -> if1(le(x, y), x, y, z) 1105.99/291.67 del(x, nil) -> nil 1105.99/291.67 del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) 1105.99/291.67 1105.99/291.67 S is empty. 1105.99/291.67 Rewrite Strategy: INNERMOST 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1105.99/291.67 Infered types. 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (4) 1105.99/291.67 Obligation: 1105.99/291.67 Innermost TRS: 1105.99/291.67 Rules: 1105.99/291.67 le(0', y) -> true 1105.99/291.67 le(s(x), 0') -> false 1105.99/291.67 le(s(x), s(y)) -> le(x, y) 1105.99/291.67 eq(0', 0') -> true 1105.99/291.67 eq(0', s(y)) -> false 1105.99/291.67 eq(s(x), 0') -> false 1105.99/291.67 eq(s(x), s(y)) -> eq(x, y) 1105.99/291.67 if1(true, x, y, xs) -> min(x, xs) 1105.99/291.67 if1(false, x, y, xs) -> min(y, xs) 1105.99/291.67 if2(true, x, y, xs) -> xs 1105.99/291.67 if2(false, x, y, xs) -> cons(y, del(x, xs)) 1105.99/291.67 minsort(nil) -> nil 1105.99/291.67 minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) 1105.99/291.67 min(x, nil) -> x 1105.99/291.67 min(x, cons(y, z)) -> if1(le(x, y), x, y, z) 1105.99/291.67 del(x, nil) -> nil 1105.99/291.67 del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) 1105.99/291.67 1105.99/291.67 Types: 1105.99/291.67 le :: 0':s -> 0':s -> true:false 1105.99/291.67 0' :: 0':s 1105.99/291.67 true :: true:false 1105.99/291.67 s :: 0':s -> 0':s 1105.99/291.67 false :: true:false 1105.99/291.67 eq :: 0':s -> 0':s -> true:false 1105.99/291.67 if1 :: true:false -> 0':s -> 0':s -> cons:nil -> 0':s 1105.99/291.67 min :: 0':s -> cons:nil -> 0':s 1105.99/291.67 if2 :: true:false -> 0':s -> 0':s -> cons:nil -> cons:nil 1105.99/291.67 cons :: 0':s -> cons:nil -> cons:nil 1105.99/291.67 del :: 0':s -> cons:nil -> cons:nil 1105.99/291.67 minsort :: cons:nil -> cons:nil 1105.99/291.67 nil :: cons:nil 1105.99/291.67 hole_true:false1_0 :: true:false 1105.99/291.67 hole_0':s2_0 :: 0':s 1105.99/291.67 hole_cons:nil3_0 :: cons:nil 1105.99/291.67 gen_0':s4_0 :: Nat -> 0':s 1105.99/291.67 gen_cons:nil5_0 :: Nat -> cons:nil 1105.99/291.67 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (5) OrderProof (LOWER BOUND(ID)) 1105.99/291.67 Heuristically decided to analyse the following defined symbols: 1105.99/291.67 le, eq, min, del, minsort 1105.99/291.67 1105.99/291.67 They will be analysed ascendingly in the following order: 1105.99/291.67 le < min 1105.99/291.67 eq < del 1105.99/291.67 min < minsort 1105.99/291.67 del < minsort 1105.99/291.67 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (6) 1105.99/291.67 Obligation: 1105.99/291.67 Innermost TRS: 1105.99/291.67 Rules: 1105.99/291.67 le(0', y) -> true 1105.99/291.67 le(s(x), 0') -> false 1105.99/291.67 le(s(x), s(y)) -> le(x, y) 1105.99/291.67 eq(0', 0') -> true 1105.99/291.67 eq(0', s(y)) -> false 1105.99/291.67 eq(s(x), 0') -> false 1105.99/291.67 eq(s(x), s(y)) -> eq(x, y) 1105.99/291.67 if1(true, x, y, xs) -> min(x, xs) 1105.99/291.67 if1(false, x, y, xs) -> min(y, xs) 1105.99/291.67 if2(true, x, y, xs) -> xs 1105.99/291.67 if2(false, x, y, xs) -> cons(y, del(x, xs)) 1105.99/291.67 minsort(nil) -> nil 1105.99/291.67 minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) 1105.99/291.67 min(x, nil) -> x 1105.99/291.67 min(x, cons(y, z)) -> if1(le(x, y), x, y, z) 1105.99/291.67 del(x, nil) -> nil 1105.99/291.67 del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) 1105.99/291.67 1105.99/291.67 Types: 1105.99/291.67 le :: 0':s -> 0':s -> true:false 1105.99/291.67 0' :: 0':s 1105.99/291.67 true :: true:false 1105.99/291.67 s :: 0':s -> 0':s 1105.99/291.67 false :: true:false 1105.99/291.67 eq :: 0':s -> 0':s -> true:false 1105.99/291.67 if1 :: true:false -> 0':s -> 0':s -> cons:nil -> 0':s 1105.99/291.67 min :: 0':s -> cons:nil -> 0':s 1105.99/291.67 if2 :: true:false -> 0':s -> 0':s -> cons:nil -> cons:nil 1105.99/291.67 cons :: 0':s -> cons:nil -> cons:nil 1105.99/291.67 del :: 0':s -> cons:nil -> cons:nil 1105.99/291.67 minsort :: cons:nil -> cons:nil 1105.99/291.67 nil :: cons:nil 1105.99/291.67 hole_true:false1_0 :: true:false 1105.99/291.67 hole_0':s2_0 :: 0':s 1105.99/291.67 hole_cons:nil3_0 :: cons:nil 1105.99/291.67 gen_0':s4_0 :: Nat -> 0':s 1105.99/291.67 gen_cons:nil5_0 :: Nat -> cons:nil 1105.99/291.67 1105.99/291.67 1105.99/291.67 Generator Equations: 1105.99/291.67 gen_0':s4_0(0) <=> 0' 1105.99/291.67 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1105.99/291.67 gen_cons:nil5_0(0) <=> nil 1105.99/291.67 gen_cons:nil5_0(+(x, 1)) <=> cons(0', gen_cons:nil5_0(x)) 1105.99/291.67 1105.99/291.67 1105.99/291.67 The following defined symbols remain to be analysed: 1105.99/291.67 le, eq, min, del, minsort 1105.99/291.67 1105.99/291.67 They will be analysed ascendingly in the following order: 1105.99/291.67 le < min 1105.99/291.67 eq < del 1105.99/291.67 min < minsort 1105.99/291.67 del < minsort 1105.99/291.67 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1105.99/291.67 Proved the following rewrite lemma: 1105.99/291.67 le(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 1105.99/291.67 1105.99/291.67 Induction Base: 1105.99/291.67 le(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 1105.99/291.67 true 1105.99/291.67 1105.99/291.67 Induction Step: 1105.99/291.67 le(gen_0':s4_0(+(n7_0, 1)), gen_0':s4_0(+(n7_0, 1))) ->_R^Omega(1) 1105.99/291.67 le(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) ->_IH 1105.99/291.67 true 1105.99/291.67 1105.99/291.67 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (8) 1105.99/291.67 Complex Obligation (BEST) 1105.99/291.67 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (9) 1105.99/291.67 Obligation: 1105.99/291.67 Proved the lower bound n^1 for the following obligation: 1105.99/291.67 1105.99/291.67 Innermost TRS: 1105.99/291.67 Rules: 1105.99/291.67 le(0', y) -> true 1105.99/291.67 le(s(x), 0') -> false 1105.99/291.67 le(s(x), s(y)) -> le(x, y) 1105.99/291.67 eq(0', 0') -> true 1105.99/291.67 eq(0', s(y)) -> false 1105.99/291.67 eq(s(x), 0') -> false 1105.99/291.67 eq(s(x), s(y)) -> eq(x, y) 1105.99/291.67 if1(true, x, y, xs) -> min(x, xs) 1105.99/291.67 if1(false, x, y, xs) -> min(y, xs) 1105.99/291.67 if2(true, x, y, xs) -> xs 1105.99/291.67 if2(false, x, y, xs) -> cons(y, del(x, xs)) 1105.99/291.67 minsort(nil) -> nil 1105.99/291.67 minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) 1105.99/291.67 min(x, nil) -> x 1105.99/291.67 min(x, cons(y, z)) -> if1(le(x, y), x, y, z) 1105.99/291.67 del(x, nil) -> nil 1105.99/291.67 del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) 1105.99/291.67 1105.99/291.67 Types: 1105.99/291.67 le :: 0':s -> 0':s -> true:false 1105.99/291.67 0' :: 0':s 1105.99/291.67 true :: true:false 1105.99/291.67 s :: 0':s -> 0':s 1105.99/291.67 false :: true:false 1105.99/291.67 eq :: 0':s -> 0':s -> true:false 1105.99/291.67 if1 :: true:false -> 0':s -> 0':s -> cons:nil -> 0':s 1105.99/291.67 min :: 0':s -> cons:nil -> 0':s 1105.99/291.67 if2 :: true:false -> 0':s -> 0':s -> cons:nil -> cons:nil 1105.99/291.67 cons :: 0':s -> cons:nil -> cons:nil 1105.99/291.67 del :: 0':s -> cons:nil -> cons:nil 1105.99/291.67 minsort :: cons:nil -> cons:nil 1105.99/291.67 nil :: cons:nil 1105.99/291.67 hole_true:false1_0 :: true:false 1105.99/291.67 hole_0':s2_0 :: 0':s 1105.99/291.67 hole_cons:nil3_0 :: cons:nil 1105.99/291.67 gen_0':s4_0 :: Nat -> 0':s 1105.99/291.67 gen_cons:nil5_0 :: Nat -> cons:nil 1105.99/291.67 1105.99/291.67 1105.99/291.67 Generator Equations: 1105.99/291.67 gen_0':s4_0(0) <=> 0' 1105.99/291.67 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1105.99/291.67 gen_cons:nil5_0(0) <=> nil 1105.99/291.67 gen_cons:nil5_0(+(x, 1)) <=> cons(0', gen_cons:nil5_0(x)) 1105.99/291.67 1105.99/291.67 1105.99/291.67 The following defined symbols remain to be analysed: 1105.99/291.67 le, eq, min, del, minsort 1105.99/291.67 1105.99/291.67 They will be analysed ascendingly in the following order: 1105.99/291.67 le < min 1105.99/291.67 eq < del 1105.99/291.67 min < minsort 1105.99/291.67 del < minsort 1105.99/291.67 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (10) LowerBoundPropagationProof (FINISHED) 1105.99/291.67 Propagated lower bound. 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (11) 1105.99/291.67 BOUNDS(n^1, INF) 1105.99/291.67 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (12) 1105.99/291.67 Obligation: 1105.99/291.67 Innermost TRS: 1105.99/291.67 Rules: 1105.99/291.67 le(0', y) -> true 1105.99/291.67 le(s(x), 0') -> false 1105.99/291.67 le(s(x), s(y)) -> le(x, y) 1105.99/291.67 eq(0', 0') -> true 1105.99/291.67 eq(0', s(y)) -> false 1105.99/291.67 eq(s(x), 0') -> false 1105.99/291.67 eq(s(x), s(y)) -> eq(x, y) 1105.99/291.67 if1(true, x, y, xs) -> min(x, xs) 1105.99/291.67 if1(false, x, y, xs) -> min(y, xs) 1105.99/291.67 if2(true, x, y, xs) -> xs 1105.99/291.67 if2(false, x, y, xs) -> cons(y, del(x, xs)) 1105.99/291.67 minsort(nil) -> nil 1105.99/291.67 minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) 1105.99/291.67 min(x, nil) -> x 1105.99/291.67 min(x, cons(y, z)) -> if1(le(x, y), x, y, z) 1105.99/291.67 del(x, nil) -> nil 1105.99/291.67 del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) 1105.99/291.67 1105.99/291.67 Types: 1105.99/291.67 le :: 0':s -> 0':s -> true:false 1105.99/291.67 0' :: 0':s 1105.99/291.67 true :: true:false 1105.99/291.67 s :: 0':s -> 0':s 1105.99/291.67 false :: true:false 1105.99/291.67 eq :: 0':s -> 0':s -> true:false 1105.99/291.67 if1 :: true:false -> 0':s -> 0':s -> cons:nil -> 0':s 1105.99/291.67 min :: 0':s -> cons:nil -> 0':s 1105.99/291.67 if2 :: true:false -> 0':s -> 0':s -> cons:nil -> cons:nil 1105.99/291.67 cons :: 0':s -> cons:nil -> cons:nil 1105.99/291.67 del :: 0':s -> cons:nil -> cons:nil 1105.99/291.67 minsort :: cons:nil -> cons:nil 1105.99/291.67 nil :: cons:nil 1105.99/291.67 hole_true:false1_0 :: true:false 1105.99/291.67 hole_0':s2_0 :: 0':s 1105.99/291.67 hole_cons:nil3_0 :: cons:nil 1105.99/291.67 gen_0':s4_0 :: Nat -> 0':s 1105.99/291.67 gen_cons:nil5_0 :: Nat -> cons:nil 1105.99/291.67 1105.99/291.67 1105.99/291.67 Lemmas: 1105.99/291.67 le(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 1105.99/291.67 1105.99/291.67 1105.99/291.67 Generator Equations: 1105.99/291.67 gen_0':s4_0(0) <=> 0' 1105.99/291.67 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1105.99/291.67 gen_cons:nil5_0(0) <=> nil 1105.99/291.67 gen_cons:nil5_0(+(x, 1)) <=> cons(0', gen_cons:nil5_0(x)) 1105.99/291.67 1105.99/291.67 1105.99/291.67 The following defined symbols remain to be analysed: 1105.99/291.67 eq, min, del, minsort 1105.99/291.67 1105.99/291.67 They will be analysed ascendingly in the following order: 1105.99/291.67 eq < del 1105.99/291.67 min < minsort 1105.99/291.67 del < minsort 1105.99/291.67 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (13) RewriteLemmaProof (LOWER BOUND(ID)) 1105.99/291.67 Proved the following rewrite lemma: 1105.99/291.67 eq(gen_0':s4_0(n324_0), gen_0':s4_0(n324_0)) -> true, rt in Omega(1 + n324_0) 1105.99/291.67 1105.99/291.67 Induction Base: 1105.99/291.67 eq(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 1105.99/291.67 true 1105.99/291.67 1105.99/291.67 Induction Step: 1105.99/291.67 eq(gen_0':s4_0(+(n324_0, 1)), gen_0':s4_0(+(n324_0, 1))) ->_R^Omega(1) 1105.99/291.67 eq(gen_0':s4_0(n324_0), gen_0':s4_0(n324_0)) ->_IH 1105.99/291.67 true 1105.99/291.67 1105.99/291.67 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (14) 1105.99/291.67 Obligation: 1105.99/291.67 Innermost TRS: 1105.99/291.67 Rules: 1105.99/291.67 le(0', y) -> true 1105.99/291.67 le(s(x), 0') -> false 1105.99/291.67 le(s(x), s(y)) -> le(x, y) 1105.99/291.67 eq(0', 0') -> true 1105.99/291.67 eq(0', s(y)) -> false 1105.99/291.67 eq(s(x), 0') -> false 1105.99/291.67 eq(s(x), s(y)) -> eq(x, y) 1105.99/291.67 if1(true, x, y, xs) -> min(x, xs) 1105.99/291.67 if1(false, x, y, xs) -> min(y, xs) 1105.99/291.67 if2(true, x, y, xs) -> xs 1105.99/291.67 if2(false, x, y, xs) -> cons(y, del(x, xs)) 1105.99/291.67 minsort(nil) -> nil 1105.99/291.67 minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) 1105.99/291.67 min(x, nil) -> x 1105.99/291.67 min(x, cons(y, z)) -> if1(le(x, y), x, y, z) 1105.99/291.67 del(x, nil) -> nil 1105.99/291.67 del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) 1105.99/291.67 1105.99/291.67 Types: 1105.99/291.67 le :: 0':s -> 0':s -> true:false 1105.99/291.67 0' :: 0':s 1105.99/291.67 true :: true:false 1105.99/291.67 s :: 0':s -> 0':s 1105.99/291.67 false :: true:false 1105.99/291.67 eq :: 0':s -> 0':s -> true:false 1105.99/291.67 if1 :: true:false -> 0':s -> 0':s -> cons:nil -> 0':s 1105.99/291.67 min :: 0':s -> cons:nil -> 0':s 1105.99/291.67 if2 :: true:false -> 0':s -> 0':s -> cons:nil -> cons:nil 1105.99/291.67 cons :: 0':s -> cons:nil -> cons:nil 1105.99/291.67 del :: 0':s -> cons:nil -> cons:nil 1105.99/291.67 minsort :: cons:nil -> cons:nil 1105.99/291.67 nil :: cons:nil 1105.99/291.67 hole_true:false1_0 :: true:false 1105.99/291.67 hole_0':s2_0 :: 0':s 1105.99/291.67 hole_cons:nil3_0 :: cons:nil 1105.99/291.67 gen_0':s4_0 :: Nat -> 0':s 1105.99/291.67 gen_cons:nil5_0 :: Nat -> cons:nil 1105.99/291.67 1105.99/291.67 1105.99/291.67 Lemmas: 1105.99/291.67 le(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 1105.99/291.67 eq(gen_0':s4_0(n324_0), gen_0':s4_0(n324_0)) -> true, rt in Omega(1 + n324_0) 1105.99/291.67 1105.99/291.67 1105.99/291.67 Generator Equations: 1105.99/291.67 gen_0':s4_0(0) <=> 0' 1105.99/291.67 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1105.99/291.67 gen_cons:nil5_0(0) <=> nil 1105.99/291.67 gen_cons:nil5_0(+(x, 1)) <=> cons(0', gen_cons:nil5_0(x)) 1105.99/291.67 1105.99/291.67 1105.99/291.67 The following defined symbols remain to be analysed: 1105.99/291.67 min, del, minsort 1105.99/291.67 1105.99/291.67 They will be analysed ascendingly in the following order: 1105.99/291.67 min < minsort 1105.99/291.67 del < minsort 1105.99/291.67 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (15) RewriteLemmaProof (LOWER BOUND(ID)) 1105.99/291.67 Proved the following rewrite lemma: 1105.99/291.67 min(gen_0':s4_0(0), gen_cons:nil5_0(n859_0)) -> gen_0':s4_0(0), rt in Omega(1 + n859_0) 1105.99/291.67 1105.99/291.67 Induction Base: 1105.99/291.67 min(gen_0':s4_0(0), gen_cons:nil5_0(0)) ->_R^Omega(1) 1105.99/291.67 gen_0':s4_0(0) 1105.99/291.67 1105.99/291.67 Induction Step: 1105.99/291.67 min(gen_0':s4_0(0), gen_cons:nil5_0(+(n859_0, 1))) ->_R^Omega(1) 1105.99/291.67 if1(le(gen_0':s4_0(0), 0'), gen_0':s4_0(0), 0', gen_cons:nil5_0(n859_0)) ->_L^Omega(1) 1105.99/291.67 if1(true, gen_0':s4_0(0), 0', gen_cons:nil5_0(n859_0)) ->_R^Omega(1) 1105.99/291.67 min(gen_0':s4_0(0), gen_cons:nil5_0(n859_0)) ->_IH 1105.99/291.67 gen_0':s4_0(0) 1105.99/291.67 1105.99/291.67 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (16) 1105.99/291.67 Obligation: 1105.99/291.67 Innermost TRS: 1105.99/291.67 Rules: 1105.99/291.67 le(0', y) -> true 1105.99/291.67 le(s(x), 0') -> false 1105.99/291.67 le(s(x), s(y)) -> le(x, y) 1105.99/291.67 eq(0', 0') -> true 1105.99/291.67 eq(0', s(y)) -> false 1105.99/291.67 eq(s(x), 0') -> false 1105.99/291.67 eq(s(x), s(y)) -> eq(x, y) 1105.99/291.67 if1(true, x, y, xs) -> min(x, xs) 1105.99/291.67 if1(false, x, y, xs) -> min(y, xs) 1105.99/291.67 if2(true, x, y, xs) -> xs 1105.99/291.67 if2(false, x, y, xs) -> cons(y, del(x, xs)) 1105.99/291.67 minsort(nil) -> nil 1105.99/291.67 minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) 1105.99/291.67 min(x, nil) -> x 1105.99/291.67 min(x, cons(y, z)) -> if1(le(x, y), x, y, z) 1105.99/291.67 del(x, nil) -> nil 1105.99/291.67 del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) 1105.99/291.67 1105.99/291.67 Types: 1105.99/291.67 le :: 0':s -> 0':s -> true:false 1105.99/291.67 0' :: 0':s 1105.99/291.67 true :: true:false 1105.99/291.67 s :: 0':s -> 0':s 1105.99/291.67 false :: true:false 1105.99/291.67 eq :: 0':s -> 0':s -> true:false 1105.99/291.67 if1 :: true:false -> 0':s -> 0':s -> cons:nil -> 0':s 1105.99/291.67 min :: 0':s -> cons:nil -> 0':s 1105.99/291.67 if2 :: true:false -> 0':s -> 0':s -> cons:nil -> cons:nil 1105.99/291.67 cons :: 0':s -> cons:nil -> cons:nil 1105.99/291.67 del :: 0':s -> cons:nil -> cons:nil 1105.99/291.67 minsort :: cons:nil -> cons:nil 1105.99/291.67 nil :: cons:nil 1105.99/291.67 hole_true:false1_0 :: true:false 1105.99/291.67 hole_0':s2_0 :: 0':s 1105.99/291.67 hole_cons:nil3_0 :: cons:nil 1105.99/291.67 gen_0':s4_0 :: Nat -> 0':s 1105.99/291.67 gen_cons:nil5_0 :: Nat -> cons:nil 1105.99/291.67 1105.99/291.67 1105.99/291.67 Lemmas: 1105.99/291.67 le(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 1105.99/291.67 eq(gen_0':s4_0(n324_0), gen_0':s4_0(n324_0)) -> true, rt in Omega(1 + n324_0) 1105.99/291.67 min(gen_0':s4_0(0), gen_cons:nil5_0(n859_0)) -> gen_0':s4_0(0), rt in Omega(1 + n859_0) 1105.99/291.67 1105.99/291.67 1105.99/291.67 Generator Equations: 1105.99/291.67 gen_0':s4_0(0) <=> 0' 1105.99/291.67 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1105.99/291.67 gen_cons:nil5_0(0) <=> nil 1105.99/291.67 gen_cons:nil5_0(+(x, 1)) <=> cons(0', gen_cons:nil5_0(x)) 1105.99/291.67 1105.99/291.67 1105.99/291.67 The following defined symbols remain to be analysed: 1105.99/291.67 del, minsort 1105.99/291.67 1105.99/291.67 They will be analysed ascendingly in the following order: 1105.99/291.67 del < minsort 1105.99/291.67 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (17) RewriteLemmaProof (LOWER BOUND(ID)) 1105.99/291.67 Proved the following rewrite lemma: 1105.99/291.67 minsort(gen_cons:nil5_0(n1671_0)) -> gen_cons:nil5_0(n1671_0), rt in Omega(1 + n1671_0 + n1671_0^2) 1105.99/291.67 1105.99/291.67 Induction Base: 1105.99/291.67 minsort(gen_cons:nil5_0(0)) ->_R^Omega(1) 1105.99/291.67 nil 1105.99/291.67 1105.99/291.67 Induction Step: 1105.99/291.67 minsort(gen_cons:nil5_0(+(n1671_0, 1))) ->_R^Omega(1) 1105.99/291.67 cons(min(0', gen_cons:nil5_0(n1671_0)), minsort(del(min(0', gen_cons:nil5_0(n1671_0)), cons(0', gen_cons:nil5_0(n1671_0))))) ->_L^Omega(1 + n1671_0) 1105.99/291.67 cons(gen_0':s4_0(0), minsort(del(min(0', gen_cons:nil5_0(n1671_0)), cons(0', gen_cons:nil5_0(n1671_0))))) ->_L^Omega(1 + n1671_0) 1105.99/291.67 cons(gen_0':s4_0(0), minsort(del(gen_0':s4_0(0), cons(0', gen_cons:nil5_0(n1671_0))))) ->_R^Omega(1) 1105.99/291.67 cons(gen_0':s4_0(0), minsort(if2(eq(gen_0':s4_0(0), 0'), gen_0':s4_0(0), 0', gen_cons:nil5_0(n1671_0)))) ->_L^Omega(1) 1105.99/291.67 cons(gen_0':s4_0(0), minsort(if2(true, gen_0':s4_0(0), 0', gen_cons:nil5_0(n1671_0)))) ->_R^Omega(1) 1105.99/291.67 cons(gen_0':s4_0(0), minsort(gen_cons:nil5_0(n1671_0))) ->_IH 1105.99/291.67 cons(gen_0':s4_0(0), gen_cons:nil5_0(c1672_0)) 1105.99/291.67 1105.99/291.67 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (18) 1105.99/291.67 Obligation: 1105.99/291.67 Proved the lower bound n^2 for the following obligation: 1105.99/291.67 1105.99/291.67 Innermost TRS: 1105.99/291.67 Rules: 1105.99/291.67 le(0', y) -> true 1105.99/291.67 le(s(x), 0') -> false 1105.99/291.67 le(s(x), s(y)) -> le(x, y) 1105.99/291.67 eq(0', 0') -> true 1105.99/291.67 eq(0', s(y)) -> false 1105.99/291.67 eq(s(x), 0') -> false 1105.99/291.67 eq(s(x), s(y)) -> eq(x, y) 1105.99/291.67 if1(true, x, y, xs) -> min(x, xs) 1105.99/291.67 if1(false, x, y, xs) -> min(y, xs) 1105.99/291.67 if2(true, x, y, xs) -> xs 1105.99/291.67 if2(false, x, y, xs) -> cons(y, del(x, xs)) 1105.99/291.67 minsort(nil) -> nil 1105.99/291.67 minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) 1105.99/291.67 min(x, nil) -> x 1105.99/291.67 min(x, cons(y, z)) -> if1(le(x, y), x, y, z) 1105.99/291.67 del(x, nil) -> nil 1105.99/291.67 del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) 1105.99/291.67 1105.99/291.67 Types: 1105.99/291.67 le :: 0':s -> 0':s -> true:false 1105.99/291.67 0' :: 0':s 1105.99/291.67 true :: true:false 1105.99/291.67 s :: 0':s -> 0':s 1105.99/291.67 false :: true:false 1105.99/291.67 eq :: 0':s -> 0':s -> true:false 1105.99/291.67 if1 :: true:false -> 0':s -> 0':s -> cons:nil -> 0':s 1105.99/291.67 min :: 0':s -> cons:nil -> 0':s 1105.99/291.67 if2 :: true:false -> 0':s -> 0':s -> cons:nil -> cons:nil 1105.99/291.67 cons :: 0':s -> cons:nil -> cons:nil 1105.99/291.67 del :: 0':s -> cons:nil -> cons:nil 1105.99/291.67 minsort :: cons:nil -> cons:nil 1105.99/291.67 nil :: cons:nil 1105.99/291.67 hole_true:false1_0 :: true:false 1105.99/291.67 hole_0':s2_0 :: 0':s 1105.99/291.67 hole_cons:nil3_0 :: cons:nil 1105.99/291.67 gen_0':s4_0 :: Nat -> 0':s 1105.99/291.67 gen_cons:nil5_0 :: Nat -> cons:nil 1105.99/291.67 1105.99/291.67 1105.99/291.67 Lemmas: 1105.99/291.67 le(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 1105.99/291.67 eq(gen_0':s4_0(n324_0), gen_0':s4_0(n324_0)) -> true, rt in Omega(1 + n324_0) 1105.99/291.67 min(gen_0':s4_0(0), gen_cons:nil5_0(n859_0)) -> gen_0':s4_0(0), rt in Omega(1 + n859_0) 1105.99/291.67 1105.99/291.67 1105.99/291.67 Generator Equations: 1105.99/291.67 gen_0':s4_0(0) <=> 0' 1105.99/291.67 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1105.99/291.67 gen_cons:nil5_0(0) <=> nil 1105.99/291.67 gen_cons:nil5_0(+(x, 1)) <=> cons(0', gen_cons:nil5_0(x)) 1105.99/291.67 1105.99/291.67 1105.99/291.67 The following defined symbols remain to be analysed: 1105.99/291.67 minsort 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (19) LowerBoundPropagationProof (FINISHED) 1105.99/291.67 Propagated lower bound. 1105.99/291.67 ---------------------------------------- 1105.99/291.67 1105.99/291.67 (20) 1105.99/291.67 BOUNDS(n^2, INF) 1106.16/291.74 EOF