/export/starexec/sandbox/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^1). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 168 ms] (4) CpxRelTRS (5) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] (6) CdtProblem (7) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] (8) CdtProblem (9) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CdtProblem (11) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] (12) CdtProblem (13) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (14) CdtProblem (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 97 ms] (16) CdtProblem (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 42 ms] (18) CdtProblem (19) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] (20) BOUNDS(1, 1) (21) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (22) CpxRelTRS (23) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (24) typed CpxTrs (25) OrderProof [LOWER BOUND(ID), 0 ms] (26) typed CpxTrs (27) RewriteLemmaProof [LOWER BOUND(ID), 219 ms] (28) proven lower bound (29) LowerBoundPropagationProof [FINISHED, 0 ms] (30) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: f(0, 1, x) -> f(x, x, x) f(x, y, z) -> 2 0 -> 2 1 -> 2 g(x, x, y) -> y g(x, y, y) -> x S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID)) The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem: encArg(2) -> 2 encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_0) -> 0 encArg(cons_1) -> 1 encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_0 -> 0 encode_1 -> 1 encode_2 -> 2 encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: f(0, 1, x) -> f(x, x, x) f(x, y, z) -> 2 0 -> 2 1 -> 2 g(x, x, y) -> y g(x, y, y) -> x The (relative) TRS S consists of the following rules: encArg(2) -> 2 encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_0) -> 0 encArg(cons_1) -> 1 encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_0 -> 0 encode_1 -> 1 encode_2 -> 2 encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) Rewrite Strategy: INNERMOST ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: f(0, 1, x) -> f(x, x, x) f(x, y, z) -> 2 0 -> 2 1 -> 2 g(x, x, y) -> y g(x, y, y) -> x The (relative) TRS S consists of the following rules: encArg(2) -> 2 encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_0) -> 0 encArg(cons_1) -> 1 encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_0 -> 0 encode_1 -> 1 encode_2 -> 2 encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) Rewrite Strategy: INNERMOST ---------------------------------------- (5) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules: encArg(2) -> 2 encArg(cons_f(z0, z1, z2)) -> f(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_0) -> 0 encArg(cons_1) -> 1 encArg(cons_g(z0, z1, z2)) -> g(encArg(z0), encArg(z1), encArg(z2)) encode_f(z0, z1, z2) -> f(encArg(z0), encArg(z1), encArg(z2)) encode_0 -> 0 encode_1 -> 1 encode_2 -> 2 encode_g(z0, z1, z2) -> g(encArg(z0), encArg(z1), encArg(z2)) f(0, 1, z0) -> f(z0, z0, z0) f(z0, z1, z2) -> 2 0 -> 2 1 -> 2 g(z0, z0, z1) -> z1 g(z0, z1, z1) -> z0 Tuples: ENCARG(2) -> c ENCARG(cons_f(z0, z1, z2)) -> c1(F(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_0) -> c2(0') ENCARG(cons_1) -> c3(1') ENCARG(cons_g(z0, z1, z2)) -> c4(G(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCODE_F(z0, z1, z2) -> c5(F(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCODE_0 -> c6(0') ENCODE_1 -> c7(1') ENCODE_2 -> c8 ENCODE_G(z0, z1, z2) -> c9(G(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) F(0, 1, z0) -> c10(F(z0, z0, z0)) F(z0, z1, z2) -> c11 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 S tuples: F(0, 1, z0) -> c10(F(z0, z0, z0)) F(z0, z1, z2) -> c11 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 K tuples:none Defined Rule Symbols: f_3, 0, 1, g_3, encArg_1, encode_f_3, encode_0, encode_1, encode_2, encode_g_3 Defined Pair Symbols: ENCARG_1, ENCODE_F_3, ENCODE_0, ENCODE_1, ENCODE_2, ENCODE_G_3, F_3, 0', 1', G_3 Compound Symbols: c, c1_4, c2_1, c3_1, c4_4, c5_4, c6_1, c7_1, c8, c9_4, c10_1, c11, c12, c13, c14, c15 ---------------------------------------- (7) CdtLeafRemovalProof (ComplexityIfPolyImplication) Removed 3 leading nodes: ENCODE_0 -> c6(0') ENCODE_1 -> c7(1') F(0, 1, z0) -> c10(F(z0, z0, z0)) Removed 2 trailing nodes: ENCODE_2 -> c8 ENCARG(2) -> c ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules: encArg(2) -> 2 encArg(cons_f(z0, z1, z2)) -> f(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_0) -> 0 encArg(cons_1) -> 1 encArg(cons_g(z0, z1, z2)) -> g(encArg(z0), encArg(z1), encArg(z2)) encode_f(z0, z1, z2) -> f(encArg(z0), encArg(z1), encArg(z2)) encode_0 -> 0 encode_1 -> 1 encode_2 -> 2 encode_g(z0, z1, z2) -> g(encArg(z0), encArg(z1), encArg(z2)) f(0, 1, z0) -> f(z0, z0, z0) f(z0, z1, z2) -> 2 0 -> 2 1 -> 2 g(z0, z0, z1) -> z1 g(z0, z1, z1) -> z0 Tuples: ENCARG(cons_f(z0, z1, z2)) -> c1(F(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_0) -> c2(0') ENCARG(cons_1) -> c3(1') ENCARG(cons_g(z0, z1, z2)) -> c4(G(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCODE_F(z0, z1, z2) -> c5(F(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCODE_G(z0, z1, z2) -> c9(G(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) F(z0, z1, z2) -> c11 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 S tuples: F(z0, z1, z2) -> c11 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 K tuples:none Defined Rule Symbols: f_3, 0, 1, g_3, encArg_1, encode_f_3, encode_0, encode_1, encode_2, encode_g_3 Defined Pair Symbols: ENCARG_1, ENCODE_F_3, ENCODE_G_3, F_3, 0', 1', G_3 Compound Symbols: c1_4, c2_1, c3_1, c4_4, c5_4, c9_4, c11, c12, c13, c14, c15 ---------------------------------------- (9) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID)) Split RHS of tuples not part of any SCC ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules: encArg(2) -> 2 encArg(cons_f(z0, z1, z2)) -> f(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_0) -> 0 encArg(cons_1) -> 1 encArg(cons_g(z0, z1, z2)) -> g(encArg(z0), encArg(z1), encArg(z2)) encode_f(z0, z1, z2) -> f(encArg(z0), encArg(z1), encArg(z2)) encode_0 -> 0 encode_1 -> 1 encode_2 -> 2 encode_g(z0, z1, z2) -> g(encArg(z0), encArg(z1), encArg(z2)) f(0, 1, z0) -> f(z0, z0, z0) f(z0, z1, z2) -> 2 0 -> 2 1 -> 2 g(z0, z0, z1) -> z1 g(z0, z1, z1) -> z0 Tuples: ENCARG(cons_f(z0, z1, z2)) -> c1(F(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_0) -> c2(0') ENCARG(cons_1) -> c3(1') ENCARG(cons_g(z0, z1, z2)) -> c4(G(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) F(z0, z1, z2) -> c11 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 ENCODE_F(z0, z1, z2) -> c(F(encArg(z0), encArg(z1), encArg(z2))) ENCODE_F(z0, z1, z2) -> c(ENCARG(z0)) ENCODE_F(z0, z1, z2) -> c(ENCARG(z1)) ENCODE_F(z0, z1, z2) -> c(ENCARG(z2)) ENCODE_G(z0, z1, z2) -> c(G(encArg(z0), encArg(z1), encArg(z2))) ENCODE_G(z0, z1, z2) -> c(ENCARG(z0)) ENCODE_G(z0, z1, z2) -> c(ENCARG(z1)) ENCODE_G(z0, z1, z2) -> c(ENCARG(z2)) S tuples: F(z0, z1, z2) -> c11 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 K tuples:none Defined Rule Symbols: f_3, 0, 1, g_3, encArg_1, encode_f_3, encode_0, encode_1, encode_2, encode_g_3 Defined Pair Symbols: ENCARG_1, F_3, 0', 1', G_3, ENCODE_F_3, ENCODE_G_3 Compound Symbols: c1_4, c2_1, c3_1, c4_4, c11, c12, c13, c14, c15, c_1 ---------------------------------------- (11) CdtLeafRemovalProof (ComplexityIfPolyImplication) Removed 6 leading nodes: ENCODE_F(z0, z1, z2) -> c(ENCARG(z0)) ENCODE_F(z0, z1, z2) -> c(ENCARG(z1)) ENCODE_F(z0, z1, z2) -> c(ENCARG(z2)) ENCODE_G(z0, z1, z2) -> c(ENCARG(z0)) ENCODE_G(z0, z1, z2) -> c(ENCARG(z1)) ENCODE_G(z0, z1, z2) -> c(ENCARG(z2)) ---------------------------------------- (12) Obligation: Complexity Dependency Tuples Problem Rules: encArg(2) -> 2 encArg(cons_f(z0, z1, z2)) -> f(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_0) -> 0 encArg(cons_1) -> 1 encArg(cons_g(z0, z1, z2)) -> g(encArg(z0), encArg(z1), encArg(z2)) encode_f(z0, z1, z2) -> f(encArg(z0), encArg(z1), encArg(z2)) encode_0 -> 0 encode_1 -> 1 encode_2 -> 2 encode_g(z0, z1, z2) -> g(encArg(z0), encArg(z1), encArg(z2)) f(0, 1, z0) -> f(z0, z0, z0) f(z0, z1, z2) -> 2 0 -> 2 1 -> 2 g(z0, z0, z1) -> z1 g(z0, z1, z1) -> z0 Tuples: ENCARG(cons_f(z0, z1, z2)) -> c1(F(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_0) -> c2(0') ENCARG(cons_1) -> c3(1') ENCARG(cons_g(z0, z1, z2)) -> c4(G(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) F(z0, z1, z2) -> c11 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 ENCODE_F(z0, z1, z2) -> c(F(encArg(z0), encArg(z1), encArg(z2))) ENCODE_G(z0, z1, z2) -> c(G(encArg(z0), encArg(z1), encArg(z2))) S tuples: F(z0, z1, z2) -> c11 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 K tuples:none Defined Rule Symbols: f_3, 0, 1, g_3, encArg_1, encode_f_3, encode_0, encode_1, encode_2, encode_g_3 Defined Pair Symbols: ENCARG_1, F_3, 0', 1', G_3, ENCODE_F_3, ENCODE_G_3 Compound Symbols: c1_4, c2_1, c3_1, c4_4, c11, c12, c13, c14, c15, c_1 ---------------------------------------- (13) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: encode_f(z0, z1, z2) -> f(encArg(z0), encArg(z1), encArg(z2)) encode_0 -> 0 encode_1 -> 1 encode_2 -> 2 encode_g(z0, z1, z2) -> g(encArg(z0), encArg(z1), encArg(z2)) f(0, 1, z0) -> f(z0, z0, z0) ---------------------------------------- (14) Obligation: Complexity Dependency Tuples Problem Rules: encArg(2) -> 2 encArg(cons_f(z0, z1, z2)) -> f(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_0) -> 0 encArg(cons_1) -> 1 encArg(cons_g(z0, z1, z2)) -> g(encArg(z0), encArg(z1), encArg(z2)) f(z0, z1, z2) -> 2 0 -> 2 1 -> 2 g(z0, z0, z1) -> z1 g(z0, z1, z1) -> z0 Tuples: ENCARG(cons_f(z0, z1, z2)) -> c1(F(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_0) -> c2(0') ENCARG(cons_1) -> c3(1') ENCARG(cons_g(z0, z1, z2)) -> c4(G(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) F(z0, z1, z2) -> c11 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 ENCODE_F(z0, z1, z2) -> c(F(encArg(z0), encArg(z1), encArg(z2))) ENCODE_G(z0, z1, z2) -> c(G(encArg(z0), encArg(z1), encArg(z2))) S tuples: F(z0, z1, z2) -> c11 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 K tuples:none Defined Rule Symbols: encArg_1, f_3, 0, 1, g_3 Defined Pair Symbols: ENCARG_1, F_3, 0', 1', G_3, ENCODE_F_3, ENCODE_G_3 Compound Symbols: c1_4, c2_1, c3_1, c4_4, c11, c12, c13, c14, c15, c_1 ---------------------------------------- (15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 We considered the (Usable) Rules:none And the Tuples: ENCARG(cons_f(z0, z1, z2)) -> c1(F(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_0) -> c2(0') ENCARG(cons_1) -> c3(1') ENCARG(cons_g(z0, z1, z2)) -> c4(G(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) F(z0, z1, z2) -> c11 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 ENCODE_F(z0, z1, z2) -> c(F(encArg(z0), encArg(z1), encArg(z2))) ENCODE_G(z0, z1, z2) -> c(G(encArg(z0), encArg(z1), encArg(z2))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(0') = [1] POL(1) = 0 POL(1') = [1] POL(2) = 0 POL(ENCARG(x_1)) = x_1 POL(ENCODE_F(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(ENCODE_G(x_1, x_2, x_3)) = [1] + x_2 POL(F(x_1, x_2, x_3)) = 0 POL(G(x_1, x_2, x_3)) = [1] POL(c(x_1)) = x_1 POL(c1(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 POL(c11) = 0 POL(c12) = 0 POL(c13) = 0 POL(c14) = 0 POL(c15) = 0 POL(c2(x_1)) = x_1 POL(c3(x_1)) = x_1 POL(c4(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 POL(cons_0) = [1] POL(cons_1) = [1] POL(cons_f(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(cons_g(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3 POL(encArg(x_1)) = [1] + x_1 POL(f(x_1, x_2, x_3)) = x_1 POL(g(x_1, x_2, x_3)) = x_1 + x_3 ---------------------------------------- (16) Obligation: Complexity Dependency Tuples Problem Rules: encArg(2) -> 2 encArg(cons_f(z0, z1, z2)) -> f(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_0) -> 0 encArg(cons_1) -> 1 encArg(cons_g(z0, z1, z2)) -> g(encArg(z0), encArg(z1), encArg(z2)) f(z0, z1, z2) -> 2 0 -> 2 1 -> 2 g(z0, z0, z1) -> z1 g(z0, z1, z1) -> z0 Tuples: ENCARG(cons_f(z0, z1, z2)) -> c1(F(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_0) -> c2(0') ENCARG(cons_1) -> c3(1') ENCARG(cons_g(z0, z1, z2)) -> c4(G(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) F(z0, z1, z2) -> c11 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 ENCODE_F(z0, z1, z2) -> c(F(encArg(z0), encArg(z1), encArg(z2))) ENCODE_G(z0, z1, z2) -> c(G(encArg(z0), encArg(z1), encArg(z2))) S tuples: F(z0, z1, z2) -> c11 K tuples: 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 Defined Rule Symbols: encArg_1, f_3, 0, 1, g_3 Defined Pair Symbols: ENCARG_1, F_3, 0', 1', G_3, ENCODE_F_3, ENCODE_G_3 Compound Symbols: c1_4, c2_1, c3_1, c4_4, c11, c12, c13, c14, c15, c_1 ---------------------------------------- (17) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. F(z0, z1, z2) -> c11 We considered the (Usable) Rules:none And the Tuples: ENCARG(cons_f(z0, z1, z2)) -> c1(F(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_0) -> c2(0') ENCARG(cons_1) -> c3(1') ENCARG(cons_g(z0, z1, z2)) -> c4(G(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) F(z0, z1, z2) -> c11 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 ENCODE_F(z0, z1, z2) -> c(F(encArg(z0), encArg(z1), encArg(z2))) ENCODE_G(z0, z1, z2) -> c(G(encArg(z0), encArg(z1), encArg(z2))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(0') = 0 POL(1) = [1] POL(1') = [1] POL(2) = 0 POL(ENCARG(x_1)) = x_1 POL(ENCODE_F(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3 POL(ENCODE_G(x_1, x_2, x_3)) = [1] POL(F(x_1, x_2, x_3)) = [1] POL(G(x_1, x_2, x_3)) = [1] POL(c(x_1)) = x_1 POL(c1(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 POL(c11) = 0 POL(c12) = 0 POL(c13) = 0 POL(c14) = 0 POL(c15) = 0 POL(c2(x_1)) = x_1 POL(c3(x_1)) = x_1 POL(c4(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 POL(cons_0) = 0 POL(cons_1) = [1] POL(cons_f(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3 POL(cons_g(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3 POL(encArg(x_1)) = [1] + x_1 POL(f(x_1, x_2, x_3)) = x_1 + x_3 POL(g(x_1, x_2, x_3)) = x_1 + x_3 ---------------------------------------- (18) Obligation: Complexity Dependency Tuples Problem Rules: encArg(2) -> 2 encArg(cons_f(z0, z1, z2)) -> f(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_0) -> 0 encArg(cons_1) -> 1 encArg(cons_g(z0, z1, z2)) -> g(encArg(z0), encArg(z1), encArg(z2)) f(z0, z1, z2) -> 2 0 -> 2 1 -> 2 g(z0, z0, z1) -> z1 g(z0, z1, z1) -> z0 Tuples: ENCARG(cons_f(z0, z1, z2)) -> c1(F(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_0) -> c2(0') ENCARG(cons_1) -> c3(1') ENCARG(cons_g(z0, z1, z2)) -> c4(G(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) F(z0, z1, z2) -> c11 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 ENCODE_F(z0, z1, z2) -> c(F(encArg(z0), encArg(z1), encArg(z2))) ENCODE_G(z0, z1, z2) -> c(G(encArg(z0), encArg(z1), encArg(z2))) S tuples:none K tuples: 0' -> c12 1' -> c13 G(z0, z0, z1) -> c14 G(z0, z1, z1) -> c15 F(z0, z1, z2) -> c11 Defined Rule Symbols: encArg_1, f_3, 0, 1, g_3 Defined Pair Symbols: ENCARG_1, F_3, 0', 1', G_3, ENCODE_F_3, ENCODE_G_3 Compound Symbols: c1_4, c2_1, c3_1, c4_4, c11, c12, c13, c14, c15, c_1 ---------------------------------------- (19) SIsEmptyProof (BOTH BOUNDS(ID, ID)) The set S is empty ---------------------------------------- (20) BOUNDS(1, 1) ---------------------------------------- (21) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (22) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: f(0', 1', x) -> f(x, x, x) f(x, y, z) -> 2' 0' -> 2' 1' -> 2' g(x, x, y) -> y g(x, y, y) -> x The (relative) TRS S consists of the following rules: encArg(2') -> 2' encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_0) -> 0' encArg(cons_1) -> 1' encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_0 -> 0' encode_1 -> 1' encode_2 -> 2' encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) Rewrite Strategy: INNERMOST ---------------------------------------- (23) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (24) Obligation: Innermost TRS: Rules: f(0', 1', x) -> f(x, x, x) f(x, y, z) -> 2' 0' -> 2' 1' -> 2' g(x, x, y) -> y g(x, y, y) -> x encArg(2') -> 2' encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_0) -> 0' encArg(cons_1) -> 1' encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_0 -> 0' encode_1 -> 1' encode_2 -> 2' encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) Types: f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g 0' :: 2':cons_f:cons_0:cons_1:cons_g 1' :: 2':cons_f:cons_0:cons_1:cons_g 2' :: 2':cons_f:cons_0:cons_1:cons_g g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g encArg :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g cons_f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g cons_0 :: 2':cons_f:cons_0:cons_1:cons_g cons_1 :: 2':cons_f:cons_0:cons_1:cons_g cons_g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g encode_f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g encode_0 :: 2':cons_f:cons_0:cons_1:cons_g encode_1 :: 2':cons_f:cons_0:cons_1:cons_g encode_2 :: 2':cons_f:cons_0:cons_1:cons_g encode_g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g hole_2':cons_f:cons_0:cons_1:cons_g1_4 :: 2':cons_f:cons_0:cons_1:cons_g gen_2':cons_f:cons_0:cons_1:cons_g2_4 :: Nat -> 2':cons_f:cons_0:cons_1:cons_g ---------------------------------------- (25) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: f, encArg They will be analysed ascendingly in the following order: f < encArg ---------------------------------------- (26) Obligation: Innermost TRS: Rules: f(0', 1', x) -> f(x, x, x) f(x, y, z) -> 2' 0' -> 2' 1' -> 2' g(x, x, y) -> y g(x, y, y) -> x encArg(2') -> 2' encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_0) -> 0' encArg(cons_1) -> 1' encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_0 -> 0' encode_1 -> 1' encode_2 -> 2' encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) Types: f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g 0' :: 2':cons_f:cons_0:cons_1:cons_g 1' :: 2':cons_f:cons_0:cons_1:cons_g 2' :: 2':cons_f:cons_0:cons_1:cons_g g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g encArg :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g cons_f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g cons_0 :: 2':cons_f:cons_0:cons_1:cons_g cons_1 :: 2':cons_f:cons_0:cons_1:cons_g cons_g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g encode_f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g encode_0 :: 2':cons_f:cons_0:cons_1:cons_g encode_1 :: 2':cons_f:cons_0:cons_1:cons_g encode_2 :: 2':cons_f:cons_0:cons_1:cons_g encode_g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g hole_2':cons_f:cons_0:cons_1:cons_g1_4 :: 2':cons_f:cons_0:cons_1:cons_g gen_2':cons_f:cons_0:cons_1:cons_g2_4 :: Nat -> 2':cons_f:cons_0:cons_1:cons_g Generator Equations: gen_2':cons_f:cons_0:cons_1:cons_g2_4(0) <=> 2' gen_2':cons_f:cons_0:cons_1:cons_g2_4(+(x, 1)) <=> cons_f(2', 2', gen_2':cons_f:cons_0:cons_1:cons_g2_4(x)) The following defined symbols remain to be analysed: f, encArg They will be analysed ascendingly in the following order: f < encArg ---------------------------------------- (27) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_2':cons_f:cons_0:cons_1:cons_g2_4(n14_4)) -> gen_2':cons_f:cons_0:cons_1:cons_g2_4(0), rt in Omega(n14_4) Induction Base: encArg(gen_2':cons_f:cons_0:cons_1:cons_g2_4(0)) ->_R^Omega(0) 2' Induction Step: encArg(gen_2':cons_f:cons_0:cons_1:cons_g2_4(+(n14_4, 1))) ->_R^Omega(0) f(encArg(2'), encArg(2'), encArg(gen_2':cons_f:cons_0:cons_1:cons_g2_4(n14_4))) ->_R^Omega(0) f(2', encArg(2'), encArg(gen_2':cons_f:cons_0:cons_1:cons_g2_4(n14_4))) ->_R^Omega(0) f(2', 2', encArg(gen_2':cons_f:cons_0:cons_1:cons_g2_4(n14_4))) ->_IH f(2', 2', gen_2':cons_f:cons_0:cons_1:cons_g2_4(0)) ->_R^Omega(1) 2' We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (28) Obligation: Proved the lower bound n^1 for the following obligation: Innermost TRS: Rules: f(0', 1', x) -> f(x, x, x) f(x, y, z) -> 2' 0' -> 2' 1' -> 2' g(x, x, y) -> y g(x, y, y) -> x encArg(2') -> 2' encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_0) -> 0' encArg(cons_1) -> 1' encArg(cons_g(x_1, x_2, x_3)) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_0 -> 0' encode_1 -> 1' encode_2 -> 2' encode_g(x_1, x_2, x_3) -> g(encArg(x_1), encArg(x_2), encArg(x_3)) Types: f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g 0' :: 2':cons_f:cons_0:cons_1:cons_g 1' :: 2':cons_f:cons_0:cons_1:cons_g 2' :: 2':cons_f:cons_0:cons_1:cons_g g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g encArg :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g cons_f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g cons_0 :: 2':cons_f:cons_0:cons_1:cons_g cons_1 :: 2':cons_f:cons_0:cons_1:cons_g cons_g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g encode_f :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g encode_0 :: 2':cons_f:cons_0:cons_1:cons_g encode_1 :: 2':cons_f:cons_0:cons_1:cons_g encode_2 :: 2':cons_f:cons_0:cons_1:cons_g encode_g :: 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g -> 2':cons_f:cons_0:cons_1:cons_g hole_2':cons_f:cons_0:cons_1:cons_g1_4 :: 2':cons_f:cons_0:cons_1:cons_g gen_2':cons_f:cons_0:cons_1:cons_g2_4 :: Nat -> 2':cons_f:cons_0:cons_1:cons_g Generator Equations: gen_2':cons_f:cons_0:cons_1:cons_g2_4(0) <=> 2' gen_2':cons_f:cons_0:cons_1:cons_g2_4(+(x, 1)) <=> cons_f(2', 2', gen_2':cons_f:cons_0:cons_1:cons_g2_4(x)) The following defined symbols remain to be analysed: encArg ---------------------------------------- (29) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (30) BOUNDS(n^1, INF)