333.96/291.54 WORST_CASE(Omega(n^1), O(n^2)) 333.96/291.55 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 333.96/291.55 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 333.96/291.55 333.96/291.55 333.96/291.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 333.96/291.55 333.96/291.55 (0) CpxTRS 333.96/291.55 (1) CpxTrsToCdtProof [UPPER BOUND(ID), 5 ms] 333.96/291.55 (2) CdtProblem 333.96/291.55 (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 333.96/291.55 (4) CdtProblem 333.96/291.55 (5) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 333.96/291.55 (6) CdtProblem 333.96/291.55 (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 91 ms] 333.96/291.55 (8) CdtProblem 333.96/291.55 (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 34 ms] 333.96/291.55 (10) CdtProblem 333.96/291.55 (11) CdtKnowledgeProof [FINISHED, 0 ms] 333.96/291.55 (12) BOUNDS(1, 1) 333.96/291.55 (13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 333.96/291.55 (14) TRS for Loop Detection 333.96/291.55 (15) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 333.96/291.55 (16) BEST 333.96/291.55 (17) proven lower bound 333.96/291.55 (18) LowerBoundPropagationProof [FINISHED, 0 ms] 333.96/291.55 (19) BOUNDS(n^1, INF) 333.96/291.55 (20) TRS for Loop Detection 333.96/291.55 333.96/291.55 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (0) 333.96/291.55 Obligation: 333.96/291.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 333.96/291.55 333.96/291.55 333.96/291.55 The TRS R consists of the following rules: 333.96/291.55 333.96/291.55 from(X) -> cons(X, n__from(s(X))) 333.96/291.55 first(0, Z) -> nil 333.96/291.55 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 333.96/291.55 sel(0, cons(X, Z)) -> X 333.96/291.55 sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) 333.96/291.55 from(X) -> n__from(X) 333.96/291.55 first(X1, X2) -> n__first(X1, X2) 333.96/291.55 activate(n__from(X)) -> from(X) 333.96/291.55 activate(n__first(X1, X2)) -> first(X1, X2) 333.96/291.55 activate(X) -> X 333.96/291.55 333.96/291.55 S is empty. 333.96/291.55 Rewrite Strategy: INNERMOST 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (1) CpxTrsToCdtProof (UPPER BOUND(ID)) 333.96/291.55 Converted Cpx (relative) TRS to CDT 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (2) 333.96/291.55 Obligation: 333.96/291.55 Complexity Dependency Tuples Problem 333.96/291.55 333.96/291.55 Rules: 333.96/291.55 from(z0) -> cons(z0, n__from(s(z0))) 333.96/291.55 from(z0) -> n__from(z0) 333.96/291.55 first(0, z0) -> nil 333.96/291.55 first(s(z0), cons(z1, z2)) -> cons(z1, n__first(z0, activate(z2))) 333.96/291.55 first(z0, z1) -> n__first(z0, z1) 333.96/291.55 sel(0, cons(z0, z1)) -> z0 333.96/291.55 sel(s(z0), cons(z1, z2)) -> sel(z0, activate(z2)) 333.96/291.55 activate(n__from(z0)) -> from(z0) 333.96/291.55 activate(n__first(z0, z1)) -> first(z0, z1) 333.96/291.55 activate(z0) -> z0 333.96/291.55 Tuples: 333.96/291.55 FROM(z0) -> c 333.96/291.55 FROM(z0) -> c1 333.96/291.55 FIRST(0, z0) -> c2 333.96/291.55 FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) 333.96/291.55 FIRST(z0, z1) -> c4 333.96/291.55 SEL(0, cons(z0, z1)) -> c5 333.96/291.55 SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) 333.96/291.55 ACTIVATE(n__from(z0)) -> c7(FROM(z0)) 333.96/291.55 ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) 333.96/291.55 ACTIVATE(z0) -> c9 333.96/291.55 S tuples: 333.96/291.55 FROM(z0) -> c 333.96/291.55 FROM(z0) -> c1 333.96/291.55 FIRST(0, z0) -> c2 333.96/291.55 FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) 333.96/291.55 FIRST(z0, z1) -> c4 333.96/291.55 SEL(0, cons(z0, z1)) -> c5 333.96/291.55 SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) 333.96/291.55 ACTIVATE(n__from(z0)) -> c7(FROM(z0)) 333.96/291.55 ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) 333.96/291.55 ACTIVATE(z0) -> c9 333.96/291.55 K tuples:none 333.96/291.55 Defined Rule Symbols: from_1, first_2, sel_2, activate_1 333.96/291.55 333.96/291.55 Defined Pair Symbols: FROM_1, FIRST_2, SEL_2, ACTIVATE_1 333.96/291.55 333.96/291.55 Compound Symbols: c, c1, c2, c3_1, c4, c5, c6_2, c7_1, c8_1, c9 333.96/291.55 333.96/291.55 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 333.96/291.55 Removed 7 trailing nodes: 333.96/291.55 FROM(z0) -> c 333.96/291.55 SEL(0, cons(z0, z1)) -> c5 333.96/291.55 FIRST(z0, z1) -> c4 333.96/291.55 ACTIVATE(z0) -> c9 333.96/291.55 FIRST(0, z0) -> c2 333.96/291.55 FROM(z0) -> c1 333.96/291.55 ACTIVATE(n__from(z0)) -> c7(FROM(z0)) 333.96/291.55 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (4) 333.96/291.55 Obligation: 333.96/291.55 Complexity Dependency Tuples Problem 333.96/291.55 333.96/291.55 Rules: 333.96/291.55 from(z0) -> cons(z0, n__from(s(z0))) 333.96/291.55 from(z0) -> n__from(z0) 333.96/291.55 first(0, z0) -> nil 333.96/291.55 first(s(z0), cons(z1, z2)) -> cons(z1, n__first(z0, activate(z2))) 333.96/291.55 first(z0, z1) -> n__first(z0, z1) 333.96/291.55 sel(0, cons(z0, z1)) -> z0 333.96/291.55 sel(s(z0), cons(z1, z2)) -> sel(z0, activate(z2)) 333.96/291.55 activate(n__from(z0)) -> from(z0) 333.96/291.55 activate(n__first(z0, z1)) -> first(z0, z1) 333.96/291.55 activate(z0) -> z0 333.96/291.55 Tuples: 333.96/291.55 FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) 333.96/291.55 SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) 333.96/291.55 ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) 333.96/291.55 S tuples: 333.96/291.55 FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) 333.96/291.55 SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) 333.96/291.55 ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) 333.96/291.55 K tuples:none 333.96/291.55 Defined Rule Symbols: from_1, first_2, sel_2, activate_1 333.96/291.55 333.96/291.55 Defined Pair Symbols: FIRST_2, SEL_2, ACTIVATE_1 333.96/291.55 333.96/291.55 Compound Symbols: c3_1, c6_2, c8_1 333.96/291.55 333.96/291.55 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (5) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 333.96/291.55 The following rules are not usable and were removed: 333.96/291.55 sel(0, cons(z0, z1)) -> z0 333.96/291.55 sel(s(z0), cons(z1, z2)) -> sel(z0, activate(z2)) 333.96/291.55 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (6) 333.96/291.55 Obligation: 333.96/291.55 Complexity Dependency Tuples Problem 333.96/291.55 333.96/291.55 Rules: 333.96/291.55 activate(n__from(z0)) -> from(z0) 333.96/291.55 activate(n__first(z0, z1)) -> first(z0, z1) 333.96/291.55 activate(z0) -> z0 333.96/291.55 from(z0) -> cons(z0, n__from(s(z0))) 333.96/291.55 from(z0) -> n__from(z0) 333.96/291.55 first(0, z0) -> nil 333.96/291.55 first(s(z0), cons(z1, z2)) -> cons(z1, n__first(z0, activate(z2))) 333.96/291.55 first(z0, z1) -> n__first(z0, z1) 333.96/291.55 Tuples: 333.96/291.55 FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) 333.96/291.55 SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) 333.96/291.55 ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) 333.96/291.55 S tuples: 333.96/291.55 FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) 333.96/291.55 SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) 333.96/291.55 ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) 333.96/291.55 K tuples:none 333.96/291.55 Defined Rule Symbols: activate_1, from_1, first_2 333.96/291.55 333.96/291.55 Defined Pair Symbols: FIRST_2, SEL_2, ACTIVATE_1 333.96/291.55 333.96/291.55 Compound Symbols: c3_1, c6_2, c8_1 333.96/291.55 333.96/291.55 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 333.96/291.55 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 333.96/291.55 SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) 333.96/291.55 We considered the (Usable) Rules:none 333.96/291.55 And the Tuples: 333.96/291.55 FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) 333.96/291.55 SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) 333.96/291.55 ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) 333.96/291.55 The order we found is given by the following interpretation: 333.96/291.55 333.96/291.55 Polynomial interpretation : 333.96/291.55 333.96/291.55 POL(0) = [1] 333.96/291.55 POL(ACTIVATE(x_1)) = 0 333.96/291.55 POL(FIRST(x_1, x_2)) = 0 333.96/291.55 POL(SEL(x_1, x_2)) = x_1 333.96/291.55 POL(activate(x_1)) = [1] 333.96/291.55 POL(c3(x_1)) = x_1 333.96/291.55 POL(c6(x_1, x_2)) = x_1 + x_2 333.96/291.55 POL(c8(x_1)) = x_1 333.96/291.55 POL(cons(x_1, x_2)) = [1] + x_1 333.96/291.55 POL(first(x_1, x_2)) = [1] + x_1 + x_2 333.96/291.55 POL(from(x_1)) = [1] + x_1 333.96/291.55 POL(n__first(x_1, x_2)) = [1] + x_1 + x_2 333.96/291.55 POL(n__from(x_1)) = [1] + x_1 333.96/291.55 POL(nil) = [1] 333.96/291.55 POL(s(x_1)) = [1] + x_1 333.96/291.55 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (8) 333.96/291.55 Obligation: 333.96/291.55 Complexity Dependency Tuples Problem 333.96/291.55 333.96/291.55 Rules: 333.96/291.55 activate(n__from(z0)) -> from(z0) 333.96/291.55 activate(n__first(z0, z1)) -> first(z0, z1) 333.96/291.55 activate(z0) -> z0 333.96/291.55 from(z0) -> cons(z0, n__from(s(z0))) 333.96/291.55 from(z0) -> n__from(z0) 333.96/291.55 first(0, z0) -> nil 333.96/291.55 first(s(z0), cons(z1, z2)) -> cons(z1, n__first(z0, activate(z2))) 333.96/291.55 first(z0, z1) -> n__first(z0, z1) 333.96/291.55 Tuples: 333.96/291.55 FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) 333.96/291.55 SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) 333.96/291.55 ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) 333.96/291.55 S tuples: 333.96/291.55 FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) 333.96/291.55 ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) 333.96/291.55 K tuples: 333.96/291.55 SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) 333.96/291.55 Defined Rule Symbols: activate_1, from_1, first_2 333.96/291.55 333.96/291.55 Defined Pair Symbols: FIRST_2, SEL_2, ACTIVATE_1 333.96/291.55 333.96/291.55 Compound Symbols: c3_1, c6_2, c8_1 333.96/291.55 333.96/291.55 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 333.96/291.55 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 333.96/291.55 FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) 333.96/291.55 We considered the (Usable) Rules: 333.96/291.55 first(z0, z1) -> n__first(z0, z1) 333.96/291.55 from(z0) -> cons(z0, n__from(s(z0))) 333.96/291.55 first(s(z0), cons(z1, z2)) -> cons(z1, n__first(z0, activate(z2))) 333.96/291.55 first(0, z0) -> nil 333.96/291.55 from(z0) -> n__from(z0) 333.96/291.55 activate(n__from(z0)) -> from(z0) 333.96/291.55 activate(z0) -> z0 333.96/291.55 activate(n__first(z0, z1)) -> first(z0, z1) 333.96/291.55 And the Tuples: 333.96/291.55 FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) 333.96/291.55 SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) 333.96/291.55 ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) 333.96/291.55 The order we found is given by the following interpretation: 333.96/291.55 333.96/291.55 Polynomial interpretation : 333.96/291.55 333.96/291.55 POL(0) = [2] 333.96/291.55 POL(ACTIVATE(x_1)) = x_1 333.96/291.55 POL(FIRST(x_1, x_2)) = x_1 + x_2 333.96/291.55 POL(SEL(x_1, x_2)) = x_1*x_2 + x_1^2 333.96/291.55 POL(activate(x_1)) = [1] + x_1 333.96/291.55 POL(c3(x_1)) = x_1 333.96/291.55 POL(c6(x_1, x_2)) = x_1 + x_2 333.96/291.55 POL(c8(x_1)) = x_1 333.96/291.55 POL(cons(x_1, x_2)) = x_2 333.96/291.55 POL(first(x_1, x_2)) = [1] + x_1 + x_2 333.96/291.55 POL(from(x_1)) = 0 333.96/291.55 POL(n__first(x_1, x_2)) = x_1 + x_2 333.96/291.55 POL(n__from(x_1)) = 0 333.96/291.55 POL(nil) = [2] 333.96/291.55 POL(s(x_1)) = [1] + x_1 333.96/291.55 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (10) 333.96/291.55 Obligation: 333.96/291.55 Complexity Dependency Tuples Problem 333.96/291.55 333.96/291.55 Rules: 333.96/291.55 activate(n__from(z0)) -> from(z0) 333.96/291.55 activate(n__first(z0, z1)) -> first(z0, z1) 333.96/291.55 activate(z0) -> z0 333.96/291.55 from(z0) -> cons(z0, n__from(s(z0))) 333.96/291.55 from(z0) -> n__from(z0) 333.96/291.55 first(0, z0) -> nil 333.96/291.55 first(s(z0), cons(z1, z2)) -> cons(z1, n__first(z0, activate(z2))) 333.96/291.55 first(z0, z1) -> n__first(z0, z1) 333.96/291.55 Tuples: 333.96/291.55 FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) 333.96/291.55 SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) 333.96/291.55 ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) 333.96/291.55 S tuples: 333.96/291.55 ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) 333.96/291.55 K tuples: 333.96/291.55 SEL(s(z0), cons(z1, z2)) -> c6(SEL(z0, activate(z2)), ACTIVATE(z2)) 333.96/291.55 FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) 333.96/291.55 Defined Rule Symbols: activate_1, from_1, first_2 333.96/291.55 333.96/291.55 Defined Pair Symbols: FIRST_2, SEL_2, ACTIVATE_1 333.96/291.55 333.96/291.55 Compound Symbols: c3_1, c6_2, c8_1 333.96/291.55 333.96/291.55 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (11) CdtKnowledgeProof (FINISHED) 333.96/291.55 The following tuples could be moved from S to K by knowledge propagation: 333.96/291.55 ACTIVATE(n__first(z0, z1)) -> c8(FIRST(z0, z1)) 333.96/291.55 FIRST(s(z0), cons(z1, z2)) -> c3(ACTIVATE(z2)) 333.96/291.55 Now S is empty 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (12) 333.96/291.55 BOUNDS(1, 1) 333.96/291.55 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (13) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 333.96/291.55 Transformed a relative TRS into a decreasing-loop problem. 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (14) 333.96/291.55 Obligation: 333.96/291.55 Analyzing the following TRS for decreasing loops: 333.96/291.55 333.96/291.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 333.96/291.55 333.96/291.55 333.96/291.55 The TRS R consists of the following rules: 333.96/291.55 333.96/291.55 from(X) -> cons(X, n__from(s(X))) 333.96/291.55 first(0, Z) -> nil 333.96/291.55 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 333.96/291.55 sel(0, cons(X, Z)) -> X 333.96/291.55 sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) 333.96/291.55 from(X) -> n__from(X) 333.96/291.55 first(X1, X2) -> n__first(X1, X2) 333.96/291.55 activate(n__from(X)) -> from(X) 333.96/291.55 activate(n__first(X1, X2)) -> first(X1, X2) 333.96/291.55 activate(X) -> X 333.96/291.55 333.96/291.55 S is empty. 333.96/291.55 Rewrite Strategy: INNERMOST 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (15) DecreasingLoopProof (LOWER BOUND(ID)) 333.96/291.55 The following loop(s) give(s) rise to the lower bound Omega(n^1): 333.96/291.55 333.96/291.55 The rewrite sequence 333.96/291.55 333.96/291.55 sel(s(X), cons(Y, Z)) ->^+ sel(X, Z) 333.96/291.55 333.96/291.55 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 333.96/291.55 333.96/291.55 The pumping substitution is [X / s(X), Z / cons(Y, Z)]. 333.96/291.55 333.96/291.55 The result substitution is [ ]. 333.96/291.55 333.96/291.55 333.96/291.55 333.96/291.55 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (16) 333.96/291.55 Complex Obligation (BEST) 333.96/291.55 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (17) 333.96/291.55 Obligation: 333.96/291.55 Proved the lower bound n^1 for the following obligation: 333.96/291.55 333.96/291.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 333.96/291.55 333.96/291.55 333.96/291.55 The TRS R consists of the following rules: 333.96/291.55 333.96/291.55 from(X) -> cons(X, n__from(s(X))) 333.96/291.55 first(0, Z) -> nil 333.96/291.55 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 333.96/291.55 sel(0, cons(X, Z)) -> X 333.96/291.55 sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) 333.96/291.55 from(X) -> n__from(X) 333.96/291.55 first(X1, X2) -> n__first(X1, X2) 333.96/291.55 activate(n__from(X)) -> from(X) 333.96/291.55 activate(n__first(X1, X2)) -> first(X1, X2) 333.96/291.55 activate(X) -> X 333.96/291.55 333.96/291.55 S is empty. 333.96/291.55 Rewrite Strategy: INNERMOST 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (18) LowerBoundPropagationProof (FINISHED) 333.96/291.55 Propagated lower bound. 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (19) 333.96/291.55 BOUNDS(n^1, INF) 333.96/291.55 333.96/291.55 ---------------------------------------- 333.96/291.55 333.96/291.55 (20) 333.96/291.55 Obligation: 333.96/291.55 Analyzing the following TRS for decreasing loops: 333.96/291.55 333.96/291.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 333.96/291.55 333.96/291.55 333.96/291.55 The TRS R consists of the following rules: 333.96/291.55 333.96/291.55 from(X) -> cons(X, n__from(s(X))) 333.96/291.55 first(0, Z) -> nil 333.96/291.55 first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) 333.96/291.55 sel(0, cons(X, Z)) -> X 333.96/291.55 sel(s(X), cons(Y, Z)) -> sel(X, activate(Z)) 333.96/291.55 from(X) -> n__from(X) 333.96/291.55 first(X1, X2) -> n__first(X1, X2) 333.96/291.55 activate(n__from(X)) -> from(X) 333.96/291.55 activate(n__first(X1, X2)) -> first(X1, X2) 333.96/291.55 activate(X) -> X 333.96/291.55 333.96/291.55 S is empty. 333.96/291.55 Rewrite Strategy: INNERMOST 334.08/291.59 EOF