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