315.82/291.54 WORST_CASE(Omega(n^2), ?) 315.82/291.55 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 315.82/291.55 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 315.82/291.55 315.82/291.55 315.82/291.55 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 315.82/291.55 315.82/291.55 (0) CpxTRS 315.82/291.55 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 315.82/291.55 (2) CpxTRS 315.82/291.55 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 315.82/291.55 (4) typed CpxTrs 315.82/291.55 (5) OrderProof [LOWER BOUND(ID), 0 ms] 315.82/291.55 (6) typed CpxTrs 315.82/291.55 (7) RewriteLemmaProof [LOWER BOUND(ID), 293 ms] 315.82/291.55 (8) BEST 315.82/291.55 (9) proven lower bound 315.82/291.55 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 315.82/291.55 (11) BOUNDS(n^1, INF) 315.82/291.55 (12) typed CpxTrs 315.82/291.55 (13) RewriteLemmaProof [LOWER BOUND(ID), 56 ms] 315.82/291.55 (14) typed CpxTrs 315.82/291.55 (15) RewriteLemmaProof [LOWER BOUND(ID), 395 ms] 315.82/291.55 (16) BEST 315.82/291.55 (17) proven lower bound 315.82/291.55 (18) LowerBoundPropagationProof [FINISHED, 0 ms] 315.82/291.55 (19) BOUNDS(n^2, INF) 315.82/291.55 (20) typed CpxTrs 315.82/291.55 (21) RewriteLemmaProof [LOWER BOUND(ID), 0 ms] 315.82/291.55 (22) BOUNDS(1, INF) 315.82/291.55 315.82/291.55 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (0) 315.82/291.55 Obligation: 315.82/291.55 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 315.82/291.55 315.82/291.55 315.82/291.55 The TRS R consists of the following rules: 315.82/291.55 315.82/291.55 app(nil, k) -> k 315.82/291.55 app(l, nil) -> l 315.82/291.55 app(cons(x, l), k) -> cons(x, app(l, k)) 315.82/291.55 sum(cons(x, nil)) -> cons(x, nil) 315.82/291.55 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 315.82/291.55 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 315.82/291.55 plus(s(x), s(y)) -> s(s(plus(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 315.82/291.55 plus(s(x), x) -> plus(if(gt(x, x), id(x), id(x)), s(x)) 315.82/291.55 plus(zero, y) -> y 315.82/291.55 plus(id(x), s(y)) -> s(plus(x, if(gt(s(y), y), y, s(y)))) 315.82/291.55 id(x) -> x 315.82/291.55 if(true, x, y) -> x 315.82/291.55 if(false, x, y) -> y 315.82/291.55 not(x) -> if(x, false, true) 315.82/291.55 gt(s(x), zero) -> true 315.82/291.55 gt(zero, y) -> false 315.82/291.55 gt(s(x), s(y)) -> gt(x, y) 315.82/291.55 315.82/291.55 S is empty. 315.82/291.55 Rewrite Strategy: FULL 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 315.82/291.55 Renamed function symbols to avoid clashes with predefined symbol. 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (2) 315.82/291.55 Obligation: 315.82/291.55 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 315.82/291.55 315.82/291.55 315.82/291.55 The TRS R consists of the following rules: 315.82/291.55 315.82/291.55 app(nil, k) -> k 315.82/291.55 app(l, nil) -> l 315.82/291.55 app(cons(x, l), k) -> cons(x, app(l, k)) 315.82/291.55 sum(cons(x, nil)) -> cons(x, nil) 315.82/291.55 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 315.82/291.55 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 315.82/291.55 plus(s(x), s(y)) -> s(s(plus(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 315.82/291.55 plus(s(x), x) -> plus(if(gt(x, x), id(x), id(x)), s(x)) 315.82/291.55 plus(zero, y) -> y 315.82/291.55 plus(id(x), s(y)) -> s(plus(x, if(gt(s(y), y), y, s(y)))) 315.82/291.55 id(x) -> x 315.82/291.55 if(true, x, y) -> x 315.82/291.55 if(false, x, y) -> y 315.82/291.55 not(x) -> if(x, false, true) 315.82/291.55 gt(s(x), zero) -> true 315.82/291.55 gt(zero, y) -> false 315.82/291.55 gt(s(x), s(y)) -> gt(x, y) 315.82/291.55 315.82/291.55 S is empty. 315.82/291.55 Rewrite Strategy: FULL 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 315.82/291.55 Infered types. 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (4) 315.82/291.55 Obligation: 315.82/291.55 TRS: 315.82/291.55 Rules: 315.82/291.55 app(nil, k) -> k 315.82/291.55 app(l, nil) -> l 315.82/291.55 app(cons(x, l), k) -> cons(x, app(l, k)) 315.82/291.55 sum(cons(x, nil)) -> cons(x, nil) 315.82/291.55 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 315.82/291.55 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 315.82/291.55 plus(s(x), s(y)) -> s(s(plus(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 315.82/291.55 plus(s(x), x) -> plus(if(gt(x, x), id(x), id(x)), s(x)) 315.82/291.55 plus(zero, y) -> y 315.82/291.55 plus(id(x), s(y)) -> s(plus(x, if(gt(s(y), y), y, s(y)))) 315.82/291.55 id(x) -> x 315.82/291.55 if(true, x, y) -> x 315.82/291.55 if(false, x, y) -> y 315.82/291.55 not(x) -> if(x, false, true) 315.82/291.55 gt(s(x), zero) -> true 315.82/291.55 gt(zero, y) -> false 315.82/291.55 gt(s(x), s(y)) -> gt(x, y) 315.82/291.55 315.82/291.55 Types: 315.82/291.55 app :: nil:cons -> nil:cons -> nil:cons 315.82/291.55 nil :: nil:cons 315.82/291.55 cons :: s:zero:true:false -> nil:cons -> nil:cons 315.82/291.55 sum :: nil:cons -> nil:cons 315.82/291.55 plus :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 s :: s:zero:true:false -> s:zero:true:false 315.82/291.55 if :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 gt :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 not :: s:zero:true:false -> s:zero:true:false 315.82/291.55 id :: s:zero:true:false -> s:zero:true:false 315.82/291.55 zero :: s:zero:true:false 315.82/291.55 true :: s:zero:true:false 315.82/291.55 false :: s:zero:true:false 315.82/291.55 hole_nil:cons1_0 :: nil:cons 315.82/291.55 hole_s:zero:true:false2_0 :: s:zero:true:false 315.82/291.55 gen_nil:cons3_0 :: Nat -> nil:cons 315.82/291.55 gen_s:zero:true:false4_0 :: Nat -> s:zero:true:false 315.82/291.55 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (5) OrderProof (LOWER BOUND(ID)) 315.82/291.55 Heuristically decided to analyse the following defined symbols: 315.82/291.55 app, sum, plus, gt 315.82/291.55 315.82/291.55 They will be analysed ascendingly in the following order: 315.82/291.55 app < sum 315.82/291.55 plus < sum 315.82/291.55 gt < plus 315.82/291.55 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (6) 315.82/291.55 Obligation: 315.82/291.55 TRS: 315.82/291.55 Rules: 315.82/291.55 app(nil, k) -> k 315.82/291.55 app(l, nil) -> l 315.82/291.55 app(cons(x, l), k) -> cons(x, app(l, k)) 315.82/291.55 sum(cons(x, nil)) -> cons(x, nil) 315.82/291.55 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 315.82/291.55 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 315.82/291.55 plus(s(x), s(y)) -> s(s(plus(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 315.82/291.55 plus(s(x), x) -> plus(if(gt(x, x), id(x), id(x)), s(x)) 315.82/291.55 plus(zero, y) -> y 315.82/291.55 plus(id(x), s(y)) -> s(plus(x, if(gt(s(y), y), y, s(y)))) 315.82/291.55 id(x) -> x 315.82/291.55 if(true, x, y) -> x 315.82/291.55 if(false, x, y) -> y 315.82/291.55 not(x) -> if(x, false, true) 315.82/291.55 gt(s(x), zero) -> true 315.82/291.55 gt(zero, y) -> false 315.82/291.55 gt(s(x), s(y)) -> gt(x, y) 315.82/291.55 315.82/291.55 Types: 315.82/291.55 app :: nil:cons -> nil:cons -> nil:cons 315.82/291.55 nil :: nil:cons 315.82/291.55 cons :: s:zero:true:false -> nil:cons -> nil:cons 315.82/291.55 sum :: nil:cons -> nil:cons 315.82/291.55 plus :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 s :: s:zero:true:false -> s:zero:true:false 315.82/291.55 if :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 gt :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 not :: s:zero:true:false -> s:zero:true:false 315.82/291.55 id :: s:zero:true:false -> s:zero:true:false 315.82/291.55 zero :: s:zero:true:false 315.82/291.55 true :: s:zero:true:false 315.82/291.55 false :: s:zero:true:false 315.82/291.55 hole_nil:cons1_0 :: nil:cons 315.82/291.55 hole_s:zero:true:false2_0 :: s:zero:true:false 315.82/291.55 gen_nil:cons3_0 :: Nat -> nil:cons 315.82/291.55 gen_s:zero:true:false4_0 :: Nat -> s:zero:true:false 315.82/291.55 315.82/291.55 315.82/291.55 Generator Equations: 315.82/291.55 gen_nil:cons3_0(0) <=> nil 315.82/291.55 gen_nil:cons3_0(+(x, 1)) <=> cons(zero, gen_nil:cons3_0(x)) 315.82/291.55 gen_s:zero:true:false4_0(0) <=> zero 315.82/291.55 gen_s:zero:true:false4_0(+(x, 1)) <=> s(gen_s:zero:true:false4_0(x)) 315.82/291.55 315.82/291.55 315.82/291.55 The following defined symbols remain to be analysed: 315.82/291.55 app, sum, plus, gt 315.82/291.55 315.82/291.55 They will be analysed ascendingly in the following order: 315.82/291.55 app < sum 315.82/291.55 plus < sum 315.82/291.55 gt < plus 315.82/291.55 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (7) RewriteLemmaProof (LOWER BOUND(ID)) 315.82/291.55 Proved the following rewrite lemma: 315.82/291.55 app(gen_nil:cons3_0(n6_0), gen_nil:cons3_0(b)) -> gen_nil:cons3_0(+(n6_0, b)), rt in Omega(1 + n6_0) 315.82/291.55 315.82/291.55 Induction Base: 315.82/291.55 app(gen_nil:cons3_0(0), gen_nil:cons3_0(b)) ->_R^Omega(1) 315.82/291.55 gen_nil:cons3_0(b) 315.82/291.55 315.82/291.55 Induction Step: 315.82/291.55 app(gen_nil:cons3_0(+(n6_0, 1)), gen_nil:cons3_0(b)) ->_R^Omega(1) 315.82/291.55 cons(zero, app(gen_nil:cons3_0(n6_0), gen_nil:cons3_0(b))) ->_IH 315.82/291.55 cons(zero, gen_nil:cons3_0(+(b, c7_0))) 315.82/291.55 315.82/291.55 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (8) 315.82/291.55 Complex Obligation (BEST) 315.82/291.55 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (9) 315.82/291.55 Obligation: 315.82/291.55 Proved the lower bound n^1 for the following obligation: 315.82/291.55 315.82/291.55 TRS: 315.82/291.55 Rules: 315.82/291.55 app(nil, k) -> k 315.82/291.55 app(l, nil) -> l 315.82/291.55 app(cons(x, l), k) -> cons(x, app(l, k)) 315.82/291.55 sum(cons(x, nil)) -> cons(x, nil) 315.82/291.55 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 315.82/291.55 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 315.82/291.55 plus(s(x), s(y)) -> s(s(plus(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 315.82/291.55 plus(s(x), x) -> plus(if(gt(x, x), id(x), id(x)), s(x)) 315.82/291.55 plus(zero, y) -> y 315.82/291.55 plus(id(x), s(y)) -> s(plus(x, if(gt(s(y), y), y, s(y)))) 315.82/291.55 id(x) -> x 315.82/291.55 if(true, x, y) -> x 315.82/291.55 if(false, x, y) -> y 315.82/291.55 not(x) -> if(x, false, true) 315.82/291.55 gt(s(x), zero) -> true 315.82/291.55 gt(zero, y) -> false 315.82/291.55 gt(s(x), s(y)) -> gt(x, y) 315.82/291.55 315.82/291.55 Types: 315.82/291.55 app :: nil:cons -> nil:cons -> nil:cons 315.82/291.55 nil :: nil:cons 315.82/291.55 cons :: s:zero:true:false -> nil:cons -> nil:cons 315.82/291.55 sum :: nil:cons -> nil:cons 315.82/291.55 plus :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 s :: s:zero:true:false -> s:zero:true:false 315.82/291.55 if :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 gt :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 not :: s:zero:true:false -> s:zero:true:false 315.82/291.55 id :: s:zero:true:false -> s:zero:true:false 315.82/291.55 zero :: s:zero:true:false 315.82/291.55 true :: s:zero:true:false 315.82/291.55 false :: s:zero:true:false 315.82/291.55 hole_nil:cons1_0 :: nil:cons 315.82/291.55 hole_s:zero:true:false2_0 :: s:zero:true:false 315.82/291.55 gen_nil:cons3_0 :: Nat -> nil:cons 315.82/291.55 gen_s:zero:true:false4_0 :: Nat -> s:zero:true:false 315.82/291.55 315.82/291.55 315.82/291.55 Generator Equations: 315.82/291.55 gen_nil:cons3_0(0) <=> nil 315.82/291.55 gen_nil:cons3_0(+(x, 1)) <=> cons(zero, gen_nil:cons3_0(x)) 315.82/291.55 gen_s:zero:true:false4_0(0) <=> zero 315.82/291.55 gen_s:zero:true:false4_0(+(x, 1)) <=> s(gen_s:zero:true:false4_0(x)) 315.82/291.55 315.82/291.55 315.82/291.55 The following defined symbols remain to be analysed: 315.82/291.55 app, sum, plus, gt 315.82/291.55 315.82/291.55 They will be analysed ascendingly in the following order: 315.82/291.55 app < sum 315.82/291.55 plus < sum 315.82/291.55 gt < plus 315.82/291.55 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (10) LowerBoundPropagationProof (FINISHED) 315.82/291.55 Propagated lower bound. 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (11) 315.82/291.55 BOUNDS(n^1, INF) 315.82/291.55 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (12) 315.82/291.55 Obligation: 315.82/291.55 TRS: 315.82/291.55 Rules: 315.82/291.55 app(nil, k) -> k 315.82/291.55 app(l, nil) -> l 315.82/291.55 app(cons(x, l), k) -> cons(x, app(l, k)) 315.82/291.55 sum(cons(x, nil)) -> cons(x, nil) 315.82/291.55 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 315.82/291.55 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 315.82/291.55 plus(s(x), s(y)) -> s(s(plus(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 315.82/291.55 plus(s(x), x) -> plus(if(gt(x, x), id(x), id(x)), s(x)) 315.82/291.55 plus(zero, y) -> y 315.82/291.55 plus(id(x), s(y)) -> s(plus(x, if(gt(s(y), y), y, s(y)))) 315.82/291.55 id(x) -> x 315.82/291.55 if(true, x, y) -> x 315.82/291.55 if(false, x, y) -> y 315.82/291.55 not(x) -> if(x, false, true) 315.82/291.55 gt(s(x), zero) -> true 315.82/291.55 gt(zero, y) -> false 315.82/291.55 gt(s(x), s(y)) -> gt(x, y) 315.82/291.55 315.82/291.55 Types: 315.82/291.55 app :: nil:cons -> nil:cons -> nil:cons 315.82/291.55 nil :: nil:cons 315.82/291.55 cons :: s:zero:true:false -> nil:cons -> nil:cons 315.82/291.55 sum :: nil:cons -> nil:cons 315.82/291.55 plus :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 s :: s:zero:true:false -> s:zero:true:false 315.82/291.55 if :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 gt :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 not :: s:zero:true:false -> s:zero:true:false 315.82/291.55 id :: s:zero:true:false -> s:zero:true:false 315.82/291.55 zero :: s:zero:true:false 315.82/291.55 true :: s:zero:true:false 315.82/291.55 false :: s:zero:true:false 315.82/291.55 hole_nil:cons1_0 :: nil:cons 315.82/291.55 hole_s:zero:true:false2_0 :: s:zero:true:false 315.82/291.55 gen_nil:cons3_0 :: Nat -> nil:cons 315.82/291.55 gen_s:zero:true:false4_0 :: Nat -> s:zero:true:false 315.82/291.55 315.82/291.55 315.82/291.55 Lemmas: 315.82/291.55 app(gen_nil:cons3_0(n6_0), gen_nil:cons3_0(b)) -> gen_nil:cons3_0(+(n6_0, b)), rt in Omega(1 + n6_0) 315.82/291.55 315.82/291.55 315.82/291.55 Generator Equations: 315.82/291.55 gen_nil:cons3_0(0) <=> nil 315.82/291.55 gen_nil:cons3_0(+(x, 1)) <=> cons(zero, gen_nil:cons3_0(x)) 315.82/291.55 gen_s:zero:true:false4_0(0) <=> zero 315.82/291.55 gen_s:zero:true:false4_0(+(x, 1)) <=> s(gen_s:zero:true:false4_0(x)) 315.82/291.55 315.82/291.55 315.82/291.55 The following defined symbols remain to be analysed: 315.82/291.55 gt, sum, plus 315.82/291.55 315.82/291.55 They will be analysed ascendingly in the following order: 315.82/291.55 plus < sum 315.82/291.55 gt < plus 315.82/291.55 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (13) RewriteLemmaProof (LOWER BOUND(ID)) 315.82/291.55 Proved the following rewrite lemma: 315.82/291.55 gt(gen_s:zero:true:false4_0(+(1, n798_0)), gen_s:zero:true:false4_0(n798_0)) -> true, rt in Omega(1 + n798_0) 315.82/291.55 315.82/291.55 Induction Base: 315.82/291.55 gt(gen_s:zero:true:false4_0(+(1, 0)), gen_s:zero:true:false4_0(0)) ->_R^Omega(1) 315.82/291.55 true 315.82/291.55 315.82/291.55 Induction Step: 315.82/291.55 gt(gen_s:zero:true:false4_0(+(1, +(n798_0, 1))), gen_s:zero:true:false4_0(+(n798_0, 1))) ->_R^Omega(1) 315.82/291.55 gt(gen_s:zero:true:false4_0(+(1, n798_0)), gen_s:zero:true:false4_0(n798_0)) ->_IH 315.82/291.55 true 315.82/291.55 315.82/291.55 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (14) 315.82/291.55 Obligation: 315.82/291.55 TRS: 315.82/291.55 Rules: 315.82/291.55 app(nil, k) -> k 315.82/291.55 app(l, nil) -> l 315.82/291.55 app(cons(x, l), k) -> cons(x, app(l, k)) 315.82/291.55 sum(cons(x, nil)) -> cons(x, nil) 315.82/291.55 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 315.82/291.55 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 315.82/291.55 plus(s(x), s(y)) -> s(s(plus(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 315.82/291.55 plus(s(x), x) -> plus(if(gt(x, x), id(x), id(x)), s(x)) 315.82/291.55 plus(zero, y) -> y 315.82/291.55 plus(id(x), s(y)) -> s(plus(x, if(gt(s(y), y), y, s(y)))) 315.82/291.55 id(x) -> x 315.82/291.55 if(true, x, y) -> x 315.82/291.55 if(false, x, y) -> y 315.82/291.55 not(x) -> if(x, false, true) 315.82/291.55 gt(s(x), zero) -> true 315.82/291.55 gt(zero, y) -> false 315.82/291.55 gt(s(x), s(y)) -> gt(x, y) 315.82/291.55 315.82/291.55 Types: 315.82/291.55 app :: nil:cons -> nil:cons -> nil:cons 315.82/291.55 nil :: nil:cons 315.82/291.55 cons :: s:zero:true:false -> nil:cons -> nil:cons 315.82/291.55 sum :: nil:cons -> nil:cons 315.82/291.55 plus :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 s :: s:zero:true:false -> s:zero:true:false 315.82/291.55 if :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 gt :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 not :: s:zero:true:false -> s:zero:true:false 315.82/291.55 id :: s:zero:true:false -> s:zero:true:false 315.82/291.55 zero :: s:zero:true:false 315.82/291.55 true :: s:zero:true:false 315.82/291.55 false :: s:zero:true:false 315.82/291.55 hole_nil:cons1_0 :: nil:cons 315.82/291.55 hole_s:zero:true:false2_0 :: s:zero:true:false 315.82/291.55 gen_nil:cons3_0 :: Nat -> nil:cons 315.82/291.55 gen_s:zero:true:false4_0 :: Nat -> s:zero:true:false 315.82/291.55 315.82/291.55 315.82/291.55 Lemmas: 315.82/291.55 app(gen_nil:cons3_0(n6_0), gen_nil:cons3_0(b)) -> gen_nil:cons3_0(+(n6_0, b)), rt in Omega(1 + n6_0) 315.82/291.55 gt(gen_s:zero:true:false4_0(+(1, n798_0)), gen_s:zero:true:false4_0(n798_0)) -> true, rt in Omega(1 + n798_0) 315.82/291.55 315.82/291.55 315.82/291.55 Generator Equations: 315.82/291.55 gen_nil:cons3_0(0) <=> nil 315.82/291.55 gen_nil:cons3_0(+(x, 1)) <=> cons(zero, gen_nil:cons3_0(x)) 315.82/291.55 gen_s:zero:true:false4_0(0) <=> zero 315.82/291.55 gen_s:zero:true:false4_0(+(x, 1)) <=> s(gen_s:zero:true:false4_0(x)) 315.82/291.55 315.82/291.55 315.82/291.55 The following defined symbols remain to be analysed: 315.82/291.55 plus, sum 315.82/291.55 315.82/291.55 They will be analysed ascendingly in the following order: 315.82/291.55 plus < sum 315.82/291.55 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (15) RewriteLemmaProof (LOWER BOUND(ID)) 315.82/291.55 Proved the following rewrite lemma: 315.82/291.55 plus(gen_s:zero:true:false4_0(+(2, n1097_0)), gen_s:zero:true:false4_0(+(1, n1097_0))) -> *5_0, rt in Omega(n1097_0 + n1097_0^2) 315.82/291.55 315.82/291.55 Induction Base: 315.82/291.55 plus(gen_s:zero:true:false4_0(+(2, 0)), gen_s:zero:true:false4_0(+(1, 0))) 315.82/291.55 315.82/291.55 Induction Step: 315.82/291.55 plus(gen_s:zero:true:false4_0(+(2, +(n1097_0, 1))), gen_s:zero:true:false4_0(+(1, +(n1097_0, 1)))) ->_R^Omega(1) 315.82/291.55 s(s(plus(if(gt(gen_s:zero:true:false4_0(+(2, n1097_0)), gen_s:zero:true:false4_0(+(1, n1097_0))), gen_s:zero:true:false4_0(+(2, n1097_0)), gen_s:zero:true:false4_0(+(1, n1097_0))), if(not(gt(gen_s:zero:true:false4_0(+(2, n1097_0)), gen_s:zero:true:false4_0(+(1, n1097_0)))), id(gen_s:zero:true:false4_0(+(2, n1097_0))), id(gen_s:zero:true:false4_0(+(1, n1097_0))))))) ->_L^Omega(2 + n1097_0) 315.82/291.55 s(s(plus(if(true, gen_s:zero:true:false4_0(+(2, n1097_0)), gen_s:zero:true:false4_0(+(1, n1097_0))), if(not(gt(gen_s:zero:true:false4_0(+(2, n1097_0)), gen_s:zero:true:false4_0(+(1, n1097_0)))), id(gen_s:zero:true:false4_0(+(2, n1097_0))), id(gen_s:zero:true:false4_0(+(1, n1097_0))))))) ->_R^Omega(1) 315.82/291.55 s(s(plus(gen_s:zero:true:false4_0(+(2, n1097_0)), if(not(gt(gen_s:zero:true:false4_0(+(2, n1097_0)), gen_s:zero:true:false4_0(+(1, n1097_0)))), id(gen_s:zero:true:false4_0(+(2, n1097_0))), id(gen_s:zero:true:false4_0(+(1, n1097_0))))))) ->_L^Omega(2 + n1097_0) 315.82/291.55 s(s(plus(gen_s:zero:true:false4_0(+(2, n1097_0)), if(not(true), id(gen_s:zero:true:false4_0(+(2, n1097_0))), id(gen_s:zero:true:false4_0(+(1, n1097_0))))))) ->_R^Omega(1) 315.82/291.55 s(s(plus(gen_s:zero:true:false4_0(+(2, n1097_0)), if(if(true, false, true), id(gen_s:zero:true:false4_0(+(2, n1097_0))), id(gen_s:zero:true:false4_0(+(1, n1097_0))))))) ->_R^Omega(1) 315.82/291.55 s(s(plus(gen_s:zero:true:false4_0(+(2, n1097_0)), if(false, id(gen_s:zero:true:false4_0(+(2, n1097_0))), id(gen_s:zero:true:false4_0(+(1, n1097_0))))))) ->_R^Omega(1) 315.82/291.55 s(s(plus(gen_s:zero:true:false4_0(+(2, n1097_0)), if(false, gen_s:zero:true:false4_0(+(2, n1097_0)), id(gen_s:zero:true:false4_0(+(1, n1097_0))))))) ->_R^Omega(1) 315.82/291.55 s(s(plus(gen_s:zero:true:false4_0(+(2, n1097_0)), if(false, gen_s:zero:true:false4_0(+(2, n1097_0)), gen_s:zero:true:false4_0(+(1, n1097_0)))))) ->_R^Omega(1) 315.82/291.55 s(s(plus(gen_s:zero:true:false4_0(+(2, n1097_0)), gen_s:zero:true:false4_0(+(1, n1097_0))))) ->_IH 315.82/291.55 s(s(*5_0)) 315.82/291.55 315.82/291.55 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (16) 315.82/291.55 Complex Obligation (BEST) 315.82/291.55 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (17) 315.82/291.55 Obligation: 315.82/291.55 Proved the lower bound n^2 for the following obligation: 315.82/291.55 315.82/291.55 TRS: 315.82/291.55 Rules: 315.82/291.55 app(nil, k) -> k 315.82/291.55 app(l, nil) -> l 315.82/291.55 app(cons(x, l), k) -> cons(x, app(l, k)) 315.82/291.55 sum(cons(x, nil)) -> cons(x, nil) 315.82/291.55 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 315.82/291.55 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 315.82/291.55 plus(s(x), s(y)) -> s(s(plus(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 315.82/291.55 plus(s(x), x) -> plus(if(gt(x, x), id(x), id(x)), s(x)) 315.82/291.55 plus(zero, y) -> y 315.82/291.55 plus(id(x), s(y)) -> s(plus(x, if(gt(s(y), y), y, s(y)))) 315.82/291.55 id(x) -> x 315.82/291.55 if(true, x, y) -> x 315.82/291.55 if(false, x, y) -> y 315.82/291.55 not(x) -> if(x, false, true) 315.82/291.55 gt(s(x), zero) -> true 315.82/291.55 gt(zero, y) -> false 315.82/291.55 gt(s(x), s(y)) -> gt(x, y) 315.82/291.55 315.82/291.55 Types: 315.82/291.55 app :: nil:cons -> nil:cons -> nil:cons 315.82/291.55 nil :: nil:cons 315.82/291.55 cons :: s:zero:true:false -> nil:cons -> nil:cons 315.82/291.55 sum :: nil:cons -> nil:cons 315.82/291.55 plus :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 s :: s:zero:true:false -> s:zero:true:false 315.82/291.55 if :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 gt :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 not :: s:zero:true:false -> s:zero:true:false 315.82/291.55 id :: s:zero:true:false -> s:zero:true:false 315.82/291.55 zero :: s:zero:true:false 315.82/291.55 true :: s:zero:true:false 315.82/291.55 false :: s:zero:true:false 315.82/291.55 hole_nil:cons1_0 :: nil:cons 315.82/291.55 hole_s:zero:true:false2_0 :: s:zero:true:false 315.82/291.55 gen_nil:cons3_0 :: Nat -> nil:cons 315.82/291.55 gen_s:zero:true:false4_0 :: Nat -> s:zero:true:false 315.82/291.55 315.82/291.55 315.82/291.55 Lemmas: 315.82/291.55 app(gen_nil:cons3_0(n6_0), gen_nil:cons3_0(b)) -> gen_nil:cons3_0(+(n6_0, b)), rt in Omega(1 + n6_0) 315.82/291.55 gt(gen_s:zero:true:false4_0(+(1, n798_0)), gen_s:zero:true:false4_0(n798_0)) -> true, rt in Omega(1 + n798_0) 315.82/291.55 315.82/291.55 315.82/291.55 Generator Equations: 315.82/291.55 gen_nil:cons3_0(0) <=> nil 315.82/291.55 gen_nil:cons3_0(+(x, 1)) <=> cons(zero, gen_nil:cons3_0(x)) 315.82/291.55 gen_s:zero:true:false4_0(0) <=> zero 315.82/291.55 gen_s:zero:true:false4_0(+(x, 1)) <=> s(gen_s:zero:true:false4_0(x)) 315.82/291.55 315.82/291.55 315.82/291.55 The following defined symbols remain to be analysed: 315.82/291.55 plus, sum 315.82/291.55 315.82/291.55 They will be analysed ascendingly in the following order: 315.82/291.55 plus < sum 315.82/291.55 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (18) LowerBoundPropagationProof (FINISHED) 315.82/291.55 Propagated lower bound. 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (19) 315.82/291.55 BOUNDS(n^2, INF) 315.82/291.55 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (20) 315.82/291.55 Obligation: 315.82/291.55 TRS: 315.82/291.55 Rules: 315.82/291.55 app(nil, k) -> k 315.82/291.55 app(l, nil) -> l 315.82/291.55 app(cons(x, l), k) -> cons(x, app(l, k)) 315.82/291.55 sum(cons(x, nil)) -> cons(x, nil) 315.82/291.55 sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 315.82/291.55 sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) 315.82/291.55 plus(s(x), s(y)) -> s(s(plus(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 315.82/291.55 plus(s(x), x) -> plus(if(gt(x, x), id(x), id(x)), s(x)) 315.82/291.55 plus(zero, y) -> y 315.82/291.55 plus(id(x), s(y)) -> s(plus(x, if(gt(s(y), y), y, s(y)))) 315.82/291.55 id(x) -> x 315.82/291.55 if(true, x, y) -> x 315.82/291.55 if(false, x, y) -> y 315.82/291.55 not(x) -> if(x, false, true) 315.82/291.55 gt(s(x), zero) -> true 315.82/291.55 gt(zero, y) -> false 315.82/291.55 gt(s(x), s(y)) -> gt(x, y) 315.82/291.55 315.82/291.55 Types: 315.82/291.55 app :: nil:cons -> nil:cons -> nil:cons 315.82/291.55 nil :: nil:cons 315.82/291.55 cons :: s:zero:true:false -> nil:cons -> nil:cons 315.82/291.55 sum :: nil:cons -> nil:cons 315.82/291.55 plus :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 s :: s:zero:true:false -> s:zero:true:false 315.82/291.55 if :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 gt :: s:zero:true:false -> s:zero:true:false -> s:zero:true:false 315.82/291.55 not :: s:zero:true:false -> s:zero:true:false 315.82/291.55 id :: s:zero:true:false -> s:zero:true:false 315.82/291.55 zero :: s:zero:true:false 315.82/291.55 true :: s:zero:true:false 315.82/291.55 false :: s:zero:true:false 315.82/291.55 hole_nil:cons1_0 :: nil:cons 315.82/291.55 hole_s:zero:true:false2_0 :: s:zero:true:false 315.82/291.55 gen_nil:cons3_0 :: Nat -> nil:cons 315.82/291.55 gen_s:zero:true:false4_0 :: Nat -> s:zero:true:false 315.82/291.55 315.82/291.55 315.82/291.55 Lemmas: 315.82/291.55 app(gen_nil:cons3_0(n6_0), gen_nil:cons3_0(b)) -> gen_nil:cons3_0(+(n6_0, b)), rt in Omega(1 + n6_0) 315.82/291.55 gt(gen_s:zero:true:false4_0(+(1, n798_0)), gen_s:zero:true:false4_0(n798_0)) -> true, rt in Omega(1 + n798_0) 315.82/291.55 plus(gen_s:zero:true:false4_0(+(2, n1097_0)), gen_s:zero:true:false4_0(+(1, n1097_0))) -> *5_0, rt in Omega(n1097_0 + n1097_0^2) 315.82/291.55 315.82/291.55 315.82/291.55 Generator Equations: 315.82/291.55 gen_nil:cons3_0(0) <=> nil 315.82/291.55 gen_nil:cons3_0(+(x, 1)) <=> cons(zero, gen_nil:cons3_0(x)) 315.82/291.55 gen_s:zero:true:false4_0(0) <=> zero 315.82/291.55 gen_s:zero:true:false4_0(+(x, 1)) <=> s(gen_s:zero:true:false4_0(x)) 315.82/291.55 315.82/291.55 315.82/291.55 The following defined symbols remain to be analysed: 315.82/291.55 sum 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (21) RewriteLemmaProof (LOWER BOUND(ID)) 315.82/291.55 Proved the following rewrite lemma: 315.82/291.55 sum(gen_nil:cons3_0(+(1, n7328_0))) -> gen_nil:cons3_0(1), rt in Omega(1 + n7328_0) 315.82/291.55 315.82/291.55 Induction Base: 315.82/291.55 sum(gen_nil:cons3_0(+(1, 0))) ->_R^Omega(1) 315.82/291.55 cons(zero, nil) 315.82/291.55 315.82/291.55 Induction Step: 315.82/291.55 sum(gen_nil:cons3_0(+(1, +(n7328_0, 1)))) ->_R^Omega(1) 315.82/291.55 sum(cons(plus(zero, zero), gen_nil:cons3_0(n7328_0))) ->_R^Omega(1) 315.82/291.55 sum(cons(zero, gen_nil:cons3_0(n7328_0))) ->_IH 315.82/291.55 gen_nil:cons3_0(1) 315.82/291.55 315.82/291.55 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 315.82/291.55 ---------------------------------------- 315.82/291.55 315.82/291.55 (22) 315.82/291.55 BOUNDS(1, INF) 315.92/291.59 EOF