/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: p(s(x)) -> x fac(0) -> s(0) fac(s(x)) -> times(s(x), fac(p(s(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: p(s(z0)) -> z0 fac(0) -> s(0) fac(s(z0)) -> times(s(z0), fac(p(s(z0)))) Tuples: P(s(z0)) -> c FAC(0) -> c1 FAC(s(z0)) -> c2(FAC(p(s(z0))), P(s(z0))) S tuples: P(s(z0)) -> c FAC(0) -> c1 FAC(s(z0)) -> c2(FAC(p(s(z0))), P(s(z0))) K tuples:none Defined Rule Symbols: p_1, fac_1 Defined Pair Symbols: P_1, FAC_1 Compound Symbols: c, c1, c2_2 ---------------------------------------- (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) Removed 2 trailing nodes: FAC(0) -> c1 P(s(z0)) -> c ---------------------------------------- (4) Obligation: Complexity Dependency Tuples Problem Rules: p(s(z0)) -> z0 fac(0) -> s(0) fac(s(z0)) -> times(s(z0), fac(p(s(z0)))) Tuples: FAC(s(z0)) -> c2(FAC(p(s(z0))), P(s(z0))) S tuples: FAC(s(z0)) -> c2(FAC(p(s(z0))), P(s(z0))) K tuples:none Defined Rule Symbols: p_1, fac_1 Defined Pair Symbols: FAC_1 Compound Symbols: c2_2 ---------------------------------------- (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules: p(s(z0)) -> z0 fac(0) -> s(0) fac(s(z0)) -> times(s(z0), fac(p(s(z0)))) Tuples: FAC(s(z0)) -> c2(FAC(p(s(z0)))) S tuples: FAC(s(z0)) -> c2(FAC(p(s(z0)))) K tuples:none Defined Rule Symbols: p_1, fac_1 Defined Pair Symbols: FAC_1 Compound Symbols: c2_1 ---------------------------------------- (7) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: fac(0) -> s(0) fac(s(z0)) -> times(s(z0), fac(p(s(z0)))) ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules: p(s(z0)) -> z0 Tuples: FAC(s(z0)) -> c2(FAC(p(s(z0)))) S tuples: FAC(s(z0)) -> c2(FAC(p(s(z0)))) K tuples:none Defined Rule Symbols: p_1 Defined Pair Symbols: FAC_1 Compound Symbols: c2_1 ---------------------------------------- (9) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) Use narrowing to replace FAC(s(z0)) -> c2(FAC(p(s(z0)))) by FAC(s(z0)) -> c2(FAC(z0)) ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules: p(s(z0)) -> z0 Tuples: FAC(s(z0)) -> c2(FAC(z0)) S tuples: FAC(s(z0)) -> c2(FAC(z0)) K tuples:none Defined Rule Symbols: p_1 Defined Pair Symbols: FAC_1 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: FAC(s(z0)) -> c2(FAC(z0)) S tuples: FAC(s(z0)) -> c2(FAC(z0)) K tuples:none Defined Rule Symbols:none Defined Pair Symbols: FAC_1 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. FAC(s(z0)) -> c2(FAC(z0)) We considered the (Usable) Rules:none And the Tuples: FAC(s(z0)) -> c2(FAC(z0)) The order we found is given by the following interpretation: Polynomial interpretation : POL(FAC(x_1)) = x_1 POL(c2(x_1)) = x_1 POL(s(x_1)) = [1] + x_1 ---------------------------------------- (14) Obligation: Complexity Dependency Tuples Problem Rules:none Tuples: FAC(s(z0)) -> c2(FAC(z0)) S tuples:none K tuples: FAC(s(z0)) -> c2(FAC(z0)) Defined Rule Symbols:none Defined Pair Symbols: FAC_1 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: p(s(x)) -> x fac(0) -> s(0) fac(s(x)) -> times(s(x), fac(p(s(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 fac(s(x)) ->^+ times(s(x), fac(x)) gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. The pumping substitution is [x / s(x)]. 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: p(s(x)) -> x fac(0) -> s(0) fac(s(x)) -> times(s(x), fac(p(s(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: p(s(x)) -> x fac(0) -> s(0) fac(s(x)) -> times(s(x), fac(p(s(x)))) S is empty. Rewrite Strategy: INNERMOST