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