15.47/5.65 WORST_CASE(Omega(n^1), O(n^1)) 15.59/5.66 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 15.59/5.66 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 15.59/5.66 15.59/5.66 15.59/5.66 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 15.59/5.66 15.59/5.66 (0) CpxTRS 15.59/5.66 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 15.59/5.66 (2) CpxTRS 15.59/5.66 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 15.59/5.66 (4) CpxWeightedTrs 15.59/5.66 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 15.59/5.66 (6) CpxTypedWeightedTrs 15.59/5.66 (7) CompletionProof [UPPER BOUND(ID), 0 ms] 15.59/5.66 (8) CpxTypedWeightedCompleteTrs 15.59/5.66 (9) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 15.59/5.66 (10) CpxTypedWeightedCompleteTrs 15.59/5.66 (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 15.59/5.66 (12) CpxRNTS 15.59/5.66 (13) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 15.59/5.66 (14) CpxRNTS 15.59/5.66 (15) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] 15.59/5.66 (16) CpxRNTS 15.59/5.66 (17) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 15.59/5.66 (18) CpxRNTS 15.59/5.66 (19) IntTrsBoundProof [UPPER BOUND(ID), 605 ms] 15.59/5.66 (20) CpxRNTS 15.59/5.66 (21) IntTrsBoundProof [UPPER BOUND(ID), 117 ms] 15.59/5.66 (22) CpxRNTS 15.59/5.66 (23) FinalProof [FINISHED, 0 ms] 15.59/5.66 (24) BOUNDS(1, n^1) 15.59/5.66 (25) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 15.59/5.66 (26) CpxTRS 15.59/5.66 (27) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 15.59/5.66 (28) typed CpxTrs 15.59/5.66 (29) OrderProof [LOWER BOUND(ID), 0 ms] 15.59/5.66 (30) typed CpxTrs 15.59/5.66 (31) RewriteLemmaProof [LOWER BOUND(ID), 641 ms] 15.59/5.66 (32) proven lower bound 15.59/5.66 (33) LowerBoundPropagationProof [FINISHED, 0 ms] 15.59/5.66 (34) BOUNDS(n^1, INF) 15.59/5.66 15.59/5.66 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (0) 15.59/5.66 Obligation: 15.59/5.66 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 15.59/5.66 15.59/5.66 15.59/5.66 The TRS R consists of the following rules: 15.59/5.66 15.59/5.66 D(t) -> 1 15.59/5.66 D(constant) -> 0 15.59/5.66 D(+(x, y)) -> +(D(x), D(y)) 15.59/5.66 D(*(x, y)) -> +(*(y, D(x)), *(x, D(y))) 15.59/5.66 D(-(x, y)) -> -(D(x), D(y)) 15.59/5.66 15.59/5.66 S is empty. 15.59/5.66 Rewrite Strategy: FULL 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 15.59/5.66 Converted rc-obligation to irc-obligation. 15.59/5.66 15.59/5.66 As the TRS does not nest defined symbols, we have rc = irc. 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (2) 15.59/5.66 Obligation: 15.59/5.66 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 15.59/5.66 15.59/5.66 15.59/5.66 The TRS R consists of the following rules: 15.59/5.66 15.59/5.66 D(t) -> 1 15.59/5.66 D(constant) -> 0 15.59/5.66 D(+(x, y)) -> +(D(x), D(y)) 15.59/5.66 D(*(x, y)) -> +(*(y, D(x)), *(x, D(y))) 15.59/5.66 D(-(x, y)) -> -(D(x), D(y)) 15.59/5.66 15.59/5.66 S is empty. 15.59/5.66 Rewrite Strategy: INNERMOST 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 15.59/5.66 Transformed relative TRS to weighted TRS 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (4) 15.59/5.66 Obligation: 15.59/5.66 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 15.59/5.66 15.59/5.66 15.59/5.66 The TRS R consists of the following rules: 15.59/5.66 15.59/5.66 D(t) -> 1 [1] 15.59/5.66 D(constant) -> 0 [1] 15.59/5.66 D(+(x, y)) -> +(D(x), D(y)) [1] 15.59/5.66 D(*(x, y)) -> +(*(y, D(x)), *(x, D(y))) [1] 15.59/5.66 D(-(x, y)) -> -(D(x), D(y)) [1] 15.59/5.66 15.59/5.66 Rewrite Strategy: INNERMOST 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 15.59/5.66 Infered types. 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (6) 15.59/5.66 Obligation: 15.59/5.66 Runtime Complexity Weighted TRS with Types. 15.59/5.66 The TRS R consists of the following rules: 15.59/5.66 15.59/5.66 D(t) -> 1 [1] 15.59/5.66 D(constant) -> 0 [1] 15.59/5.66 D(+(x, y)) -> +(D(x), D(y)) [1] 15.59/5.66 D(*(x, y)) -> +(*(y, D(x)), *(x, D(y))) [1] 15.59/5.66 D(-(x, y)) -> -(D(x), D(y)) [1] 15.59/5.66 15.59/5.66 The TRS has the following type information: 15.59/5.66 D :: t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- 15.59/5.66 t :: t:1:constant:0:+:*:- 15.59/5.66 1 :: t:1:constant:0:+:*:- 15.59/5.66 constant :: t:1:constant:0:+:*:- 15.59/5.66 0 :: t:1:constant:0:+:*:- 15.59/5.66 + :: t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- 15.59/5.66 * :: t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- 15.59/5.66 - :: t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- 15.59/5.66 15.59/5.66 Rewrite Strategy: INNERMOST 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (7) CompletionProof (UPPER BOUND(ID)) 15.59/5.66 The transformation into a RNTS is sound, since: 15.59/5.66 15.59/5.66 (a) The obligation is a constructor system where every type has a constant constructor, 15.59/5.66 15.59/5.66 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 15.59/5.66 15.59/5.66 D_1 15.59/5.66 15.59/5.66 (c) The following functions are completely defined: 15.59/5.66 none 15.59/5.66 15.59/5.66 Due to the following rules being added: 15.59/5.66 none 15.59/5.66 15.59/5.66 And the following fresh constants: none 15.59/5.66 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (8) 15.59/5.66 Obligation: 15.59/5.66 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 15.59/5.66 15.59/5.66 Runtime Complexity Weighted TRS with Types. 15.59/5.66 The TRS R consists of the following rules: 15.59/5.66 15.59/5.66 D(t) -> 1 [1] 15.59/5.66 D(constant) -> 0 [1] 15.59/5.66 D(+(x, y)) -> +(D(x), D(y)) [1] 15.59/5.66 D(*(x, y)) -> +(*(y, D(x)), *(x, D(y))) [1] 15.59/5.66 D(-(x, y)) -> -(D(x), D(y)) [1] 15.59/5.66 15.59/5.66 The TRS has the following type information: 15.59/5.66 D :: t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- 15.59/5.66 t :: t:1:constant:0:+:*:- 15.59/5.66 1 :: t:1:constant:0:+:*:- 15.59/5.66 constant :: t:1:constant:0:+:*:- 15.59/5.66 0 :: t:1:constant:0:+:*:- 15.59/5.66 + :: t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- 15.59/5.66 * :: t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- 15.59/5.66 - :: t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- 15.59/5.66 15.59/5.66 Rewrite Strategy: INNERMOST 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (9) NarrowingProof (BOTH BOUNDS(ID, ID)) 15.59/5.66 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (10) 15.59/5.66 Obligation: 15.59/5.66 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 15.59/5.66 15.59/5.66 Runtime Complexity Weighted TRS with Types. 15.59/5.66 The TRS R consists of the following rules: 15.59/5.66 15.59/5.66 D(t) -> 1 [1] 15.59/5.66 D(constant) -> 0 [1] 15.59/5.66 D(+(x, y)) -> +(D(x), D(y)) [1] 15.59/5.66 D(*(x, y)) -> +(*(y, D(x)), *(x, D(y))) [1] 15.59/5.66 D(-(x, y)) -> -(D(x), D(y)) [1] 15.59/5.66 15.59/5.66 The TRS has the following type information: 15.59/5.66 D :: t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- 15.59/5.66 t :: t:1:constant:0:+:*:- 15.59/5.66 1 :: t:1:constant:0:+:*:- 15.59/5.66 constant :: t:1:constant:0:+:*:- 15.59/5.66 0 :: t:1:constant:0:+:*:- 15.59/5.66 + :: t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- 15.59/5.66 * :: t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- 15.59/5.66 - :: t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- -> t:1:constant:0:+:*:- 15.59/5.66 15.59/5.66 Rewrite Strategy: INNERMOST 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 15.59/5.66 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 15.59/5.66 The constant constructors are abstracted as follows: 15.59/5.66 15.59/5.66 t => 3 15.59/5.66 1 => 1 15.59/5.66 constant => 2 15.59/5.66 0 => 0 15.59/5.66 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (12) 15.59/5.66 Obligation: 15.59/5.66 Complexity RNTS consisting of the following rules: 15.59/5.66 15.59/5.66 D(z) -{ 1 }-> 1 :|: z = 3 15.59/5.66 D(z) -{ 1 }-> 0 :|: z = 2 15.59/5.66 D(z) -{ 1 }-> 1 + D(x) + D(y) :|: z = 1 + x + y, x >= 0, y >= 0 15.59/5.66 D(z) -{ 1 }-> 1 + (1 + y + D(x)) + (1 + x + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0 15.59/5.66 15.59/5.66 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (13) SimplificationProof (BOTH BOUNDS(ID, ID)) 15.59/5.66 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (14) 15.59/5.66 Obligation: 15.59/5.66 Complexity RNTS consisting of the following rules: 15.59/5.66 15.59/5.66 D(z) -{ 1 }-> 1 :|: z = 3 15.59/5.66 D(z) -{ 1 }-> 0 :|: z = 2 15.59/5.66 D(z) -{ 1 }-> 1 + D(x) + D(y) :|: z = 1 + x + y, x >= 0, y >= 0 15.59/5.66 D(z) -{ 1 }-> 1 + (1 + y + D(x)) + (1 + x + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0 15.59/5.66 15.59/5.66 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (15) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 15.59/5.66 Found the following analysis order by SCC decomposition: 15.59/5.66 15.59/5.66 { D } 15.59/5.66 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (16) 15.59/5.66 Obligation: 15.59/5.66 Complexity RNTS consisting of the following rules: 15.59/5.66 15.59/5.66 D(z) -{ 1 }-> 1 :|: z = 3 15.59/5.66 D(z) -{ 1 }-> 0 :|: z = 2 15.59/5.66 D(z) -{ 1 }-> 1 + D(x) + D(y) :|: z = 1 + x + y, x >= 0, y >= 0 15.59/5.66 D(z) -{ 1 }-> 1 + (1 + y + D(x)) + (1 + x + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0 15.59/5.66 15.59/5.66 Function symbols to be analyzed: {D} 15.59/5.66 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (17) ResultPropagationProof (UPPER BOUND(ID)) 15.59/5.66 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (18) 15.59/5.66 Obligation: 15.59/5.66 Complexity RNTS consisting of the following rules: 15.59/5.66 15.59/5.66 D(z) -{ 1 }-> 1 :|: z = 3 15.59/5.66 D(z) -{ 1 }-> 0 :|: z = 2 15.59/5.66 D(z) -{ 1 }-> 1 + D(x) + D(y) :|: z = 1 + x + y, x >= 0, y >= 0 15.59/5.66 D(z) -{ 1 }-> 1 + (1 + y + D(x)) + (1 + x + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0 15.59/5.66 15.59/5.66 Function symbols to be analyzed: {D} 15.59/5.66 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (19) IntTrsBoundProof (UPPER BOUND(ID)) 15.59/5.66 15.59/5.66 Computed SIZE bound using CoFloCo for: D 15.59/5.66 after applying outer abstraction to obtain an ITS, 15.59/5.66 resulting in: O(n^2) with polynomial bound: 1 + 2*z + z^2 15.59/5.66 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (20) 15.59/5.66 Obligation: 15.59/5.66 Complexity RNTS consisting of the following rules: 15.59/5.66 15.59/5.66 D(z) -{ 1 }-> 1 :|: z = 3 15.59/5.66 D(z) -{ 1 }-> 0 :|: z = 2 15.59/5.66 D(z) -{ 1 }-> 1 + D(x) + D(y) :|: z = 1 + x + y, x >= 0, y >= 0 15.59/5.66 D(z) -{ 1 }-> 1 + (1 + y + D(x)) + (1 + x + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0 15.59/5.66 15.59/5.66 Function symbols to be analyzed: {D} 15.59/5.66 Previous analysis results are: 15.59/5.66 D: runtime: ?, size: O(n^2) [1 + 2*z + z^2] 15.59/5.66 15.59/5.66 ---------------------------------------- 15.59/5.66 15.59/5.66 (21) IntTrsBoundProof (UPPER BOUND(ID)) 15.59/5.66 15.59/5.66 Computed RUNTIME bound using KoAT for: D 15.59/5.66 after applying outer abstraction to obtain an ITS, 15.59/5.67 resulting in: O(n^1) with polynomial bound: 3*z 15.59/5.67 15.59/5.67 ---------------------------------------- 15.59/5.67 15.59/5.67 (22) 15.59/5.67 Obligation: 15.59/5.67 Complexity RNTS consisting of the following rules: 15.59/5.67 15.59/5.67 D(z) -{ 1 }-> 1 :|: z = 3 15.59/5.67 D(z) -{ 1 }-> 0 :|: z = 2 15.59/5.67 D(z) -{ 1 }-> 1 + D(x) + D(y) :|: z = 1 + x + y, x >= 0, y >= 0 15.59/5.67 D(z) -{ 1 }-> 1 + (1 + y + D(x)) + (1 + x + D(y)) :|: z = 1 + x + y, x >= 0, y >= 0 15.59/5.67 15.59/5.67 Function symbols to be analyzed: 15.59/5.67 Previous analysis results are: 15.59/5.67 D: runtime: O(n^1) [3*z], size: O(n^2) [1 + 2*z + z^2] 15.59/5.67 15.59/5.67 ---------------------------------------- 15.59/5.67 15.59/5.67 (23) FinalProof (FINISHED) 15.59/5.67 Computed overall runtime complexity 15.59/5.67 ---------------------------------------- 15.59/5.67 15.59/5.67 (24) 15.59/5.67 BOUNDS(1, n^1) 15.59/5.67 15.59/5.67 ---------------------------------------- 15.59/5.67 15.59/5.67 (25) RenamingProof (BOTH BOUNDS(ID, ID)) 15.59/5.67 Renamed function symbols to avoid clashes with predefined symbol. 15.59/5.67 ---------------------------------------- 15.59/5.67 15.59/5.67 (26) 15.59/5.67 Obligation: 15.59/5.67 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 15.59/5.67 15.59/5.67 15.59/5.67 The TRS R consists of the following rules: 15.59/5.67 15.59/5.67 D(t) -> 1' 15.59/5.67 D(constant) -> 0' 15.59/5.67 D(+'(x, y)) -> +'(D(x), D(y)) 15.59/5.67 D(*'(x, y)) -> +'(*'(y, D(x)), *'(x, D(y))) 15.59/5.67 D(-(x, y)) -> -(D(x), D(y)) 15.59/5.67 15.59/5.67 S is empty. 15.59/5.67 Rewrite Strategy: FULL 15.59/5.67 ---------------------------------------- 15.59/5.67 15.59/5.67 (27) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 15.59/5.67 Infered types. 15.59/5.67 ---------------------------------------- 15.59/5.67 15.59/5.67 (28) 15.59/5.67 Obligation: 15.59/5.67 TRS: 15.59/5.67 Rules: 15.59/5.67 D(t) -> 1' 15.59/5.67 D(constant) -> 0' 15.59/5.67 D(+'(x, y)) -> +'(D(x), D(y)) 15.59/5.67 D(*'(x, y)) -> +'(*'(y, D(x)), *'(x, D(y))) 15.59/5.67 D(-(x, y)) -> -(D(x), D(y)) 15.59/5.67 15.59/5.67 Types: 15.59/5.67 D :: t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- 15.59/5.67 t :: t:1':constant:0':+':*':- 15.59/5.67 1' :: t:1':constant:0':+':*':- 15.59/5.67 constant :: t:1':constant:0':+':*':- 15.59/5.67 0' :: t:1':constant:0':+':*':- 15.59/5.67 +' :: t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- 15.59/5.67 *' :: t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- 15.59/5.67 - :: t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- 15.59/5.67 hole_t:1':constant:0':+':*':-1_0 :: t:1':constant:0':+':*':- 15.59/5.67 gen_t:1':constant:0':+':*':-2_0 :: Nat -> t:1':constant:0':+':*':- 15.59/5.67 15.59/5.67 ---------------------------------------- 15.59/5.67 15.59/5.67 (29) OrderProof (LOWER BOUND(ID)) 15.59/5.67 Heuristically decided to analyse the following defined symbols: 15.59/5.67 D 15.59/5.67 ---------------------------------------- 15.59/5.67 15.59/5.67 (30) 15.59/5.67 Obligation: 15.59/5.67 TRS: 15.59/5.67 Rules: 15.59/5.67 D(t) -> 1' 15.59/5.67 D(constant) -> 0' 15.59/5.67 D(+'(x, y)) -> +'(D(x), D(y)) 15.59/5.67 D(*'(x, y)) -> +'(*'(y, D(x)), *'(x, D(y))) 15.59/5.67 D(-(x, y)) -> -(D(x), D(y)) 15.59/5.67 15.59/5.67 Types: 15.59/5.67 D :: t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- 15.59/5.67 t :: t:1':constant:0':+':*':- 15.59/5.67 1' :: t:1':constant:0':+':*':- 15.59/5.67 constant :: t:1':constant:0':+':*':- 15.59/5.67 0' :: t:1':constant:0':+':*':- 15.59/5.67 +' :: t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- 15.59/5.67 *' :: t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- 15.59/5.67 - :: t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- 15.59/5.67 hole_t:1':constant:0':+':*':-1_0 :: t:1':constant:0':+':*':- 15.59/5.67 gen_t:1':constant:0':+':*':-2_0 :: Nat -> t:1':constant:0':+':*':- 15.59/5.67 15.59/5.67 15.59/5.67 Generator Equations: 15.59/5.67 gen_t:1':constant:0':+':*':-2_0(0) <=> t 15.59/5.67 gen_t:1':constant:0':+':*':-2_0(+(x, 1)) <=> +'(t, gen_t:1':constant:0':+':*':-2_0(x)) 15.59/5.67 15.59/5.67 15.59/5.67 The following defined symbols remain to be analysed: 15.59/5.67 D 15.59/5.67 ---------------------------------------- 15.59/5.67 15.59/5.67 (31) RewriteLemmaProof (LOWER BOUND(ID)) 15.59/5.67 Proved the following rewrite lemma: 15.59/5.67 D(gen_t:1':constant:0':+':*':-2_0(n4_0)) -> *3_0, rt in Omega(n4_0) 15.59/5.67 15.59/5.67 Induction Base: 15.59/5.67 D(gen_t:1':constant:0':+':*':-2_0(0)) 15.59/5.67 15.59/5.67 Induction Step: 15.59/5.67 D(gen_t:1':constant:0':+':*':-2_0(+(n4_0, 1))) ->_R^Omega(1) 15.59/5.67 +'(D(t), D(gen_t:1':constant:0':+':*':-2_0(n4_0))) ->_R^Omega(1) 15.59/5.67 +'(1', D(gen_t:1':constant:0':+':*':-2_0(n4_0))) ->_IH 15.59/5.67 +'(1', *3_0) 15.59/5.67 15.59/5.67 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 15.59/5.67 ---------------------------------------- 15.59/5.67 15.59/5.67 (32) 15.59/5.67 Obligation: 15.59/5.67 Proved the lower bound n^1 for the following obligation: 15.59/5.67 15.59/5.67 TRS: 15.59/5.67 Rules: 15.59/5.67 D(t) -> 1' 15.59/5.67 D(constant) -> 0' 15.59/5.67 D(+'(x, y)) -> +'(D(x), D(y)) 15.59/5.67 D(*'(x, y)) -> +'(*'(y, D(x)), *'(x, D(y))) 15.59/5.67 D(-(x, y)) -> -(D(x), D(y)) 15.59/5.67 15.59/5.67 Types: 15.59/5.67 D :: t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- 15.59/5.67 t :: t:1':constant:0':+':*':- 15.59/5.67 1' :: t:1':constant:0':+':*':- 15.59/5.67 constant :: t:1':constant:0':+':*':- 15.59/5.67 0' :: t:1':constant:0':+':*':- 15.59/5.67 +' :: t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- 15.59/5.67 *' :: t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- 15.59/5.67 - :: t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- -> t:1':constant:0':+':*':- 15.59/5.67 hole_t:1':constant:0':+':*':-1_0 :: t:1':constant:0':+':*':- 15.59/5.67 gen_t:1':constant:0':+':*':-2_0 :: Nat -> t:1':constant:0':+':*':- 15.59/5.67 15.59/5.67 15.59/5.67 Generator Equations: 15.59/5.67 gen_t:1':constant:0':+':*':-2_0(0) <=> t 15.59/5.67 gen_t:1':constant:0':+':*':-2_0(+(x, 1)) <=> +'(t, gen_t:1':constant:0':+':*':-2_0(x)) 15.59/5.67 15.59/5.67 15.59/5.67 The following defined symbols remain to be analysed: 15.59/5.67 D 15.59/5.67 ---------------------------------------- 15.59/5.67 15.59/5.67 (33) LowerBoundPropagationProof (FINISHED) 15.59/5.67 Propagated lower bound. 15.59/5.67 ---------------------------------------- 15.59/5.67 15.59/5.67 (34) 15.59/5.67 BOUNDS(n^1, INF) 15.59/5.70 EOF