315.42/291.58 WORST_CASE(Omega(n^1), ?) 315.42/291.58 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 315.42/291.58 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 315.42/291.58 315.42/291.58 315.42/291.58 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 315.42/291.58 315.42/291.58 (0) CpxTRS 315.42/291.58 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 315.42/291.58 (2) CpxTRS 315.42/291.58 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 315.42/291.58 (4) typed CpxTrs 315.42/291.58 (5) OrderProof [LOWER BOUND(ID), 0 ms] 315.42/291.58 (6) typed CpxTrs 315.42/291.58 (7) RewriteLemmaProof [LOWER BOUND(ID), 310 ms] 315.42/291.58 (8) BEST 315.42/291.58 (9) proven lower bound 315.42/291.58 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 315.42/291.58 (11) BOUNDS(n^1, INF) 315.42/291.58 (12) typed CpxTrs 315.42/291.58 (13) RewriteLemmaProof [LOWER BOUND(ID), 78 ms] 315.42/291.58 (14) typed CpxTrs 315.42/291.58 315.42/291.58 315.42/291.58 ---------------------------------------- 315.42/291.58 315.42/291.58 (0) 315.42/291.58 Obligation: 315.42/291.58 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 315.42/291.58 315.42/291.58 315.42/291.58 The TRS R consists of the following rules: 315.42/291.58 315.42/291.58 lt(0, s(x)) -> true 315.42/291.58 lt(x, 0) -> false 315.42/291.58 lt(s(x), s(y)) -> lt(x, y) 315.42/291.58 logarithm(x) -> ifa(lt(0, x), x) 315.42/291.58 ifa(true, x) -> help(x, 1) 315.42/291.58 ifa(false, x) -> logZeroError 315.42/291.58 help(x, y) -> ifb(lt(y, x), x, y) 315.42/291.58 ifb(true, x, y) -> help(half(x), s(y)) 315.42/291.58 ifb(false, x, y) -> y 315.42/291.58 half(0) -> 0 315.42/291.58 half(s(0)) -> 0 315.42/291.58 half(s(s(x))) -> s(half(x)) 315.42/291.58 315.42/291.58 S is empty. 315.42/291.58 Rewrite Strategy: FULL 315.42/291.58 ---------------------------------------- 315.42/291.58 315.42/291.58 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 315.42/291.58 Renamed function symbols to avoid clashes with predefined symbol. 315.42/291.58 ---------------------------------------- 315.42/291.58 315.42/291.58 (2) 315.42/291.58 Obligation: 315.42/291.58 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 315.42/291.58 315.42/291.58 315.42/291.58 The TRS R consists of the following rules: 315.42/291.58 315.42/291.58 lt(0', s(x)) -> true 315.42/291.58 lt(x, 0') -> false 315.42/291.58 lt(s(x), s(y)) -> lt(x, y) 315.42/291.58 logarithm(x) -> ifa(lt(0', x), x) 315.42/291.58 ifa(true, x) -> help(x, 1') 315.42/291.58 ifa(false, x) -> logZeroError 315.42/291.58 help(x, y) -> ifb(lt(y, x), x, y) 315.42/291.58 ifb(true, x, y) -> help(half(x), s(y)) 315.42/291.58 ifb(false, x, y) -> y 315.42/291.58 half(0') -> 0' 315.42/291.58 half(s(0')) -> 0' 315.42/291.58 half(s(s(x))) -> s(half(x)) 315.42/291.58 315.42/291.58 S is empty. 315.42/291.58 Rewrite Strategy: FULL 315.42/291.58 ---------------------------------------- 315.42/291.58 315.42/291.58 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 315.42/291.58 Infered types. 315.42/291.58 ---------------------------------------- 315.42/291.58 315.42/291.58 (4) 315.42/291.58 Obligation: 315.42/291.58 TRS: 315.42/291.58 Rules: 315.42/291.58 lt(0', s(x)) -> true 315.42/291.58 lt(x, 0') -> false 315.42/291.58 lt(s(x), s(y)) -> lt(x, y) 315.42/291.58 logarithm(x) -> ifa(lt(0', x), x) 315.42/291.58 ifa(true, x) -> help(x, 1') 315.42/291.58 ifa(false, x) -> logZeroError 315.42/291.58 help(x, y) -> ifb(lt(y, x), x, y) 315.42/291.58 ifb(true, x, y) -> help(half(x), s(y)) 315.42/291.58 ifb(false, x, y) -> y 315.42/291.58 half(0') -> 0' 315.42/291.58 half(s(0')) -> 0' 315.42/291.58 half(s(s(x))) -> s(half(x)) 315.42/291.58 315.42/291.58 Types: 315.42/291.58 lt :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> true:false 315.42/291.58 0' :: 0':s:1':logZeroError 315.42/291.58 s :: 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.58 true :: true:false 315.42/291.58 false :: true:false 315.42/291.58 logarithm :: 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.58 ifa :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.58 help :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.58 1' :: 0':s:1':logZeroError 315.42/291.58 logZeroError :: 0':s:1':logZeroError 315.42/291.58 ifb :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.58 half :: 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 hole_true:false1_0 :: true:false 315.42/291.59 hole_0':s:1':logZeroError2_0 :: 0':s:1':logZeroError 315.42/291.59 gen_0':s:1':logZeroError3_0 :: Nat -> 0':s:1':logZeroError 315.42/291.59 315.42/291.59 ---------------------------------------- 315.42/291.59 315.42/291.59 (5) OrderProof (LOWER BOUND(ID)) 315.42/291.59 Heuristically decided to analyse the following defined symbols: 315.42/291.59 lt, help, half 315.42/291.59 315.42/291.59 They will be analysed ascendingly in the following order: 315.42/291.59 lt < help 315.42/291.59 half < help 315.42/291.59 315.42/291.59 ---------------------------------------- 315.42/291.59 315.42/291.59 (6) 315.42/291.59 Obligation: 315.42/291.59 TRS: 315.42/291.59 Rules: 315.42/291.59 lt(0', s(x)) -> true 315.42/291.59 lt(x, 0') -> false 315.42/291.59 lt(s(x), s(y)) -> lt(x, y) 315.42/291.59 logarithm(x) -> ifa(lt(0', x), x) 315.42/291.59 ifa(true, x) -> help(x, 1') 315.42/291.59 ifa(false, x) -> logZeroError 315.42/291.59 help(x, y) -> ifb(lt(y, x), x, y) 315.42/291.59 ifb(true, x, y) -> help(half(x), s(y)) 315.42/291.59 ifb(false, x, y) -> y 315.42/291.59 half(0') -> 0' 315.42/291.59 half(s(0')) -> 0' 315.42/291.59 half(s(s(x))) -> s(half(x)) 315.42/291.59 315.42/291.59 Types: 315.42/291.59 lt :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> true:false 315.42/291.59 0' :: 0':s:1':logZeroError 315.42/291.59 s :: 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 true :: true:false 315.42/291.59 false :: true:false 315.42/291.59 logarithm :: 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 ifa :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 help :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 1' :: 0':s:1':logZeroError 315.42/291.59 logZeroError :: 0':s:1':logZeroError 315.42/291.59 ifb :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 half :: 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 hole_true:false1_0 :: true:false 315.42/291.59 hole_0':s:1':logZeroError2_0 :: 0':s:1':logZeroError 315.42/291.59 gen_0':s:1':logZeroError3_0 :: Nat -> 0':s:1':logZeroError 315.42/291.59 315.42/291.59 315.42/291.59 Generator Equations: 315.42/291.59 gen_0':s:1':logZeroError3_0(0) <=> 0' 315.42/291.59 gen_0':s:1':logZeroError3_0(+(x, 1)) <=> s(gen_0':s:1':logZeroError3_0(x)) 315.42/291.59 315.42/291.59 315.42/291.59 The following defined symbols remain to be analysed: 315.42/291.59 lt, help, half 315.42/291.59 315.42/291.59 They will be analysed ascendingly in the following order: 315.42/291.59 lt < help 315.42/291.59 half < help 315.42/291.59 315.42/291.59 ---------------------------------------- 315.42/291.59 315.42/291.59 (7) RewriteLemmaProof (LOWER BOUND(ID)) 315.42/291.59 Proved the following rewrite lemma: 315.42/291.59 lt(gen_0':s:1':logZeroError3_0(n5_0), gen_0':s:1':logZeroError3_0(+(1, n5_0))) -> true, rt in Omega(1 + n5_0) 315.42/291.59 315.42/291.59 Induction Base: 315.42/291.59 lt(gen_0':s:1':logZeroError3_0(0), gen_0':s:1':logZeroError3_0(+(1, 0))) ->_R^Omega(1) 315.42/291.59 true 315.42/291.59 315.42/291.59 Induction Step: 315.42/291.59 lt(gen_0':s:1':logZeroError3_0(+(n5_0, 1)), gen_0':s:1':logZeroError3_0(+(1, +(n5_0, 1)))) ->_R^Omega(1) 315.42/291.59 lt(gen_0':s:1':logZeroError3_0(n5_0), gen_0':s:1':logZeroError3_0(+(1, n5_0))) ->_IH 315.42/291.59 true 315.42/291.59 315.42/291.59 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 315.42/291.59 ---------------------------------------- 315.42/291.59 315.42/291.59 (8) 315.42/291.59 Complex Obligation (BEST) 315.42/291.59 315.42/291.59 ---------------------------------------- 315.42/291.59 315.42/291.59 (9) 315.42/291.59 Obligation: 315.42/291.59 Proved the lower bound n^1 for the following obligation: 315.42/291.59 315.42/291.59 TRS: 315.42/291.59 Rules: 315.42/291.59 lt(0', s(x)) -> true 315.42/291.59 lt(x, 0') -> false 315.42/291.59 lt(s(x), s(y)) -> lt(x, y) 315.42/291.59 logarithm(x) -> ifa(lt(0', x), x) 315.42/291.59 ifa(true, x) -> help(x, 1') 315.42/291.59 ifa(false, x) -> logZeroError 315.42/291.59 help(x, y) -> ifb(lt(y, x), x, y) 315.42/291.59 ifb(true, x, y) -> help(half(x), s(y)) 315.42/291.59 ifb(false, x, y) -> y 315.42/291.59 half(0') -> 0' 315.42/291.59 half(s(0')) -> 0' 315.42/291.59 half(s(s(x))) -> s(half(x)) 315.42/291.59 315.42/291.59 Types: 315.42/291.59 lt :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> true:false 315.42/291.59 0' :: 0':s:1':logZeroError 315.42/291.59 s :: 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 true :: true:false 315.42/291.59 false :: true:false 315.42/291.59 logarithm :: 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 ifa :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 help :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 1' :: 0':s:1':logZeroError 315.42/291.59 logZeroError :: 0':s:1':logZeroError 315.42/291.59 ifb :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 half :: 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 hole_true:false1_0 :: true:false 315.42/291.59 hole_0':s:1':logZeroError2_0 :: 0':s:1':logZeroError 315.42/291.59 gen_0':s:1':logZeroError3_0 :: Nat -> 0':s:1':logZeroError 315.42/291.59 315.42/291.59 315.42/291.59 Generator Equations: 315.42/291.59 gen_0':s:1':logZeroError3_0(0) <=> 0' 315.42/291.59 gen_0':s:1':logZeroError3_0(+(x, 1)) <=> s(gen_0':s:1':logZeroError3_0(x)) 315.42/291.59 315.42/291.59 315.42/291.59 The following defined symbols remain to be analysed: 315.42/291.59 lt, help, half 315.42/291.59 315.42/291.59 They will be analysed ascendingly in the following order: 315.42/291.59 lt < help 315.42/291.59 half < help 315.42/291.59 315.42/291.59 ---------------------------------------- 315.42/291.59 315.42/291.59 (10) LowerBoundPropagationProof (FINISHED) 315.42/291.59 Propagated lower bound. 315.42/291.59 ---------------------------------------- 315.42/291.59 315.42/291.59 (11) 315.42/291.59 BOUNDS(n^1, INF) 315.42/291.59 315.42/291.59 ---------------------------------------- 315.42/291.59 315.42/291.59 (12) 315.42/291.59 Obligation: 315.42/291.59 TRS: 315.42/291.59 Rules: 315.42/291.59 lt(0', s(x)) -> true 315.42/291.59 lt(x, 0') -> false 315.42/291.59 lt(s(x), s(y)) -> lt(x, y) 315.42/291.59 logarithm(x) -> ifa(lt(0', x), x) 315.42/291.59 ifa(true, x) -> help(x, 1') 315.42/291.59 ifa(false, x) -> logZeroError 315.42/291.59 help(x, y) -> ifb(lt(y, x), x, y) 315.42/291.59 ifb(true, x, y) -> help(half(x), s(y)) 315.42/291.59 ifb(false, x, y) -> y 315.42/291.59 half(0') -> 0' 315.42/291.59 half(s(0')) -> 0' 315.42/291.59 half(s(s(x))) -> s(half(x)) 315.42/291.59 315.42/291.59 Types: 315.42/291.59 lt :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> true:false 315.42/291.59 0' :: 0':s:1':logZeroError 315.42/291.59 s :: 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 true :: true:false 315.42/291.59 false :: true:false 315.42/291.59 logarithm :: 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 ifa :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 help :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 1' :: 0':s:1':logZeroError 315.42/291.59 logZeroError :: 0':s:1':logZeroError 315.42/291.59 ifb :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 half :: 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 hole_true:false1_0 :: true:false 315.42/291.59 hole_0':s:1':logZeroError2_0 :: 0':s:1':logZeroError 315.42/291.59 gen_0':s:1':logZeroError3_0 :: Nat -> 0':s:1':logZeroError 315.42/291.59 315.42/291.59 315.42/291.59 Lemmas: 315.42/291.59 lt(gen_0':s:1':logZeroError3_0(n5_0), gen_0':s:1':logZeroError3_0(+(1, n5_0))) -> true, rt in Omega(1 + n5_0) 315.42/291.59 315.42/291.59 315.42/291.59 Generator Equations: 315.42/291.59 gen_0':s:1':logZeroError3_0(0) <=> 0' 315.42/291.59 gen_0':s:1':logZeroError3_0(+(x, 1)) <=> s(gen_0':s:1':logZeroError3_0(x)) 315.42/291.59 315.42/291.59 315.42/291.59 The following defined symbols remain to be analysed: 315.42/291.59 half, help 315.42/291.59 315.42/291.59 They will be analysed ascendingly in the following order: 315.42/291.59 half < help 315.42/291.59 315.42/291.59 ---------------------------------------- 315.42/291.59 315.42/291.59 (13) RewriteLemmaProof (LOWER BOUND(ID)) 315.42/291.59 Proved the following rewrite lemma: 315.42/291.59 half(gen_0':s:1':logZeroError3_0(*(2, n263_0))) -> gen_0':s:1':logZeroError3_0(n263_0), rt in Omega(1 + n263_0) 315.42/291.59 315.42/291.59 Induction Base: 315.42/291.59 half(gen_0':s:1':logZeroError3_0(*(2, 0))) ->_R^Omega(1) 315.42/291.59 0' 315.42/291.59 315.42/291.59 Induction Step: 315.42/291.59 half(gen_0':s:1':logZeroError3_0(*(2, +(n263_0, 1)))) ->_R^Omega(1) 315.42/291.59 s(half(gen_0':s:1':logZeroError3_0(*(2, n263_0)))) ->_IH 315.42/291.59 s(gen_0':s:1':logZeroError3_0(c264_0)) 315.42/291.59 315.42/291.59 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 315.42/291.59 ---------------------------------------- 315.42/291.59 315.42/291.59 (14) 315.42/291.59 Obligation: 315.42/291.59 TRS: 315.42/291.59 Rules: 315.42/291.59 lt(0', s(x)) -> true 315.42/291.59 lt(x, 0') -> false 315.42/291.59 lt(s(x), s(y)) -> lt(x, y) 315.42/291.59 logarithm(x) -> ifa(lt(0', x), x) 315.42/291.59 ifa(true, x) -> help(x, 1') 315.42/291.59 ifa(false, x) -> logZeroError 315.42/291.59 help(x, y) -> ifb(lt(y, x), x, y) 315.42/291.59 ifb(true, x, y) -> help(half(x), s(y)) 315.42/291.59 ifb(false, x, y) -> y 315.42/291.59 half(0') -> 0' 315.42/291.59 half(s(0')) -> 0' 315.42/291.59 half(s(s(x))) -> s(half(x)) 315.42/291.59 315.42/291.59 Types: 315.42/291.59 lt :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> true:false 315.42/291.59 0' :: 0':s:1':logZeroError 315.42/291.59 s :: 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 true :: true:false 315.42/291.59 false :: true:false 315.42/291.59 logarithm :: 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 ifa :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 help :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 1' :: 0':s:1':logZeroError 315.42/291.59 logZeroError :: 0':s:1':logZeroError 315.42/291.59 ifb :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 half :: 0':s:1':logZeroError -> 0':s:1':logZeroError 315.42/291.59 hole_true:false1_0 :: true:false 315.42/291.59 hole_0':s:1':logZeroError2_0 :: 0':s:1':logZeroError 315.42/291.59 gen_0':s:1':logZeroError3_0 :: Nat -> 0':s:1':logZeroError 315.42/291.59 315.42/291.59 315.42/291.59 Lemmas: 315.42/291.59 lt(gen_0':s:1':logZeroError3_0(n5_0), gen_0':s:1':logZeroError3_0(+(1, n5_0))) -> true, rt in Omega(1 + n5_0) 315.42/291.59 half(gen_0':s:1':logZeroError3_0(*(2, n263_0))) -> gen_0':s:1':logZeroError3_0(n263_0), rt in Omega(1 + n263_0) 315.42/291.59 315.42/291.59 315.42/291.59 Generator Equations: 315.42/291.59 gen_0':s:1':logZeroError3_0(0) <=> 0' 315.42/291.59 gen_0':s:1':logZeroError3_0(+(x, 1)) <=> s(gen_0':s:1':logZeroError3_0(x)) 315.42/291.59 315.42/291.59 315.42/291.59 The following defined symbols remain to be analysed: 315.42/291.59 help 315.50/291.62 EOF