19.99/6.63 WORST_CASE(Omega(n^1), O(n^1)) 19.99/6.65 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 19.99/6.65 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 19.99/6.65 19.99/6.65 19.99/6.65 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 19.99/6.65 19.99/6.65 (0) CpxTRS 19.99/6.65 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 19.99/6.65 (2) CpxTRS 19.99/6.65 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 19.99/6.65 (4) CpxWeightedTrs 19.99/6.65 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 19.99/6.65 (6) CpxTypedWeightedTrs 19.99/6.65 (7) CompletionProof [UPPER BOUND(ID), 0 ms] 19.99/6.65 (8) CpxTypedWeightedCompleteTrs 19.99/6.65 (9) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 19.99/6.65 (10) CpxTypedWeightedCompleteTrs 19.99/6.65 (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 19.99/6.65 (12) CpxRNTS 19.99/6.65 (13) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 19.99/6.65 (14) CpxRNTS 19.99/6.65 (15) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] 19.99/6.65 (16) CpxRNTS 19.99/6.65 (17) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 19.99/6.65 (18) CpxRNTS 19.99/6.65 (19) IntTrsBoundProof [UPPER BOUND(ID), 633 ms] 19.99/6.65 (20) CpxRNTS 19.99/6.65 (21) IntTrsBoundProof [UPPER BOUND(ID), 243 ms] 19.99/6.65 (22) CpxRNTS 19.99/6.65 (23) FinalProof [FINISHED, 0 ms] 19.99/6.65 (24) BOUNDS(1, n^1) 19.99/6.65 (25) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 19.99/6.65 (26) TRS for Loop Detection 19.99/6.65 (27) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 19.99/6.65 (28) BEST 19.99/6.65 (29) proven lower bound 19.99/6.65 (30) LowerBoundPropagationProof [FINISHED, 0 ms] 19.99/6.65 (31) BOUNDS(n^1, INF) 19.99/6.65 (32) TRS for Loop Detection 19.99/6.65 19.99/6.65 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (0) 19.99/6.65 Obligation: 19.99/6.65 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 19.99/6.65 19.99/6.65 19.99/6.65 The TRS R consists of the following rules: 19.99/6.65 19.99/6.65 f(empty, l) -> l 19.99/6.65 f(cons(x, k), l) -> g(k, l, cons(x, k)) 19.99/6.65 g(a, b, c) -> f(a, cons(b, c)) 19.99/6.65 19.99/6.65 S is empty. 19.99/6.65 Rewrite Strategy: FULL 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 19.99/6.65 Converted rc-obligation to irc-obligation. 19.99/6.65 19.99/6.65 As the TRS does not nest defined symbols, we have rc = irc. 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (2) 19.99/6.65 Obligation: 19.99/6.65 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 19.99/6.65 19.99/6.65 19.99/6.65 The TRS R consists of the following rules: 19.99/6.65 19.99/6.65 f(empty, l) -> l 19.99/6.65 f(cons(x, k), l) -> g(k, l, cons(x, k)) 19.99/6.65 g(a, b, c) -> f(a, cons(b, c)) 19.99/6.65 19.99/6.65 S is empty. 19.99/6.65 Rewrite Strategy: INNERMOST 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 19.99/6.65 Transformed relative TRS to weighted TRS 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (4) 19.99/6.65 Obligation: 19.99/6.65 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 19.99/6.65 19.99/6.65 19.99/6.65 The TRS R consists of the following rules: 19.99/6.65 19.99/6.65 f(empty, l) -> l [1] 19.99/6.65 f(cons(x, k), l) -> g(k, l, cons(x, k)) [1] 19.99/6.65 g(a, b, c) -> f(a, cons(b, c)) [1] 19.99/6.65 19.99/6.65 Rewrite Strategy: INNERMOST 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 19.99/6.65 Infered types. 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (6) 19.99/6.65 Obligation: 19.99/6.65 Runtime Complexity Weighted TRS with Types. 19.99/6.65 The TRS R consists of the following rules: 19.99/6.65 19.99/6.65 f(empty, l) -> l [1] 19.99/6.65 f(cons(x, k), l) -> g(k, l, cons(x, k)) [1] 19.99/6.65 g(a, b, c) -> f(a, cons(b, c)) [1] 19.99/6.65 19.99/6.65 The TRS has the following type information: 19.99/6.65 f :: empty:cons -> empty:cons -> empty:cons 19.99/6.65 empty :: empty:cons 19.99/6.65 cons :: empty:cons -> empty:cons -> empty:cons 19.99/6.65 g :: empty:cons -> empty:cons -> empty:cons -> empty:cons 19.99/6.65 19.99/6.65 Rewrite Strategy: INNERMOST 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (7) CompletionProof (UPPER BOUND(ID)) 19.99/6.65 The transformation into a RNTS is sound, since: 19.99/6.65 19.99/6.65 (a) The obligation is a constructor system where every type has a constant constructor, 19.99/6.65 19.99/6.65 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 19.99/6.65 19.99/6.65 f_2 19.99/6.65 g_3 19.99/6.65 19.99/6.65 (c) The following functions are completely defined: 19.99/6.65 none 19.99/6.65 19.99/6.65 Due to the following rules being added: 19.99/6.65 none 19.99/6.65 19.99/6.65 And the following fresh constants: none 19.99/6.65 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (8) 19.99/6.65 Obligation: 19.99/6.65 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 19.99/6.65 19.99/6.65 Runtime Complexity Weighted TRS with Types. 19.99/6.65 The TRS R consists of the following rules: 19.99/6.65 19.99/6.65 f(empty, l) -> l [1] 19.99/6.65 f(cons(x, k), l) -> g(k, l, cons(x, k)) [1] 19.99/6.65 g(a, b, c) -> f(a, cons(b, c)) [1] 19.99/6.65 19.99/6.65 The TRS has the following type information: 19.99/6.65 f :: empty:cons -> empty:cons -> empty:cons 19.99/6.65 empty :: empty:cons 19.99/6.65 cons :: empty:cons -> empty:cons -> empty:cons 19.99/6.65 g :: empty:cons -> empty:cons -> empty:cons -> empty:cons 19.99/6.65 19.99/6.65 Rewrite Strategy: INNERMOST 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (9) NarrowingProof (BOTH BOUNDS(ID, ID)) 19.99/6.65 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (10) 19.99/6.65 Obligation: 19.99/6.65 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 19.99/6.65 19.99/6.65 Runtime Complexity Weighted TRS with Types. 19.99/6.65 The TRS R consists of the following rules: 19.99/6.65 19.99/6.65 f(empty, l) -> l [1] 19.99/6.65 f(cons(x, k), l) -> g(k, l, cons(x, k)) [1] 19.99/6.65 g(a, b, c) -> f(a, cons(b, c)) [1] 19.99/6.65 19.99/6.65 The TRS has the following type information: 19.99/6.65 f :: empty:cons -> empty:cons -> empty:cons 19.99/6.65 empty :: empty:cons 19.99/6.65 cons :: empty:cons -> empty:cons -> empty:cons 19.99/6.65 g :: empty:cons -> empty:cons -> empty:cons -> empty:cons 19.99/6.65 19.99/6.65 Rewrite Strategy: INNERMOST 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 19.99/6.65 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 19.99/6.65 The constant constructors are abstracted as follows: 19.99/6.65 19.99/6.65 empty => 0 19.99/6.65 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (12) 19.99/6.65 Obligation: 19.99/6.65 Complexity RNTS consisting of the following rules: 19.99/6.65 19.99/6.65 f(z, z') -{ 1 }-> l :|: z' = l, l >= 0, z = 0 19.99/6.65 f(z, z') -{ 1 }-> g(k, l, 1 + x + k) :|: z' = l, x >= 0, l >= 0, k >= 0, z = 1 + x + k 19.99/6.65 g(z, z', z'') -{ 1 }-> f(a, 1 + b + c) :|: z = a, b >= 0, a >= 0, c >= 0, z' = b, z'' = c 19.99/6.65 19.99/6.65 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (13) SimplificationProof (BOTH BOUNDS(ID, ID)) 19.99/6.65 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (14) 19.99/6.65 Obligation: 19.99/6.65 Complexity RNTS consisting of the following rules: 19.99/6.65 19.99/6.65 f(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 19.99/6.65 f(z, z') -{ 1 }-> g(k, z', 1 + x + k) :|: x >= 0, z' >= 0, k >= 0, z = 1 + x + k 19.99/6.65 g(z, z', z'') -{ 1 }-> f(z, 1 + z' + z'') :|: z' >= 0, z >= 0, z'' >= 0 19.99/6.65 19.99/6.65 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (15) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 19.99/6.65 Found the following analysis order by SCC decomposition: 19.99/6.65 19.99/6.65 { f, g } 19.99/6.65 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (16) 19.99/6.65 Obligation: 19.99/6.65 Complexity RNTS consisting of the following rules: 19.99/6.65 19.99/6.65 f(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 19.99/6.65 f(z, z') -{ 1 }-> g(k, z', 1 + x + k) :|: x >= 0, z' >= 0, k >= 0, z = 1 + x + k 19.99/6.65 g(z, z', z'') -{ 1 }-> f(z, 1 + z' + z'') :|: z' >= 0, z >= 0, z'' >= 0 19.99/6.65 19.99/6.65 Function symbols to be analyzed: {f,g} 19.99/6.65 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (17) ResultPropagationProof (UPPER BOUND(ID)) 19.99/6.65 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (18) 19.99/6.65 Obligation: 19.99/6.65 Complexity RNTS consisting of the following rules: 19.99/6.65 19.99/6.65 f(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 19.99/6.65 f(z, z') -{ 1 }-> g(k, z', 1 + x + k) :|: x >= 0, z' >= 0, k >= 0, z = 1 + x + k 19.99/6.65 g(z, z', z'') -{ 1 }-> f(z, 1 + z' + z'') :|: z' >= 0, z >= 0, z'' >= 0 19.99/6.65 19.99/6.65 Function symbols to be analyzed: {f,g} 19.99/6.65 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (19) IntTrsBoundProof (UPPER BOUND(ID)) 19.99/6.65 19.99/6.65 Computed SIZE bound using CoFloCo for: f 19.99/6.65 after applying outer abstraction to obtain an ITS, 19.99/6.65 resulting in: O(n^2) with polynomial bound: z + z^2 + z' 19.99/6.65 19.99/6.65 Computed SIZE bound using KoAT for: g 19.99/6.65 after applying outer abstraction to obtain an ITS, 19.99/6.65 resulting in: O(n^2) with polynomial bound: 1 + z + z^2 + z' + z'' 19.99/6.65 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (20) 19.99/6.65 Obligation: 19.99/6.65 Complexity RNTS consisting of the following rules: 19.99/6.65 19.99/6.65 f(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 19.99/6.65 f(z, z') -{ 1 }-> g(k, z', 1 + x + k) :|: x >= 0, z' >= 0, k >= 0, z = 1 + x + k 19.99/6.65 g(z, z', z'') -{ 1 }-> f(z, 1 + z' + z'') :|: z' >= 0, z >= 0, z'' >= 0 19.99/6.65 19.99/6.65 Function symbols to be analyzed: {f,g} 19.99/6.65 Previous analysis results are: 19.99/6.65 f: runtime: ?, size: O(n^2) [z + z^2 + z'] 19.99/6.65 g: runtime: ?, size: O(n^2) [1 + z + z^2 + z' + z''] 19.99/6.65 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (21) IntTrsBoundProof (UPPER BOUND(ID)) 19.99/6.65 19.99/6.65 Computed RUNTIME bound using CoFloCo for: f 19.99/6.65 after applying outer abstraction to obtain an ITS, 19.99/6.65 resulting in: O(n^1) with polynomial bound: 3 + 2*z 19.99/6.65 19.99/6.65 Computed RUNTIME bound using CoFloCo for: g 19.99/6.65 after applying outer abstraction to obtain an ITS, 19.99/6.65 resulting in: O(n^1) with polynomial bound: 4 + 2*z 19.99/6.65 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (22) 19.99/6.65 Obligation: 19.99/6.65 Complexity RNTS consisting of the following rules: 19.99/6.65 19.99/6.65 f(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 19.99/6.65 f(z, z') -{ 1 }-> g(k, z', 1 + x + k) :|: x >= 0, z' >= 0, k >= 0, z = 1 + x + k 19.99/6.65 g(z, z', z'') -{ 1 }-> f(z, 1 + z' + z'') :|: z' >= 0, z >= 0, z'' >= 0 19.99/6.65 19.99/6.65 Function symbols to be analyzed: 19.99/6.65 Previous analysis results are: 19.99/6.65 f: runtime: O(n^1) [3 + 2*z], size: O(n^2) [z + z^2 + z'] 19.99/6.65 g: runtime: O(n^1) [4 + 2*z], size: O(n^2) [1 + z + z^2 + z' + z''] 19.99/6.65 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (23) FinalProof (FINISHED) 19.99/6.65 Computed overall runtime complexity 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (24) 19.99/6.65 BOUNDS(1, n^1) 19.99/6.65 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (25) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 19.99/6.65 Transformed a relative TRS into a decreasing-loop problem. 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (26) 19.99/6.65 Obligation: 19.99/6.65 Analyzing the following TRS for decreasing loops: 19.99/6.65 19.99/6.65 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 19.99/6.65 19.99/6.65 19.99/6.65 The TRS R consists of the following rules: 19.99/6.65 19.99/6.65 f(empty, l) -> l 19.99/6.65 f(cons(x, k), l) -> g(k, l, cons(x, k)) 19.99/6.65 g(a, b, c) -> f(a, cons(b, c)) 19.99/6.65 19.99/6.65 S is empty. 19.99/6.65 Rewrite Strategy: FULL 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (27) DecreasingLoopProof (LOWER BOUND(ID)) 19.99/6.65 The following loop(s) give(s) rise to the lower bound Omega(n^1): 19.99/6.65 19.99/6.65 The rewrite sequence 19.99/6.65 19.99/6.65 g(cons(x1_0, k2_0), b, c) ->^+ g(k2_0, cons(b, c), cons(x1_0, k2_0)) 19.99/6.65 19.99/6.65 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 19.99/6.65 19.99/6.65 The pumping substitution is [k2_0 / cons(x1_0, k2_0)]. 19.99/6.65 19.99/6.65 The result substitution is [b / cons(b, c), c / cons(x1_0, k2_0)]. 19.99/6.65 19.99/6.65 19.99/6.65 19.99/6.65 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (28) 19.99/6.65 Complex Obligation (BEST) 19.99/6.65 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (29) 19.99/6.65 Obligation: 19.99/6.65 Proved the lower bound n^1 for the following obligation: 19.99/6.65 19.99/6.65 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 19.99/6.65 19.99/6.65 19.99/6.65 The TRS R consists of the following rules: 19.99/6.65 19.99/6.65 f(empty, l) -> l 19.99/6.65 f(cons(x, k), l) -> g(k, l, cons(x, k)) 19.99/6.65 g(a, b, c) -> f(a, cons(b, c)) 19.99/6.65 19.99/6.65 S is empty. 19.99/6.65 Rewrite Strategy: FULL 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (30) LowerBoundPropagationProof (FINISHED) 19.99/6.65 Propagated lower bound. 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (31) 19.99/6.65 BOUNDS(n^1, INF) 19.99/6.65 19.99/6.65 ---------------------------------------- 19.99/6.65 19.99/6.65 (32) 19.99/6.65 Obligation: 19.99/6.65 Analyzing the following TRS for decreasing loops: 19.99/6.65 19.99/6.65 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 19.99/6.65 19.99/6.65 19.99/6.65 The TRS R consists of the following rules: 19.99/6.65 19.99/6.65 f(empty, l) -> l 19.99/6.65 f(cons(x, k), l) -> g(k, l, cons(x, k)) 19.99/6.65 g(a, b, c) -> f(a, cons(b, c)) 19.99/6.65 19.99/6.65 S is empty. 19.99/6.65 Rewrite Strategy: FULL 20.17/6.72 EOF