308.73/291.49 WORST_CASE(Omega(n^1), ?) 308.79/291.50 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 308.79/291.50 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 308.79/291.50 308.79/291.50 308.79/291.50 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 308.79/291.50 308.79/291.50 (0) CpxTRS 308.79/291.50 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 308.79/291.50 (2) CpxTRS 308.79/291.50 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 308.79/291.50 (4) typed CpxTrs 308.79/291.50 (5) OrderProof [LOWER BOUND(ID), 0 ms] 308.79/291.50 (6) typed CpxTrs 308.79/291.50 (7) RewriteLemmaProof [LOWER BOUND(ID), 296 ms] 308.79/291.50 (8) BEST 308.79/291.50 (9) proven lower bound 308.79/291.50 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 308.79/291.50 (11) BOUNDS(n^1, INF) 308.79/291.50 (12) typed CpxTrs 308.79/291.50 (13) RewriteLemmaProof [LOWER BOUND(ID), 86 ms] 308.79/291.50 (14) typed CpxTrs 308.79/291.50 (15) RewriteLemmaProof [LOWER BOUND(ID), 0 ms] 308.79/291.50 (16) typed CpxTrs 308.79/291.50 308.79/291.50 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (0) 308.79/291.50 Obligation: 308.79/291.50 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 308.79/291.50 308.79/291.50 308.79/291.50 The TRS R consists of the following rules: 308.79/291.50 308.79/291.50 minus(x, 0) -> x 308.79/291.50 minus(s(x), s(y)) -> minus(x, y) 308.79/291.50 quot(0, s(y)) -> 0 308.79/291.50 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 308.79/291.50 le(0, y) -> true 308.79/291.50 le(s(x), 0) -> false 308.79/291.50 le(s(x), s(y)) -> le(x, y) 308.79/291.50 inc(s(x)) -> s(inc(x)) 308.79/291.50 inc(0) -> s(0) 308.79/291.50 log(x) -> logIter(x, 0) 308.79/291.50 logIter(x, y) -> if(le(s(0), x), le(s(s(0)), x), quot(x, s(s(0))), inc(y)) 308.79/291.50 if(false, b, x, y) -> logZeroError 308.79/291.50 if(true, false, x, s(y)) -> y 308.79/291.50 if(true, true, x, y) -> logIter(x, y) 308.79/291.50 308.79/291.50 S is empty. 308.79/291.50 Rewrite Strategy: FULL 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 308.79/291.50 Renamed function symbols to avoid clashes with predefined symbol. 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (2) 308.79/291.50 Obligation: 308.79/291.50 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 308.79/291.50 308.79/291.50 308.79/291.50 The TRS R consists of the following rules: 308.79/291.50 308.79/291.50 minus(x, 0') -> x 308.79/291.50 minus(s(x), s(y)) -> minus(x, y) 308.79/291.50 quot(0', s(y)) -> 0' 308.79/291.50 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 308.79/291.50 le(0', y) -> true 308.79/291.50 le(s(x), 0') -> false 308.79/291.50 le(s(x), s(y)) -> le(x, y) 308.79/291.50 inc(s(x)) -> s(inc(x)) 308.79/291.50 inc(0') -> s(0') 308.79/291.50 log(x) -> logIter(x, 0') 308.79/291.50 logIter(x, y) -> if(le(s(0'), x), le(s(s(0')), x), quot(x, s(s(0'))), inc(y)) 308.79/291.50 if(false, b, x, y) -> logZeroError 308.79/291.50 if(true, false, x, s(y)) -> y 308.79/291.50 if(true, true, x, y) -> logIter(x, y) 308.79/291.50 308.79/291.50 S is empty. 308.79/291.50 Rewrite Strategy: FULL 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 308.79/291.50 Infered types. 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (4) 308.79/291.50 Obligation: 308.79/291.50 TRS: 308.79/291.50 Rules: 308.79/291.50 minus(x, 0') -> x 308.79/291.50 minus(s(x), s(y)) -> minus(x, y) 308.79/291.50 quot(0', s(y)) -> 0' 308.79/291.50 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 308.79/291.50 le(0', y) -> true 308.79/291.50 le(s(x), 0') -> false 308.79/291.50 le(s(x), s(y)) -> le(x, y) 308.79/291.50 inc(s(x)) -> s(inc(x)) 308.79/291.50 inc(0') -> s(0') 308.79/291.50 log(x) -> logIter(x, 0') 308.79/291.50 logIter(x, y) -> if(le(s(0'), x), le(s(s(0')), x), quot(x, s(s(0'))), inc(y)) 308.79/291.50 if(false, b, x, y) -> logZeroError 308.79/291.50 if(true, false, x, s(y)) -> y 308.79/291.50 if(true, true, x, y) -> logIter(x, y) 308.79/291.50 308.79/291.50 Types: 308.79/291.50 minus :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 0' :: 0':s:logZeroError 308.79/291.50 s :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 quot :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 le :: 0':s:logZeroError -> 0':s:logZeroError -> true:false 308.79/291.50 true :: true:false 308.79/291.50 false :: true:false 308.79/291.50 inc :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 log :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 logIter :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 if :: true:false -> true:false -> 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 logZeroError :: 0':s:logZeroError 308.79/291.50 hole_0':s:logZeroError1_0 :: 0':s:logZeroError 308.79/291.50 hole_true:false2_0 :: true:false 308.79/291.50 gen_0':s:logZeroError3_0 :: Nat -> 0':s:logZeroError 308.79/291.50 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (5) OrderProof (LOWER BOUND(ID)) 308.79/291.50 Heuristically decided to analyse the following defined symbols: 308.79/291.50 minus, quot, le, inc, logIter 308.79/291.50 308.79/291.50 They will be analysed ascendingly in the following order: 308.79/291.50 minus < quot 308.79/291.50 quot < logIter 308.79/291.50 le < logIter 308.79/291.50 inc < logIter 308.79/291.50 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (6) 308.79/291.50 Obligation: 308.79/291.50 TRS: 308.79/291.50 Rules: 308.79/291.50 minus(x, 0') -> x 308.79/291.50 minus(s(x), s(y)) -> minus(x, y) 308.79/291.50 quot(0', s(y)) -> 0' 308.79/291.50 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 308.79/291.50 le(0', y) -> true 308.79/291.50 le(s(x), 0') -> false 308.79/291.50 le(s(x), s(y)) -> le(x, y) 308.79/291.50 inc(s(x)) -> s(inc(x)) 308.79/291.50 inc(0') -> s(0') 308.79/291.50 log(x) -> logIter(x, 0') 308.79/291.50 logIter(x, y) -> if(le(s(0'), x), le(s(s(0')), x), quot(x, s(s(0'))), inc(y)) 308.79/291.50 if(false, b, x, y) -> logZeroError 308.79/291.50 if(true, false, x, s(y)) -> y 308.79/291.50 if(true, true, x, y) -> logIter(x, y) 308.79/291.50 308.79/291.50 Types: 308.79/291.50 minus :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 0' :: 0':s:logZeroError 308.79/291.50 s :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 quot :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 le :: 0':s:logZeroError -> 0':s:logZeroError -> true:false 308.79/291.50 true :: true:false 308.79/291.50 false :: true:false 308.79/291.50 inc :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 log :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 logIter :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 if :: true:false -> true:false -> 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 logZeroError :: 0':s:logZeroError 308.79/291.50 hole_0':s:logZeroError1_0 :: 0':s:logZeroError 308.79/291.50 hole_true:false2_0 :: true:false 308.79/291.50 gen_0':s:logZeroError3_0 :: Nat -> 0':s:logZeroError 308.79/291.50 308.79/291.50 308.79/291.50 Generator Equations: 308.79/291.50 gen_0':s:logZeroError3_0(0) <=> 0' 308.79/291.50 gen_0':s:logZeroError3_0(+(x, 1)) <=> s(gen_0':s:logZeroError3_0(x)) 308.79/291.50 308.79/291.50 308.79/291.50 The following defined symbols remain to be analysed: 308.79/291.50 minus, quot, le, inc, logIter 308.79/291.50 308.79/291.50 They will be analysed ascendingly in the following order: 308.79/291.50 minus < quot 308.79/291.50 quot < logIter 308.79/291.50 le < logIter 308.79/291.50 inc < logIter 308.79/291.50 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (7) RewriteLemmaProof (LOWER BOUND(ID)) 308.79/291.50 Proved the following rewrite lemma: 308.79/291.50 minus(gen_0':s:logZeroError3_0(n5_0), gen_0':s:logZeroError3_0(n5_0)) -> gen_0':s:logZeroError3_0(0), rt in Omega(1 + n5_0) 308.79/291.50 308.79/291.50 Induction Base: 308.79/291.50 minus(gen_0':s:logZeroError3_0(0), gen_0':s:logZeroError3_0(0)) ->_R^Omega(1) 308.79/291.50 gen_0':s:logZeroError3_0(0) 308.79/291.50 308.79/291.50 Induction Step: 308.79/291.50 minus(gen_0':s:logZeroError3_0(+(n5_0, 1)), gen_0':s:logZeroError3_0(+(n5_0, 1))) ->_R^Omega(1) 308.79/291.50 minus(gen_0':s:logZeroError3_0(n5_0), gen_0':s:logZeroError3_0(n5_0)) ->_IH 308.79/291.50 gen_0':s:logZeroError3_0(0) 308.79/291.50 308.79/291.50 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (8) 308.79/291.50 Complex Obligation (BEST) 308.79/291.50 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (9) 308.79/291.50 Obligation: 308.79/291.50 Proved the lower bound n^1 for the following obligation: 308.79/291.50 308.79/291.50 TRS: 308.79/291.50 Rules: 308.79/291.50 minus(x, 0') -> x 308.79/291.50 minus(s(x), s(y)) -> minus(x, y) 308.79/291.50 quot(0', s(y)) -> 0' 308.79/291.50 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 308.79/291.50 le(0', y) -> true 308.79/291.50 le(s(x), 0') -> false 308.79/291.50 le(s(x), s(y)) -> le(x, y) 308.79/291.50 inc(s(x)) -> s(inc(x)) 308.79/291.50 inc(0') -> s(0') 308.79/291.50 log(x) -> logIter(x, 0') 308.79/291.50 logIter(x, y) -> if(le(s(0'), x), le(s(s(0')), x), quot(x, s(s(0'))), inc(y)) 308.79/291.50 if(false, b, x, y) -> logZeroError 308.79/291.50 if(true, false, x, s(y)) -> y 308.79/291.50 if(true, true, x, y) -> logIter(x, y) 308.79/291.50 308.79/291.50 Types: 308.79/291.50 minus :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 0' :: 0':s:logZeroError 308.79/291.50 s :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 quot :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 le :: 0':s:logZeroError -> 0':s:logZeroError -> true:false 308.79/291.50 true :: true:false 308.79/291.50 false :: true:false 308.79/291.50 inc :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 log :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 logIter :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 if :: true:false -> true:false -> 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 logZeroError :: 0':s:logZeroError 308.79/291.50 hole_0':s:logZeroError1_0 :: 0':s:logZeroError 308.79/291.50 hole_true:false2_0 :: true:false 308.79/291.50 gen_0':s:logZeroError3_0 :: Nat -> 0':s:logZeroError 308.79/291.50 308.79/291.50 308.79/291.50 Generator Equations: 308.79/291.50 gen_0':s:logZeroError3_0(0) <=> 0' 308.79/291.50 gen_0':s:logZeroError3_0(+(x, 1)) <=> s(gen_0':s:logZeroError3_0(x)) 308.79/291.50 308.79/291.50 308.79/291.50 The following defined symbols remain to be analysed: 308.79/291.50 minus, quot, le, inc, logIter 308.79/291.50 308.79/291.50 They will be analysed ascendingly in the following order: 308.79/291.50 minus < quot 308.79/291.50 quot < logIter 308.79/291.50 le < logIter 308.79/291.50 inc < logIter 308.79/291.50 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (10) LowerBoundPropagationProof (FINISHED) 308.79/291.50 Propagated lower bound. 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (11) 308.79/291.50 BOUNDS(n^1, INF) 308.79/291.50 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (12) 308.79/291.50 Obligation: 308.79/291.50 TRS: 308.79/291.50 Rules: 308.79/291.50 minus(x, 0') -> x 308.79/291.50 minus(s(x), s(y)) -> minus(x, y) 308.79/291.50 quot(0', s(y)) -> 0' 308.79/291.50 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 308.79/291.50 le(0', y) -> true 308.79/291.50 le(s(x), 0') -> false 308.79/291.50 le(s(x), s(y)) -> le(x, y) 308.79/291.50 inc(s(x)) -> s(inc(x)) 308.79/291.50 inc(0') -> s(0') 308.79/291.50 log(x) -> logIter(x, 0') 308.79/291.50 logIter(x, y) -> if(le(s(0'), x), le(s(s(0')), x), quot(x, s(s(0'))), inc(y)) 308.79/291.50 if(false, b, x, y) -> logZeroError 308.79/291.50 if(true, false, x, s(y)) -> y 308.79/291.50 if(true, true, x, y) -> logIter(x, y) 308.79/291.50 308.79/291.50 Types: 308.79/291.50 minus :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 0' :: 0':s:logZeroError 308.79/291.50 s :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 quot :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 le :: 0':s:logZeroError -> 0':s:logZeroError -> true:false 308.79/291.50 true :: true:false 308.79/291.50 false :: true:false 308.79/291.50 inc :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 log :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 logIter :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 if :: true:false -> true:false -> 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 logZeroError :: 0':s:logZeroError 308.79/291.50 hole_0':s:logZeroError1_0 :: 0':s:logZeroError 308.79/291.50 hole_true:false2_0 :: true:false 308.79/291.50 gen_0':s:logZeroError3_0 :: Nat -> 0':s:logZeroError 308.79/291.50 308.79/291.50 308.79/291.50 Lemmas: 308.79/291.50 minus(gen_0':s:logZeroError3_0(n5_0), gen_0':s:logZeroError3_0(n5_0)) -> gen_0':s:logZeroError3_0(0), rt in Omega(1 + n5_0) 308.79/291.50 308.79/291.50 308.79/291.50 Generator Equations: 308.79/291.50 gen_0':s:logZeroError3_0(0) <=> 0' 308.79/291.50 gen_0':s:logZeroError3_0(+(x, 1)) <=> s(gen_0':s:logZeroError3_0(x)) 308.79/291.50 308.79/291.50 308.79/291.50 The following defined symbols remain to be analysed: 308.79/291.50 quot, le, inc, logIter 308.79/291.50 308.79/291.50 They will be analysed ascendingly in the following order: 308.79/291.50 quot < logIter 308.79/291.50 le < logIter 308.79/291.50 inc < logIter 308.79/291.50 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (13) RewriteLemmaProof (LOWER BOUND(ID)) 308.79/291.50 Proved the following rewrite lemma: 308.79/291.50 le(gen_0':s:logZeroError3_0(n353_0), gen_0':s:logZeroError3_0(n353_0)) -> true, rt in Omega(1 + n353_0) 308.79/291.50 308.79/291.50 Induction Base: 308.79/291.50 le(gen_0':s:logZeroError3_0(0), gen_0':s:logZeroError3_0(0)) ->_R^Omega(1) 308.79/291.50 true 308.79/291.50 308.79/291.50 Induction Step: 308.79/291.50 le(gen_0':s:logZeroError3_0(+(n353_0, 1)), gen_0':s:logZeroError3_0(+(n353_0, 1))) ->_R^Omega(1) 308.79/291.50 le(gen_0':s:logZeroError3_0(n353_0), gen_0':s:logZeroError3_0(n353_0)) ->_IH 308.79/291.50 true 308.79/291.50 308.79/291.50 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (14) 308.79/291.50 Obligation: 308.79/291.50 TRS: 308.79/291.50 Rules: 308.79/291.50 minus(x, 0') -> x 308.79/291.50 minus(s(x), s(y)) -> minus(x, y) 308.79/291.50 quot(0', s(y)) -> 0' 308.79/291.50 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 308.79/291.50 le(0', y) -> true 308.79/291.50 le(s(x), 0') -> false 308.79/291.50 le(s(x), s(y)) -> le(x, y) 308.79/291.50 inc(s(x)) -> s(inc(x)) 308.79/291.50 inc(0') -> s(0') 308.79/291.50 log(x) -> logIter(x, 0') 308.79/291.50 logIter(x, y) -> if(le(s(0'), x), le(s(s(0')), x), quot(x, s(s(0'))), inc(y)) 308.79/291.50 if(false, b, x, y) -> logZeroError 308.79/291.50 if(true, false, x, s(y)) -> y 308.79/291.50 if(true, true, x, y) -> logIter(x, y) 308.79/291.50 308.79/291.50 Types: 308.79/291.50 minus :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 0' :: 0':s:logZeroError 308.79/291.50 s :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 quot :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 le :: 0':s:logZeroError -> 0':s:logZeroError -> true:false 308.79/291.50 true :: true:false 308.79/291.50 false :: true:false 308.79/291.50 inc :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 log :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 logIter :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 if :: true:false -> true:false -> 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 logZeroError :: 0':s:logZeroError 308.79/291.50 hole_0':s:logZeroError1_0 :: 0':s:logZeroError 308.79/291.50 hole_true:false2_0 :: true:false 308.79/291.50 gen_0':s:logZeroError3_0 :: Nat -> 0':s:logZeroError 308.79/291.50 308.79/291.50 308.79/291.50 Lemmas: 308.79/291.50 minus(gen_0':s:logZeroError3_0(n5_0), gen_0':s:logZeroError3_0(n5_0)) -> gen_0':s:logZeroError3_0(0), rt in Omega(1 + n5_0) 308.79/291.50 le(gen_0':s:logZeroError3_0(n353_0), gen_0':s:logZeroError3_0(n353_0)) -> true, rt in Omega(1 + n353_0) 308.79/291.50 308.79/291.50 308.79/291.50 Generator Equations: 308.79/291.50 gen_0':s:logZeroError3_0(0) <=> 0' 308.79/291.50 gen_0':s:logZeroError3_0(+(x, 1)) <=> s(gen_0':s:logZeroError3_0(x)) 308.79/291.50 308.79/291.50 308.79/291.50 The following defined symbols remain to be analysed: 308.79/291.50 inc, logIter 308.79/291.50 308.79/291.50 They will be analysed ascendingly in the following order: 308.79/291.50 inc < logIter 308.79/291.50 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (15) RewriteLemmaProof (LOWER BOUND(ID)) 308.79/291.50 Proved the following rewrite lemma: 308.79/291.50 inc(gen_0':s:logZeroError3_0(n630_0)) -> gen_0':s:logZeroError3_0(+(1, n630_0)), rt in Omega(1 + n630_0) 308.79/291.50 308.79/291.50 Induction Base: 308.79/291.50 inc(gen_0':s:logZeroError3_0(0)) ->_R^Omega(1) 308.79/291.50 s(0') 308.79/291.50 308.79/291.50 Induction Step: 308.79/291.50 inc(gen_0':s:logZeroError3_0(+(n630_0, 1))) ->_R^Omega(1) 308.79/291.50 s(inc(gen_0':s:logZeroError3_0(n630_0))) ->_IH 308.79/291.50 s(gen_0':s:logZeroError3_0(+(1, c631_0))) 308.79/291.50 308.79/291.50 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 308.79/291.50 ---------------------------------------- 308.79/291.50 308.79/291.50 (16) 308.79/291.50 Obligation: 308.79/291.50 TRS: 308.79/291.50 Rules: 308.79/291.50 minus(x, 0') -> x 308.79/291.50 minus(s(x), s(y)) -> minus(x, y) 308.79/291.50 quot(0', s(y)) -> 0' 308.79/291.50 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) 308.79/291.50 le(0', y) -> true 308.79/291.50 le(s(x), 0') -> false 308.79/291.50 le(s(x), s(y)) -> le(x, y) 308.79/291.50 inc(s(x)) -> s(inc(x)) 308.79/291.50 inc(0') -> s(0') 308.79/291.50 log(x) -> logIter(x, 0') 308.79/291.50 logIter(x, y) -> if(le(s(0'), x), le(s(s(0')), x), quot(x, s(s(0'))), inc(y)) 308.79/291.50 if(false, b, x, y) -> logZeroError 308.79/291.50 if(true, false, x, s(y)) -> y 308.79/291.50 if(true, true, x, y) -> logIter(x, y) 308.79/291.50 308.79/291.50 Types: 308.79/291.50 minus :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 0' :: 0':s:logZeroError 308.79/291.50 s :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 quot :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 le :: 0':s:logZeroError -> 0':s:logZeroError -> true:false 308.79/291.50 true :: true:false 308.79/291.50 false :: true:false 308.79/291.50 inc :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 log :: 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 logIter :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 if :: true:false -> true:false -> 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 308.79/291.50 logZeroError :: 0':s:logZeroError 308.79/291.50 hole_0':s:logZeroError1_0 :: 0':s:logZeroError 308.79/291.50 hole_true:false2_0 :: true:false 308.79/291.50 gen_0':s:logZeroError3_0 :: Nat -> 0':s:logZeroError 308.79/291.50 308.79/291.50 308.79/291.50 Lemmas: 308.79/291.50 minus(gen_0':s:logZeroError3_0(n5_0), gen_0':s:logZeroError3_0(n5_0)) -> gen_0':s:logZeroError3_0(0), rt in Omega(1 + n5_0) 308.79/291.50 le(gen_0':s:logZeroError3_0(n353_0), gen_0':s:logZeroError3_0(n353_0)) -> true, rt in Omega(1 + n353_0) 308.79/291.50 inc(gen_0':s:logZeroError3_0(n630_0)) -> gen_0':s:logZeroError3_0(+(1, n630_0)), rt in Omega(1 + n630_0) 308.79/291.50 308.79/291.50 308.79/291.50 Generator Equations: 308.79/291.50 gen_0':s:logZeroError3_0(0) <=> 0' 308.79/291.50 gen_0':s:logZeroError3_0(+(x, 1)) <=> s(gen_0':s:logZeroError3_0(x)) 308.79/291.50 308.79/291.50 308.79/291.50 The following defined symbols remain to be analysed: 308.79/291.50 logIter 308.79/291.54 EOF