1124.47/291.50 WORST_CASE(Omega(n^1), ?) 1124.47/291.53 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1124.47/291.53 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1124.47/291.53 1124.47/291.53 1124.47/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1124.47/291.53 1124.47/291.53 (0) CpxTRS 1124.47/291.53 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1124.47/291.53 (2) CpxTRS 1124.47/291.53 (3) SlicingProof [LOWER BOUND(ID), 0 ms] 1124.47/291.53 (4) CpxTRS 1124.47/291.53 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1124.47/291.53 (6) typed CpxTrs 1124.47/291.53 (7) OrderProof [LOWER BOUND(ID), 0 ms] 1124.47/291.53 (8) typed CpxTrs 1124.47/291.53 (9) RewriteLemmaProof [LOWER BOUND(ID), 386 ms] 1124.47/291.53 (10) BEST 1124.47/291.53 (11) proven lower bound 1124.47/291.53 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 1124.47/291.53 (13) BOUNDS(n^1, INF) 1124.47/291.53 (14) typed CpxTrs 1124.47/291.53 (15) RewriteLemmaProof [LOWER BOUND(ID), 123 ms] 1124.47/291.53 (16) typed CpxTrs 1124.47/291.53 (17) RewriteLemmaProof [LOWER BOUND(ID), 108 ms] 1124.47/291.53 (18) BOUNDS(1, INF) 1124.47/291.53 1124.47/291.53 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (0) 1124.47/291.53 Obligation: 1124.47/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1124.47/291.53 1124.47/291.53 1124.47/291.53 The TRS R consists of the following rules: 1124.47/291.53 1124.47/291.53 g(A) -> A 1124.47/291.53 g(B) -> A 1124.47/291.53 g(B) -> B 1124.47/291.53 g(C) -> A 1124.47/291.53 g(C) -> B 1124.47/291.53 g(C) -> C 1124.47/291.53 foldB(t, 0) -> t 1124.47/291.53 foldB(t, s(n)) -> f(foldB(t, n), B) 1124.47/291.53 foldC(t, 0) -> t 1124.47/291.53 foldC(t, s(n)) -> f(foldC(t, n), C) 1124.47/291.53 f(t, x) -> f'(t, g(x)) 1124.47/291.53 f'(triple(a, b, c), C) -> triple(a, b, s(c)) 1124.47/291.53 f'(triple(a, b, c), B) -> f(triple(a, b, c), A) 1124.47/291.53 f'(triple(a, b, c), A) -> f''(foldB(triple(s(a), 0, c), b)) 1124.47/291.53 f''(triple(a, b, c)) -> foldC(triple(a, b, 0), c) 1124.47/291.53 1124.47/291.53 S is empty. 1124.47/291.53 Rewrite Strategy: FULL 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1124.47/291.53 Renamed function symbols to avoid clashes with predefined symbol. 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (2) 1124.47/291.53 Obligation: 1124.47/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1124.47/291.53 1124.47/291.53 1124.47/291.53 The TRS R consists of the following rules: 1124.47/291.53 1124.47/291.53 g(A) -> A 1124.47/291.53 g(B) -> A 1124.47/291.53 g(B) -> B 1124.47/291.53 g(C) -> A 1124.47/291.53 g(C) -> B 1124.47/291.53 g(C) -> C 1124.47/291.53 foldB(t, 0') -> t 1124.47/291.53 foldB(t, s(n)) -> f(foldB(t, n), B) 1124.47/291.53 foldC(t, 0') -> t 1124.47/291.53 foldC(t, s(n)) -> f(foldC(t, n), C) 1124.47/291.53 f(t, x) -> f'(t, g(x)) 1124.47/291.53 f'(triple(a, b, c), C) -> triple(a, b, s(c)) 1124.47/291.53 f'(triple(a, b, c), B) -> f(triple(a, b, c), A) 1124.47/291.53 f'(triple(a, b, c), A) -> f''(foldB(triple(s(a), 0', c), b)) 1124.47/291.53 f''(triple(a, b, c)) -> foldC(triple(a, b, 0'), c) 1124.47/291.53 1124.47/291.53 S is empty. 1124.47/291.53 Rewrite Strategy: FULL 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (3) SlicingProof (LOWER BOUND(ID)) 1124.47/291.53 Sliced the following arguments: 1124.47/291.53 triple/0 1124.47/291.53 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (4) 1124.47/291.53 Obligation: 1124.47/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1124.47/291.53 1124.47/291.53 1124.47/291.53 The TRS R consists of the following rules: 1124.47/291.53 1124.47/291.53 g(A) -> A 1124.47/291.53 g(B) -> A 1124.47/291.53 g(B) -> B 1124.47/291.53 g(C) -> A 1124.47/291.53 g(C) -> B 1124.47/291.53 g(C) -> C 1124.47/291.53 foldB(t, 0') -> t 1124.47/291.53 foldB(t, s(n)) -> f(foldB(t, n), B) 1124.47/291.53 foldC(t, 0') -> t 1124.47/291.53 foldC(t, s(n)) -> f(foldC(t, n), C) 1124.47/291.53 f(t, x) -> f'(t, g(x)) 1124.47/291.53 f'(triple(b, c), C) -> triple(b, s(c)) 1124.47/291.53 f'(triple(b, c), B) -> f(triple(b, c), A) 1124.47/291.53 f'(triple(b, c), A) -> f''(foldB(triple(0', c), b)) 1124.47/291.53 f''(triple(b, c)) -> foldC(triple(b, 0'), c) 1124.47/291.53 1124.47/291.53 S is empty. 1124.47/291.53 Rewrite Strategy: FULL 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1124.47/291.53 Infered types. 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (6) 1124.47/291.53 Obligation: 1124.47/291.53 TRS: 1124.47/291.53 Rules: 1124.47/291.53 g(A) -> A 1124.47/291.53 g(B) -> A 1124.47/291.53 g(B) -> B 1124.47/291.53 g(C) -> A 1124.47/291.53 g(C) -> B 1124.47/291.53 g(C) -> C 1124.47/291.53 foldB(t, 0') -> t 1124.47/291.53 foldB(t, s(n)) -> f(foldB(t, n), B) 1124.47/291.53 foldC(t, 0') -> t 1124.47/291.53 foldC(t, s(n)) -> f(foldC(t, n), C) 1124.47/291.53 f(t, x) -> f'(t, g(x)) 1124.47/291.53 f'(triple(b, c), C) -> triple(b, s(c)) 1124.47/291.53 f'(triple(b, c), B) -> f(triple(b, c), A) 1124.47/291.53 f'(triple(b, c), A) -> f''(foldB(triple(0', c), b)) 1124.47/291.53 f''(triple(b, c)) -> foldC(triple(b, 0'), c) 1124.47/291.53 1124.47/291.53 Types: 1124.47/291.53 g :: A:B:C -> A:B:C 1124.47/291.53 A :: A:B:C 1124.47/291.53 B :: A:B:C 1124.47/291.53 C :: A:B:C 1124.47/291.53 foldB :: triple -> 0':s -> triple 1124.47/291.53 0' :: 0':s 1124.47/291.53 s :: 0':s -> 0':s 1124.47/291.53 f :: triple -> A:B:C -> triple 1124.47/291.53 foldC :: triple -> 0':s -> triple 1124.47/291.53 f' :: triple -> A:B:C -> triple 1124.47/291.53 triple :: 0':s -> 0':s -> triple 1124.47/291.53 f'' :: triple -> triple 1124.47/291.53 hole_A:B:C1_0 :: A:B:C 1124.47/291.53 hole_triple2_0 :: triple 1124.47/291.53 hole_0':s3_0 :: 0':s 1124.47/291.53 gen_0':s4_0 :: Nat -> 0':s 1124.47/291.53 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (7) OrderProof (LOWER BOUND(ID)) 1124.47/291.53 Heuristically decided to analyse the following defined symbols: 1124.47/291.53 foldB, f, foldC, f', f'' 1124.47/291.53 1124.47/291.53 They will be analysed ascendingly in the following order: 1124.47/291.53 foldB = f 1124.47/291.53 foldB = foldC 1124.47/291.53 foldB = f' 1124.47/291.53 foldB = f'' 1124.47/291.53 f = foldC 1124.47/291.53 f = f' 1124.47/291.53 f = f'' 1124.47/291.53 foldC = f' 1124.47/291.53 foldC = f'' 1124.47/291.53 f' = f'' 1124.47/291.53 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (8) 1124.47/291.53 Obligation: 1124.47/291.53 TRS: 1124.47/291.53 Rules: 1124.47/291.53 g(A) -> A 1124.47/291.53 g(B) -> A 1124.47/291.53 g(B) -> B 1124.47/291.53 g(C) -> A 1124.47/291.53 g(C) -> B 1124.47/291.53 g(C) -> C 1124.47/291.53 foldB(t, 0') -> t 1124.47/291.53 foldB(t, s(n)) -> f(foldB(t, n), B) 1124.47/291.53 foldC(t, 0') -> t 1124.47/291.53 foldC(t, s(n)) -> f(foldC(t, n), C) 1124.47/291.53 f(t, x) -> f'(t, g(x)) 1124.47/291.53 f'(triple(b, c), C) -> triple(b, s(c)) 1124.47/291.53 f'(triple(b, c), B) -> f(triple(b, c), A) 1124.47/291.53 f'(triple(b, c), A) -> f''(foldB(triple(0', c), b)) 1124.47/291.53 f''(triple(b, c)) -> foldC(triple(b, 0'), c) 1124.47/291.53 1124.47/291.53 Types: 1124.47/291.53 g :: A:B:C -> A:B:C 1124.47/291.53 A :: A:B:C 1124.47/291.53 B :: A:B:C 1124.47/291.53 C :: A:B:C 1124.47/291.53 foldB :: triple -> 0':s -> triple 1124.47/291.53 0' :: 0':s 1124.47/291.53 s :: 0':s -> 0':s 1124.47/291.53 f :: triple -> A:B:C -> triple 1124.47/291.53 foldC :: triple -> 0':s -> triple 1124.47/291.53 f' :: triple -> A:B:C -> triple 1124.47/291.53 triple :: 0':s -> 0':s -> triple 1124.47/291.53 f'' :: triple -> triple 1124.47/291.53 hole_A:B:C1_0 :: A:B:C 1124.47/291.53 hole_triple2_0 :: triple 1124.47/291.53 hole_0':s3_0 :: 0':s 1124.47/291.53 gen_0':s4_0 :: Nat -> 0':s 1124.47/291.53 1124.47/291.53 1124.47/291.53 Generator Equations: 1124.47/291.53 gen_0':s4_0(0) <=> 0' 1124.47/291.53 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1124.47/291.53 1124.47/291.53 1124.47/291.53 The following defined symbols remain to be analysed: 1124.47/291.53 f, foldB, foldC, f', f'' 1124.47/291.53 1124.47/291.53 They will be analysed ascendingly in the following order: 1124.47/291.53 foldB = f 1124.47/291.53 foldB = foldC 1124.47/291.53 foldB = f' 1124.47/291.53 foldB = f'' 1124.47/291.53 f = foldC 1124.47/291.53 f = f' 1124.47/291.53 f = f'' 1124.47/291.53 foldC = f' 1124.47/291.53 foldC = f'' 1124.47/291.53 f' = f'' 1124.47/291.53 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (9) RewriteLemmaProof (LOWER BOUND(ID)) 1124.47/291.53 Proved the following rewrite lemma: 1124.47/291.53 foldC(triple(0', 0'), gen_0':s4_0(n143_0)) -> triple(gen_0':s4_0(0), gen_0':s4_0(0)), rt in Omega(1 + n143_0) 1124.47/291.53 1124.47/291.53 Induction Base: 1124.47/291.53 foldC(triple(0', 0'), gen_0':s4_0(0)) ->_R^Omega(1) 1124.47/291.53 triple(0', 0') 1124.47/291.53 1124.47/291.53 Induction Step: 1124.47/291.53 foldC(triple(0', 0'), gen_0':s4_0(+(n143_0, 1))) ->_R^Omega(1) 1124.47/291.53 f(foldC(triple(0', 0'), gen_0':s4_0(n143_0)), C) ->_IH 1124.47/291.53 f(triple(gen_0':s4_0(0), gen_0':s4_0(0)), C) ->_R^Omega(1) 1124.47/291.53 f'(triple(gen_0':s4_0(0), gen_0':s4_0(0)), g(C)) ->_R^Omega(1) 1124.47/291.53 f'(triple(gen_0':s4_0(0), gen_0':s4_0(0)), A) ->_R^Omega(1) 1124.47/291.53 f''(foldB(triple(0', gen_0':s4_0(0)), gen_0':s4_0(0))) ->_R^Omega(1) 1124.47/291.53 f''(triple(0', gen_0':s4_0(0))) ->_R^Omega(1) 1124.47/291.53 foldC(triple(0', 0'), gen_0':s4_0(0)) ->_R^Omega(1) 1124.47/291.53 triple(0', 0') 1124.47/291.53 1124.47/291.53 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (10) 1124.47/291.53 Complex Obligation (BEST) 1124.47/291.53 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (11) 1124.47/291.53 Obligation: 1124.47/291.53 Proved the lower bound n^1 for the following obligation: 1124.47/291.53 1124.47/291.53 TRS: 1124.47/291.53 Rules: 1124.47/291.53 g(A) -> A 1124.47/291.53 g(B) -> A 1124.47/291.53 g(B) -> B 1124.47/291.53 g(C) -> A 1124.47/291.53 g(C) -> B 1124.47/291.53 g(C) -> C 1124.47/291.53 foldB(t, 0') -> t 1124.47/291.53 foldB(t, s(n)) -> f(foldB(t, n), B) 1124.47/291.53 foldC(t, 0') -> t 1124.47/291.53 foldC(t, s(n)) -> f(foldC(t, n), C) 1124.47/291.53 f(t, x) -> f'(t, g(x)) 1124.47/291.53 f'(triple(b, c), C) -> triple(b, s(c)) 1124.47/291.53 f'(triple(b, c), B) -> f(triple(b, c), A) 1124.47/291.53 f'(triple(b, c), A) -> f''(foldB(triple(0', c), b)) 1124.47/291.53 f''(triple(b, c)) -> foldC(triple(b, 0'), c) 1124.47/291.53 1124.47/291.53 Types: 1124.47/291.53 g :: A:B:C -> A:B:C 1124.47/291.53 A :: A:B:C 1124.47/291.53 B :: A:B:C 1124.47/291.53 C :: A:B:C 1124.47/291.53 foldB :: triple -> 0':s -> triple 1124.47/291.53 0' :: 0':s 1124.47/291.53 s :: 0':s -> 0':s 1124.47/291.53 f :: triple -> A:B:C -> triple 1124.47/291.53 foldC :: triple -> 0':s -> triple 1124.47/291.53 f' :: triple -> A:B:C -> triple 1124.47/291.53 triple :: 0':s -> 0':s -> triple 1124.47/291.53 f'' :: triple -> triple 1124.47/291.53 hole_A:B:C1_0 :: A:B:C 1124.47/291.53 hole_triple2_0 :: triple 1124.47/291.53 hole_0':s3_0 :: 0':s 1124.47/291.53 gen_0':s4_0 :: Nat -> 0':s 1124.47/291.53 1124.47/291.53 1124.47/291.53 Generator Equations: 1124.47/291.53 gen_0':s4_0(0) <=> 0' 1124.47/291.53 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1124.47/291.53 1124.47/291.53 1124.47/291.53 The following defined symbols remain to be analysed: 1124.47/291.53 foldC, foldB 1124.47/291.53 1124.47/291.53 They will be analysed ascendingly in the following order: 1124.47/291.53 foldB = f 1124.47/291.53 foldB = foldC 1124.47/291.53 foldB = f' 1124.47/291.53 foldB = f'' 1124.47/291.53 f = foldC 1124.47/291.53 f = f' 1124.47/291.53 f = f'' 1124.47/291.53 foldC = f' 1124.47/291.53 foldC = f'' 1124.47/291.53 f' = f'' 1124.47/291.53 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (12) LowerBoundPropagationProof (FINISHED) 1124.47/291.53 Propagated lower bound. 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (13) 1124.47/291.53 BOUNDS(n^1, INF) 1124.47/291.53 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (14) 1124.47/291.53 Obligation: 1124.47/291.53 TRS: 1124.47/291.53 Rules: 1124.47/291.53 g(A) -> A 1124.47/291.53 g(B) -> A 1124.47/291.53 g(B) -> B 1124.47/291.53 g(C) -> A 1124.47/291.53 g(C) -> B 1124.47/291.53 g(C) -> C 1124.47/291.53 foldB(t, 0') -> t 1124.47/291.53 foldB(t, s(n)) -> f(foldB(t, n), B) 1124.47/291.53 foldC(t, 0') -> t 1124.47/291.53 foldC(t, s(n)) -> f(foldC(t, n), C) 1124.47/291.53 f(t, x) -> f'(t, g(x)) 1124.47/291.53 f'(triple(b, c), C) -> triple(b, s(c)) 1124.47/291.53 f'(triple(b, c), B) -> f(triple(b, c), A) 1124.47/291.53 f'(triple(b, c), A) -> f''(foldB(triple(0', c), b)) 1124.47/291.53 f''(triple(b, c)) -> foldC(triple(b, 0'), c) 1124.47/291.53 1124.47/291.53 Types: 1124.47/291.53 g :: A:B:C -> A:B:C 1124.47/291.53 A :: A:B:C 1124.47/291.53 B :: A:B:C 1124.47/291.53 C :: A:B:C 1124.47/291.53 foldB :: triple -> 0':s -> triple 1124.47/291.53 0' :: 0':s 1124.47/291.53 s :: 0':s -> 0':s 1124.47/291.53 f :: triple -> A:B:C -> triple 1124.47/291.53 foldC :: triple -> 0':s -> triple 1124.47/291.53 f' :: triple -> A:B:C -> triple 1124.47/291.53 triple :: 0':s -> 0':s -> triple 1124.47/291.53 f'' :: triple -> triple 1124.47/291.53 hole_A:B:C1_0 :: A:B:C 1124.47/291.53 hole_triple2_0 :: triple 1124.47/291.53 hole_0':s3_0 :: 0':s 1124.47/291.53 gen_0':s4_0 :: Nat -> 0':s 1124.47/291.53 1124.47/291.53 1124.47/291.53 Lemmas: 1124.47/291.53 foldC(triple(0', 0'), gen_0':s4_0(n143_0)) -> triple(gen_0':s4_0(0), gen_0':s4_0(0)), rt in Omega(1 + n143_0) 1124.47/291.53 1124.47/291.53 1124.47/291.53 Generator Equations: 1124.47/291.53 gen_0':s4_0(0) <=> 0' 1124.47/291.53 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1124.47/291.53 1124.47/291.53 1124.47/291.53 The following defined symbols remain to be analysed: 1124.47/291.53 foldB, f, f', f'' 1124.47/291.53 1124.47/291.53 They will be analysed ascendingly in the following order: 1124.47/291.53 foldB = f 1124.47/291.53 foldB = foldC 1124.47/291.53 foldB = f' 1124.47/291.53 foldB = f'' 1124.47/291.53 f = foldC 1124.47/291.53 f = f' 1124.47/291.53 f = f'' 1124.47/291.53 foldC = f' 1124.47/291.53 foldC = f'' 1124.47/291.53 f' = f'' 1124.47/291.53 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (15) RewriteLemmaProof (LOWER BOUND(ID)) 1124.47/291.53 Proved the following rewrite lemma: 1124.47/291.53 foldB(triple(0', 0'), gen_0':s4_0(n2037_0)) -> triple(gen_0':s4_0(0), gen_0':s4_0(0)), rt in Omega(1 + n2037_0) 1124.47/291.53 1124.47/291.53 Induction Base: 1124.47/291.53 foldB(triple(0', 0'), gen_0':s4_0(0)) ->_R^Omega(1) 1124.47/291.53 triple(0', 0') 1124.47/291.53 1124.47/291.53 Induction Step: 1124.47/291.53 foldB(triple(0', 0'), gen_0':s4_0(+(n2037_0, 1))) ->_R^Omega(1) 1124.47/291.53 f(foldB(triple(0', 0'), gen_0':s4_0(n2037_0)), B) ->_IH 1124.47/291.53 f(triple(gen_0':s4_0(0), gen_0':s4_0(0)), B) ->_R^Omega(1) 1124.47/291.53 f'(triple(gen_0':s4_0(0), gen_0':s4_0(0)), g(B)) ->_R^Omega(1) 1124.47/291.53 f'(triple(gen_0':s4_0(0), gen_0':s4_0(0)), A) ->_R^Omega(1) 1124.47/291.53 f''(foldB(triple(0', gen_0':s4_0(0)), gen_0':s4_0(0))) ->_R^Omega(1) 1124.47/291.53 f''(triple(0', gen_0':s4_0(0))) ->_R^Omega(1) 1124.47/291.53 foldC(triple(0', 0'), gen_0':s4_0(0)) ->_L^Omega(1) 1124.47/291.53 triple(gen_0':s4_0(0), gen_0':s4_0(0)) 1124.47/291.53 1124.47/291.53 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (16) 1124.47/291.53 Obligation: 1124.47/291.53 TRS: 1124.47/291.53 Rules: 1124.47/291.53 g(A) -> A 1124.47/291.53 g(B) -> A 1124.47/291.53 g(B) -> B 1124.47/291.53 g(C) -> A 1124.47/291.53 g(C) -> B 1124.47/291.53 g(C) -> C 1124.47/291.53 foldB(t, 0') -> t 1124.47/291.53 foldB(t, s(n)) -> f(foldB(t, n), B) 1124.47/291.53 foldC(t, 0') -> t 1124.47/291.53 foldC(t, s(n)) -> f(foldC(t, n), C) 1124.47/291.53 f(t, x) -> f'(t, g(x)) 1124.47/291.53 f'(triple(b, c), C) -> triple(b, s(c)) 1124.47/291.53 f'(triple(b, c), B) -> f(triple(b, c), A) 1124.47/291.53 f'(triple(b, c), A) -> f''(foldB(triple(0', c), b)) 1124.47/291.53 f''(triple(b, c)) -> foldC(triple(b, 0'), c) 1124.47/291.53 1124.47/291.53 Types: 1124.47/291.53 g :: A:B:C -> A:B:C 1124.47/291.53 A :: A:B:C 1124.47/291.53 B :: A:B:C 1124.47/291.53 C :: A:B:C 1124.47/291.53 foldB :: triple -> 0':s -> triple 1124.47/291.53 0' :: 0':s 1124.47/291.53 s :: 0':s -> 0':s 1124.47/291.53 f :: triple -> A:B:C -> triple 1124.47/291.53 foldC :: triple -> 0':s -> triple 1124.47/291.53 f' :: triple -> A:B:C -> triple 1124.47/291.53 triple :: 0':s -> 0':s -> triple 1124.47/291.53 f'' :: triple -> triple 1124.47/291.53 hole_A:B:C1_0 :: A:B:C 1124.47/291.53 hole_triple2_0 :: triple 1124.47/291.53 hole_0':s3_0 :: 0':s 1124.47/291.53 gen_0':s4_0 :: Nat -> 0':s 1124.47/291.53 1124.47/291.53 1124.47/291.53 Lemmas: 1124.47/291.53 foldC(triple(0', 0'), gen_0':s4_0(n143_0)) -> triple(gen_0':s4_0(0), gen_0':s4_0(0)), rt in Omega(1 + n143_0) 1124.47/291.53 foldB(triple(0', 0'), gen_0':s4_0(n2037_0)) -> triple(gen_0':s4_0(0), gen_0':s4_0(0)), rt in Omega(1 + n2037_0) 1124.47/291.53 1124.47/291.53 1124.47/291.53 Generator Equations: 1124.47/291.53 gen_0':s4_0(0) <=> 0' 1124.47/291.53 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1124.47/291.53 1124.47/291.53 1124.47/291.53 The following defined symbols remain to be analysed: 1124.47/291.53 f, foldC, f', f'' 1124.47/291.53 1124.47/291.53 They will be analysed ascendingly in the following order: 1124.47/291.53 foldB = f 1124.47/291.53 foldB = foldC 1124.47/291.53 foldB = f' 1124.47/291.53 foldB = f'' 1124.47/291.53 f = foldC 1124.47/291.53 f = f' 1124.47/291.53 f = f'' 1124.47/291.53 foldC = f' 1124.47/291.53 foldC = f'' 1124.47/291.53 f' = f'' 1124.47/291.53 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (17) RewriteLemmaProof (LOWER BOUND(ID)) 1124.47/291.53 Proved the following rewrite lemma: 1124.47/291.53 foldC(triple(0', 0'), gen_0':s4_0(n4048_0)) -> triple(gen_0':s4_0(0), gen_0':s4_0(0)), rt in Omega(1 + n4048_0) 1124.47/291.53 1124.47/291.53 Induction Base: 1124.47/291.53 foldC(triple(0', 0'), gen_0':s4_0(0)) ->_R^Omega(1) 1124.47/291.53 triple(0', 0') 1124.47/291.53 1124.47/291.53 Induction Step: 1124.47/291.53 foldC(triple(0', 0'), gen_0':s4_0(+(n4048_0, 1))) ->_R^Omega(1) 1124.47/291.53 f(foldC(triple(0', 0'), gen_0':s4_0(n4048_0)), C) ->_IH 1124.47/291.53 f(triple(gen_0':s4_0(0), gen_0':s4_0(0)), C) ->_R^Omega(1) 1124.47/291.53 f'(triple(gen_0':s4_0(0), gen_0':s4_0(0)), g(C)) ->_R^Omega(1) 1124.47/291.53 f'(triple(gen_0':s4_0(0), gen_0':s4_0(0)), A) ->_R^Omega(1) 1124.47/291.53 f''(foldB(triple(0', gen_0':s4_0(0)), gen_0':s4_0(0))) ->_L^Omega(1) 1124.47/291.53 f''(triple(gen_0':s4_0(0), gen_0':s4_0(0))) ->_R^Omega(1) 1124.47/291.53 foldC(triple(gen_0':s4_0(0), 0'), gen_0':s4_0(0)) ->_R^Omega(1) 1124.47/291.53 triple(gen_0':s4_0(0), 0') 1124.47/291.53 1124.47/291.53 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1124.47/291.53 ---------------------------------------- 1124.47/291.53 1124.47/291.53 (18) 1124.47/291.53 BOUNDS(1, INF) 1124.95/291.64 EOF