/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^1)) 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^1). (0) CpxTRS (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] (2) CdtProblem (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] (4) CdtProblem (5) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CdtProblem (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 97 ms] (8) CdtProblem (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 20 ms] (10) CdtProblem (11) CdtKnowledgeProof [FINISHED, 0 ms] (12) BOUNDS(1, 1) (13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (14) TRS for Loop Detection (15) DecreasingLoopProof [LOWER BOUND(ID), 40 ms] (16) BEST (17) proven lower bound (18) LowerBoundPropagationProof [FINISHED, 0 ms] (19) BOUNDS(n^1, INF) (20) TRS for Loop Detection ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: f4(S(x''), S(x'), x3, x4, S(x)) -> f2(S(x''), x', x3, x4, x) f4(S(x'), 0, x3, x4, S(x)) -> f3(x', 0, x3, x4, x) f2(x1, x2, S(x''), S(x'), S(x)) -> f5(x1, x2, S(x''), x', x) f2(x1, x2, S(x'), 0, S(x)) -> f3(x1, x2, x', 0, x) f4(S(x'), S(x), x3, x4, 0) -> 0 f4(S(x), 0, x3, x4, 0) -> 0 f2(x1, x2, S(x'), S(x), 0) -> 0 f2(x1, x2, S(x), 0, 0) -> 0 f0(x1, S(x'), x3, S(x), x5) -> f1(x', S(x'), x, S(x), S(x)) f0(x1, S(x), x3, 0, x5) -> 0 f6(x1, x2, x3, x4, S(x)) -> f0(x1, x2, x4, x3, x) f5(x1, x2, x3, x4, S(x)) -> f6(x2, x1, x3, x4, x) f3(x1, x2, x3, x4, S(x)) -> f4(x1, x2, x4, x3, x) f1(x1, x2, x3, x4, S(x)) -> f2(x2, x1, x3, x4, x) f6(x1, x2, x3, x4, 0) -> 0 f5(x1, x2, x3, x4, 0) -> 0 f4(0, x2, x3, x4, x5) -> 0 f3(x1, x2, x3, x4, 0) -> 0 f2(x1, x2, 0, x4, x5) -> 0 f1(x1, x2, x3, x4, 0) -> 0 f0(x1, 0, x3, x4, x5) -> 0 S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (2) Obligation: Complexity Dependency Tuples Problem Rules: f4(S(z0), S(z1), z2, z3, S(z4)) -> f2(S(z0), z1, z2, z3, z4) f4(S(z0), 0, z1, z2, S(z3)) -> f3(z0, 0, z1, z2, z3) f4(S(z0), S(z1), z2, z3, 0) -> 0 f4(S(z0), 0, z1, z2, 0) -> 0 f4(0, z0, z1, z2, z3) -> 0 f2(z0, z1, S(z2), S(z3), S(z4)) -> f5(z0, z1, S(z2), z3, z4) f2(z0, z1, S(z2), 0, S(z3)) -> f3(z0, z1, z2, 0, z3) f2(z0, z1, S(z2), S(z3), 0) -> 0 f2(z0, z1, S(z2), 0, 0) -> 0 f2(z0, z1, 0, z2, z3) -> 0 f0(z0, S(z1), z2, S(z3), z4) -> f1(z1, S(z1), z3, S(z3), S(z3)) f0(z0, S(z1), z2, 0, z3) -> 0 f0(z0, 0, z1, z2, z3) -> 0 f6(z0, z1, z2, z3, S(z4)) -> f0(z0, z1, z3, z2, z4) f6(z0, z1, z2, z3, 0) -> 0 f5(z0, z1, z2, z3, S(z4)) -> f6(z1, z0, z2, z3, z4) f5(z0, z1, z2, z3, 0) -> 0 f3(z0, z1, z2, z3, S(z4)) -> f4(z0, z1, z3, z2, z4) f3(z0, z1, z2, z3, 0) -> 0 f1(z0, z1, z2, z3, S(z4)) -> f2(z1, z0, z2, z3, z4) f1(z0, z1, z2, z3, 0) -> 0 Tuples: F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) F4(S(z0), S(z1), z2, z3, 0) -> c2 F4(S(z0), 0, z1, z2, 0) -> c3 F4(0, z0, z1, z2, z3) -> c4 F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) F2(z0, z1, S(z2), S(z3), 0) -> c7 F2(z0, z1, S(z2), 0, 0) -> c8 F2(z0, z1, 0, z2, z3) -> c9 F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) F0(z0, S(z1), z2, 0, z3) -> c11 F0(z0, 0, z1, z2, z3) -> c12 F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) F6(z0, z1, z2, z3, 0) -> c14 F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) F5(z0, z1, z2, z3, 0) -> c16 F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) F3(z0, z1, z2, z3, 0) -> c18 F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) F1(z0, z1, z2, z3, 0) -> c20 S tuples: F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) F4(S(z0), S(z1), z2, z3, 0) -> c2 F4(S(z0), 0, z1, z2, 0) -> c3 F4(0, z0, z1, z2, z3) -> c4 F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) F2(z0, z1, S(z2), S(z3), 0) -> c7 F2(z0, z1, S(z2), 0, 0) -> c8 F2(z0, z1, 0, z2, z3) -> c9 F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) F0(z0, S(z1), z2, 0, z3) -> c11 F0(z0, 0, z1, z2, z3) -> c12 F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) F6(z0, z1, z2, z3, 0) -> c14 F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) F5(z0, z1, z2, z3, 0) -> c16 F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) F3(z0, z1, z2, z3, 0) -> c18 F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) F1(z0, z1, z2, z3, 0) -> c20 K tuples:none Defined Rule Symbols: f4_5, f2_5, f0_5, f6_5, f5_5, f3_5, f1_5 Defined Pair Symbols: F4_5, F2_5, F0_5, F6_5, F5_5, F3_5, F1_5 Compound Symbols: c_1, c1_1, c2, c3, c4, c5_1, c6_1, c7, c8, c9, c10_1, c11, c12, c13_1, c14, c15_1, c16, c17_1, c18, c19_1, c20 ---------------------------------------- (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) Removed 12 trailing nodes: F3(z0, z1, z2, z3, 0) -> c18 F2(z0, z1, S(z2), 0, 0) -> c8 F4(S(z0), 0, z1, z2, 0) -> c3 F2(z0, z1, S(z2), S(z3), 0) -> c7 F2(z0, z1, 0, z2, z3) -> c9 F5(z0, z1, z2, z3, 0) -> c16 F6(z0, z1, z2, z3, 0) -> c14 F4(0, z0, z1, z2, z3) -> c4 F0(z0, 0, z1, z2, z3) -> c12 F0(z0, S(z1), z2, 0, z3) -> c11 F1(z0, z1, z2, z3, 0) -> c20 F4(S(z0), S(z1), z2, z3, 0) -> c2 ---------------------------------------- (4) Obligation: Complexity Dependency Tuples Problem Rules: f4(S(z0), S(z1), z2, z3, S(z4)) -> f2(S(z0), z1, z2, z3, z4) f4(S(z0), 0, z1, z2, S(z3)) -> f3(z0, 0, z1, z2, z3) f4(S(z0), S(z1), z2, z3, 0) -> 0 f4(S(z0), 0, z1, z2, 0) -> 0 f4(0, z0, z1, z2, z3) -> 0 f2(z0, z1, S(z2), S(z3), S(z4)) -> f5(z0, z1, S(z2), z3, z4) f2(z0, z1, S(z2), 0, S(z3)) -> f3(z0, z1, z2, 0, z3) f2(z0, z1, S(z2), S(z3), 0) -> 0 f2(z0, z1, S(z2), 0, 0) -> 0 f2(z0, z1, 0, z2, z3) -> 0 f0(z0, S(z1), z2, S(z3), z4) -> f1(z1, S(z1), z3, S(z3), S(z3)) f0(z0, S(z1), z2, 0, z3) -> 0 f0(z0, 0, z1, z2, z3) -> 0 f6(z0, z1, z2, z3, S(z4)) -> f0(z0, z1, z3, z2, z4) f6(z0, z1, z2, z3, 0) -> 0 f5(z0, z1, z2, z3, S(z4)) -> f6(z1, z0, z2, z3, z4) f5(z0, z1, z2, z3, 0) -> 0 f3(z0, z1, z2, z3, S(z4)) -> f4(z0, z1, z3, z2, z4) f3(z0, z1, z2, z3, 0) -> 0 f1(z0, z1, z2, z3, S(z4)) -> f2(z1, z0, z2, z3, z4) f1(z0, z1, z2, z3, 0) -> 0 Tuples: F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) S tuples: F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) K tuples:none Defined Rule Symbols: f4_5, f2_5, f0_5, f6_5, f5_5, f3_5, f1_5 Defined Pair Symbols: F4_5, F2_5, F0_5, F6_5, F5_5, F3_5, F1_5 Compound Symbols: c_1, c1_1, c5_1, c6_1, c10_1, c13_1, c15_1, c17_1, c19_1 ---------------------------------------- (5) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: f4(S(z0), S(z1), z2, z3, S(z4)) -> f2(S(z0), z1, z2, z3, z4) f4(S(z0), 0, z1, z2, S(z3)) -> f3(z0, 0, z1, z2, z3) f4(S(z0), S(z1), z2, z3, 0) -> 0 f4(S(z0), 0, z1, z2, 0) -> 0 f4(0, z0, z1, z2, z3) -> 0 f2(z0, z1, S(z2), S(z3), S(z4)) -> f5(z0, z1, S(z2), z3, z4) f2(z0, z1, S(z2), 0, S(z3)) -> f3(z0, z1, z2, 0, z3) f2(z0, z1, S(z2), S(z3), 0) -> 0 f2(z0, z1, S(z2), 0, 0) -> 0 f2(z0, z1, 0, z2, z3) -> 0 f0(z0, S(z1), z2, S(z3), z4) -> f1(z1, S(z1), z3, S(z3), S(z3)) f0(z0, S(z1), z2, 0, z3) -> 0 f0(z0, 0, z1, z2, z3) -> 0 f6(z0, z1, z2, z3, S(z4)) -> f0(z0, z1, z3, z2, z4) f6(z0, z1, z2, z3, 0) -> 0 f5(z0, z1, z2, z3, S(z4)) -> f6(z1, z0, z2, z3, z4) f5(z0, z1, z2, z3, 0) -> 0 f3(z0, z1, z2, z3, S(z4)) -> f4(z0, z1, z3, z2, z4) f3(z0, z1, z2, z3, 0) -> 0 f1(z0, z1, z2, z3, S(z4)) -> f2(z1, z0, z2, z3, z4) f1(z0, z1, z2, z3, 0) -> 0 ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules:none Tuples: F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) S tuples: F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) K tuples:none Defined Rule Symbols:none Defined Pair Symbols: F4_5, F2_5, F0_5, F6_5, F5_5, F3_5, F1_5 Compound Symbols: c_1, c1_1, c5_1, c6_1, c10_1, c13_1, c15_1, c17_1, c19_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. F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) We considered the (Usable) Rules:none And the Tuples: F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(F0(x_1, x_2, x_3, x_4, x_5)) = x_2 POL(F1(x_1, x_2, x_3, x_4, x_5)) = x_2 POL(F2(x_1, x_2, x_3, x_4, x_5)) = x_1 POL(F3(x_1, x_2, x_3, x_4, x_5)) = x_1 POL(F4(x_1, x_2, x_3, x_4, x_5)) = x_1 POL(F5(x_1, x_2, x_3, x_4, x_5)) = x_1 POL(F6(x_1, x_2, x_3, x_4, x_5)) = x_2 POL(S(x_1)) = [1] + x_1 POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c10(x_1)) = x_1 POL(c13(x_1)) = x_1 POL(c15(x_1)) = x_1 POL(c17(x_1)) = x_1 POL(c19(x_1)) = x_1 POL(c5(x_1)) = x_1 POL(c6(x_1)) = x_1 ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules:none Tuples: F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) S tuples: F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) K tuples: F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) Defined Rule Symbols:none Defined Pair Symbols: F4_5, F2_5, F0_5, F6_5, F5_5, F3_5, F1_5 Compound Symbols: c_1, c1_1, c5_1, c6_1, c10_1, c13_1, c15_1, c17_1, c19_1 ---------------------------------------- (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) We considered the (Usable) Rules:none And the Tuples: F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = 0 POL(F0(x_1, x_2, x_3, x_4, x_5)) = x_4 POL(F1(x_1, x_2, x_3, x_4, x_5)) = x_3 POL(F2(x_1, x_2, x_3, x_4, x_5)) = x_3 POL(F3(x_1, x_2, x_3, x_4, x_5)) = x_3 + x_4 POL(F4(x_1, x_2, x_3, x_4, x_5)) = x_3 + x_4 POL(F5(x_1, x_2, x_3, x_4, x_5)) = x_3 POL(F6(x_1, x_2, x_3, x_4, x_5)) = x_3 POL(S(x_1)) = [1] + x_1 POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c10(x_1)) = x_1 POL(c13(x_1)) = x_1 POL(c15(x_1)) = x_1 POL(c17(x_1)) = x_1 POL(c19(x_1)) = x_1 POL(c5(x_1)) = x_1 POL(c6(x_1)) = x_1 ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules:none Tuples: F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) S tuples: F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) K tuples: F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) Defined Rule Symbols:none Defined Pair Symbols: F4_5, F2_5, F0_5, F6_5, F5_5, F3_5, F1_5 Compound Symbols: c_1, c1_1, c5_1, c6_1, c10_1, c13_1, c15_1, c17_1, c19_1 ---------------------------------------- (11) CdtKnowledgeProof (FINISHED) The following tuples could be moved from S to K by knowledge propagation: F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) Now S is empty ---------------------------------------- (12) BOUNDS(1, 1) ---------------------------------------- (13) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (14) 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^1). The TRS R consists of the following rules: f4(S(x''), S(x'), x3, x4, S(x)) -> f2(S(x''), x', x3, x4, x) f4(S(x'), 0, x3, x4, S(x)) -> f3(x', 0, x3, x4, x) f2(x1, x2, S(x''), S(x'), S(x)) -> f5(x1, x2, S(x''), x', x) f2(x1, x2, S(x'), 0, S(x)) -> f3(x1, x2, x', 0, x) f4(S(x'), S(x), x3, x4, 0) -> 0 f4(S(x), 0, x3, x4, 0) -> 0 f2(x1, x2, S(x'), S(x), 0) -> 0 f2(x1, x2, S(x), 0, 0) -> 0 f0(x1, S(x'), x3, S(x), x5) -> f1(x', S(x'), x, S(x), S(x)) f0(x1, S(x), x3, 0, x5) -> 0 f6(x1, x2, x3, x4, S(x)) -> f0(x1, x2, x4, x3, x) f5(x1, x2, x3, x4, S(x)) -> f6(x2, x1, x3, x4, x) f3(x1, x2, x3, x4, S(x)) -> f4(x1, x2, x4, x3, x) f1(x1, x2, x3, x4, S(x)) -> f2(x2, x1, x3, x4, x) f6(x1, x2, x3, x4, 0) -> 0 f5(x1, x2, x3, x4, 0) -> 0 f4(0, x2, x3, x4, x5) -> 0 f3(x1, x2, x3, x4, 0) -> 0 f2(x1, x2, 0, x4, x5) -> 0 f1(x1, x2, x3, x4, 0) -> 0 f0(x1, 0, x3, x4, x5) -> 0 S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (15) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence f4(S(x'), 0, x3, x4, S(S(x5_0))) ->^+ f4(x', 0, x4, x3, x5_0) gives rise to a decreasing loop by considering the right hand sides subterm at position []. The pumping substitution is [x' / S(x'), x5_0 / S(S(x5_0))]. The result substitution is [x3 / x4, x4 / x3]. ---------------------------------------- (16) Complex Obligation (BEST) ---------------------------------------- (17) 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^1). The TRS R consists of the following rules: f4(S(x''), S(x'), x3, x4, S(x)) -> f2(S(x''), x', x3, x4, x) f4(S(x'), 0, x3, x4, S(x)) -> f3(x', 0, x3, x4, x) f2(x1, x2, S(x''), S(x'), S(x)) -> f5(x1, x2, S(x''), x', x) f2(x1, x2, S(x'), 0, S(x)) -> f3(x1, x2, x', 0, x) f4(S(x'), S(x), x3, x4, 0) -> 0 f4(S(x), 0, x3, x4, 0) -> 0 f2(x1, x2, S(x'), S(x), 0) -> 0 f2(x1, x2, S(x), 0, 0) -> 0 f0(x1, S(x'), x3, S(x), x5) -> f1(x', S(x'), x, S(x), S(x)) f0(x1, S(x), x3, 0, x5) -> 0 f6(x1, x2, x3, x4, S(x)) -> f0(x1, x2, x4, x3, x) f5(x1, x2, x3, x4, S(x)) -> f6(x2, x1, x3, x4, x) f3(x1, x2, x3, x4, S(x)) -> f4(x1, x2, x4, x3, x) f1(x1, x2, x3, x4, S(x)) -> f2(x2, x1, x3, x4, x) f6(x1, x2, x3, x4, 0) -> 0 f5(x1, x2, x3, x4, 0) -> 0 f4(0, x2, x3, x4, x5) -> 0 f3(x1, x2, x3, x4, 0) -> 0 f2(x1, x2, 0, x4, x5) -> 0 f1(x1, x2, x3, x4, 0) -> 0 f0(x1, 0, x3, x4, x5) -> 0 S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (18) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (19) BOUNDS(n^1, INF) ---------------------------------------- (20) 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^1). The TRS R consists of the following rules: f4(S(x''), S(x'), x3, x4, S(x)) -> f2(S(x''), x', x3, x4, x) f4(S(x'), 0, x3, x4, S(x)) -> f3(x', 0, x3, x4, x) f2(x1, x2, S(x''), S(x'), S(x)) -> f5(x1, x2, S(x''), x', x) f2(x1, x2, S(x'), 0, S(x)) -> f3(x1, x2, x', 0, x) f4(S(x'), S(x), x3, x4, 0) -> 0 f4(S(x), 0, x3, x4, 0) -> 0 f2(x1, x2, S(x'), S(x), 0) -> 0 f2(x1, x2, S(x), 0, 0) -> 0 f0(x1, S(x'), x3, S(x), x5) -> f1(x', S(x'), x, S(x), S(x)) f0(x1, S(x), x3, 0, x5) -> 0 f6(x1, x2, x3, x4, S(x)) -> f0(x1, x2, x4, x3, x) f5(x1, x2, x3, x4, S(x)) -> f6(x2, x1, x3, x4, x) f3(x1, x2, x3, x4, S(x)) -> f4(x1, x2, x4, x3, x) f1(x1, x2, x3, x4, S(x)) -> f2(x2, x1, x3, x4, x) f6(x1, x2, x3, x4, 0) -> 0 f5(x1, x2, x3, x4, 0) -> 0 f4(0, x2, x3, x4, x5) -> 0 f3(x1, x2, x3, x4, 0) -> 0 f2(x1, x2, 0, x4, x5) -> 0 f1(x1, x2, x3, x4, 0) -> 0 f0(x1, 0, x3, x4, x5) -> 0 S is empty. Rewrite Strategy: INNERMOST