316.52/291.50 WORST_CASE(Omega(n^2), ?) 316.52/291.51 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 316.52/291.51 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 316.52/291.51 316.52/291.51 316.52/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 316.52/291.51 316.52/291.51 (0) CpxTRS 316.52/291.51 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 316.52/291.51 (2) CpxTRS 316.52/291.51 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 316.52/291.51 (4) typed CpxTrs 316.52/291.51 (5) OrderProof [LOWER BOUND(ID), 0 ms] 316.52/291.51 (6) typed CpxTrs 316.52/291.51 (7) RewriteLemmaProof [LOWER BOUND(ID), 286 ms] 316.52/291.51 (8) BEST 316.52/291.51 (9) proven lower bound 316.52/291.51 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 316.52/291.51 (11) BOUNDS(n^1, INF) 316.52/291.51 (12) typed CpxTrs 316.52/291.51 (13) RewriteLemmaProof [LOWER BOUND(ID), 84 ms] 316.52/291.51 (14) typed CpxTrs 316.52/291.51 (15) RewriteLemmaProof [LOWER BOUND(ID), 12 ms] 316.52/291.51 (16) typed CpxTrs 316.52/291.51 (17) RewriteLemmaProof [LOWER BOUND(ID), 114 ms] 316.52/291.51 (18) BEST 316.52/291.51 (19) proven lower bound 316.52/291.51 (20) LowerBoundPropagationProof [FINISHED, 0 ms] 316.52/291.51 (21) BOUNDS(n^2, INF) 316.52/291.51 (22) typed CpxTrs 316.52/291.51 316.52/291.51 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (0) 316.52/291.51 Obligation: 316.52/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 316.52/291.51 316.52/291.51 316.52/291.51 The TRS R consists of the following rules: 316.52/291.51 316.52/291.51 log(x, s(s(y))) -> cond(le(x, s(s(y))), x, y) 316.52/291.51 cond(true, x, y) -> s(0) 316.52/291.51 cond(false, x, y) -> double(log(x, square(s(s(y))))) 316.52/291.51 le(0, v) -> true 316.52/291.51 le(s(u), 0) -> false 316.52/291.51 le(s(u), s(v)) -> le(u, v) 316.52/291.51 double(0) -> 0 316.52/291.51 double(s(x)) -> s(s(double(x))) 316.52/291.51 square(0) -> 0 316.52/291.51 square(s(x)) -> s(plus(square(x), double(x))) 316.52/291.51 plus(n, 0) -> n 316.52/291.51 plus(n, s(m)) -> s(plus(n, m)) 316.52/291.51 316.52/291.51 S is empty. 316.52/291.51 Rewrite Strategy: FULL 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 316.52/291.51 Renamed function symbols to avoid clashes with predefined symbol. 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (2) 316.52/291.51 Obligation: 316.52/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 316.52/291.51 316.52/291.51 316.52/291.51 The TRS R consists of the following rules: 316.52/291.51 316.52/291.51 log(x, s(s(y))) -> cond(le(x, s(s(y))), x, y) 316.52/291.51 cond(true, x, y) -> s(0') 316.52/291.51 cond(false, x, y) -> double(log(x, square(s(s(y))))) 316.52/291.51 le(0', v) -> true 316.52/291.51 le(s(u), 0') -> false 316.52/291.51 le(s(u), s(v)) -> le(u, v) 316.52/291.51 double(0') -> 0' 316.52/291.51 double(s(x)) -> s(s(double(x))) 316.52/291.51 square(0') -> 0' 316.52/291.51 square(s(x)) -> s(plus(square(x), double(x))) 316.52/291.51 plus(n, 0') -> n 316.52/291.51 plus(n, s(m)) -> s(plus(n, m)) 316.52/291.51 316.52/291.51 S is empty. 316.52/291.51 Rewrite Strategy: FULL 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 316.52/291.51 Infered types. 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (4) 316.52/291.51 Obligation: 316.52/291.51 TRS: 316.52/291.51 Rules: 316.52/291.51 log(x, s(s(y))) -> cond(le(x, s(s(y))), x, y) 316.52/291.51 cond(true, x, y) -> s(0') 316.52/291.51 cond(false, x, y) -> double(log(x, square(s(s(y))))) 316.52/291.51 le(0', v) -> true 316.52/291.51 le(s(u), 0') -> false 316.52/291.51 le(s(u), s(v)) -> le(u, v) 316.52/291.51 double(0') -> 0' 316.52/291.51 double(s(x)) -> s(s(double(x))) 316.52/291.51 square(0') -> 0' 316.52/291.51 square(s(x)) -> s(plus(square(x), double(x))) 316.52/291.51 plus(n, 0') -> n 316.52/291.51 plus(n, s(m)) -> s(plus(n, m)) 316.52/291.51 316.52/291.51 Types: 316.52/291.51 log :: s:0' -> s:0' -> s:0' 316.52/291.51 s :: s:0' -> s:0' 316.52/291.51 cond :: true:false -> s:0' -> s:0' -> s:0' 316.52/291.51 le :: s:0' -> s:0' -> true:false 316.52/291.51 true :: true:false 316.52/291.51 0' :: s:0' 316.52/291.51 false :: true:false 316.52/291.51 double :: s:0' -> s:0' 316.52/291.51 square :: s:0' -> s:0' 316.52/291.51 plus :: s:0' -> s:0' -> s:0' 316.52/291.51 hole_s:0'1_0 :: s:0' 316.52/291.51 hole_true:false2_0 :: true:false 316.52/291.51 gen_s:0'3_0 :: Nat -> s:0' 316.52/291.51 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (5) OrderProof (LOWER BOUND(ID)) 316.52/291.51 Heuristically decided to analyse the following defined symbols: 316.52/291.51 log, le, double, square, plus 316.52/291.51 316.52/291.51 They will be analysed ascendingly in the following order: 316.52/291.51 le < log 316.52/291.51 double < log 316.52/291.51 square < log 316.52/291.51 double < square 316.52/291.51 plus < square 316.52/291.51 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (6) 316.52/291.51 Obligation: 316.52/291.51 TRS: 316.52/291.51 Rules: 316.52/291.51 log(x, s(s(y))) -> cond(le(x, s(s(y))), x, y) 316.52/291.51 cond(true, x, y) -> s(0') 316.52/291.51 cond(false, x, y) -> double(log(x, square(s(s(y))))) 316.52/291.51 le(0', v) -> true 316.52/291.51 le(s(u), 0') -> false 316.52/291.51 le(s(u), s(v)) -> le(u, v) 316.52/291.51 double(0') -> 0' 316.52/291.51 double(s(x)) -> s(s(double(x))) 316.52/291.51 square(0') -> 0' 316.52/291.51 square(s(x)) -> s(plus(square(x), double(x))) 316.52/291.51 plus(n, 0') -> n 316.52/291.51 plus(n, s(m)) -> s(plus(n, m)) 316.52/291.51 316.52/291.51 Types: 316.52/291.51 log :: s:0' -> s:0' -> s:0' 316.52/291.51 s :: s:0' -> s:0' 316.52/291.51 cond :: true:false -> s:0' -> s:0' -> s:0' 316.52/291.51 le :: s:0' -> s:0' -> true:false 316.52/291.51 true :: true:false 316.52/291.51 0' :: s:0' 316.52/291.51 false :: true:false 316.52/291.51 double :: s:0' -> s:0' 316.52/291.51 square :: s:0' -> s:0' 316.52/291.51 plus :: s:0' -> s:0' -> s:0' 316.52/291.51 hole_s:0'1_0 :: s:0' 316.52/291.51 hole_true:false2_0 :: true:false 316.52/291.51 gen_s:0'3_0 :: Nat -> s:0' 316.52/291.51 316.52/291.51 316.52/291.51 Generator Equations: 316.52/291.51 gen_s:0'3_0(0) <=> 0' 316.52/291.51 gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x)) 316.52/291.51 316.52/291.51 316.52/291.51 The following defined symbols remain to be analysed: 316.52/291.51 le, log, double, square, plus 316.52/291.51 316.52/291.51 They will be analysed ascendingly in the following order: 316.52/291.51 le < log 316.52/291.51 double < log 316.52/291.51 square < log 316.52/291.51 double < square 316.52/291.51 plus < square 316.52/291.51 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (7) RewriteLemmaProof (LOWER BOUND(ID)) 316.52/291.51 Proved the following rewrite lemma: 316.52/291.51 le(gen_s:0'3_0(n5_0), gen_s:0'3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 316.52/291.51 316.52/291.51 Induction Base: 316.52/291.51 le(gen_s:0'3_0(0), gen_s:0'3_0(0)) ->_R^Omega(1) 316.52/291.51 true 316.52/291.51 316.52/291.51 Induction Step: 316.52/291.51 le(gen_s:0'3_0(+(n5_0, 1)), gen_s:0'3_0(+(n5_0, 1))) ->_R^Omega(1) 316.52/291.51 le(gen_s:0'3_0(n5_0), gen_s:0'3_0(n5_0)) ->_IH 316.52/291.51 true 316.52/291.51 316.52/291.51 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (8) 316.52/291.51 Complex Obligation (BEST) 316.52/291.51 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (9) 316.52/291.51 Obligation: 316.52/291.51 Proved the lower bound n^1 for the following obligation: 316.52/291.51 316.52/291.51 TRS: 316.52/291.51 Rules: 316.52/291.51 log(x, s(s(y))) -> cond(le(x, s(s(y))), x, y) 316.52/291.51 cond(true, x, y) -> s(0') 316.52/291.51 cond(false, x, y) -> double(log(x, square(s(s(y))))) 316.52/291.51 le(0', v) -> true 316.52/291.51 le(s(u), 0') -> false 316.52/291.51 le(s(u), s(v)) -> le(u, v) 316.52/291.51 double(0') -> 0' 316.52/291.51 double(s(x)) -> s(s(double(x))) 316.52/291.51 square(0') -> 0' 316.52/291.51 square(s(x)) -> s(plus(square(x), double(x))) 316.52/291.51 plus(n, 0') -> n 316.52/291.51 plus(n, s(m)) -> s(plus(n, m)) 316.52/291.51 316.52/291.51 Types: 316.52/291.51 log :: s:0' -> s:0' -> s:0' 316.52/291.51 s :: s:0' -> s:0' 316.52/291.51 cond :: true:false -> s:0' -> s:0' -> s:0' 316.52/291.51 le :: s:0' -> s:0' -> true:false 316.52/291.51 true :: true:false 316.52/291.51 0' :: s:0' 316.52/291.51 false :: true:false 316.52/291.51 double :: s:0' -> s:0' 316.52/291.51 square :: s:0' -> s:0' 316.52/291.51 plus :: s:0' -> s:0' -> s:0' 316.52/291.51 hole_s:0'1_0 :: s:0' 316.52/291.51 hole_true:false2_0 :: true:false 316.52/291.51 gen_s:0'3_0 :: Nat -> s:0' 316.52/291.51 316.52/291.51 316.52/291.51 Generator Equations: 316.52/291.51 gen_s:0'3_0(0) <=> 0' 316.52/291.51 gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x)) 316.52/291.51 316.52/291.51 316.52/291.51 The following defined symbols remain to be analysed: 316.52/291.51 le, log, double, square, plus 316.52/291.51 316.52/291.51 They will be analysed ascendingly in the following order: 316.52/291.51 le < log 316.52/291.51 double < log 316.52/291.51 square < log 316.52/291.51 double < square 316.52/291.51 plus < square 316.52/291.51 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (10) LowerBoundPropagationProof (FINISHED) 316.52/291.51 Propagated lower bound. 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (11) 316.52/291.51 BOUNDS(n^1, INF) 316.52/291.51 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (12) 316.52/291.51 Obligation: 316.52/291.51 TRS: 316.52/291.51 Rules: 316.52/291.51 log(x, s(s(y))) -> cond(le(x, s(s(y))), x, y) 316.52/291.51 cond(true, x, y) -> s(0') 316.52/291.51 cond(false, x, y) -> double(log(x, square(s(s(y))))) 316.52/291.51 le(0', v) -> true 316.52/291.51 le(s(u), 0') -> false 316.52/291.51 le(s(u), s(v)) -> le(u, v) 316.52/291.51 double(0') -> 0' 316.52/291.51 double(s(x)) -> s(s(double(x))) 316.52/291.51 square(0') -> 0' 316.52/291.51 square(s(x)) -> s(plus(square(x), double(x))) 316.52/291.51 plus(n, 0') -> n 316.52/291.51 plus(n, s(m)) -> s(plus(n, m)) 316.52/291.51 316.52/291.51 Types: 316.52/291.51 log :: s:0' -> s:0' -> s:0' 316.52/291.51 s :: s:0' -> s:0' 316.52/291.51 cond :: true:false -> s:0' -> s:0' -> s:0' 316.52/291.51 le :: s:0' -> s:0' -> true:false 316.52/291.51 true :: true:false 316.52/291.51 0' :: s:0' 316.52/291.51 false :: true:false 316.52/291.51 double :: s:0' -> s:0' 316.52/291.51 square :: s:0' -> s:0' 316.52/291.51 plus :: s:0' -> s:0' -> s:0' 316.52/291.51 hole_s:0'1_0 :: s:0' 316.52/291.51 hole_true:false2_0 :: true:false 316.52/291.51 gen_s:0'3_0 :: Nat -> s:0' 316.52/291.51 316.52/291.51 316.52/291.51 Lemmas: 316.52/291.51 le(gen_s:0'3_0(n5_0), gen_s:0'3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 316.52/291.51 316.52/291.51 316.52/291.51 Generator Equations: 316.52/291.51 gen_s:0'3_0(0) <=> 0' 316.52/291.51 gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x)) 316.52/291.51 316.52/291.51 316.52/291.51 The following defined symbols remain to be analysed: 316.52/291.51 double, log, square, plus 316.52/291.51 316.52/291.51 They will be analysed ascendingly in the following order: 316.52/291.51 double < log 316.52/291.51 square < log 316.52/291.51 double < square 316.52/291.51 plus < square 316.52/291.51 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (13) RewriteLemmaProof (LOWER BOUND(ID)) 316.52/291.51 Proved the following rewrite lemma: 316.52/291.51 double(gen_s:0'3_0(n264_0)) -> gen_s:0'3_0(*(2, n264_0)), rt in Omega(1 + n264_0) 316.52/291.51 316.52/291.51 Induction Base: 316.52/291.51 double(gen_s:0'3_0(0)) ->_R^Omega(1) 316.52/291.51 0' 316.52/291.51 316.52/291.51 Induction Step: 316.52/291.51 double(gen_s:0'3_0(+(n264_0, 1))) ->_R^Omega(1) 316.52/291.51 s(s(double(gen_s:0'3_0(n264_0)))) ->_IH 316.52/291.51 s(s(gen_s:0'3_0(*(2, c265_0)))) 316.52/291.51 316.52/291.51 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (14) 316.52/291.51 Obligation: 316.52/291.51 TRS: 316.52/291.51 Rules: 316.52/291.51 log(x, s(s(y))) -> cond(le(x, s(s(y))), x, y) 316.52/291.51 cond(true, x, y) -> s(0') 316.52/291.51 cond(false, x, y) -> double(log(x, square(s(s(y))))) 316.52/291.51 le(0', v) -> true 316.52/291.51 le(s(u), 0') -> false 316.52/291.51 le(s(u), s(v)) -> le(u, v) 316.52/291.51 double(0') -> 0' 316.52/291.51 double(s(x)) -> s(s(double(x))) 316.52/291.51 square(0') -> 0' 316.52/291.51 square(s(x)) -> s(plus(square(x), double(x))) 316.52/291.51 plus(n, 0') -> n 316.52/291.51 plus(n, s(m)) -> s(plus(n, m)) 316.52/291.51 316.52/291.51 Types: 316.52/291.51 log :: s:0' -> s:0' -> s:0' 316.52/291.51 s :: s:0' -> s:0' 316.52/291.51 cond :: true:false -> s:0' -> s:0' -> s:0' 316.52/291.51 le :: s:0' -> s:0' -> true:false 316.52/291.51 true :: true:false 316.52/291.51 0' :: s:0' 316.52/291.51 false :: true:false 316.52/291.51 double :: s:0' -> s:0' 316.52/291.51 square :: s:0' -> s:0' 316.52/291.51 plus :: s:0' -> s:0' -> s:0' 316.52/291.51 hole_s:0'1_0 :: s:0' 316.52/291.51 hole_true:false2_0 :: true:false 316.52/291.51 gen_s:0'3_0 :: Nat -> s:0' 316.52/291.51 316.52/291.51 316.52/291.51 Lemmas: 316.52/291.51 le(gen_s:0'3_0(n5_0), gen_s:0'3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 316.52/291.51 double(gen_s:0'3_0(n264_0)) -> gen_s:0'3_0(*(2, n264_0)), rt in Omega(1 + n264_0) 316.52/291.51 316.52/291.51 316.52/291.51 Generator Equations: 316.52/291.51 gen_s:0'3_0(0) <=> 0' 316.52/291.51 gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x)) 316.52/291.51 316.52/291.51 316.52/291.51 The following defined symbols remain to be analysed: 316.52/291.51 plus, log, square 316.52/291.51 316.52/291.51 They will be analysed ascendingly in the following order: 316.52/291.51 square < log 316.52/291.51 plus < square 316.52/291.51 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (15) RewriteLemmaProof (LOWER BOUND(ID)) 316.52/291.51 Proved the following rewrite lemma: 316.52/291.51 plus(gen_s:0'3_0(a), gen_s:0'3_0(n520_0)) -> gen_s:0'3_0(+(n520_0, a)), rt in Omega(1 + n520_0) 316.52/291.51 316.52/291.51 Induction Base: 316.52/291.51 plus(gen_s:0'3_0(a), gen_s:0'3_0(0)) ->_R^Omega(1) 316.52/291.51 gen_s:0'3_0(a) 316.52/291.51 316.52/291.51 Induction Step: 316.52/291.51 plus(gen_s:0'3_0(a), gen_s:0'3_0(+(n520_0, 1))) ->_R^Omega(1) 316.52/291.51 s(plus(gen_s:0'3_0(a), gen_s:0'3_0(n520_0))) ->_IH 316.52/291.51 s(gen_s:0'3_0(+(a, c521_0))) 316.52/291.51 316.52/291.51 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (16) 316.52/291.51 Obligation: 316.52/291.51 TRS: 316.52/291.51 Rules: 316.52/291.51 log(x, s(s(y))) -> cond(le(x, s(s(y))), x, y) 316.52/291.51 cond(true, x, y) -> s(0') 316.52/291.51 cond(false, x, y) -> double(log(x, square(s(s(y))))) 316.52/291.51 le(0', v) -> true 316.52/291.51 le(s(u), 0') -> false 316.52/291.51 le(s(u), s(v)) -> le(u, v) 316.52/291.51 double(0') -> 0' 316.52/291.51 double(s(x)) -> s(s(double(x))) 316.52/291.51 square(0') -> 0' 316.52/291.51 square(s(x)) -> s(plus(square(x), double(x))) 316.52/291.51 plus(n, 0') -> n 316.52/291.51 plus(n, s(m)) -> s(plus(n, m)) 316.52/291.51 316.52/291.51 Types: 316.52/291.51 log :: s:0' -> s:0' -> s:0' 316.52/291.51 s :: s:0' -> s:0' 316.52/291.51 cond :: true:false -> s:0' -> s:0' -> s:0' 316.52/291.51 le :: s:0' -> s:0' -> true:false 316.52/291.51 true :: true:false 316.52/291.51 0' :: s:0' 316.52/291.51 false :: true:false 316.52/291.51 double :: s:0' -> s:0' 316.52/291.51 square :: s:0' -> s:0' 316.52/291.51 plus :: s:0' -> s:0' -> s:0' 316.52/291.51 hole_s:0'1_0 :: s:0' 316.52/291.51 hole_true:false2_0 :: true:false 316.52/291.51 gen_s:0'3_0 :: Nat -> s:0' 316.52/291.51 316.52/291.51 316.52/291.51 Lemmas: 316.52/291.51 le(gen_s:0'3_0(n5_0), gen_s:0'3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 316.52/291.51 double(gen_s:0'3_0(n264_0)) -> gen_s:0'3_0(*(2, n264_0)), rt in Omega(1 + n264_0) 316.52/291.51 plus(gen_s:0'3_0(a), gen_s:0'3_0(n520_0)) -> gen_s:0'3_0(+(n520_0, a)), rt in Omega(1 + n520_0) 316.52/291.51 316.52/291.51 316.52/291.51 Generator Equations: 316.52/291.51 gen_s:0'3_0(0) <=> 0' 316.52/291.51 gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x)) 316.52/291.51 316.52/291.51 316.52/291.51 The following defined symbols remain to be analysed: 316.52/291.51 square, log 316.52/291.51 316.52/291.51 They will be analysed ascendingly in the following order: 316.52/291.51 square < log 316.52/291.51 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (17) RewriteLemmaProof (LOWER BOUND(ID)) 316.52/291.51 Proved the following rewrite lemma: 316.52/291.51 square(gen_s:0'3_0(n1099_0)) -> gen_s:0'3_0(*(n1099_0, n1099_0)), rt in Omega(1 + n1099_0 + n1099_0^2) 316.52/291.51 316.52/291.51 Induction Base: 316.52/291.51 square(gen_s:0'3_0(0)) ->_R^Omega(1) 316.52/291.51 0' 316.52/291.51 316.52/291.51 Induction Step: 316.52/291.51 square(gen_s:0'3_0(+(n1099_0, 1))) ->_R^Omega(1) 316.52/291.51 s(plus(square(gen_s:0'3_0(n1099_0)), double(gen_s:0'3_0(n1099_0)))) ->_IH 316.52/291.51 s(plus(gen_s:0'3_0(*(c1100_0, c1100_0)), double(gen_s:0'3_0(n1099_0)))) ->_L^Omega(1 + n1099_0) 316.52/291.51 s(plus(gen_s:0'3_0(*(n1099_0, n1099_0)), gen_s:0'3_0(*(2, n1099_0)))) ->_L^Omega(1 + 2*n1099_0) 316.52/291.51 s(gen_s:0'3_0(+(*(2, n1099_0), *(n1099_0, n1099_0)))) 316.52/291.51 316.52/291.51 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (18) 316.52/291.51 Complex Obligation (BEST) 316.52/291.51 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (19) 316.52/291.51 Obligation: 316.52/291.51 Proved the lower bound n^2 for the following obligation: 316.52/291.51 316.52/291.51 TRS: 316.52/291.51 Rules: 316.52/291.51 log(x, s(s(y))) -> cond(le(x, s(s(y))), x, y) 316.52/291.51 cond(true, x, y) -> s(0') 316.52/291.51 cond(false, x, y) -> double(log(x, square(s(s(y))))) 316.52/291.51 le(0', v) -> true 316.52/291.51 le(s(u), 0') -> false 316.52/291.51 le(s(u), s(v)) -> le(u, v) 316.52/291.51 double(0') -> 0' 316.52/291.51 double(s(x)) -> s(s(double(x))) 316.52/291.51 square(0') -> 0' 316.52/291.51 square(s(x)) -> s(plus(square(x), double(x))) 316.52/291.51 plus(n, 0') -> n 316.52/291.51 plus(n, s(m)) -> s(plus(n, m)) 316.52/291.51 316.52/291.51 Types: 316.52/291.51 log :: s:0' -> s:0' -> s:0' 316.52/291.51 s :: s:0' -> s:0' 316.52/291.51 cond :: true:false -> s:0' -> s:0' -> s:0' 316.52/291.51 le :: s:0' -> s:0' -> true:false 316.52/291.51 true :: true:false 316.52/291.51 0' :: s:0' 316.52/291.51 false :: true:false 316.52/291.51 double :: s:0' -> s:0' 316.52/291.51 square :: s:0' -> s:0' 316.52/291.51 plus :: s:0' -> s:0' -> s:0' 316.52/291.51 hole_s:0'1_0 :: s:0' 316.52/291.51 hole_true:false2_0 :: true:false 316.52/291.51 gen_s:0'3_0 :: Nat -> s:0' 316.52/291.51 316.52/291.51 316.52/291.51 Lemmas: 316.52/291.51 le(gen_s:0'3_0(n5_0), gen_s:0'3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 316.52/291.51 double(gen_s:0'3_0(n264_0)) -> gen_s:0'3_0(*(2, n264_0)), rt in Omega(1 + n264_0) 316.52/291.51 plus(gen_s:0'3_0(a), gen_s:0'3_0(n520_0)) -> gen_s:0'3_0(+(n520_0, a)), rt in Omega(1 + n520_0) 316.52/291.51 316.52/291.51 316.52/291.51 Generator Equations: 316.52/291.51 gen_s:0'3_0(0) <=> 0' 316.52/291.51 gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x)) 316.52/291.51 316.52/291.51 316.52/291.51 The following defined symbols remain to be analysed: 316.52/291.51 square, log 316.52/291.51 316.52/291.51 They will be analysed ascendingly in the following order: 316.52/291.51 square < log 316.52/291.51 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (20) LowerBoundPropagationProof (FINISHED) 316.52/291.51 Propagated lower bound. 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (21) 316.52/291.51 BOUNDS(n^2, INF) 316.52/291.51 316.52/291.51 ---------------------------------------- 316.52/291.51 316.52/291.51 (22) 316.52/291.51 Obligation: 316.52/291.51 TRS: 316.52/291.51 Rules: 316.52/291.51 log(x, s(s(y))) -> cond(le(x, s(s(y))), x, y) 316.52/291.51 cond(true, x, y) -> s(0') 316.52/291.51 cond(false, x, y) -> double(log(x, square(s(s(y))))) 316.52/291.51 le(0', v) -> true 316.52/291.51 le(s(u), 0') -> false 316.52/291.51 le(s(u), s(v)) -> le(u, v) 316.52/291.51 double(0') -> 0' 316.52/291.51 double(s(x)) -> s(s(double(x))) 316.52/291.51 square(0') -> 0' 316.52/291.51 square(s(x)) -> s(plus(square(x), double(x))) 316.52/291.51 plus(n, 0') -> n 316.52/291.51 plus(n, s(m)) -> s(plus(n, m)) 316.52/291.51 316.52/291.51 Types: 316.52/291.51 log :: s:0' -> s:0' -> s:0' 316.52/291.51 s :: s:0' -> s:0' 316.52/291.51 cond :: true:false -> s:0' -> s:0' -> s:0' 316.52/291.51 le :: s:0' -> s:0' -> true:false 316.52/291.51 true :: true:false 316.52/291.51 0' :: s:0' 316.52/291.51 false :: true:false 316.52/291.51 double :: s:0' -> s:0' 316.52/291.51 square :: s:0' -> s:0' 316.52/291.51 plus :: s:0' -> s:0' -> s:0' 316.52/291.51 hole_s:0'1_0 :: s:0' 316.52/291.51 hole_true:false2_0 :: true:false 316.52/291.51 gen_s:0'3_0 :: Nat -> s:0' 316.52/291.51 316.52/291.51 316.52/291.51 Lemmas: 316.52/291.51 le(gen_s:0'3_0(n5_0), gen_s:0'3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 316.52/291.51 double(gen_s:0'3_0(n264_0)) -> gen_s:0'3_0(*(2, n264_0)), rt in Omega(1 + n264_0) 316.52/291.51 plus(gen_s:0'3_0(a), gen_s:0'3_0(n520_0)) -> gen_s:0'3_0(+(n520_0, a)), rt in Omega(1 + n520_0) 316.52/291.51 square(gen_s:0'3_0(n1099_0)) -> gen_s:0'3_0(*(n1099_0, n1099_0)), rt in Omega(1 + n1099_0 + n1099_0^2) 316.52/291.51 316.52/291.51 316.52/291.51 Generator Equations: 316.52/291.51 gen_s:0'3_0(0) <=> 0' 316.52/291.51 gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x)) 316.52/291.51 316.52/291.51 316.52/291.51 The following defined symbols remain to be analysed: 316.52/291.51 log 316.58/291.55 EOF