/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^2)) proof of /export/starexec/sandbox2/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) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 141 ms] (8) CdtProblem (9) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CdtProblem (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 1056 ms] (12) CdtProblem (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 712 ms] (14) CdtProblem (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 573 ms] (16) CdtProblem (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 570 ms] (18) CdtProblem (19) SIsEmptyProof [BOTH BOUNDS(ID, ID), 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: lt(0, s(X)) -> true lt(s(X), 0) -> false lt(s(X), s(Y)) -> lt(X, Y) append(nil, Y) -> Y append(add(N, X), Y) -> add(N, append(X, Y)) split(N, nil) -> pair(nil, nil) split(N, add(M, Y)) -> f_1(split(N, Y), N, M, Y) f_1(pair(X, Z), N, M, Y) -> f_2(lt(N, M), N, M, Y, X, Z) f_2(true, N, M, Y, X, Z) -> pair(X, add(M, Z)) f_2(false, N, M, Y, X, Z) -> pair(add(M, X), Z) qsort(nil) -> nil qsort(add(N, X)) -> f_3(split(N, X), N, X) f_3(pair(Y, Z), N, X) -> append(qsort(Y), add(X, qsort(Z))) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (2) Obligation: Complexity Dependency Tuples Problem Rules: lt(0, s(z0)) -> true lt(s(z0), 0) -> false lt(s(z0), s(z1)) -> lt(z0, z1) append(nil, z0) -> z0 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) split(z0, nil) -> pair(nil, nil) split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) qsort(nil) -> nil qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) Tuples: LT(0, s(z0)) -> c LT(s(z0), 0) -> c1 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(nil, z0) -> c3 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, nil) -> c5 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) F_1(pair(z0, z1), z2, z3, z4) -> c7(F_2(lt(z2, z3), z2, z3, z4, z0, z1), LT(z2, z3)) F_2(true, z0, z1, z2, z3, z4) -> c8 F_2(false, z0, z1, z2, z3, z4) -> c9 QSORT(nil) -> c10 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) S tuples: LT(0, s(z0)) -> c LT(s(z0), 0) -> c1 LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(nil, z0) -> c3 APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, nil) -> c5 SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) F_1(pair(z0, z1), z2, z3, z4) -> c7(F_2(lt(z2, z3), z2, z3, z4, z0, z1), LT(z2, z3)) F_2(true, z0, z1, z2, z3, z4) -> c8 F_2(false, z0, z1, z2, z3, z4) -> c9 QSORT(nil) -> c10 QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) K tuples:none Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, F_1_4, F_2_6, QSORT_1, F_3_3 Compound Symbols: c, c1, c2_1, c3, c4_1, c5, c6_2, c7_2, c8, c9, c10, c11_2, c12_3 ---------------------------------------- (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) Removed 7 trailing nodes: APPEND(nil, z0) -> c3 F_2(false, z0, z1, z2, z3, z4) -> c9 QSORT(nil) -> c10 SPLIT(z0, nil) -> c5 F_2(true, z0, z1, z2, z3, z4) -> c8 LT(0, s(z0)) -> c LT(s(z0), 0) -> c1 ---------------------------------------- (4) Obligation: Complexity Dependency Tuples Problem Rules: lt(0, s(z0)) -> true lt(s(z0), 0) -> false lt(s(z0), s(z1)) -> lt(z0, z1) append(nil, z0) -> z0 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) split(z0, nil) -> pair(nil, nil) split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) qsort(nil) -> nil qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) Tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) F_1(pair(z0, z1), z2, z3, z4) -> c7(F_2(lt(z2, z3), z2, z3, z4, z0, z1), LT(z2, z3)) QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) S tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) F_1(pair(z0, z1), z2, z3, z4) -> c7(F_2(lt(z2, z3), z2, z3, z4, z0, z1), LT(z2, z3)) QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) K tuples:none Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, F_1_4, QSORT_1, F_3_3 Compound Symbols: c2_1, c4_1, c6_2, c7_2, c11_2, c12_3 ---------------------------------------- (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules: lt(0, s(z0)) -> true lt(s(z0), 0) -> false lt(s(z0), s(z1)) -> lt(z0, z1) append(nil, z0) -> z0 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) split(z0, nil) -> pair(nil, nil) split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) qsort(nil) -> nil qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) Tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) S tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) K tuples:none Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, QSORT_1, F_3_3, F_1_4 Compound Symbols: c2_1, c4_1, c6_2, c11_2, c12_3, c7_1 ---------------------------------------- (7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) We considered the (Usable) Rules: f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) split(z0, nil) -> pair(nil, nil) f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) And the Tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(APPEND(x_1, x_2)) = 0 POL(F_1(x_1, x_2, x_3, x_4)) = 0 POL(F_3(x_1, x_2, x_3)) = x_1 POL(LT(x_1, x_2)) = 0 POL(QSORT(x_1)) = x_1 POL(SPLIT(x_1, x_2)) = 0 POL(add(x_1, x_2)) = [1] + x_2 POL(append(x_1, x_2)) = [1] POL(c11(x_1, x_2)) = x_1 + x_2 POL(c12(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c2(x_1)) = x_1 POL(c4(x_1)) = x_1 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c7(x_1)) = x_1 POL(f_1(x_1, x_2, x_3, x_4)) = [1] + x_1 POL(f_2(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_5 + x_6 POL(f_3(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3 POL(false) = [1] POL(lt(x_1, x_2)) = [1] POL(nil) = 0 POL(pair(x_1, x_2)) = x_1 + x_2 POL(qsort(x_1)) = [1] + x_1 POL(s(x_1)) = [1] + x_1 POL(split(x_1, x_2)) = x_2 POL(true) = [1] ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules: lt(0, s(z0)) -> true lt(s(z0), 0) -> false lt(s(z0), s(z1)) -> lt(z0, z1) append(nil, z0) -> z0 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) split(z0, nil) -> pair(nil, nil) split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) qsort(nil) -> nil qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) Tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) S tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) K tuples: QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, QSORT_1, F_3_3, F_1_4 Compound Symbols: c2_1, c4_1, c6_2, c11_2, c12_3, c7_1 ---------------------------------------- (9) CdtKnowledgeProof (BOTH BOUNDS(ID, ID)) The following tuples could be moved from S to K by knowledge propagation: F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules: lt(0, s(z0)) -> true lt(s(z0), 0) -> false lt(s(z0), s(z1)) -> lt(z0, z1) append(nil, z0) -> z0 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) split(z0, nil) -> pair(nil, nil) split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) qsort(nil) -> nil qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) Tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) S tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) K tuples: QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, QSORT_1, F_3_3, F_1_4 Compound Symbols: c2_1, c4_1, c6_2, c11_2, c12_3, c7_1 ---------------------------------------- (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. LT(s(z0), s(z1)) -> c2(LT(z0, z1)) We considered the (Usable) Rules: f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) split(z0, nil) -> pair(nil, nil) f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) And the Tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [2] POL(APPEND(x_1, x_2)) = 0 POL(F_1(x_1, x_2, x_3, x_4)) = [2]x_2*x_3 POL(F_3(x_1, x_2, x_3)) = x_1^2 POL(LT(x_1, x_2)) = [2]x_1*x_2 POL(QSORT(x_1)) = x_1^2 POL(SPLIT(x_1, x_2)) = [2]x_1*x_2 POL(add(x_1, x_2)) = x_1 + x_2 POL(append(x_1, x_2)) = [2] + x_2^2 + x_1*x_2 + x_1^2 POL(c11(x_1, x_2)) = x_1 + x_2 POL(c12(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c2(x_1)) = x_1 POL(c4(x_1)) = x_1 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c7(x_1)) = x_1 POL(f_1(x_1, x_2, x_3, x_4)) = x_1 + x_3 POL(f_2(x_1, x_2, x_3, x_4, x_5, x_6)) = x_3 + x_5 + x_6 POL(f_3(x_1, x_2, x_3)) = [1] + x_2 + x_3 + x_3^2 + x_2*x_3 + x_2^2 POL(false) = 0 POL(lt(x_1, x_2)) = 0 POL(nil) = 0 POL(pair(x_1, x_2)) = x_1 + x_2 POL(qsort(x_1)) = 0 POL(s(x_1)) = [2] + x_1 POL(split(x_1, x_2)) = x_2 POL(true) = 0 ---------------------------------------- (12) Obligation: Complexity Dependency Tuples Problem Rules: lt(0, s(z0)) -> true lt(s(z0), 0) -> false lt(s(z0), s(z1)) -> lt(z0, z1) append(nil, z0) -> z0 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) split(z0, nil) -> pair(nil, nil) split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) qsort(nil) -> nil qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) Tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) S tuples: APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) K tuples: QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) LT(s(z0), s(z1)) -> c2(LT(z0, z1)) Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, QSORT_1, F_3_3, F_1_4 Compound Symbols: c2_1, c4_1, c6_2, c11_2, c12_3, c7_1 ---------------------------------------- (13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) We considered the (Usable) Rules: f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) split(z0, nil) -> pair(nil, nil) f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) And the Tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [2] POL(APPEND(x_1, x_2)) = 0 POL(F_1(x_1, x_2, x_3, x_4)) = [1] POL(F_3(x_1, x_2, x_3)) = x_1^2 POL(LT(x_1, x_2)) = 0 POL(QSORT(x_1)) = x_1^2 POL(SPLIT(x_1, x_2)) = x_2 POL(add(x_1, x_2)) = [1] + x_2 POL(append(x_1, x_2)) = [2] + x_2^2 + x_1*x_2 + x_1^2 POL(c11(x_1, x_2)) = x_1 + x_2 POL(c12(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c2(x_1)) = x_1 POL(c4(x_1)) = x_1 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c7(x_1)) = x_1 POL(f_1(x_1, x_2, x_3, x_4)) = [1] + x_1 POL(f_2(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_5 + x_6 POL(f_3(x_1, x_2, x_3)) = [1] + x_2 + x_3 + x_3^2 + x_2*x_3 + x_2^2 POL(false) = 0 POL(lt(x_1, x_2)) = 0 POL(nil) = 0 POL(pair(x_1, x_2)) = x_1 + x_2 POL(qsort(x_1)) = 0 POL(s(x_1)) = 0 POL(split(x_1, x_2)) = x_2 POL(true) = 0 ---------------------------------------- (14) Obligation: Complexity Dependency Tuples Problem Rules: lt(0, s(z0)) -> true lt(s(z0), 0) -> false lt(s(z0), s(z1)) -> lt(z0, z1) append(nil, z0) -> z0 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) split(z0, nil) -> pair(nil, nil) split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) qsort(nil) -> nil qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) Tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) S tuples: APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) K tuples: QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) LT(s(z0), s(z1)) -> c2(LT(z0, z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, QSORT_1, F_3_3, F_1_4 Compound Symbols: c2_1, c4_1, c6_2, c11_2, c12_3, c7_1 ---------------------------------------- (15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) We considered the (Usable) Rules: f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) split(z0, nil) -> pair(nil, nil) f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) And the Tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [2] POL(APPEND(x_1, x_2)) = 0 POL(F_1(x_1, x_2, x_3, x_4)) = 0 POL(F_3(x_1, x_2, x_3)) = x_1^2 POL(LT(x_1, x_2)) = 0 POL(QSORT(x_1)) = x_1^2 POL(SPLIT(x_1, x_2)) = x_2 POL(add(x_1, x_2)) = [1] + x_2 POL(append(x_1, x_2)) = [2] + x_2^2 + x_1*x_2 + x_1^2 POL(c11(x_1, x_2)) = x_1 + x_2 POL(c12(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c2(x_1)) = x_1 POL(c4(x_1)) = x_1 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c7(x_1)) = x_1 POL(f_1(x_1, x_2, x_3, x_4)) = [1] + x_1 POL(f_2(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_5 + x_6 POL(f_3(x_1, x_2, x_3)) = [1] + x_2 + x_3 + x_3^2 + x_2*x_3 + x_2^2 POL(false) = 0 POL(lt(x_1, x_2)) = 0 POL(nil) = 0 POL(pair(x_1, x_2)) = x_1 + x_2 POL(qsort(x_1)) = 0 POL(s(x_1)) = 0 POL(split(x_1, x_2)) = x_2 POL(true) = 0 ---------------------------------------- (16) Obligation: Complexity Dependency Tuples Problem Rules: lt(0, s(z0)) -> true lt(s(z0), 0) -> false lt(s(z0), s(z1)) -> lt(z0, z1) append(nil, z0) -> z0 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) split(z0, nil) -> pair(nil, nil) split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) qsort(nil) -> nil qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) Tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) S tuples: APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) K tuples: QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) LT(s(z0), s(z1)) -> c2(LT(z0, z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, QSORT_1, F_3_3, F_1_4 Compound Symbols: c2_1, c4_1, c6_2, c11_2, c12_3, c7_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. APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) We considered the (Usable) Rules: f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) split(z0, nil) -> pair(nil, nil) f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) qsort(nil) -> nil f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) append(nil, z0) -> z0 split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) append(add(z0, z1), z2) -> add(z0, append(z1, z2)) qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) And the Tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [2] POL(APPEND(x_1, x_2)) = x_1 POL(F_1(x_1, x_2, x_3, x_4)) = 0 POL(F_3(x_1, x_2, x_3)) = [2]x_1 + x_1^2 POL(LT(x_1, x_2)) = 0 POL(QSORT(x_1)) = x_1^2 POL(SPLIT(x_1, x_2)) = 0 POL(add(x_1, x_2)) = [1] + x_2 POL(append(x_1, x_2)) = x_1 + x_2 POL(c11(x_1, x_2)) = x_1 + x_2 POL(c12(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c2(x_1)) = x_1 POL(c4(x_1)) = x_1 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c7(x_1)) = x_1 POL(f_1(x_1, x_2, x_3, x_4)) = [1] + x_1 POL(f_2(x_1, x_2, x_3, x_4, x_5, x_6)) = [1] + x_5 + x_6 POL(f_3(x_1, x_2, x_3)) = [1] + x_1 POL(false) = 0 POL(lt(x_1, x_2)) = 0 POL(nil) = 0 POL(pair(x_1, x_2)) = x_1 + x_2 POL(qsort(x_1)) = x_1 POL(s(x_1)) = 0 POL(split(x_1, x_2)) = x_2 POL(true) = 0 ---------------------------------------- (18) Obligation: Complexity Dependency Tuples Problem Rules: lt(0, s(z0)) -> true lt(s(z0), 0) -> false lt(s(z0), s(z1)) -> lt(z0, z1) append(nil, z0) -> z0 append(add(z0, z1), z2) -> add(z0, append(z1, z2)) split(z0, nil) -> pair(nil, nil) split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2) f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1) f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4)) f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4) qsort(nil) -> nil qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1) f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1))) Tuples: LT(s(z0), s(z1)) -> c2(LT(z0, z1)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) S tuples:none K tuples: QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1)) F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1)) LT(s(z0), s(z1)) -> c2(LT(z0, z1)) F_1(pair(z0, z1), z2, z3, z4) -> c7(LT(z2, z3)) SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2)) APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2)) Defined Rule Symbols: lt_2, append_2, split_2, f_1_4, f_2_6, qsort_1, f_3_3 Defined Pair Symbols: LT_2, APPEND_2, SPLIT_2, QSORT_1, F_3_3, F_1_4 Compound Symbols: c2_1, c4_1, c6_2, c11_2, c12_3, c7_1 ---------------------------------------- (19) SIsEmptyProof (BOTH BOUNDS(ID, ID)) The set 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: lt(0, s(X)) -> true lt(s(X), 0) -> false lt(s(X), s(Y)) -> lt(X, Y) append(nil, Y) -> Y append(add(N, X), Y) -> add(N, append(X, Y)) split(N, nil) -> pair(nil, nil) split(N, add(M, Y)) -> f_1(split(N, Y), N, M, Y) f_1(pair(X, Z), N, M, Y) -> f_2(lt(N, M), N, M, Y, X, Z) f_2(true, N, M, Y, X, Z) -> pair(X, add(M, Z)) f_2(false, N, M, Y, X, Z) -> pair(add(M, X), Z) qsort(nil) -> nil qsort(add(N, X)) -> f_3(split(N, X), N, X) f_3(pair(Y, Z), N, X) -> append(qsort(Y), add(X, qsort(Z))) 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 split(N, add(M, Y)) ->^+ f_1(split(N, Y), N, M, Y) gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. The pumping substitution is [Y / add(M, Y)]. 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: lt(0, s(X)) -> true lt(s(X), 0) -> false lt(s(X), s(Y)) -> lt(X, Y) append(nil, Y) -> Y append(add(N, X), Y) -> add(N, append(X, Y)) split(N, nil) -> pair(nil, nil) split(N, add(M, Y)) -> f_1(split(N, Y), N, M, Y) f_1(pair(X, Z), N, M, Y) -> f_2(lt(N, M), N, M, Y, X, Z) f_2(true, N, M, Y, X, Z) -> pair(X, add(M, Z)) f_2(false, N, M, Y, X, Z) -> pair(add(M, X), Z) qsort(nil) -> nil qsort(add(N, X)) -> f_3(split(N, X), N, X) f_3(pair(Y, Z), N, X) -> append(qsort(Y), add(X, qsort(Z))) 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: lt(0, s(X)) -> true lt(s(X), 0) -> false lt(s(X), s(Y)) -> lt(X, Y) append(nil, Y) -> Y append(add(N, X), Y) -> add(N, append(X, Y)) split(N, nil) -> pair(nil, nil) split(N, add(M, Y)) -> f_1(split(N, Y), N, M, Y) f_1(pair(X, Z), N, M, Y) -> f_2(lt(N, M), N, M, Y, X, Z) f_2(true, N, M, Y, X, Z) -> pair(X, add(M, Z)) f_2(false, N, M, Y, X, Z) -> pair(add(M, X), Z) qsort(nil) -> nil qsort(add(N, X)) -> f_3(split(N, X), N, X) f_3(pair(Y, Z), N, X) -> append(qsort(Y), add(X, qsort(Z))) S is empty. Rewrite Strategy: INNERMOST