/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). (0) CpxTRS (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] (2) CdtProblem (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] (4) CdtProblem (5) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CdtProblem (7) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CdtProblem (9) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CdtProblem (11) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (12) CdtProblem (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 0 ms] (14) CdtProblem (15) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] (16) BOUNDS(1, 1) (17) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (18) TRS for Loop Detection (19) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] (20) BEST (21) proven lower bound (22) LowerBoundPropagationProof [FINISHED, 0 ms] (23) BOUNDS(n^1, INF) (24) TRS for Loop Detection ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: -(0, y) -> 0 -(x, 0) -> x -(x, s(y)) -> if(greater(x, s(y)), s(-(x, p(s(y)))), 0) p(0) -> 0 p(s(x)) -> x S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (2) Obligation: Complexity Dependency Tuples Problem Rules: -(0, z0) -> 0 -(z0, 0) -> z0 -(z0, s(z1)) -> if(greater(z0, s(z1)), s(-(z0, p(s(z1)))), 0) p(0) -> 0 p(s(z0)) -> z0 Tuples: -'(0, z0) -> c -'(z0, 0) -> c1 -'(z0, s(z1)) -> c2(-'(z0, p(s(z1))), P(s(z1))) P(0) -> c3 P(s(z0)) -> c4 S tuples: -'(0, z0) -> c -'(z0, 0) -> c1 -'(z0, s(z1)) -> c2(-'(z0, p(s(z1))), P(s(z1))) P(0) -> c3 P(s(z0)) -> c4 K tuples:none Defined Rule Symbols: -_2, p_1 Defined Pair Symbols: -'_2, P_1 Compound Symbols: c, c1, c2_2, c3, c4 ---------------------------------------- (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) Removed 4 trailing nodes: P(0) -> c3 P(s(z0)) -> c4 -'(0, z0) -> c -'(z0, 0) -> c1 ---------------------------------------- (4) Obligation: Complexity Dependency Tuples Problem Rules: -(0, z0) -> 0 -(z0, 0) -> z0 -(z0, s(z1)) -> if(greater(z0, s(z1)), s(-(z0, p(s(z1)))), 0) p(0) -> 0 p(s(z0)) -> z0 Tuples: -'(z0, s(z1)) -> c2(-'(z0, p(s(z1))), P(s(z1))) S tuples: -'(z0, s(z1)) -> c2(-'(z0, p(s(z1))), P(s(z1))) K tuples:none Defined Rule Symbols: -_2, p_1 Defined Pair Symbols: -'_2 Compound Symbols: c2_2 ---------------------------------------- (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules: -(0, z0) -> 0 -(z0, 0) -> z0 -(z0, s(z1)) -> if(greater(z0, s(z1)), s(-(z0, p(s(z1)))), 0) p(0) -> 0 p(s(z0)) -> z0 Tuples: -'(z0, s(z1)) -> c2(-'(z0, p(s(z1)))) S tuples: -'(z0, s(z1)) -> c2(-'(z0, p(s(z1)))) K tuples:none Defined Rule Symbols: -_2, p_1 Defined Pair Symbols: -'_2 Compound Symbols: c2_1 ---------------------------------------- (7) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: -(0, z0) -> 0 -(z0, 0) -> z0 -(z0, s(z1)) -> if(greater(z0, s(z1)), s(-(z0, p(s(z1)))), 0) p(0) -> 0 ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules: p(s(z0)) -> z0 Tuples: -'(z0, s(z1)) -> c2(-'(z0, p(s(z1)))) S tuples: -'(z0, s(z1)) -> c2(-'(z0, p(s(z1)))) K tuples:none Defined Rule Symbols: p_1 Defined Pair Symbols: -'_2 Compound Symbols: c2_1 ---------------------------------------- (9) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) Use narrowing to replace -'(z0, s(z1)) -> c2(-'(z0, p(s(z1)))) by -'(x0, s(z0)) -> c2(-'(x0, z0)) ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules: p(s(z0)) -> z0 Tuples: -'(x0, s(z0)) -> c2(-'(x0, z0)) S tuples: -'(x0, s(z0)) -> c2(-'(x0, z0)) K tuples:none Defined Rule Symbols: p_1 Defined Pair Symbols: -'_2 Compound Symbols: c2_1 ---------------------------------------- (11) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: p(s(z0)) -> z0 ---------------------------------------- (12) Obligation: Complexity Dependency Tuples Problem Rules:none Tuples: -'(x0, s(z0)) -> c2(-'(x0, z0)) S tuples: -'(x0, s(z0)) -> c2(-'(x0, z0)) K tuples:none Defined Rule Symbols:none Defined Pair Symbols: -'_2 Compound Symbols: c2_1 ---------------------------------------- (13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. -'(x0, s(z0)) -> c2(-'(x0, z0)) We considered the (Usable) Rules:none And the Tuples: -'(x0, s(z0)) -> c2(-'(x0, z0)) The order we found is given by the following interpretation: Polynomial interpretation : POL(-'(x_1, x_2)) = x_2 POL(c2(x_1)) = x_1 POL(s(x_1)) = [1] + x_1 ---------------------------------------- (14) Obligation: Complexity Dependency Tuples Problem Rules:none Tuples: -'(x0, s(z0)) -> c2(-'(x0, z0)) S tuples:none K tuples: -'(x0, s(z0)) -> c2(-'(x0, z0)) Defined Rule Symbols:none Defined Pair Symbols: -'_2 Compound Symbols: c2_1 ---------------------------------------- (15) SIsEmptyProof (BOTH BOUNDS(ID, ID)) The set S is empty ---------------------------------------- (16) BOUNDS(1, 1) ---------------------------------------- (17) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (18) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: -(0, y) -> 0 -(x, 0) -> x -(x, s(y)) -> if(greater(x, s(y)), s(-(x, p(s(y)))), 0) p(0) -> 0 p(s(x)) -> x S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (19) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence -(x, s(y)) ->^+ if(greater(x, s(y)), s(-(x, y)), 0) gives rise to a decreasing loop by considering the right hand sides subterm at position [1,0]. The pumping substitution is [y / s(y)]. The result substitution is [ ]. ---------------------------------------- (20) Complex Obligation (BEST) ---------------------------------------- (21) Obligation: Proved the lower bound n^1 for the following obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: -(0, y) -> 0 -(x, 0) -> x -(x, s(y)) -> if(greater(x, s(y)), s(-(x, p(s(y)))), 0) p(0) -> 0 p(s(x)) -> x S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (22) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (23) BOUNDS(n^1, INF) ---------------------------------------- (24) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: -(0, y) -> 0 -(x, 0) -> x -(x, s(y)) -> if(greater(x, s(y)), s(-(x, p(s(y)))), 0) p(0) -> 0 p(s(x)) -> x S is empty. Rewrite Strategy: INNERMOST