353.42/291.49 WORST_CASE(Omega(n^1), O(n^2)) 353.42/291.51 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 353.42/291.51 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 353.42/291.51 353.42/291.51 353.42/291.51 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 353.42/291.51 353.42/291.51 (0) CpxTRS 353.42/291.51 (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 353.42/291.51 (2) CdtProblem 353.42/291.51 (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 353.42/291.51 (4) CdtProblem 353.42/291.51 (5) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 353.42/291.51 (6) CdtProblem 353.42/291.51 (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 120 ms] 353.42/291.51 (8) CdtProblem 353.42/291.51 (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 1040 ms] 353.42/291.51 (10) CdtProblem 353.42/291.51 (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 649 ms] 353.42/291.51 (12) CdtProblem 353.42/291.51 (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 693 ms] 353.42/291.51 (14) CdtProblem 353.42/291.51 (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 554 ms] 353.42/291.51 (16) CdtProblem 353.42/291.51 (17) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 353.42/291.51 (18) BOUNDS(1, 1) 353.42/291.51 (19) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 353.42/291.51 (20) TRS for Loop Detection 353.42/291.51 (21) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 353.42/291.51 (22) BEST 353.42/291.51 (23) proven lower bound 353.42/291.51 (24) LowerBoundPropagationProof [FINISHED, 0 ms] 353.42/291.51 (25) BOUNDS(n^1, INF) 353.42/291.51 (26) TRS for Loop Detection 353.42/291.51 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (0) 353.42/291.51 Obligation: 353.42/291.51 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 353.42/291.51 353.42/291.51 353.42/291.51 The TRS R consists of the following rules: 353.42/291.51 353.42/291.51 lt(0, s(X)) -> true 353.42/291.51 lt(s(X), 0) -> false 353.42/291.51 lt(s(X), s(Y)) -> lt(X, Y) 353.42/291.51 append(nil, Y) -> Y 353.42/291.51 append(add(N, X), Y) -> add(N, append(X, Y)) 353.42/291.51 split(N, nil) -> pair(nil, nil) 353.42/291.51 split(N, add(M, Y)) -> f_1(split(N, Y), N, M, Y) 353.42/291.51 f_1(pair(X, Z), N, M, Y) -> f_2(lt(N, M), N, M, Y, X, Z) 353.42/291.51 f_2(true, N, M, Y, X, Z) -> pair(X, add(M, Z)) 353.42/291.51 f_2(false, N, M, Y, X, Z) -> pair(add(M, X), Z) 353.42/291.51 qsort(nil) -> nil 353.42/291.51 qsort(add(N, X)) -> f_3(split(N, X), N, X) 353.42/291.51 f_3(pair(Y, Z), N, X) -> append(qsort(Y), add(X, qsort(Z))) 353.42/291.51 353.42/291.51 S is empty. 353.42/291.51 Rewrite Strategy: INNERMOST 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (1) CpxTrsToCdtProof (UPPER BOUND(ID)) 353.42/291.51 Converted Cpx (relative) TRS to CDT 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (2) 353.42/291.51 Obligation: 353.42/291.51 Complexity Dependency Tuples Problem 353.42/291.51 353.42/291.51 Rules: 353.42/291.51 lt(0, s(z0)) -> true 353.42/291.51 lt(s(z0), 0) -> false 353.42/291.51 lt(s(z0), s(z1)) -> lt(z0, z1) 353.42/291.51 append(nil, z0) -> z0 353.42/291.51 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) 353.42/291.51 split(z0, nil) -> pair(nil, nil) 353.42/291.51 split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) 353.42/291.51 f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) 353.42/291.51 f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) 353.42/291.51 f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) 353.42/291.51 qsort(nil) -> nil 353.42/291.51 qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) 353.42/291.51 f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) 353.42/291.51 Tuples: 353.42/291.51 LT(0, s(z0)) -> c 353.42/291.51 LT(s(z0), 0) -> c1 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(nil, z0) -> c3 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, nil) -> c5 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(F_2(lt(z2, z3), z2, z3, z4, z0, z1), LT(z2, z3)) 353.42/291.51 F_2(true, z0, z1, z2, z3, z4) -> c8 353.42/291.51 F_2(false, z0, z1, z2, z3, z4) -> c9 353.42/291.51 QSORT(nil) -> c10 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 S tuples: 353.42/291.51 LT(0, s(z0)) -> c 353.42/291.51 LT(s(z0), 0) -> c1 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(nil, z0) -> c3 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, nil) -> c5 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(F_2(lt(z2, z3), z2, z3, z4, z0, z1), LT(z2, z3)) 353.42/291.51 F_2(true, z0, z1, z2, z3, z4) -> c8 353.42/291.51 F_2(false, z0, z1, z2, z3, z4) -> c9 353.42/291.51 QSORT(nil) -> c10 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 K tuples:none 353.42/291.51 Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 353.42/291.51 353.42/291.51 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, F_1_4, F_2_6, QSORT_1, F_3_3 353.42/291.51 353.42/291.51 Compound Symbols: c, c1, c2_1, c3, c4_1, c5, c6_2, c7_2, c8, c9, c10, c11_2, c12_3 353.42/291.51 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 353.42/291.51 Removed 7 trailing nodes: 353.42/291.51 LT(0, s(z0)) -> c 353.42/291.51 F_2(true, z0, z1, z2, z3, z4) -> c8 353.42/291.51 LT(s(z0), 0) -> c1 353.42/291.51 APPEND(nil, z0) -> c3 353.42/291.51 QSORT(nil) -> c10 353.42/291.51 F_2(false, z0, z1, z2, z3, z4) -> c9 353.42/291.51 SPLIT(z0, nil) -> c5 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (4) 353.42/291.51 Obligation: 353.42/291.51 Complexity Dependency Tuples Problem 353.42/291.51 353.42/291.51 Rules: 353.42/291.51 lt(0, s(z0)) -> true 353.42/291.51 lt(s(z0), 0) -> false 353.42/291.51 lt(s(z0), s(z1)) -> lt(z0, z1) 353.42/291.51 append(nil, z0) -> z0 353.42/291.51 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) 353.42/291.51 split(z0, nil) -> pair(nil, nil) 353.42/291.51 split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) 353.42/291.51 f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) 353.42/291.51 f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) 353.42/291.51 f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) 353.42/291.51 qsort(nil) -> nil 353.42/291.51 qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) 353.42/291.51 f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) 353.42/291.51 Tuples: 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(F_2(lt(z2, z3), z2, z3, z4, z0, z1), LT(z2, z3)) 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 S tuples: 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(F_2(lt(z2, z3), z2, z3, z4, z0, z1), LT(z2, z3)) 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 K tuples:none 353.42/291.51 Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 353.42/291.51 353.42/291.51 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, F_1_4, QSORT_1, F_3_3 353.42/291.51 353.42/291.51 Compound Symbols: c2_1, c4_1, c6_2, c7_2, c11_2, c12_3 353.42/291.51 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 353.42/291.51 Removed 1 trailing tuple parts 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (6) 353.42/291.51 Obligation: 353.42/291.51 Complexity Dependency Tuples Problem 353.42/291.51 353.42/291.51 Rules: 353.42/291.51 lt(0, s(z0)) -> true 353.42/291.51 lt(s(z0), 0) -> false 353.42/291.51 lt(s(z0), s(z1)) -> lt(z0, z1) 353.42/291.51 append(nil, z0) -> z0 353.42/291.51 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) 353.42/291.51 split(z0, nil) -> pair(nil, nil) 353.42/291.51 split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) 353.42/291.51 f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) 353.42/291.51 f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) 353.42/291.51 f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) 353.42/291.51 qsort(nil) -> nil 353.42/291.51 qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) 353.42/291.51 f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) 353.42/291.51 Tuples: 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 S tuples: 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 K tuples:none 353.42/291.51 Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 353.42/291.51 353.42/291.51 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, QSORT_1, F_3_3, F_1_4 353.42/291.51 353.42/291.51 Compound Symbols: c2_1, c4_1, c6_2, c11_2, c12_3, c7_1 353.42/291.51 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 353.42/291.51 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 We considered the (Usable) Rules: 353.42/291.51 f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) 353.42/291.51 f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) 353.42/291.51 split(z0, nil) -> pair(nil, nil) 353.42/291.51 f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) 353.42/291.51 split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) 353.42/291.51 And the Tuples: 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 The order we found is given by the following interpretation: 353.42/291.51 353.42/291.51 Polynomial interpretation : 353.42/291.51 353.42/291.51 POL(0) = 0 353.42/291.51 POL(APPEND(x_1, x_2)) = 0 353.42/291.51 POL(F_1(x_1, x_2, x_3, x_4)) = 0 353.42/291.51 POL(F_3(x_1, x_2, x_3)) = [1] + x_1 353.42/291.51 POL(LT(x_1, x_2)) = 0 353.42/291.51 POL(QSORT(x_1)) = x_1 353.42/291.51 POL(SPLIT(x_1, x_2)) = 0 353.42/291.51 POL(add(x_1, x_2)) = [2] + x_2 353.42/291.51 POL(append(x_1, x_2)) = [3] 353.42/291.51 POL(c11(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(c12(x_1, x_2, x_3)) = x_1 + x_2 + x_3 353.42/291.51 POL(c2(x_1)) = x_1 353.42/291.51 POL(c4(x_1)) = x_1 353.42/291.51 POL(c6(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(c7(x_1)) = x_1 353.42/291.51 POL(f_1(x_1, x_2, x_3, x_4)) = [2] + x_1 353.42/291.51 POL(f_2(x_1, x_2, x_3, x_4, x_5, x_6)) = [2] + x_5 + x_6 353.42/291.51 POL(f_3(x_1, x_2, x_3)) = [3] + [3]x_2 + [3]x_3 353.42/291.51 POL(false) = [3] 353.42/291.51 POL(lt(x_1, x_2)) = [3]x_1 + [3]x_2 353.42/291.51 POL(nil) = 0 353.42/291.51 POL(pair(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(qsort(x_1)) = 0 353.42/291.51 POL(s(x_1)) = x_1 353.42/291.51 POL(split(x_1, x_2)) = x_2 353.42/291.51 POL(true) = [3] 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (8) 353.42/291.51 Obligation: 353.42/291.51 Complexity Dependency Tuples Problem 353.42/291.51 353.42/291.51 Rules: 353.42/291.51 lt(0, s(z0)) -> true 353.42/291.51 lt(s(z0), 0) -> false 353.42/291.51 lt(s(z0), s(z1)) -> lt(z0, z1) 353.42/291.51 append(nil, z0) -> z0 353.42/291.51 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) 353.42/291.51 split(z0, nil) -> pair(nil, nil) 353.42/291.51 split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) 353.42/291.51 f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) 353.42/291.51 f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) 353.42/291.51 f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) 353.42/291.51 qsort(nil) -> nil 353.42/291.51 qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) 353.42/291.51 f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) 353.42/291.51 Tuples: 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 S tuples: 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 K tuples: 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 353.42/291.51 353.42/291.51 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, QSORT_1, F_3_3, F_1_4 353.42/291.51 353.42/291.51 Compound Symbols: c2_1, c4_1, c6_2, c11_2, c12_3, c7_1 353.42/291.51 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 353.42/291.51 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 We considered the (Usable) Rules: 353.42/291.51 f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) 353.42/291.51 f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) 353.42/291.51 split(z0, nil) -> pair(nil, nil) 353.42/291.51 f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) 353.42/291.51 split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) 353.42/291.51 And the Tuples: 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 The order we found is given by the following interpretation: 353.42/291.51 353.42/291.51 Polynomial interpretation : 353.42/291.51 353.42/291.51 POL(0) = [2] 353.42/291.51 POL(APPEND(x_1, x_2)) = 0 353.42/291.51 POL(F_1(x_1, x_2, x_3, x_4)) = [2]x_2*x_3 353.42/291.51 POL(F_3(x_1, x_2, x_3)) = x_1^2 353.42/291.51 POL(LT(x_1, x_2)) = [2]x_1*x_2 353.42/291.51 POL(QSORT(x_1)) = x_1^2 353.42/291.51 POL(SPLIT(x_1, x_2)) = [2]x_1*x_2 353.42/291.51 POL(add(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(append(x_1, x_2)) = [2] + x_2^2 + x_1*x_2 + x_1^2 353.42/291.51 POL(c11(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(c12(x_1, x_2, x_3)) = x_1 + x_2 + x_3 353.42/291.51 POL(c2(x_1)) = x_1 353.42/291.51 POL(c4(x_1)) = x_1 353.42/291.51 POL(c6(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(c7(x_1)) = x_1 353.42/291.51 POL(f_1(x_1, x_2, x_3, x_4)) = x_1 + x_3 353.42/291.51 POL(f_2(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 + x_5 + x_6 353.42/291.51 POL(f_3(x_1, x_2, x_3)) = [1] + x_2 + x_3 + x_3^2 + x_2*x_3 + x_2^2 353.42/291.51 POL(false) = 0 353.42/291.51 POL(lt(x_1, x_2)) = 0 353.42/291.51 POL(nil) = 0 353.42/291.51 POL(pair(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(qsort(x_1)) = 0 353.42/291.51 POL(s(x_1)) = [2] + x_1 353.42/291.51 POL(split(x_1, x_2)) = x_2 353.42/291.51 POL(true) = 0 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (10) 353.42/291.51 Obligation: 353.42/291.51 Complexity Dependency Tuples Problem 353.42/291.51 353.42/291.51 Rules: 353.42/291.51 lt(0, s(z0)) -> true 353.42/291.51 lt(s(z0), 0) -> false 353.42/291.51 lt(s(z0), s(z1)) -> lt(z0, z1) 353.42/291.51 append(nil, z0) -> z0 353.42/291.51 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) 353.42/291.51 split(z0, nil) -> pair(nil, nil) 353.42/291.51 split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) 353.42/291.51 f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) 353.42/291.51 f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) 353.42/291.51 f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) 353.42/291.51 qsort(nil) -> nil 353.42/291.51 qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) 353.42/291.51 f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) 353.42/291.51 Tuples: 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 S tuples: 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 K tuples: 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 353.42/291.51 353.42/291.51 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, QSORT_1, F_3_3, F_1_4 353.42/291.51 353.42/291.51 Compound Symbols: c2_1, c4_1, c6_2, c11_2, c12_3, c7_1 353.42/291.51 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 353.42/291.51 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 We considered the (Usable) Rules: 353.42/291.51 f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) 353.42/291.51 f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) 353.42/291.51 split(z0, nil) -> pair(nil, nil) 353.42/291.51 f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) 353.42/291.51 split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) 353.42/291.51 And the Tuples: 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 The order we found is given by the following interpretation: 353.42/291.51 353.42/291.51 Polynomial interpretation : 353.42/291.51 353.42/291.51 POL(0) = [2] 353.42/291.51 POL(APPEND(x_1, x_2)) = 0 353.42/291.51 POL(F_1(x_1, x_2, x_3, x_4)) = [1] 353.42/291.51 POL(F_3(x_1, x_2, x_3)) = x_1^2 353.42/291.51 POL(LT(x_1, x_2)) = 0 353.42/291.51 POL(QSORT(x_1)) = x_1^2 353.42/291.51 POL(SPLIT(x_1, x_2)) = x_2 353.42/291.51 POL(add(x_1, x_2)) = [1] + x_2 353.42/291.51 POL(append(x_1, x_2)) = [2] + x_2^2 + x_1*x_2 + x_1^2 353.42/291.51 POL(c11(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(c12(x_1, x_2, x_3)) = x_1 + x_2 + x_3 353.42/291.51 POL(c2(x_1)) = x_1 353.42/291.51 POL(c4(x_1)) = x_1 353.42/291.51 POL(c6(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(c7(x_1)) = x_1 353.42/291.51 POL(f_1(x_1, x_2, x_3, x_4)) = [1] + x_1 353.42/291.51 POL(f_2(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_5 + x_6 353.42/291.51 POL(f_3(x_1, x_2, x_3)) = [1] + x_2 + x_3 + x_3^2 + x_2*x_3 + x_2^2 353.42/291.51 POL(false) = 0 353.42/291.51 POL(lt(x_1, x_2)) = 0 353.42/291.51 POL(nil) = 0 353.42/291.51 POL(pair(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(qsort(x_1)) = 0 353.42/291.51 POL(s(x_1)) = 0 353.42/291.51 POL(split(x_1, x_2)) = x_2 353.42/291.51 POL(true) = 0 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (12) 353.42/291.51 Obligation: 353.42/291.51 Complexity Dependency Tuples Problem 353.42/291.51 353.42/291.51 Rules: 353.42/291.51 lt(0, s(z0)) -> true 353.42/291.51 lt(s(z0), 0) -> false 353.42/291.51 lt(s(z0), s(z1)) -> lt(z0, z1) 353.42/291.51 append(nil, z0) -> z0 353.42/291.51 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) 353.42/291.51 split(z0, nil) -> pair(nil, nil) 353.42/291.51 split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) 353.42/291.51 f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) 353.42/291.51 f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) 353.42/291.51 f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) 353.42/291.51 qsort(nil) -> nil 353.42/291.51 qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) 353.42/291.51 f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) 353.42/291.51 Tuples: 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 S tuples: 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 K tuples: 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 353.42/291.51 353.42/291.51 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, QSORT_1, F_3_3, F_1_4 353.42/291.51 353.42/291.51 Compound Symbols: c2_1, c4_1, c6_2, c11_2, c12_3, c7_1 353.42/291.51 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 353.42/291.51 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 We considered the (Usable) Rules: 353.42/291.51 f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) 353.42/291.51 f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) 353.42/291.51 split(z0, nil) -> pair(nil, nil) 353.42/291.51 f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) 353.42/291.51 split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) 353.42/291.51 And the Tuples: 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 The order we found is given by the following interpretation: 353.42/291.51 353.42/291.51 Polynomial interpretation : 353.42/291.51 353.42/291.51 POL(0) = [2] 353.42/291.51 POL(APPEND(x_1, x_2)) = 0 353.42/291.51 POL(F_1(x_1, x_2, x_3, x_4)) = 0 353.42/291.51 POL(F_3(x_1, x_2, x_3)) = x_1^2 353.42/291.51 POL(LT(x_1, x_2)) = 0 353.42/291.51 POL(QSORT(x_1)) = x_1^2 353.42/291.51 POL(SPLIT(x_1, x_2)) = x_2 353.42/291.51 POL(add(x_1, x_2)) = [1] + x_2 353.42/291.51 POL(append(x_1, x_2)) = [2] + x_2^2 + x_1*x_2 + x_1^2 353.42/291.51 POL(c11(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(c12(x_1, x_2, x_3)) = x_1 + x_2 + x_3 353.42/291.51 POL(c2(x_1)) = x_1 353.42/291.51 POL(c4(x_1)) = x_1 353.42/291.51 POL(c6(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(c7(x_1)) = x_1 353.42/291.51 POL(f_1(x_1, x_2, x_3, x_4)) = [1] + x_1 353.42/291.51 POL(f_2(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_5 + x_6 353.42/291.51 POL(f_3(x_1, x_2, x_3)) = [1] + x_2 + x_3 + x_3^2 + x_2*x_3 + x_2^2 353.42/291.51 POL(false) = 0 353.42/291.51 POL(lt(x_1, x_2)) = 0 353.42/291.51 POL(nil) = 0 353.42/291.51 POL(pair(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(qsort(x_1)) = 0 353.42/291.51 POL(s(x_1)) = 0 353.42/291.51 POL(split(x_1, x_2)) = x_2 353.42/291.51 POL(true) = 0 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (14) 353.42/291.51 Obligation: 353.42/291.51 Complexity Dependency Tuples Problem 353.42/291.51 353.42/291.51 Rules: 353.42/291.51 lt(0, s(z0)) -> true 353.42/291.51 lt(s(z0), 0) -> false 353.42/291.51 lt(s(z0), s(z1)) -> lt(z0, z1) 353.42/291.51 append(nil, z0) -> z0 353.42/291.51 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) 353.42/291.51 split(z0, nil) -> pair(nil, nil) 353.42/291.51 split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) 353.42/291.51 f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) 353.42/291.51 f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) 353.42/291.51 f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) 353.42/291.51 qsort(nil) -> nil 353.42/291.51 qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) 353.42/291.51 f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) 353.42/291.51 Tuples: 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 S tuples: 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 K tuples: 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 353.42/291.51 353.42/291.51 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, QSORT_1, F_3_3, F_1_4 353.42/291.51 353.42/291.51 Compound Symbols: c2_1, c4_1, c6_2, c11_2, c12_3, c7_1 353.42/291.51 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 353.42/291.51 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 We considered the (Usable) Rules: 353.42/291.51 f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) 353.42/291.51 f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) 353.42/291.51 split(z0, nil) -> pair(nil, nil) 353.42/291.51 f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) 353.42/291.51 qsort(nil) -> nil 353.42/291.51 f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) 353.42/291.51 append(nil, z0) -> z0 353.42/291.51 split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) 353.42/291.51 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) 353.42/291.51 qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) 353.42/291.51 And the Tuples: 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 The order we found is given by the following interpretation: 353.42/291.51 353.42/291.51 Polynomial interpretation : 353.42/291.51 353.42/291.51 POL(0) = [2] 353.42/291.51 POL(APPEND(x_1, x_2)) = x_1 353.42/291.51 POL(F_1(x_1, x_2, x_3, x_4)) = 0 353.42/291.51 POL(F_3(x_1, x_2, x_3)) = [2]x_1 + x_1^2 353.42/291.51 POL(LT(x_1, x_2)) = 0 353.42/291.51 POL(QSORT(x_1)) = x_1^2 353.42/291.51 POL(SPLIT(x_1, x_2)) = 0 353.42/291.51 POL(add(x_1, x_2)) = [1] + x_2 353.42/291.51 POL(append(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(c11(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(c12(x_1, x_2, x_3)) = x_1 + x_2 + x_3 353.42/291.51 POL(c2(x_1)) = x_1 353.42/291.51 POL(c4(x_1)) = x_1 353.42/291.51 POL(c6(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(c7(x_1)) = x_1 353.42/291.51 POL(f_1(x_1, x_2, x_3, x_4)) = [1] + x_1 353.42/291.51 POL(f_2(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_5 + x_6 353.42/291.51 POL(f_3(x_1, x_2, x_3)) = [1] + x_1 353.42/291.51 POL(false) = 0 353.42/291.51 POL(lt(x_1, x_2)) = 0 353.42/291.51 POL(nil) = 0 353.42/291.51 POL(pair(x_1, x_2)) = x_1 + x_2 353.42/291.51 POL(qsort(x_1)) = x_1 353.42/291.51 POL(s(x_1)) = 0 353.42/291.51 POL(split(x_1, x_2)) = x_2 353.42/291.51 POL(true) = 0 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (16) 353.42/291.51 Obligation: 353.42/291.51 Complexity Dependency Tuples Problem 353.42/291.51 353.42/291.51 Rules: 353.42/291.51 lt(0, s(z0)) -> true 353.42/291.51 lt(s(z0), 0) -> false 353.42/291.51 lt(s(z0), s(z1)) -> lt(z0, z1) 353.42/291.51 append(nil, z0) -> z0 353.42/291.51 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) 353.42/291.51 split(z0, nil) -> pair(nil, nil) 353.42/291.51 split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) 353.42/291.51 f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) 353.42/291.51 f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) 353.42/291.51 f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) 353.42/291.51 qsort(nil) -> nil 353.42/291.51 qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) 353.42/291.51 f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) 353.42/291.51 Tuples: 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 S tuples:none 353.42/291.51 K tuples: 353.42/291.51 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) 353.42/291.51 F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) 353.42/291.51 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) 353.42/291.51 F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) 353.42/291.51 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) 353.42/291.51 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) 353.42/291.51 Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 353.42/291.51 353.42/291.51 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, QSORT_1, F_3_3, F_1_4 353.42/291.51 353.42/291.51 Compound Symbols: c2_1, c4_1, c6_2, c11_2, c12_3, c7_1 353.42/291.51 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (17) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 353.42/291.51 The set S is empty 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (18) 353.42/291.51 BOUNDS(1, 1) 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (19) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 353.42/291.51 Transformed a relative TRS into a decreasing-loop problem. 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (20) 353.42/291.51 Obligation: 353.42/291.51 Analyzing the following TRS for decreasing loops: 353.42/291.51 353.42/291.51 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 353.42/291.51 353.42/291.51 353.42/291.51 The TRS R consists of the following rules: 353.42/291.51 353.42/291.51 lt(0, s(X)) -> true 353.42/291.51 lt(s(X), 0) -> false 353.42/291.51 lt(s(X), s(Y)) -> lt(X, Y) 353.42/291.51 append(nil, Y) -> Y 353.42/291.51 append(add(N, X), Y) -> add(N, append(X, Y)) 353.42/291.51 split(N, nil) -> pair(nil, nil) 353.42/291.51 split(N, add(M, Y)) -> f_1(split(N, Y), N, M, Y) 353.42/291.51 f_1(pair(X, Z), N, M, Y) -> f_2(lt(N, M), N, M, Y, X, Z) 353.42/291.51 f_2(true, N, M, Y, X, Z) -> pair(X, add(M, Z)) 353.42/291.51 f_2(false, N, M, Y, X, Z) -> pair(add(M, X), Z) 353.42/291.51 qsort(nil) -> nil 353.42/291.51 qsort(add(N, X)) -> f_3(split(N, X), N, X) 353.42/291.51 f_3(pair(Y, Z), N, X) -> append(qsort(Y), add(X, qsort(Z))) 353.42/291.51 353.42/291.51 S is empty. 353.42/291.51 Rewrite Strategy: INNERMOST 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (21) DecreasingLoopProof (LOWER BOUND(ID)) 353.42/291.51 The following loop(s) give(s) rise to the lower bound Omega(n^1): 353.42/291.51 353.42/291.51 The rewrite sequence 353.42/291.51 353.42/291.51 split(N, add(M, Y)) ->^+ f_1(split(N, Y), N, M, Y) 353.42/291.51 353.42/291.51 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 353.42/291.51 353.42/291.51 The pumping substitution is [Y / add(M, Y)]. 353.42/291.51 353.42/291.51 The result substitution is [ ]. 353.42/291.51 353.42/291.51 353.42/291.51 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (22) 353.42/291.51 Complex Obligation (BEST) 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (23) 353.42/291.51 Obligation: 353.42/291.51 Proved the lower bound n^1 for the following obligation: 353.42/291.51 353.42/291.51 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 353.42/291.51 353.42/291.51 353.42/291.51 The TRS R consists of the following rules: 353.42/291.51 353.42/291.51 lt(0, s(X)) -> true 353.42/291.51 lt(s(X), 0) -> false 353.42/291.51 lt(s(X), s(Y)) -> lt(X, Y) 353.42/291.51 append(nil, Y) -> Y 353.42/291.51 append(add(N, X), Y) -> add(N, append(X, Y)) 353.42/291.51 split(N, nil) -> pair(nil, nil) 353.42/291.51 split(N, add(M, Y)) -> f_1(split(N, Y), N, M, Y) 353.42/291.51 f_1(pair(X, Z), N, M, Y) -> f_2(lt(N, M), N, M, Y, X, Z) 353.42/291.51 f_2(true, N, M, Y, X, Z) -> pair(X, add(M, Z)) 353.42/291.51 f_2(false, N, M, Y, X, Z) -> pair(add(M, X), Z) 353.42/291.51 qsort(nil) -> nil 353.42/291.51 qsort(add(N, X)) -> f_3(split(N, X), N, X) 353.42/291.51 f_3(pair(Y, Z), N, X) -> append(qsort(Y), add(X, qsort(Z))) 353.42/291.51 353.42/291.51 S is empty. 353.42/291.51 Rewrite Strategy: INNERMOST 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (24) LowerBoundPropagationProof (FINISHED) 353.42/291.51 Propagated lower bound. 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (25) 353.42/291.51 BOUNDS(n^1, INF) 353.42/291.51 353.42/291.51 ---------------------------------------- 353.42/291.51 353.42/291.51 (26) 353.42/291.51 Obligation: 353.42/291.51 Analyzing the following TRS for decreasing loops: 353.42/291.51 353.42/291.51 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 353.42/291.51 353.42/291.51 353.42/291.51 The TRS R consists of the following rules: 353.42/291.51 353.42/291.51 lt(0, s(X)) -> true 353.42/291.51 lt(s(X), 0) -> false 353.42/291.51 lt(s(X), s(Y)) -> lt(X, Y) 353.42/291.51 append(nil, Y) -> Y 353.42/291.51 append(add(N, X), Y) -> add(N, append(X, Y)) 353.42/291.51 split(N, nil) -> pair(nil, nil) 353.42/291.51 split(N, add(M, Y)) -> f_1(split(N, Y), N, M, Y) 353.42/291.51 f_1(pair(X, Z), N, M, Y) -> f_2(lt(N, M), N, M, Y, X, Z) 353.42/291.51 f_2(true, N, M, Y, X, Z) -> pair(X, add(M, Z)) 353.42/291.51 f_2(false, N, M, Y, X, Z) -> pair(add(M, X), Z) 353.42/291.51 qsort(nil) -> nil 353.42/291.51 qsort(add(N, X)) -> f_3(split(N, X), N, X) 353.42/291.51 f_3(pair(Y, Z), N, X) -> append(qsort(Y), add(X, qsort(Z))) 353.42/291.51 353.42/291.51 S is empty. 353.42/291.51 Rewrite Strategy: INNERMOST 353.42/291.55 EOF