/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^2)) proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). (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) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] (8) CdtProblem (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 3 ms] (10) CdtProblem (11) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] (12) CdtProblem (13) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (14) CdtProblem (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 24 ms] (16) CdtProblem (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 17 ms] (18) CdtProblem (19) CdtKnowledgeProof [FINISHED, 0 ms] (20) BOUNDS(1, 1) (21) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (22) TRS for Loop Detection (23) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] (24) BEST (25) proven lower bound (26) LowerBoundPropagationProof [FINISHED, 0 ms] (27) BOUNDS(n^1, INF) (28) TRS for Loop Detection ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: from(X) -> cons(X, n__from(s(X))) head(cons(X, XS)) -> X 2nd(cons(X, XS)) -> head(activate(XS)) take(0, XS) -> nil take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) sel(0, cons(X, XS)) -> X sel(s(N), cons(X, XS)) -> sel(N, activate(XS)) from(X) -> n__from(X) take(X1, X2) -> n__take(X1, X2) activate(n__from(X)) -> from(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(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: from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) head(cons(z0, z1)) -> z0 2nd(cons(z0, z1)) -> head(activate(z1)) take(0, z0) -> nil take(s(z0), cons(z1, z2)) -> cons(z1, n__take(z0, activate(z2))) take(z0, z1) -> n__take(z0, z1) sel(0, cons(z0, z1)) -> z0 sel(s(z0), cons(z1, z2)) -> sel(z0, activate(z2)) activate(n__from(z0)) -> from(z0) activate(n__take(z0, z1)) -> take(z0, z1) activate(z0) -> z0 Tuples: FROM(z0) -> c FROM(z0) -> c1 HEAD(cons(z0, z1)) -> c2 2ND(cons(z0, z1)) -> c3(HEAD(activate(z1)), ACTIVATE(z1)) TAKE(0, z0) -> c4 TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) TAKE(z0, z1) -> c6 SEL(0, cons(z0, z1)) -> c7 SEL(s(z0), cons(z1, z2)) -> c8(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__from(z0)) -> c9(FROM(z0)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) ACTIVATE(z0) -> c11 S tuples: FROM(z0) -> c FROM(z0) -> c1 HEAD(cons(z0, z1)) -> c2 2ND(cons(z0, z1)) -> c3(HEAD(activate(z1)), ACTIVATE(z1)) TAKE(0, z0) -> c4 TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) TAKE(z0, z1) -> c6 SEL(0, cons(z0, z1)) -> c7 SEL(s(z0), cons(z1, z2)) -> c8(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__from(z0)) -> c9(FROM(z0)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) ACTIVATE(z0) -> c11 K tuples:none Defined Rule Symbols: from_1, head_1, 2nd_1, take_2, sel_2, activate_1 Defined Pair Symbols: FROM_1, HEAD_1, 2ND_1, TAKE_2, SEL_2, ACTIVATE_1 Compound Symbols: c, c1, c2, c3_2, c4, c5_1, c6, c7, c8_2, c9_1, c10_1, c11 ---------------------------------------- (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) Removed 8 trailing nodes: ACTIVATE(n__from(z0)) -> c9(FROM(z0)) TAKE(z0, z1) -> c6 FROM(z0) -> c FROM(z0) -> c1 ACTIVATE(z0) -> c11 TAKE(0, z0) -> c4 SEL(0, cons(z0, z1)) -> c7 HEAD(cons(z0, z1)) -> c2 ---------------------------------------- (4) Obligation: Complexity Dependency Tuples Problem Rules: from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) head(cons(z0, z1)) -> z0 2nd(cons(z0, z1)) -> head(activate(z1)) take(0, z0) -> nil take(s(z0), cons(z1, z2)) -> cons(z1, n__take(z0, activate(z2))) take(z0, z1) -> n__take(z0, z1) sel(0, cons(z0, z1)) -> z0 sel(s(z0), cons(z1, z2)) -> sel(z0, activate(z2)) activate(n__from(z0)) -> from(z0) activate(n__take(z0, z1)) -> take(z0, z1) activate(z0) -> z0 Tuples: 2ND(cons(z0, z1)) -> c3(HEAD(activate(z1)), ACTIVATE(z1)) TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) SEL(s(z0), cons(z1, z2)) -> c8(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) S tuples: 2ND(cons(z0, z1)) -> c3(HEAD(activate(z1)), ACTIVATE(z1)) TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) SEL(s(z0), cons(z1, z2)) -> c8(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) K tuples:none Defined Rule Symbols: from_1, head_1, 2nd_1, take_2, sel_2, activate_1 Defined Pair Symbols: 2ND_1, TAKE_2, SEL_2, ACTIVATE_1 Compound Symbols: c3_2, c5_1, c8_2, c10_1 ---------------------------------------- (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules: from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) head(cons(z0, z1)) -> z0 2nd(cons(z0, z1)) -> head(activate(z1)) take(0, z0) -> nil take(s(z0), cons(z1, z2)) -> cons(z1, n__take(z0, activate(z2))) take(z0, z1) -> n__take(z0, z1) sel(0, cons(z0, z1)) -> z0 sel(s(z0), cons(z1, z2)) -> sel(z0, activate(z2)) activate(n__from(z0)) -> from(z0) activate(n__take(z0, z1)) -> take(z0, z1) activate(z0) -> z0 Tuples: TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) SEL(s(z0), cons(z1, z2)) -> c8(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) 2ND(cons(z0, z1)) -> c3(ACTIVATE(z1)) S tuples: TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) SEL(s(z0), cons(z1, z2)) -> c8(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) 2ND(cons(z0, z1)) -> c3(ACTIVATE(z1)) K tuples:none Defined Rule Symbols: from_1, head_1, 2nd_1, take_2, sel_2, activate_1 Defined Pair Symbols: TAKE_2, SEL_2, ACTIVATE_1, 2ND_1 Compound Symbols: c5_1, c8_2, c10_1, c3_1 ---------------------------------------- (7) CdtLeafRemovalProof (ComplexityIfPolyImplication) Removed 1 leading nodes: 2ND(cons(z0, z1)) -> c3(ACTIVATE(z1)) ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules: from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) head(cons(z0, z1)) -> z0 2nd(cons(z0, z1)) -> head(activate(z1)) take(0, z0) -> nil take(s(z0), cons(z1, z2)) -> cons(z1, n__take(z0, activate(z2))) take(z0, z1) -> n__take(z0, z1) sel(0, cons(z0, z1)) -> z0 sel(s(z0), cons(z1, z2)) -> sel(z0, activate(z2)) activate(n__from(z0)) -> from(z0) activate(n__take(z0, z1)) -> take(z0, z1) activate(z0) -> z0 Tuples: TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) SEL(s(z0), cons(z1, z2)) -> c8(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) S tuples: TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) SEL(s(z0), cons(z1, z2)) -> c8(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) K tuples:none Defined Rule Symbols: from_1, head_1, 2nd_1, take_2, sel_2, activate_1 Defined Pair Symbols: TAKE_2, SEL_2, ACTIVATE_1 Compound Symbols: c5_1, c8_2, c10_1 ---------------------------------------- (9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: head(cons(z0, z1)) -> z0 2nd(cons(z0, z1)) -> head(activate(z1)) sel(0, cons(z0, z1)) -> z0 sel(s(z0), cons(z1, z2)) -> sel(z0, activate(z2)) ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules: activate(n__from(z0)) -> from(z0) activate(n__take(z0, z1)) -> take(z0, z1) activate(z0) -> z0 from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) take(0, z0) -> nil take(s(z0), cons(z1, z2)) -> cons(z1, n__take(z0, activate(z2))) take(z0, z1) -> n__take(z0, z1) Tuples: TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) SEL(s(z0), cons(z1, z2)) -> c8(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) S tuples: TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) SEL(s(z0), cons(z1, z2)) -> c8(SEL(z0, activate(z2)), ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) K tuples:none Defined Rule Symbols: activate_1, from_1, take_2 Defined Pair Symbols: TAKE_2, SEL_2, ACTIVATE_1 Compound Symbols: c5_1, c8_2, c10_1 ---------------------------------------- (11) CdtNarrowingProof (BOTH BOUNDS(ID, ID)) Use narrowing to replace SEL(s(z0), cons(z1, z2)) -> c8(SEL(z0, activate(z2)), ACTIVATE(z2)) by SEL(s(x0), cons(x1, n__from(z0))) -> c8(SEL(x0, from(z0)), ACTIVATE(n__from(z0))) SEL(s(x0), cons(x1, n__take(z0, z1))) -> c8(SEL(x0, take(z0, z1)), ACTIVATE(n__take(z0, z1))) SEL(s(x0), cons(x1, z0)) -> c8(SEL(x0, z0), ACTIVATE(z0)) ---------------------------------------- (12) Obligation: Complexity Dependency Tuples Problem Rules: activate(n__from(z0)) -> from(z0) activate(n__take(z0, z1)) -> take(z0, z1) activate(z0) -> z0 from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) take(0, z0) -> nil take(s(z0), cons(z1, z2)) -> cons(z1, n__take(z0, activate(z2))) take(z0, z1) -> n__take(z0, z1) Tuples: TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) SEL(s(x0), cons(x1, n__from(z0))) -> c8(SEL(x0, from(z0)), ACTIVATE(n__from(z0))) SEL(s(x0), cons(x1, n__take(z0, z1))) -> c8(SEL(x0, take(z0, z1)), ACTIVATE(n__take(z0, z1))) SEL(s(x0), cons(x1, z0)) -> c8(SEL(x0, z0), ACTIVATE(z0)) S tuples: TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) SEL(s(x0), cons(x1, n__from(z0))) -> c8(SEL(x0, from(z0)), ACTIVATE(n__from(z0))) SEL(s(x0), cons(x1, n__take(z0, z1))) -> c8(SEL(x0, take(z0, z1)), ACTIVATE(n__take(z0, z1))) SEL(s(x0), cons(x1, z0)) -> c8(SEL(x0, z0), ACTIVATE(z0)) K tuples:none Defined Rule Symbols: activate_1, from_1, take_2 Defined Pair Symbols: TAKE_2, ACTIVATE_1, SEL_2 Compound Symbols: c5_1, c10_1, c8_2 ---------------------------------------- (13) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (14) Obligation: Complexity Dependency Tuples Problem Rules: activate(n__from(z0)) -> from(z0) activate(n__take(z0, z1)) -> take(z0, z1) activate(z0) -> z0 from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) take(0, z0) -> nil take(s(z0), cons(z1, z2)) -> cons(z1, n__take(z0, activate(z2))) take(z0, z1) -> n__take(z0, z1) Tuples: TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) SEL(s(x0), cons(x1, n__take(z0, z1))) -> c8(SEL(x0, take(z0, z1)), ACTIVATE(n__take(z0, z1))) SEL(s(x0), cons(x1, z0)) -> c8(SEL(x0, z0), ACTIVATE(z0)) SEL(s(x0), cons(x1, n__from(z0))) -> c8(SEL(x0, from(z0))) S tuples: TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) SEL(s(x0), cons(x1, n__take(z0, z1))) -> c8(SEL(x0, take(z0, z1)), ACTIVATE(n__take(z0, z1))) SEL(s(x0), cons(x1, z0)) -> c8(SEL(x0, z0), ACTIVATE(z0)) SEL(s(x0), cons(x1, n__from(z0))) -> c8(SEL(x0, from(z0))) K tuples:none Defined Rule Symbols: activate_1, from_1, take_2 Defined Pair Symbols: TAKE_2, ACTIVATE_1, SEL_2 Compound Symbols: c5_1, c10_1, c8_2, c8_1 ---------------------------------------- (15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. SEL(s(x0), cons(x1, n__take(z0, z1))) -> c8(SEL(x0, take(z0, z1)), ACTIVATE(n__take(z0, z1))) SEL(s(x0), cons(x1, z0)) -> c8(SEL(x0, z0), ACTIVATE(z0)) SEL(s(x0), cons(x1, n__from(z0))) -> c8(SEL(x0, from(z0))) We considered the (Usable) Rules:none And the Tuples: TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) SEL(s(x0), cons(x1, n__take(z0, z1))) -> c8(SEL(x0, take(z0, z1)), ACTIVATE(n__take(z0, z1))) SEL(s(x0), cons(x1, z0)) -> c8(SEL(x0, z0), ACTIVATE(z0)) SEL(s(x0), cons(x1, n__from(z0))) -> c8(SEL(x0, from(z0))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(ACTIVATE(x_1)) = 0 POL(SEL(x_1, x_2)) = x_1 POL(TAKE(x_1, x_2)) = 0 POL(activate(x_1)) = [1] + x_1 POL(c10(x_1)) = x_1 POL(c5(x_1)) = x_1 POL(c8(x_1)) = x_1 POL(c8(x_1, x_2)) = x_1 + x_2 POL(cons(x_1, x_2)) = x_1 POL(from(x_1)) = [1] + x_1 POL(n__from(x_1)) = [1] + x_1 POL(n__take(x_1, x_2)) = x_1 POL(nil) = [1] POL(s(x_1)) = [1] + x_1 POL(take(x_1, x_2)) = [1] ---------------------------------------- (16) Obligation: Complexity Dependency Tuples Problem Rules: activate(n__from(z0)) -> from(z0) activate(n__take(z0, z1)) -> take(z0, z1) activate(z0) -> z0 from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) take(0, z0) -> nil take(s(z0), cons(z1, z2)) -> cons(z1, n__take(z0, activate(z2))) take(z0, z1) -> n__take(z0, z1) Tuples: TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) SEL(s(x0), cons(x1, n__take(z0, z1))) -> c8(SEL(x0, take(z0, z1)), ACTIVATE(n__take(z0, z1))) SEL(s(x0), cons(x1, z0)) -> c8(SEL(x0, z0), ACTIVATE(z0)) SEL(s(x0), cons(x1, n__from(z0))) -> c8(SEL(x0, from(z0))) S tuples: TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) K tuples: SEL(s(x0), cons(x1, n__take(z0, z1))) -> c8(SEL(x0, take(z0, z1)), ACTIVATE(n__take(z0, z1))) SEL(s(x0), cons(x1, z0)) -> c8(SEL(x0, z0), ACTIVATE(z0)) SEL(s(x0), cons(x1, n__from(z0))) -> c8(SEL(x0, from(z0))) Defined Rule Symbols: activate_1, from_1, take_2 Defined Pair Symbols: TAKE_2, ACTIVATE_1, SEL_2 Compound Symbols: c5_1, c10_1, c8_2, c8_1 ---------------------------------------- (17) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) We considered the (Usable) Rules: take(z0, z1) -> n__take(z0, z1) from(z0) -> cons(z0, n__from(s(z0))) take(s(z0), cons(z1, z2)) -> cons(z1, n__take(z0, activate(z2))) activate(n__take(z0, z1)) -> take(z0, z1) take(0, z0) -> nil from(z0) -> n__from(z0) activate(n__from(z0)) -> from(z0) activate(z0) -> z0 And the Tuples: TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) SEL(s(x0), cons(x1, n__take(z0, z1))) -> c8(SEL(x0, take(z0, z1)), ACTIVATE(n__take(z0, z1))) SEL(s(x0), cons(x1, z0)) -> c8(SEL(x0, z0), ACTIVATE(z0)) SEL(s(x0), cons(x1, n__from(z0))) -> c8(SEL(x0, from(z0))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [2] POL(ACTIVATE(x_1)) = x_1 POL(SEL(x_1, x_2)) = x_1*x_2 POL(TAKE(x_1, x_2)) = x_1 + x_2 POL(activate(x_1)) = x_1 POL(c10(x_1)) = x_1 POL(c5(x_1)) = x_1 POL(c8(x_1)) = x_1 POL(c8(x_1, x_2)) = x_1 + x_2 POL(cons(x_1, x_2)) = x_2 POL(from(x_1)) = 0 POL(n__from(x_1)) = 0 POL(n__take(x_1, x_2)) = x_1 + x_2 POL(nil) = [2] POL(s(x_1)) = [1] + x_1 POL(take(x_1, x_2)) = x_1 + x_2 ---------------------------------------- (18) Obligation: Complexity Dependency Tuples Problem Rules: activate(n__from(z0)) -> from(z0) activate(n__take(z0, z1)) -> take(z0, z1) activate(z0) -> z0 from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) take(0, z0) -> nil take(s(z0), cons(z1, z2)) -> cons(z1, n__take(z0, activate(z2))) take(z0, z1) -> n__take(z0, z1) Tuples: TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) SEL(s(x0), cons(x1, n__take(z0, z1))) -> c8(SEL(x0, take(z0, z1)), ACTIVATE(n__take(z0, z1))) SEL(s(x0), cons(x1, z0)) -> c8(SEL(x0, z0), ACTIVATE(z0)) SEL(s(x0), cons(x1, n__from(z0))) -> c8(SEL(x0, from(z0))) S tuples: ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) K tuples: SEL(s(x0), cons(x1, n__take(z0, z1))) -> c8(SEL(x0, take(z0, z1)), ACTIVATE(n__take(z0, z1))) SEL(s(x0), cons(x1, z0)) -> c8(SEL(x0, z0), ACTIVATE(z0)) SEL(s(x0), cons(x1, n__from(z0))) -> c8(SEL(x0, from(z0))) TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) Defined Rule Symbols: activate_1, from_1, take_2 Defined Pair Symbols: TAKE_2, ACTIVATE_1, SEL_2 Compound Symbols: c5_1, c10_1, c8_2, c8_1 ---------------------------------------- (19) CdtKnowledgeProof (FINISHED) The following tuples could be moved from S to K by knowledge propagation: ACTIVATE(n__take(z0, z1)) -> c10(TAKE(z0, z1)) TAKE(s(z0), cons(z1, z2)) -> c5(ACTIVATE(z2)) Now S is empty ---------------------------------------- (20) BOUNDS(1, 1) ---------------------------------------- (21) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (22) 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^2). The TRS R consists of the following rules: from(X) -> cons(X, n__from(s(X))) head(cons(X, XS)) -> X 2nd(cons(X, XS)) -> head(activate(XS)) take(0, XS) -> nil take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) sel(0, cons(X, XS)) -> X sel(s(N), cons(X, XS)) -> sel(N, activate(XS)) from(X) -> n__from(X) take(X1, X2) -> n__take(X1, X2) activate(n__from(X)) -> from(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(X) -> X S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (23) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence sel(s(N), cons(X, XS)) ->^+ sel(N, XS) gives rise to a decreasing loop by considering the right hand sides subterm at position []. The pumping substitution is [N / s(N), XS / cons(X, XS)]. The result substitution is [ ]. ---------------------------------------- (24) Complex Obligation (BEST) ---------------------------------------- (25) 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^2). The TRS R consists of the following rules: from(X) -> cons(X, n__from(s(X))) head(cons(X, XS)) -> X 2nd(cons(X, XS)) -> head(activate(XS)) take(0, XS) -> nil take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) sel(0, cons(X, XS)) -> X sel(s(N), cons(X, XS)) -> sel(N, activate(XS)) from(X) -> n__from(X) take(X1, X2) -> n__take(X1, X2) activate(n__from(X)) -> from(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(X) -> X S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (26) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (27) BOUNDS(n^1, INF) ---------------------------------------- (28) 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^2). The TRS R consists of the following rules: from(X) -> cons(X, n__from(s(X))) head(cons(X, XS)) -> X 2nd(cons(X, XS)) -> head(activate(XS)) take(0, XS) -> nil take(s(N), cons(X, XS)) -> cons(X, n__take(N, activate(XS))) sel(0, cons(X, XS)) -> X sel(s(N), cons(X, XS)) -> sel(N, activate(XS)) from(X) -> n__from(X) take(X1, X2) -> n__take(X1, X2) activate(n__from(X)) -> from(X) activate(n__take(X1, X2)) -> take(X1, X2) activate(X) -> X S is empty. Rewrite Strategy: INNERMOST