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