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