320.02/291.48 WORST_CASE(Omega(n^3), ?) 320.02/291.48 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 320.02/291.48 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 320.02/291.48 320.02/291.48 320.02/291.48 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^3, INF). 320.02/291.48 320.02/291.48 (0) CpxTRS 320.02/291.48 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 320.02/291.48 (2) CpxTRS 320.02/291.48 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 320.02/291.48 (4) typed CpxTrs 320.02/291.48 (5) OrderProof [LOWER BOUND(ID), 0 ms] 320.02/291.48 (6) typed CpxTrs 320.02/291.48 (7) RewriteLemmaProof [LOWER BOUND(ID), 314 ms] 320.02/291.48 (8) BEST 320.02/291.48 (9) proven lower bound 320.02/291.48 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 320.02/291.48 (11) BOUNDS(n^1, INF) 320.02/291.48 (12) typed CpxTrs 320.02/291.48 (13) RewriteLemmaProof [LOWER BOUND(ID), 30 ms] 320.02/291.48 (14) BEST 320.02/291.48 (15) proven lower bound 320.02/291.48 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 320.02/291.48 (17) BOUNDS(n^2, INF) 320.02/291.48 (18) typed CpxTrs 320.02/291.48 (19) RewriteLemmaProof [LOWER BOUND(ID), 729 ms] 320.02/291.48 (20) proven lower bound 320.02/291.48 (21) LowerBoundPropagationProof [FINISHED, 0 ms] 320.02/291.48 (22) BOUNDS(n^3, INF) 320.02/291.48 320.02/291.48 320.02/291.48 ---------------------------------------- 320.02/291.48 320.02/291.48 (0) 320.02/291.48 Obligation: 320.02/291.48 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^3, INF). 320.02/291.48 320.02/291.48 320.02/291.48 The TRS R consists of the following rules: 320.02/291.48 320.02/291.48 null(nil) -> true 320.02/291.48 null(add(n, x)) -> false 320.02/291.48 tail(add(n, x)) -> x 320.02/291.48 tail(nil) -> nil 320.02/291.48 head(add(n, x)) -> n 320.02/291.48 app(nil, y) -> y 320.02/291.48 app(add(n, x), y) -> add(n, app(x, y)) 320.02/291.48 reverse(nil) -> nil 320.02/291.48 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 320.02/291.48 shuffle(x) -> shuff(x, nil) 320.02/291.48 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 320.02/291.48 if(true, x, y, z) -> y 320.02/291.48 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 320.02/291.48 320.02/291.48 S is empty. 320.02/291.48 Rewrite Strategy: FULL 320.02/291.48 ---------------------------------------- 320.02/291.48 320.02/291.48 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 320.02/291.48 Renamed function symbols to avoid clashes with predefined symbol. 320.02/291.48 ---------------------------------------- 320.02/291.48 320.02/291.48 (2) 320.02/291.48 Obligation: 320.02/291.48 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^3, INF). 320.02/291.48 320.02/291.48 320.02/291.48 The TRS R consists of the following rules: 320.02/291.48 320.02/291.48 null(nil) -> true 320.02/291.48 null(add(n, x)) -> false 320.02/291.48 tail(add(n, x)) -> x 320.02/291.48 tail(nil) -> nil 320.02/291.48 head(add(n, x)) -> n 320.02/291.48 app(nil, y) -> y 320.02/291.48 app(add(n, x), y) -> add(n, app(x, y)) 320.02/291.48 reverse(nil) -> nil 320.02/291.48 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 320.02/291.48 shuffle(x) -> shuff(x, nil) 320.02/291.48 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 320.02/291.48 if(true, x, y, z) -> y 320.02/291.48 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 320.02/291.48 320.02/291.48 S is empty. 320.02/291.48 Rewrite Strategy: FULL 320.02/291.48 ---------------------------------------- 320.02/291.48 320.02/291.48 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 320.02/291.48 Infered types. 320.02/291.48 ---------------------------------------- 320.02/291.48 320.02/291.48 (4) 320.02/291.48 Obligation: 320.02/291.48 TRS: 320.02/291.48 Rules: 320.02/291.48 null(nil) -> true 320.02/291.48 null(add(n, x)) -> false 320.02/291.48 tail(add(n, x)) -> x 320.02/291.48 tail(nil) -> nil 320.02/291.48 head(add(n, x)) -> n 320.02/291.48 app(nil, y) -> y 320.02/291.48 app(add(n, x), y) -> add(n, app(x, y)) 320.02/291.48 reverse(nil) -> nil 320.02/291.48 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 320.02/291.48 shuffle(x) -> shuff(x, nil) 320.02/291.48 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 320.02/291.48 if(true, x, y, z) -> y 320.02/291.48 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 320.02/291.48 320.02/291.48 Types: 320.02/291.48 null :: nil:add -> true:false 320.02/291.48 nil :: nil:add 320.02/291.48 true :: true:false 320.02/291.48 add :: head -> nil:add -> nil:add 320.02/291.48 false :: true:false 320.02/291.48 tail :: nil:add -> nil:add 320.02/291.48 head :: nil:add -> head 320.02/291.48 app :: nil:add -> nil:add -> nil:add 320.02/291.48 reverse :: nil:add -> nil:add 320.02/291.48 shuffle :: nil:add -> nil:add 320.02/291.48 shuff :: nil:add -> nil:add -> nil:add 320.02/291.48 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 320.02/291.48 hole_true:false1_0 :: true:false 320.02/291.48 hole_nil:add2_0 :: nil:add 320.02/291.48 hole_head3_0 :: head 320.02/291.48 gen_nil:add4_0 :: Nat -> nil:add 320.02/291.48 320.02/291.48 ---------------------------------------- 320.02/291.48 320.02/291.48 (5) OrderProof (LOWER BOUND(ID)) 320.02/291.48 Heuristically decided to analyse the following defined symbols: 320.02/291.48 app, reverse, shuff 320.02/291.48 320.02/291.48 They will be analysed ascendingly in the following order: 320.02/291.48 app < reverse 320.02/291.48 app < shuff 320.02/291.48 reverse < shuff 320.02/291.48 320.02/291.48 ---------------------------------------- 320.02/291.48 320.02/291.48 (6) 320.02/291.48 Obligation: 320.02/291.48 TRS: 320.02/291.48 Rules: 320.02/291.48 null(nil) -> true 320.02/291.48 null(add(n, x)) -> false 320.02/291.48 tail(add(n, x)) -> x 320.02/291.48 tail(nil) -> nil 320.02/291.48 head(add(n, x)) -> n 320.02/291.48 app(nil, y) -> y 320.02/291.48 app(add(n, x), y) -> add(n, app(x, y)) 320.02/291.48 reverse(nil) -> nil 320.02/291.48 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 320.02/291.48 shuffle(x) -> shuff(x, nil) 320.02/291.48 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 320.02/291.48 if(true, x, y, z) -> y 320.02/291.48 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 320.02/291.48 320.02/291.48 Types: 320.02/291.48 null :: nil:add -> true:false 320.02/291.48 nil :: nil:add 320.02/291.48 true :: true:false 320.02/291.48 add :: head -> nil:add -> nil:add 320.02/291.48 false :: true:false 320.02/291.48 tail :: nil:add -> nil:add 320.02/291.48 head :: nil:add -> head 320.02/291.48 app :: nil:add -> nil:add -> nil:add 320.02/291.48 reverse :: nil:add -> nil:add 320.02/291.48 shuffle :: nil:add -> nil:add 320.02/291.48 shuff :: nil:add -> nil:add -> nil:add 320.02/291.48 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 320.02/291.48 hole_true:false1_0 :: true:false 320.02/291.48 hole_nil:add2_0 :: nil:add 320.02/291.48 hole_head3_0 :: head 320.02/291.48 gen_nil:add4_0 :: Nat -> nil:add 320.02/291.48 320.02/291.48 320.02/291.48 Generator Equations: 320.02/291.48 gen_nil:add4_0(0) <=> nil 320.02/291.48 gen_nil:add4_0(+(x, 1)) <=> add(hole_head3_0, gen_nil:add4_0(x)) 320.02/291.48 320.02/291.48 320.02/291.48 The following defined symbols remain to be analysed: 320.02/291.48 app, reverse, shuff 320.02/291.48 320.02/291.48 They will be analysed ascendingly in the following order: 320.02/291.48 app < reverse 320.02/291.48 app < shuff 320.02/291.48 reverse < shuff 320.02/291.48 320.02/291.48 ---------------------------------------- 320.02/291.48 320.02/291.48 (7) RewriteLemmaProof (LOWER BOUND(ID)) 320.02/291.48 Proved the following rewrite lemma: 320.02/291.48 app(gen_nil:add4_0(n6_0), gen_nil:add4_0(b)) -> gen_nil:add4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 320.02/291.48 320.02/291.48 Induction Base: 320.02/291.48 app(gen_nil:add4_0(0), gen_nil:add4_0(b)) ->_R^Omega(1) 320.02/291.48 gen_nil:add4_0(b) 320.02/291.48 320.02/291.48 Induction Step: 320.02/291.48 app(gen_nil:add4_0(+(n6_0, 1)), gen_nil:add4_0(b)) ->_R^Omega(1) 320.02/291.48 add(hole_head3_0, app(gen_nil:add4_0(n6_0), gen_nil:add4_0(b))) ->_IH 320.02/291.48 add(hole_head3_0, gen_nil:add4_0(+(b, c7_0))) 320.02/291.48 320.02/291.48 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 320.02/291.48 ---------------------------------------- 320.02/291.48 320.02/291.48 (8) 320.02/291.48 Complex Obligation (BEST) 320.02/291.48 320.02/291.48 ---------------------------------------- 320.02/291.48 320.02/291.48 (9) 320.02/291.48 Obligation: 320.02/291.48 Proved the lower bound n^1 for the following obligation: 320.02/291.48 320.02/291.48 TRS: 320.02/291.48 Rules: 320.02/291.48 null(nil) -> true 320.02/291.48 null(add(n, x)) -> false 320.02/291.48 tail(add(n, x)) -> x 320.02/291.48 tail(nil) -> nil 320.02/291.48 head(add(n, x)) -> n 320.02/291.48 app(nil, y) -> y 320.02/291.48 app(add(n, x), y) -> add(n, app(x, y)) 320.02/291.48 reverse(nil) -> nil 320.02/291.48 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 320.02/291.48 shuffle(x) -> shuff(x, nil) 320.02/291.48 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 320.02/291.48 if(true, x, y, z) -> y 320.02/291.48 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 320.02/291.48 320.02/291.48 Types: 320.02/291.48 null :: nil:add -> true:false 320.02/291.48 nil :: nil:add 320.02/291.48 true :: true:false 320.02/291.48 add :: head -> nil:add -> nil:add 320.02/291.48 false :: true:false 320.02/291.48 tail :: nil:add -> nil:add 320.02/291.48 head :: nil:add -> head 320.02/291.48 app :: nil:add -> nil:add -> nil:add 320.02/291.48 reverse :: nil:add -> nil:add 320.02/291.48 shuffle :: nil:add -> nil:add 320.02/291.48 shuff :: nil:add -> nil:add -> nil:add 320.02/291.48 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 320.02/291.48 hole_true:false1_0 :: true:false 320.02/291.48 hole_nil:add2_0 :: nil:add 320.02/291.48 hole_head3_0 :: head 320.02/291.48 gen_nil:add4_0 :: Nat -> nil:add 320.02/291.48 320.02/291.48 320.02/291.48 Generator Equations: 320.02/291.48 gen_nil:add4_0(0) <=> nil 320.02/291.48 gen_nil:add4_0(+(x, 1)) <=> add(hole_head3_0, gen_nil:add4_0(x)) 320.02/291.48 320.02/291.48 320.02/291.48 The following defined symbols remain to be analysed: 320.02/291.48 app, reverse, shuff 320.02/291.48 320.02/291.48 They will be analysed ascendingly in the following order: 320.02/291.48 app < reverse 320.02/291.48 app < shuff 320.02/291.48 reverse < shuff 320.02/291.48 320.02/291.48 ---------------------------------------- 320.02/291.48 320.02/291.48 (10) LowerBoundPropagationProof (FINISHED) 320.02/291.48 Propagated lower bound. 320.02/291.48 ---------------------------------------- 320.02/291.48 320.02/291.48 (11) 320.02/291.48 BOUNDS(n^1, INF) 320.02/291.48 320.02/291.48 ---------------------------------------- 320.02/291.48 320.02/291.48 (12) 320.02/291.48 Obligation: 320.02/291.48 TRS: 320.02/291.48 Rules: 320.02/291.48 null(nil) -> true 320.02/291.48 null(add(n, x)) -> false 320.02/291.48 tail(add(n, x)) -> x 320.02/291.48 tail(nil) -> nil 320.02/291.48 head(add(n, x)) -> n 320.02/291.48 app(nil, y) -> y 320.02/291.48 app(add(n, x), y) -> add(n, app(x, y)) 320.02/291.48 reverse(nil) -> nil 320.02/291.48 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 320.02/291.48 shuffle(x) -> shuff(x, nil) 320.02/291.48 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 320.02/291.48 if(true, x, y, z) -> y 320.02/291.48 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 320.02/291.48 320.02/291.48 Types: 320.02/291.48 null :: nil:add -> true:false 320.02/291.48 nil :: nil:add 320.02/291.48 true :: true:false 320.02/291.48 add :: head -> nil:add -> nil:add 320.02/291.48 false :: true:false 320.02/291.48 tail :: nil:add -> nil:add 320.02/291.48 head :: nil:add -> head 320.02/291.48 app :: nil:add -> nil:add -> nil:add 320.02/291.48 reverse :: nil:add -> nil:add 320.02/291.48 shuffle :: nil:add -> nil:add 320.02/291.48 shuff :: nil:add -> nil:add -> nil:add 320.02/291.48 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 320.02/291.48 hole_true:false1_0 :: true:false 320.02/291.48 hole_nil:add2_0 :: nil:add 320.02/291.48 hole_head3_0 :: head 320.02/291.48 gen_nil:add4_0 :: Nat -> nil:add 320.02/291.48 320.02/291.48 320.02/291.48 Lemmas: 320.02/291.48 app(gen_nil:add4_0(n6_0), gen_nil:add4_0(b)) -> gen_nil:add4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 320.02/291.48 320.02/291.48 320.02/291.48 Generator Equations: 320.02/291.48 gen_nil:add4_0(0) <=> nil 320.02/291.48 gen_nil:add4_0(+(x, 1)) <=> add(hole_head3_0, gen_nil:add4_0(x)) 320.02/291.48 320.02/291.48 320.02/291.48 The following defined symbols remain to be analysed: 320.02/291.48 reverse, shuff 320.02/291.48 320.02/291.48 They will be analysed ascendingly in the following order: 320.02/291.48 reverse < shuff 320.02/291.48 320.02/291.48 ---------------------------------------- 320.02/291.48 320.02/291.48 (13) RewriteLemmaProof (LOWER BOUND(ID)) 320.02/291.48 Proved the following rewrite lemma: 320.02/291.48 reverse(gen_nil:add4_0(n585_0)) -> gen_nil:add4_0(n585_0), rt in Omega(1 + n585_0 + n585_0^2) 320.02/291.48 320.02/291.48 Induction Base: 320.02/291.48 reverse(gen_nil:add4_0(0)) ->_R^Omega(1) 320.02/291.48 nil 320.02/291.48 320.02/291.48 Induction Step: 320.02/291.48 reverse(gen_nil:add4_0(+(n585_0, 1))) ->_R^Omega(1) 320.02/291.48 app(reverse(gen_nil:add4_0(n585_0)), add(hole_head3_0, nil)) ->_IH 320.02/291.48 app(gen_nil:add4_0(c586_0), add(hole_head3_0, nil)) ->_L^Omega(1 + n585_0) 320.02/291.48 gen_nil:add4_0(+(n585_0, +(0, 1))) 320.02/291.48 320.02/291.48 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 320.02/291.48 ---------------------------------------- 320.02/291.48 320.02/291.48 (14) 320.02/291.48 Complex Obligation (BEST) 320.02/291.48 320.02/291.48 ---------------------------------------- 320.02/291.49 320.02/291.49 (15) 320.02/291.49 Obligation: 320.02/291.49 Proved the lower bound n^2 for the following obligation: 320.02/291.49 320.02/291.49 TRS: 320.02/291.49 Rules: 320.02/291.49 null(nil) -> true 320.02/291.49 null(add(n, x)) -> false 320.02/291.49 tail(add(n, x)) -> x 320.02/291.49 tail(nil) -> nil 320.02/291.49 head(add(n, x)) -> n 320.02/291.49 app(nil, y) -> y 320.02/291.49 app(add(n, x), y) -> add(n, app(x, y)) 320.02/291.49 reverse(nil) -> nil 320.02/291.49 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 320.02/291.49 shuffle(x) -> shuff(x, nil) 320.02/291.49 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 320.02/291.49 if(true, x, y, z) -> y 320.02/291.49 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 320.02/291.49 320.02/291.49 Types: 320.02/291.49 null :: nil:add -> true:false 320.02/291.49 nil :: nil:add 320.02/291.49 true :: true:false 320.02/291.49 add :: head -> nil:add -> nil:add 320.02/291.49 false :: true:false 320.02/291.49 tail :: nil:add -> nil:add 320.02/291.49 head :: nil:add -> head 320.02/291.49 app :: nil:add -> nil:add -> nil:add 320.02/291.49 reverse :: nil:add -> nil:add 320.02/291.49 shuffle :: nil:add -> nil:add 320.02/291.49 shuff :: nil:add -> nil:add -> nil:add 320.02/291.49 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 320.02/291.49 hole_true:false1_0 :: true:false 320.02/291.49 hole_nil:add2_0 :: nil:add 320.02/291.49 hole_head3_0 :: head 320.02/291.49 gen_nil:add4_0 :: Nat -> nil:add 320.02/291.49 320.02/291.49 320.02/291.49 Lemmas: 320.02/291.49 app(gen_nil:add4_0(n6_0), gen_nil:add4_0(b)) -> gen_nil:add4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 320.02/291.49 320.02/291.49 320.02/291.49 Generator Equations: 320.02/291.49 gen_nil:add4_0(0) <=> nil 320.02/291.49 gen_nil:add4_0(+(x, 1)) <=> add(hole_head3_0, gen_nil:add4_0(x)) 320.02/291.49 320.02/291.49 320.02/291.49 The following defined symbols remain to be analysed: 320.02/291.49 reverse, shuff 320.02/291.49 320.02/291.49 They will be analysed ascendingly in the following order: 320.02/291.49 reverse < shuff 320.02/291.49 320.02/291.49 ---------------------------------------- 320.02/291.49 320.02/291.49 (16) LowerBoundPropagationProof (FINISHED) 320.02/291.49 Propagated lower bound. 320.02/291.49 ---------------------------------------- 320.02/291.49 320.02/291.49 (17) 320.02/291.49 BOUNDS(n^2, INF) 320.02/291.49 320.02/291.49 ---------------------------------------- 320.02/291.49 320.02/291.49 (18) 320.02/291.49 Obligation: 320.02/291.49 TRS: 320.02/291.49 Rules: 320.02/291.49 null(nil) -> true 320.02/291.49 null(add(n, x)) -> false 320.02/291.49 tail(add(n, x)) -> x 320.02/291.49 tail(nil) -> nil 320.02/291.49 head(add(n, x)) -> n 320.02/291.49 app(nil, y) -> y 320.02/291.49 app(add(n, x), y) -> add(n, app(x, y)) 320.02/291.49 reverse(nil) -> nil 320.02/291.49 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 320.02/291.49 shuffle(x) -> shuff(x, nil) 320.02/291.49 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 320.02/291.49 if(true, x, y, z) -> y 320.02/291.49 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 320.02/291.49 320.02/291.49 Types: 320.02/291.49 null :: nil:add -> true:false 320.02/291.49 nil :: nil:add 320.02/291.49 true :: true:false 320.02/291.49 add :: head -> nil:add -> nil:add 320.02/291.49 false :: true:false 320.02/291.49 tail :: nil:add -> nil:add 320.02/291.49 head :: nil:add -> head 320.02/291.49 app :: nil:add -> nil:add -> nil:add 320.02/291.49 reverse :: nil:add -> nil:add 320.02/291.49 shuffle :: nil:add -> nil:add 320.02/291.49 shuff :: nil:add -> nil:add -> nil:add 320.02/291.49 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 320.02/291.49 hole_true:false1_0 :: true:false 320.02/291.49 hole_nil:add2_0 :: nil:add 320.02/291.49 hole_head3_0 :: head 320.02/291.49 gen_nil:add4_0 :: Nat -> nil:add 320.02/291.49 320.02/291.49 320.02/291.49 Lemmas: 320.02/291.49 app(gen_nil:add4_0(n6_0), gen_nil:add4_0(b)) -> gen_nil:add4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 320.02/291.49 reverse(gen_nil:add4_0(n585_0)) -> gen_nil:add4_0(n585_0), rt in Omega(1 + n585_0 + n585_0^2) 320.02/291.49 320.02/291.49 320.02/291.49 Generator Equations: 320.02/291.49 gen_nil:add4_0(0) <=> nil 320.02/291.49 gen_nil:add4_0(+(x, 1)) <=> add(hole_head3_0, gen_nil:add4_0(x)) 320.02/291.49 320.02/291.49 320.02/291.49 The following defined symbols remain to be analysed: 320.02/291.49 shuff 320.02/291.49 ---------------------------------------- 320.02/291.49 320.02/291.49 (19) RewriteLemmaProof (LOWER BOUND(ID)) 320.02/291.49 Proved the following rewrite lemma: 320.02/291.49 shuff(gen_nil:add4_0(n822_0), gen_nil:add4_0(b)) -> *5_0, rt in Omega(b*n822_0 + n822_0 + n822_0^2 + n822_0^3) 320.02/291.49 320.02/291.49 Induction Base: 320.02/291.49 shuff(gen_nil:add4_0(0), gen_nil:add4_0(b)) 320.02/291.49 320.02/291.49 Induction Step: 320.02/291.49 shuff(gen_nil:add4_0(+(n822_0, 1)), gen_nil:add4_0(b)) ->_R^Omega(1) 320.02/291.49 if(null(gen_nil:add4_0(+(n822_0, 1))), gen_nil:add4_0(+(n822_0, 1)), gen_nil:add4_0(b), app(gen_nil:add4_0(b), add(head(gen_nil:add4_0(+(n822_0, 1))), nil))) ->_R^Omega(1) 320.02/291.49 if(false, gen_nil:add4_0(+(1, n822_0)), gen_nil:add4_0(b), app(gen_nil:add4_0(b), add(head(gen_nil:add4_0(+(1, n822_0))), nil))) ->_R^Omega(1) 320.02/291.49 if(false, gen_nil:add4_0(+(1, n822_0)), gen_nil:add4_0(b), app(gen_nil:add4_0(b), add(hole_head3_0, nil))) ->_L^Omega(1 + b) 320.02/291.49 if(false, gen_nil:add4_0(+(1, n822_0)), gen_nil:add4_0(+(0, 1)), gen_nil:add4_0(+(b, +(0, 1)))) ->_R^Omega(1) 320.02/291.49 shuff(reverse(tail(gen_nil:add4_0(+(1, n822_0)))), gen_nil:add4_0(+(1, b))) ->_R^Omega(1) 320.02/291.49 shuff(reverse(gen_nil:add4_0(n822_0)), gen_nil:add4_0(+(1, b))) ->_L^Omega(1 + n822_0 + n822_0^2) 320.02/291.49 shuff(gen_nil:add4_0(n822_0), gen_nil:add4_0(+(1, b))) ->_IH 320.02/291.49 *5_0 320.02/291.49 320.02/291.49 We have rt in Omega(n^3) and sz in O(n). Thus, we have irc_R in Omega(n^3). 320.02/291.49 ---------------------------------------- 320.02/291.49 320.02/291.49 (20) 320.02/291.49 Obligation: 320.02/291.49 Proved the lower bound n^3 for the following obligation: 320.02/291.49 320.02/291.49 TRS: 320.02/291.49 Rules: 320.02/291.49 null(nil) -> true 320.02/291.49 null(add(n, x)) -> false 320.02/291.49 tail(add(n, x)) -> x 320.02/291.49 tail(nil) -> nil 320.02/291.49 head(add(n, x)) -> n 320.02/291.49 app(nil, y) -> y 320.02/291.49 app(add(n, x), y) -> add(n, app(x, y)) 320.02/291.49 reverse(nil) -> nil 320.02/291.49 reverse(add(n, x)) -> app(reverse(x), add(n, nil)) 320.02/291.49 shuffle(x) -> shuff(x, nil) 320.02/291.49 shuff(x, y) -> if(null(x), x, y, app(y, add(head(x), nil))) 320.02/291.49 if(true, x, y, z) -> y 320.02/291.49 if(false, x, y, z) -> shuff(reverse(tail(x)), z) 320.02/291.49 320.02/291.49 Types: 320.02/291.49 null :: nil:add -> true:false 320.02/291.49 nil :: nil:add 320.02/291.49 true :: true:false 320.02/291.49 add :: head -> nil:add -> nil:add 320.02/291.49 false :: true:false 320.02/291.49 tail :: nil:add -> nil:add 320.02/291.49 head :: nil:add -> head 320.02/291.49 app :: nil:add -> nil:add -> nil:add 320.02/291.49 reverse :: nil:add -> nil:add 320.02/291.49 shuffle :: nil:add -> nil:add 320.02/291.49 shuff :: nil:add -> nil:add -> nil:add 320.02/291.49 if :: true:false -> nil:add -> nil:add -> nil:add -> nil:add 320.02/291.49 hole_true:false1_0 :: true:false 320.02/291.49 hole_nil:add2_0 :: nil:add 320.02/291.49 hole_head3_0 :: head 320.02/291.49 gen_nil:add4_0 :: Nat -> nil:add 320.02/291.49 320.02/291.49 320.02/291.49 Lemmas: 320.02/291.49 app(gen_nil:add4_0(n6_0), gen_nil:add4_0(b)) -> gen_nil:add4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 320.02/291.49 reverse(gen_nil:add4_0(n585_0)) -> gen_nil:add4_0(n585_0), rt in Omega(1 + n585_0 + n585_0^2) 320.02/291.49 320.02/291.49 320.02/291.49 Generator Equations: 320.02/291.49 gen_nil:add4_0(0) <=> nil 320.02/291.49 gen_nil:add4_0(+(x, 1)) <=> add(hole_head3_0, gen_nil:add4_0(x)) 320.02/291.49 320.02/291.49 320.02/291.49 The following defined symbols remain to be analysed: 320.02/291.49 shuff 320.02/291.49 ---------------------------------------- 320.02/291.49 320.02/291.49 (21) LowerBoundPropagationProof (FINISHED) 320.02/291.49 Propagated lower bound. 320.02/291.49 ---------------------------------------- 320.02/291.49 320.02/291.49 (22) 320.02/291.49 BOUNDS(n^3, INF) 320.11/291.52 EOF