/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(?, O(n^1))
proof of /export/starexec/sandbox2/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(1, n^1).

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 217 ms]
(4) CpxRelTRS
(5) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
(6) CdtProblem
(7) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
(8) CdtProblem
(9) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
(10) CdtProblem
(11) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms]
(12) CdtProblem
(13) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
(14) CdtProblem
(15) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
(16) CdtProblem
(17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 110 ms]
(18) CdtProblem
(19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 50 ms]
(20) CdtProblem
(21) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
(22) BOUNDS(1, 1)


----------------------------------------

(0)
Obligation:
The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(1, n^1).


The TRS R consists of the following rules:

   f(g(x)) -> g(g(f(x)))
   g(s(x)) -> s(s(g(x)))
   s(x) -> h(0, x)
   s(x) -> h(x, 0)
   f(0) -> 0
   s(s(s(0))) -> f(s(0))
   f(s(0)) -> s(0)
   h(f(x), g(x)) -> f(s(x))
   g(x) -> h(h(h(h(x, x), x), x), x)
   f(s(s(x))) -> h(f(x), g(h(x, x)))
   s(0) -> r(0)
   s(s(s(0))) -> r(s(0))
   r(s(0)) -> s(0)
   g(x) -> r(x)
   s(0) -> p(0)
   s(s(0)) -> p(s(0))
   p(s(0)) -> 0
   s(s(s(s(s(0))))) -> p(s(s(0)))
   p(s(s(0))) -> s(s(s(0)))
   h(p(x), g(x)) -> p(s(x))
   s(0) -> k(0)
   s(s(p(p(a)))) -> s(k(p(a)))
   s(k(p(a))) -> p(p(a))
   g(x) -> k(x)
   a -> 0
   s(h(r(k(p(x))), r(x))) -> h(r(r(p(x))), k(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(0) -> 0
   encArg(k(x_1)) -> k(encArg(x_1))
   encArg(cons_f(x_1)) -> f(encArg(x_1))
   encArg(cons_g(x_1)) -> g(encArg(x_1))
   encArg(cons_s(x_1)) -> s(encArg(x_1))
   encArg(cons_h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2))
   encArg(cons_r(x_1)) -> r(encArg(x_1))
   encArg(cons_p(x_1)) -> p(encArg(x_1))
   encArg(cons_a) -> a
   encode_f(x_1) -> f(encArg(x_1))
   encode_g(x_1) -> g(encArg(x_1))
   encode_s(x_1) -> s(encArg(x_1))
   encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2))
   encode_0 -> 0
   encode_r(x_1) -> r(encArg(x_1))
   encode_p(x_1) -> p(encArg(x_1))
   encode_k(x_1) -> k(encArg(x_1))
   encode_a -> a


----------------------------------------

(2)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1).


The TRS R consists of the following rules:

   f(g(x)) -> g(g(f(x)))
   g(s(x)) -> s(s(g(x)))
   s(x) -> h(0, x)
   s(x) -> h(x, 0)
   f(0) -> 0
   s(s(s(0))) -> f(s(0))
   f(s(0)) -> s(0)
   h(f(x), g(x)) -> f(s(x))
   g(x) -> h(h(h(h(x, x), x), x), x)
   f(s(s(x))) -> h(f(x), g(h(x, x)))
   s(0) -> r(0)
   s(s(s(0))) -> r(s(0))
   r(s(0)) -> s(0)
   g(x) -> r(x)
   s(0) -> p(0)
   s(s(0)) -> p(s(0))
   p(s(0)) -> 0
   s(s(s(s(s(0))))) -> p(s(s(0)))
   p(s(s(0))) -> s(s(s(0)))
   h(p(x), g(x)) -> p(s(x))
   s(0) -> k(0)
   s(s(p(p(a)))) -> s(k(p(a)))
   s(k(p(a))) -> p(p(a))
   g(x) -> k(x)
   a -> 0
   s(h(r(k(p(x))), r(x))) -> h(r(r(p(x))), k(x))

The (relative) TRS S consists of the following rules:

   encArg(0) -> 0
   encArg(k(x_1)) -> k(encArg(x_1))
   encArg(cons_f(x_1)) -> f(encArg(x_1))
   encArg(cons_g(x_1)) -> g(encArg(x_1))
   encArg(cons_s(x_1)) -> s(encArg(x_1))
   encArg(cons_h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2))
   encArg(cons_r(x_1)) -> r(encArg(x_1))
   encArg(cons_p(x_1)) -> p(encArg(x_1))
   encArg(cons_a) -> a
   encode_f(x_1) -> f(encArg(x_1))
   encode_g(x_1) -> g(encArg(x_1))
   encode_s(x_1) -> s(encArg(x_1))
   encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2))
   encode_0 -> 0
   encode_r(x_1) -> r(encArg(x_1))
   encode_p(x_1) -> p(encArg(x_1))
   encode_k(x_1) -> k(encArg(x_1))
   encode_a -> a

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(1, n^1).


The TRS R consists of the following rules:

   f(g(x)) -> g(g(f(x)))
   g(s(x)) -> s(s(g(x)))
   s(x) -> h(0, x)
   s(x) -> h(x, 0)
   f(0) -> 0
   s(s(s(0))) -> f(s(0))
   f(s(0)) -> s(0)
   h(f(x), g(x)) -> f(s(x))
   g(x) -> h(h(h(h(x, x), x), x), x)
   f(s(s(x))) -> h(f(x), g(h(x, x)))
   s(0) -> r(0)
   s(s(s(0))) -> r(s(0))
   r(s(0)) -> s(0)
   g(x) -> r(x)
   s(0) -> p(0)
   s(s(0)) -> p(s(0))
   p(s(0)) -> 0
   s(s(s(s(s(0))))) -> p(s(s(0)))
   p(s(s(0))) -> s(s(s(0)))
   h(p(x), g(x)) -> p(s(x))
   s(0) -> k(0)
   s(s(p(p(a)))) -> s(k(p(a)))
   s(k(p(a))) -> p(p(a))
   g(x) -> k(x)
   a -> 0
   s(h(r(k(p(x))), r(x))) -> h(r(r(p(x))), k(x))

The (relative) TRS S consists of the following rules:

   encArg(0) -> 0
   encArg(k(x_1)) -> k(encArg(x_1))
   encArg(cons_f(x_1)) -> f(encArg(x_1))
   encArg(cons_g(x_1)) -> g(encArg(x_1))
   encArg(cons_s(x_1)) -> s(encArg(x_1))
   encArg(cons_h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2))
   encArg(cons_r(x_1)) -> r(encArg(x_1))
   encArg(cons_p(x_1)) -> p(encArg(x_1))
   encArg(cons_a) -> a
   encode_f(x_1) -> f(encArg(x_1))
   encode_g(x_1) -> g(encArg(x_1))
   encode_s(x_1) -> s(encArg(x_1))
   encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2))
   encode_0 -> 0
   encode_r(x_1) -> r(encArg(x_1))
   encode_p(x_1) -> p(encArg(x_1))
   encode_k(x_1) -> k(encArg(x_1))
   encode_a -> a

Rewrite Strategy: INNERMOST
----------------------------------------

(5) CpxTrsToCdtProof (UPPER BOUND(ID))
Converted Cpx (relative) TRS to CDT
----------------------------------------

(6)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(k(z0)) -> k(encArg(z0))
   encArg(cons_f(z0)) -> f(encArg(z0))
   encArg(cons_g(z0)) -> g(encArg(z0))
   encArg(cons_s(z0)) -> s(encArg(z0))
   encArg(cons_h(z0, z1)) -> h(encArg(z0), encArg(z1))
   encArg(cons_r(z0)) -> r(encArg(z0))
   encArg(cons_p(z0)) -> p(encArg(z0))
   encArg(cons_a) -> a
   encode_f(z0) -> f(encArg(z0))
   encode_g(z0) -> g(encArg(z0))
   encode_s(z0) -> s(encArg(z0))
   encode_h(z0, z1) -> h(encArg(z0), encArg(z1))
   encode_0 -> 0
   encode_r(z0) -> r(encArg(z0))
   encode_p(z0) -> p(encArg(z0))
   encode_k(z0) -> k(encArg(z0))
   encode_a -> a
   f(g(z0)) -> g(g(f(z0)))
   f(0) -> 0
   f(s(0)) -> s(0)
   f(s(s(z0))) -> h(f(z0), g(h(z0, z0)))
   g(s(z0)) -> s(s(g(z0)))
   g(z0) -> h(h(h(h(z0, z0), z0), z0), z0)
   g(z0) -> r(z0)
   g(z0) -> k(z0)
   s(z0) -> h(0, z0)
   s(z0) -> h(z0, 0)
   s(s(s(0))) -> f(s(0))
   s(0) -> r(0)
   s(s(s(0))) -> r(s(0))
   s(0) -> p(0)
   s(s(0)) -> p(s(0))
   s(s(s(s(s(0))))) -> p(s(s(0)))
   s(0) -> k(0)
   s(s(p(p(a)))) -> s(k(p(a)))
   s(k(p(a))) -> p(p(a))
   s(h(r(k(p(z0))), r(z0))) -> h(r(r(p(z0))), k(z0))
   h(f(z0), g(z0)) -> f(s(z0))
   h(p(z0), g(z0)) -> p(s(z0))
   r(s(0)) -> s(0)
   p(s(0)) -> 0
   p(s(s(0))) -> s(s(s(0)))
   a -> 0
Tuples:
   ENCARG(0) -> c
   ENCARG(k(z0)) -> c1(ENCARG(z0))
   ENCARG(cons_f(z0)) -> c2(F(encArg(z0)), ENCARG(z0))
   ENCARG(cons_g(z0)) -> c3(G(encArg(z0)), ENCARG(z0))
   ENCARG(cons_s(z0)) -> c4(S(encArg(z0)), ENCARG(z0))
   ENCARG(cons_h(z0, z1)) -> c5(H(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_r(z0)) -> c6(R(encArg(z0)), ENCARG(z0))
   ENCARG(cons_p(z0)) -> c7(P(encArg(z0)), ENCARG(z0))
   ENCARG(cons_a) -> c8(A)
   ENCODE_F(z0) -> c9(F(encArg(z0)), ENCARG(z0))
   ENCODE_G(z0) -> c10(G(encArg(z0)), ENCARG(z0))
   ENCODE_S(z0) -> c11(S(encArg(z0)), ENCARG(z0))
   ENCODE_H(z0, z1) -> c12(H(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCODE_0 -> c13
   ENCODE_R(z0) -> c14(R(encArg(z0)), ENCARG(z0))
   ENCODE_P(z0) -> c15(P(encArg(z0)), ENCARG(z0))
   ENCODE_K(z0) -> c16(ENCARG(z0))
   ENCODE_A -> c17(A)
   F(g(z0)) -> c18(G(g(f(z0))), G(f(z0)), F(z0))
   F(0) -> c19
   F(s(0)) -> c20(S(0))
   F(s(s(z0))) -> c21(H(f(z0), g(h(z0, z0))), F(z0), G(h(z0, z0)), H(z0, z0))
   G(s(z0)) -> c22(S(s(g(z0))), S(g(z0)), G(z0))
   G(z0) -> c23(H(h(h(h(z0, z0), z0), z0), z0), H(h(h(z0, z0), z0), z0), H(h(z0, z0), z0), H(z0, z0))
   G(z0) -> c24(R(z0))
   G(z0) -> c25
   S(z0) -> c26(H(0, z0))
   S(z0) -> c27(H(z0, 0))
   S(s(s(0))) -> c28(F(s(0)), S(0))
   S(0) -> c29(R(0))
   S(s(s(0))) -> c30(R(s(0)), S(0))
   S(0) -> c31(P(0))
   S(s(0)) -> c32(P(s(0)), S(0))
   S(s(s(s(s(0))))) -> c33(P(s(s(0))), S(s(0)), S(0))
   S(0) -> c34
   S(s(p(p(a)))) -> c35(S(k(p(a))), P(a), A)
   S(k(p(a))) -> c36(P(p(a)), P(a), A)
   S(h(r(k(p(z0))), r(z0))) -> c37(H(r(r(p(z0))), k(z0)), R(r(p(z0))), R(p(z0)), P(z0))
   H(f(z0), g(z0)) -> c38(F(s(z0)), S(z0))
   H(p(z0), g(z0)) -> c39(P(s(z0)), S(z0))
   R(s(0)) -> c40(S(0))
   P(s(0)) -> c41
   P(s(s(0))) -> c42(S(s(s(0))), S(s(0)), S(0))
   A -> c43
S tuples:
   F(g(z0)) -> c18(G(g(f(z0))), G(f(z0)), F(z0))
   F(0) -> c19
   F(s(0)) -> c20(S(0))
   F(s(s(z0))) -> c21(H(f(z0), g(h(z0, z0))), F(z0), G(h(z0, z0)), H(z0, z0))
   G(s(z0)) -> c22(S(s(g(z0))), S(g(z0)), G(z0))
   G(z0) -> c23(H(h(h(h(z0, z0), z0), z0), z0), H(h(h(z0, z0), z0), z0), H(h(z0, z0), z0), H(z0, z0))
   G(z0) -> c24(R(z0))
   G(z0) -> c25
   S(z0) -> c26(H(0, z0))
   S(z0) -> c27(H(z0, 0))
   S(s(s(0))) -> c28(F(s(0)), S(0))
   S(0) -> c29(R(0))
   S(s(s(0))) -> c30(R(s(0)), S(0))
   S(0) -> c31(P(0))
   S(s(0)) -> c32(P(s(0)), S(0))
   S(s(s(s(s(0))))) -> c33(P(s(s(0))), S(s(0)), S(0))
   S(0) -> c34
   S(s(p(p(a)))) -> c35(S(k(p(a))), P(a), A)
   S(k(p(a))) -> c36(P(p(a)), P(a), A)
   S(h(r(k(p(z0))), r(z0))) -> c37(H(r(r(p(z0))), k(z0)), R(r(p(z0))), R(p(z0)), P(z0))
   H(f(z0), g(z0)) -> c38(F(s(z0)), S(z0))
   H(p(z0), g(z0)) -> c39(P(s(z0)), S(z0))
   R(s(0)) -> c40(S(0))
   P(s(0)) -> c41
   P(s(s(0))) -> c42(S(s(s(0))), S(s(0)), S(0))
   A -> c43
K tuples:none
Defined Rule Symbols:   f_1, g_1, s_1, h_2, r_1, p_1, a, encArg_1, encode_f_1, encode_g_1, encode_s_1, encode_h_2, encode_0, encode_r_1, encode_p_1, encode_k_1, encode_a

Defined Pair Symbols:   ENCARG_1, ENCODE_F_1, ENCODE_G_1, ENCODE_S_1, ENCODE_H_2, ENCODE_0, ENCODE_R_1, ENCODE_P_1, ENCODE_K_1, ENCODE_A, F_1, G_1, S_1, H_2, R_1, P_1, A

Compound Symbols:   c, c1_1, c2_2, c3_2, c4_2, c5_3, c6_2, c7_2, c8_1, c9_2, c10_2, c11_2, c12_3, c13, c14_2, c15_2, c16_1, c17_1, c18_3, c19, c20_1, c21_4, c22_3, c23_4, c24_1, c25, c26_1, c27_1, c28_2, c29_1, c30_2, c31_1, c32_2, c33_3, c34, c35_3, c36_3, c37_4, c38_2, c39_2, c40_1, c41, c42_3, c43


----------------------------------------

(7) CdtLeafRemovalProof (ComplexityIfPolyImplication)
Removed 16 leading nodes:
   ENCODE_K(z0) -> c16(ENCARG(z0))
   ENCODE_A -> c17(A)
   F(g(z0)) -> c18(G(g(f(z0))), G(f(z0)), F(z0))
   F(s(s(z0))) -> c21(H(f(z0), g(h(z0, z0))), F(z0), G(h(z0, z0)), H(z0, z0))
   F(s(0)) -> c20(S(0))
   G(s(z0)) -> c22(S(s(g(z0))), S(g(z0)), G(z0))
   S(s(s(0))) -> c28(F(s(0)), S(0))
   S(s(s(0))) -> c30(R(s(0)), S(0))
   S(s(0)) -> c32(P(s(0)), S(0))
   S(s(s(s(s(0))))) -> c33(P(s(s(0))), S(s(0)), S(0))
   H(f(z0), g(z0)) -> c38(F(s(z0)), S(z0))
   H(p(z0), g(z0)) -> c39(P(s(z0)), S(z0))
   R(s(0)) -> c40(S(0))
   P(s(s(0))) -> c42(S(s(s(0))), S(s(0)), S(0))
   S(s(p(p(a)))) -> c35(S(k(p(a))), P(a), A)
   S(k(p(a))) -> c36(P(p(a)), P(a), A)
Removed 3 trailing nodes:
   ENCARG(0) -> c
   P(s(0)) -> c41
   ENCODE_0 -> c13

----------------------------------------

(8)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(k(z0)) -> k(encArg(z0))
   encArg(cons_f(z0)) -> f(encArg(z0))
   encArg(cons_g(z0)) -> g(encArg(z0))
   encArg(cons_s(z0)) -> s(encArg(z0))
   encArg(cons_h(z0, z1)) -> h(encArg(z0), encArg(z1))
   encArg(cons_r(z0)) -> r(encArg(z0))
   encArg(cons_p(z0)) -> p(encArg(z0))
   encArg(cons_a) -> a
   encode_f(z0) -> f(encArg(z0))
   encode_g(z0) -> g(encArg(z0))
   encode_s(z0) -> s(encArg(z0))
   encode_h(z0, z1) -> h(encArg(z0), encArg(z1))
   encode_0 -> 0
   encode_r(z0) -> r(encArg(z0))
   encode_p(z0) -> p(encArg(z0))
   encode_k(z0) -> k(encArg(z0))
   encode_a -> a
   f(g(z0)) -> g(g(f(z0)))
   f(0) -> 0
   f(s(0)) -> s(0)
   f(s(s(z0))) -> h(f(z0), g(h(z0, z0)))
   g(s(z0)) -> s(s(g(z0)))
   g(z0) -> h(h(h(h(z0, z0), z0), z0), z0)
   g(z0) -> r(z0)
   g(z0) -> k(z0)
   s(z0) -> h(0, z0)
   s(z0) -> h(z0, 0)
   s(s(s(0))) -> f(s(0))
   s(0) -> r(0)
   s(s(s(0))) -> r(s(0))
   s(0) -> p(0)
   s(s(0)) -> p(s(0))
   s(s(s(s(s(0))))) -> p(s(s(0)))
   s(0) -> k(0)
   s(s(p(p(a)))) -> s(k(p(a)))
   s(k(p(a))) -> p(p(a))
   s(h(r(k(p(z0))), r(z0))) -> h(r(r(p(z0))), k(z0))
   h(f(z0), g(z0)) -> f(s(z0))
   h(p(z0), g(z0)) -> p(s(z0))
   r(s(0)) -> s(0)
   p(s(0)) -> 0
   p(s(s(0))) -> s(s(s(0)))
   a -> 0
Tuples:
   ENCARG(k(z0)) -> c1(ENCARG(z0))
   ENCARG(cons_f(z0)) -> c2(F(encArg(z0)), ENCARG(z0))
   ENCARG(cons_g(z0)) -> c3(G(encArg(z0)), ENCARG(z0))
   ENCARG(cons_s(z0)) -> c4(S(encArg(z0)), ENCARG(z0))
   ENCARG(cons_h(z0, z1)) -> c5(H(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_r(z0)) -> c6(R(encArg(z0)), ENCARG(z0))
   ENCARG(cons_p(z0)) -> c7(P(encArg(z0)), ENCARG(z0))
   ENCARG(cons_a) -> c8(A)
   ENCODE_F(z0) -> c9(F(encArg(z0)), ENCARG(z0))
   ENCODE_G(z0) -> c10(G(encArg(z0)), ENCARG(z0))
   ENCODE_S(z0) -> c11(S(encArg(z0)), ENCARG(z0))
   ENCODE_H(z0, z1) -> c12(H(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCODE_R(z0) -> c14(R(encArg(z0)), ENCARG(z0))
   ENCODE_P(z0) -> c15(P(encArg(z0)), ENCARG(z0))
   F(0) -> c19
   G(z0) -> c23(H(h(h(h(z0, z0), z0), z0), z0), H(h(h(z0, z0), z0), z0), H(h(z0, z0), z0), H(z0, z0))
   G(z0) -> c24(R(z0))
   G(z0) -> c25
   S(z0) -> c26(H(0, z0))
   S(z0) -> c27(H(z0, 0))
   S(0) -> c29(R(0))
   S(0) -> c31(P(0))
   S(0) -> c34
   S(h(r(k(p(z0))), r(z0))) -> c37(H(r(r(p(z0))), k(z0)), R(r(p(z0))), R(p(z0)), P(z0))
   A -> c43
S tuples:
   F(0) -> c19
   G(z0) -> c23(H(h(h(h(z0, z0), z0), z0), z0), H(h(h(z0, z0), z0), z0), H(h(z0, z0), z0), H(z0, z0))
   G(z0) -> c24(R(z0))
   G(z0) -> c25
   S(z0) -> c26(H(0, z0))
   S(z0) -> c27(H(z0, 0))
   S(0) -> c29(R(0))
   S(0) -> c31(P(0))
   S(0) -> c34
   S(h(r(k(p(z0))), r(z0))) -> c37(H(r(r(p(z0))), k(z0)), R(r(p(z0))), R(p(z0)), P(z0))
   A -> c43
K tuples:none
Defined Rule Symbols:   f_1, g_1, s_1, h_2, r_1, p_1, a, encArg_1, encode_f_1, encode_g_1, encode_s_1, encode_h_2, encode_0, encode_r_1, encode_p_1, encode_k_1, encode_a

Defined Pair Symbols:   ENCARG_1, ENCODE_F_1, ENCODE_G_1, ENCODE_S_1, ENCODE_H_2, ENCODE_R_1, ENCODE_P_1, F_1, G_1, S_1, A

Compound Symbols:   c1_1, c2_2, c3_2, c4_2, c5_3, c6_2, c7_2, c8_1, c9_2, c10_2, c11_2, c12_3, c14_2, c15_2, c19, c23_4, c24_1, c25, c26_1, c27_1, c29_1, c31_1, c34, c37_4, c43


----------------------------------------

(9) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))
Removed 19 trailing tuple parts
----------------------------------------

(10)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(k(z0)) -> k(encArg(z0))
   encArg(cons_f(z0)) -> f(encArg(z0))
   encArg(cons_g(z0)) -> g(encArg(z0))
   encArg(cons_s(z0)) -> s(encArg(z0))
   encArg(cons_h(z0, z1)) -> h(encArg(z0), encArg(z1))
   encArg(cons_r(z0)) -> r(encArg(z0))
   encArg(cons_p(z0)) -> p(encArg(z0))
   encArg(cons_a) -> a
   encode_f(z0) -> f(encArg(z0))
   encode_g(z0) -> g(encArg(z0))
   encode_s(z0) -> s(encArg(z0))
   encode_h(z0, z1) -> h(encArg(z0), encArg(z1))
   encode_0 -> 0
   encode_r(z0) -> r(encArg(z0))
   encode_p(z0) -> p(encArg(z0))
   encode_k(z0) -> k(encArg(z0))
   encode_a -> a
   f(g(z0)) -> g(g(f(z0)))
   f(0) -> 0
   f(s(0)) -> s(0)
   f(s(s(z0))) -> h(f(z0), g(h(z0, z0)))
   g(s(z0)) -> s(s(g(z0)))
   g(z0) -> h(h(h(h(z0, z0), z0), z0), z0)
   g(z0) -> r(z0)
   g(z0) -> k(z0)
   s(z0) -> h(0, z0)
   s(z0) -> h(z0, 0)
   s(s(s(0))) -> f(s(0))
   s(0) -> r(0)
   s(s(s(0))) -> r(s(0))
   s(0) -> p(0)
   s(s(0)) -> p(s(0))
   s(s(s(s(s(0))))) -> p(s(s(0)))
   s(0) -> k(0)
   s(s(p(p(a)))) -> s(k(p(a)))
   s(k(p(a))) -> p(p(a))
   s(h(r(k(p(z0))), r(z0))) -> h(r(r(p(z0))), k(z0))
   h(f(z0), g(z0)) -> f(s(z0))
   h(p(z0), g(z0)) -> p(s(z0))
   r(s(0)) -> s(0)
   p(s(0)) -> 0
   p(s(s(0))) -> s(s(s(0)))
   a -> 0
Tuples:
   ENCARG(k(z0)) -> c1(ENCARG(z0))
   ENCARG(cons_f(z0)) -> c2(F(encArg(z0)), ENCARG(z0))
   ENCARG(cons_g(z0)) -> c3(G(encArg(z0)), ENCARG(z0))
   ENCARG(cons_s(z0)) -> c4(S(encArg(z0)), ENCARG(z0))
   ENCARG(cons_a) -> c8(A)
   ENCODE_F(z0) -> c9(F(encArg(z0)), ENCARG(z0))
   ENCODE_G(z0) -> c10(G(encArg(z0)), ENCARG(z0))
   ENCODE_S(z0) -> c11(S(encArg(z0)), ENCARG(z0))
   F(0) -> c19
   G(z0) -> c25
   S(0) -> c34
   A -> c43
   ENCARG(cons_h(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_r(z0)) -> c6(ENCARG(z0))
   ENCARG(cons_p(z0)) -> c7(ENCARG(z0))
   ENCODE_H(z0, z1) -> c12(ENCARG(z0), ENCARG(z1))
   ENCODE_R(z0) -> c14(ENCARG(z0))
   ENCODE_P(z0) -> c15(ENCARG(z0))
   G(z0) -> c23
   G(z0) -> c24
   S(z0) -> c26
   S(z0) -> c27
   S(0) -> c29
   S(0) -> c31
   S(h(r(k(p(z0))), r(z0))) -> c37
S tuples:
   F(0) -> c19
   G(z0) -> c25
   S(0) -> c34
   A -> c43
   G(z0) -> c23
   G(z0) -> c24
   S(z0) -> c26
   S(z0) -> c27
   S(0) -> c29
   S(0) -> c31
   S(h(r(k(p(z0))), r(z0))) -> c37
K tuples:none
Defined Rule Symbols:   f_1, g_1, s_1, h_2, r_1, p_1, a, encArg_1, encode_f_1, encode_g_1, encode_s_1, encode_h_2, encode_0, encode_r_1, encode_p_1, encode_k_1, encode_a

Defined Pair Symbols:   ENCARG_1, ENCODE_F_1, ENCODE_G_1, ENCODE_S_1, F_1, G_1, S_1, A, ENCODE_H_2, ENCODE_R_1, ENCODE_P_1

Compound Symbols:   c1_1, c2_2, c3_2, c4_2, c8_1, c9_2, c10_2, c11_2, c19, c25, c34, c43, c5_2, c6_1, c7_1, c12_2, c14_1, c15_1, c23, c24, c26, c27, c29, c31, c37


----------------------------------------

(11) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID))
Split RHS of tuples not part of any SCC
----------------------------------------

(12)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(k(z0)) -> k(encArg(z0))
   encArg(cons_f(z0)) -> f(encArg(z0))
   encArg(cons_g(z0)) -> g(encArg(z0))
   encArg(cons_s(z0)) -> s(encArg(z0))
   encArg(cons_h(z0, z1)) -> h(encArg(z0), encArg(z1))
   encArg(cons_r(z0)) -> r(encArg(z0))
   encArg(cons_p(z0)) -> p(encArg(z0))
   encArg(cons_a) -> a
   encode_f(z0) -> f(encArg(z0))
   encode_g(z0) -> g(encArg(z0))
   encode_s(z0) -> s(encArg(z0))
   encode_h(z0, z1) -> h(encArg(z0), encArg(z1))
   encode_0 -> 0
   encode_r(z0) -> r(encArg(z0))
   encode_p(z0) -> p(encArg(z0))
   encode_k(z0) -> k(encArg(z0))
   encode_a -> a
   f(g(z0)) -> g(g(f(z0)))
   f(0) -> 0
   f(s(0)) -> s(0)
   f(s(s(z0))) -> h(f(z0), g(h(z0, z0)))
   g(s(z0)) -> s(s(g(z0)))
   g(z0) -> h(h(h(h(z0, z0), z0), z0), z0)
   g(z0) -> r(z0)
   g(z0) -> k(z0)
   s(z0) -> h(0, z0)
   s(z0) -> h(z0, 0)
   s(s(s(0))) -> f(s(0))
   s(0) -> r(0)
   s(s(s(0))) -> r(s(0))
   s(0) -> p(0)
   s(s(0)) -> p(s(0))
   s(s(s(s(s(0))))) -> p(s(s(0)))
   s(0) -> k(0)
   s(s(p(p(a)))) -> s(k(p(a)))
   s(k(p(a))) -> p(p(a))
   s(h(r(k(p(z0))), r(z0))) -> h(r(r(p(z0))), k(z0))
   h(f(z0), g(z0)) -> f(s(z0))
   h(p(z0), g(z0)) -> p(s(z0))
   r(s(0)) -> s(0)
   p(s(0)) -> 0
   p(s(s(0))) -> s(s(s(0)))
   a -> 0
Tuples:
   ENCARG(k(z0)) -> c1(ENCARG(z0))
   ENCARG(cons_f(z0)) -> c2(F(encArg(z0)), ENCARG(z0))
   ENCARG(cons_g(z0)) -> c3(G(encArg(z0)), ENCARG(z0))
   ENCARG(cons_s(z0)) -> c4(S(encArg(z0)), ENCARG(z0))
   ENCARG(cons_a) -> c8(A)
   F(0) -> c19
   G(z0) -> c25
   S(0) -> c34
   A -> c43
   ENCARG(cons_h(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_r(z0)) -> c6(ENCARG(z0))
   ENCARG(cons_p(z0)) -> c7(ENCARG(z0))
   ENCODE_R(z0) -> c14(ENCARG(z0))
   ENCODE_P(z0) -> c15(ENCARG(z0))
   G(z0) -> c23
   G(z0) -> c24
   S(z0) -> c26
   S(z0) -> c27
   S(0) -> c29
   S(0) -> c31
   S(h(r(k(p(z0))), r(z0))) -> c37
   ENCODE_F(z0) -> c(F(encArg(z0)))
   ENCODE_F(z0) -> c(ENCARG(z0))
   ENCODE_G(z0) -> c(G(encArg(z0)))
   ENCODE_G(z0) -> c(ENCARG(z0))
   ENCODE_S(z0) -> c(S(encArg(z0)))
   ENCODE_S(z0) -> c(ENCARG(z0))
   ENCODE_H(z0, z1) -> c(ENCARG(z0))
   ENCODE_H(z0, z1) -> c(ENCARG(z1))
S tuples:
   F(0) -> c19
   G(z0) -> c25
   S(0) -> c34
   A -> c43
   G(z0) -> c23
   G(z0) -> c24
   S(z0) -> c26
   S(z0) -> c27
   S(0) -> c29
   S(0) -> c31
   S(h(r(k(p(z0))), r(z0))) -> c37
K tuples:none
Defined Rule Symbols:   f_1, g_1, s_1, h_2, r_1, p_1, a, encArg_1, encode_f_1, encode_g_1, encode_s_1, encode_h_2, encode_0, encode_r_1, encode_p_1, encode_k_1, encode_a

Defined Pair Symbols:   ENCARG_1, F_1, G_1, S_1, A, ENCODE_R_1, ENCODE_P_1, ENCODE_F_1, ENCODE_G_1, ENCODE_S_1, ENCODE_H_2

Compound Symbols:   c1_1, c2_2, c3_2, c4_2, c8_1, c19, c25, c34, c43, c5_2, c6_1, c7_1, c14_1, c15_1, c23, c24, c26, c27, c29, c31, c37, c_1


----------------------------------------

(13) CdtLeafRemovalProof (ComplexityIfPolyImplication)
Removed 7 leading nodes:
   ENCODE_R(z0) -> c14(ENCARG(z0))
   ENCODE_P(z0) -> c15(ENCARG(z0))
   ENCODE_F(z0) -> c(ENCARG(z0))
   ENCODE_G(z0) -> c(ENCARG(z0))
   ENCODE_S(z0) -> c(ENCARG(z0))
   ENCODE_H(z0, z1) -> c(ENCARG(z0))
   ENCODE_H(z0, z1) -> c(ENCARG(z1))

----------------------------------------

(14)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(k(z0)) -> k(encArg(z0))
   encArg(cons_f(z0)) -> f(encArg(z0))
   encArg(cons_g(z0)) -> g(encArg(z0))
   encArg(cons_s(z0)) -> s(encArg(z0))
   encArg(cons_h(z0, z1)) -> h(encArg(z0), encArg(z1))
   encArg(cons_r(z0)) -> r(encArg(z0))
   encArg(cons_p(z0)) -> p(encArg(z0))
   encArg(cons_a) -> a
   encode_f(z0) -> f(encArg(z0))
   encode_g(z0) -> g(encArg(z0))
   encode_s(z0) -> s(encArg(z0))
   encode_h(z0, z1) -> h(encArg(z0), encArg(z1))
   encode_0 -> 0
   encode_r(z0) -> r(encArg(z0))
   encode_p(z0) -> p(encArg(z0))
   encode_k(z0) -> k(encArg(z0))
   encode_a -> a
   f(g(z0)) -> g(g(f(z0)))
   f(0) -> 0
   f(s(0)) -> s(0)
   f(s(s(z0))) -> h(f(z0), g(h(z0, z0)))
   g(s(z0)) -> s(s(g(z0)))
   g(z0) -> h(h(h(h(z0, z0), z0), z0), z0)
   g(z0) -> r(z0)
   g(z0) -> k(z0)
   s(z0) -> h(0, z0)
   s(z0) -> h(z0, 0)
   s(s(s(0))) -> f(s(0))
   s(0) -> r(0)
   s(s(s(0))) -> r(s(0))
   s(0) -> p(0)
   s(s(0)) -> p(s(0))
   s(s(s(s(s(0))))) -> p(s(s(0)))
   s(0) -> k(0)
   s(s(p(p(a)))) -> s(k(p(a)))
   s(k(p(a))) -> p(p(a))
   s(h(r(k(p(z0))), r(z0))) -> h(r(r(p(z0))), k(z0))
   h(f(z0), g(z0)) -> f(s(z0))
   h(p(z0), g(z0)) -> p(s(z0))
   r(s(0)) -> s(0)
   p(s(0)) -> 0
   p(s(s(0))) -> s(s(s(0)))
   a -> 0
Tuples:
   ENCARG(k(z0)) -> c1(ENCARG(z0))
   ENCARG(cons_f(z0)) -> c2(F(encArg(z0)), ENCARG(z0))
   ENCARG(cons_g(z0)) -> c3(G(encArg(z0)), ENCARG(z0))
   ENCARG(cons_s(z0)) -> c4(S(encArg(z0)), ENCARG(z0))
   ENCARG(cons_a) -> c8(A)
   F(0) -> c19
   G(z0) -> c25
   S(0) -> c34
   A -> c43
   ENCARG(cons_h(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_r(z0)) -> c6(ENCARG(z0))
   ENCARG(cons_p(z0)) -> c7(ENCARG(z0))
   G(z0) -> c23
   G(z0) -> c24
   S(z0) -> c26
   S(z0) -> c27
   S(0) -> c29
   S(0) -> c31
   S(h(r(k(p(z0))), r(z0))) -> c37
   ENCODE_F(z0) -> c(F(encArg(z0)))
   ENCODE_G(z0) -> c(G(encArg(z0)))
   ENCODE_S(z0) -> c(S(encArg(z0)))
S tuples:
   F(0) -> c19
   G(z0) -> c25
   S(0) -> c34
   A -> c43
   G(z0) -> c23
   G(z0) -> c24
   S(z0) -> c26
   S(z0) -> c27
   S(0) -> c29
   S(0) -> c31
   S(h(r(k(p(z0))), r(z0))) -> c37
K tuples:none
Defined Rule Symbols:   f_1, g_1, s_1, h_2, r_1, p_1, a, encArg_1, encode_f_1, encode_g_1, encode_s_1, encode_h_2, encode_0, encode_r_1, encode_p_1, encode_k_1, encode_a

Defined Pair Symbols:   ENCARG_1, F_1, G_1, S_1, A, ENCODE_F_1, ENCODE_G_1, ENCODE_S_1

Compound Symbols:   c1_1, c2_2, c3_2, c4_2, c8_1, c19, c25, c34, c43, c5_2, c6_1, c7_1, c23, c24, c26, c27, c29, c31, c37, c_1


----------------------------------------

(15) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
The following rules are not usable and were removed:
   encode_f(z0) -> f(encArg(z0))
   encode_g(z0) -> g(encArg(z0))
   encode_s(z0) -> s(encArg(z0))
   encode_h(z0, z1) -> h(encArg(z0), encArg(z1))
   encode_0 -> 0
   encode_r(z0) -> r(encArg(z0))
   encode_p(z0) -> p(encArg(z0))
   encode_k(z0) -> k(encArg(z0))
   encode_a -> a
   f(g(z0)) -> g(g(f(z0)))
   f(s(0)) -> s(0)
   f(s(s(z0))) -> h(f(z0), g(h(z0, z0)))
   g(s(z0)) -> s(s(g(z0)))
   s(s(s(0))) -> f(s(0))
   s(s(s(0))) -> r(s(0))
   s(s(0)) -> p(s(0))
   s(s(s(s(s(0))))) -> p(s(s(0)))
   s(s(p(p(a)))) -> s(k(p(a)))
   s(k(p(a))) -> p(p(a))
   h(f(z0), g(z0)) -> f(s(z0))
   h(p(z0), g(z0)) -> p(s(z0))
   r(s(0)) -> s(0)
   p(s(0)) -> 0
   p(s(s(0))) -> s(s(s(0)))

----------------------------------------

(16)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(k(z0)) -> k(encArg(z0))
   encArg(cons_f(z0)) -> f(encArg(z0))
   encArg(cons_g(z0)) -> g(encArg(z0))
   encArg(cons_s(z0)) -> s(encArg(z0))
   encArg(cons_h(z0, z1)) -> h(encArg(z0), encArg(z1))
   encArg(cons_r(z0)) -> r(encArg(z0))
   encArg(cons_p(z0)) -> p(encArg(z0))
   encArg(cons_a) -> a
   f(0) -> 0
   g(z0) -> h(h(h(h(z0, z0), z0), z0), z0)
   g(z0) -> r(z0)
   g(z0) -> k(z0)
   s(z0) -> h(0, z0)
   s(z0) -> h(z0, 0)
   s(0) -> r(0)
   s(0) -> p(0)
   s(0) -> k(0)
   s(h(r(k(p(z0))), r(z0))) -> h(r(r(p(z0))), k(z0))
   a -> 0
Tuples:
   ENCARG(k(z0)) -> c1(ENCARG(z0))
   ENCARG(cons_f(z0)) -> c2(F(encArg(z0)), ENCARG(z0))
   ENCARG(cons_g(z0)) -> c3(G(encArg(z0)), ENCARG(z0))
   ENCARG(cons_s(z0)) -> c4(S(encArg(z0)), ENCARG(z0))
   ENCARG(cons_a) -> c8(A)
   F(0) -> c19
   G(z0) -> c25
   S(0) -> c34
   A -> c43
   ENCARG(cons_h(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_r(z0)) -> c6(ENCARG(z0))
   ENCARG(cons_p(z0)) -> c7(ENCARG(z0))
   G(z0) -> c23
   G(z0) -> c24
   S(z0) -> c26
   S(z0) -> c27
   S(0) -> c29
   S(0) -> c31
   S(h(r(k(p(z0))), r(z0))) -> c37
   ENCODE_F(z0) -> c(F(encArg(z0)))
   ENCODE_G(z0) -> c(G(encArg(z0)))
   ENCODE_S(z0) -> c(S(encArg(z0)))
S tuples:
   F(0) -> c19
   G(z0) -> c25
   S(0) -> c34
   A -> c43
   G(z0) -> c23
   G(z0) -> c24
   S(z0) -> c26
   S(z0) -> c27
   S(0) -> c29
   S(0) -> c31
   S(h(r(k(p(z0))), r(z0))) -> c37
K tuples:none
Defined Rule Symbols:   encArg_1, f_1, g_1, s_1, a

Defined Pair Symbols:   ENCARG_1, F_1, G_1, S_1, A, ENCODE_F_1, ENCODE_G_1, ENCODE_S_1

Compound Symbols:   c1_1, c2_2, c3_2, c4_2, c8_1, c19, c25, c34, c43, c5_2, c6_1, c7_1, c23, c24, c26, c27, c29, c31, c37, 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.
   S(0) -> c34
   S(z0) -> c26
   S(z0) -> c27
   S(0) -> c29
   S(0) -> c31
   S(h(r(k(p(z0))), r(z0))) -> c37
We considered the (Usable) Rules:none
And the Tuples:
   ENCARG(k(z0)) -> c1(ENCARG(z0))
   ENCARG(cons_f(z0)) -> c2(F(encArg(z0)), ENCARG(z0))
   ENCARG(cons_g(z0)) -> c3(G(encArg(z0)), ENCARG(z0))
   ENCARG(cons_s(z0)) -> c4(S(encArg(z0)), ENCARG(z0))
   ENCARG(cons_a) -> c8(A)
   F(0) -> c19
   G(z0) -> c25
   S(0) -> c34
   A -> c43
   ENCARG(cons_h(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_r(z0)) -> c6(ENCARG(z0))
   ENCARG(cons_p(z0)) -> c7(ENCARG(z0))
   G(z0) -> c23
   G(z0) -> c24
   S(z0) -> c26
   S(z0) -> c27
   S(0) -> c29
   S(0) -> c31
   S(h(r(k(p(z0))), r(z0))) -> c37
   ENCODE_F(z0) -> c(F(encArg(z0)))
   ENCODE_G(z0) -> c(G(encArg(z0)))
   ENCODE_S(z0) -> c(S(encArg(z0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(0) = 0
   POL(A) = 0
   POL(ENCARG(x_1)) = [2]x_1
   POL(ENCODE_F(x_1)) = x_1
   POL(ENCODE_G(x_1)) = 0
   POL(ENCODE_S(x_1)) = [3]
   POL(F(x_1)) = 0
   POL(G(x_1)) = 0
   POL(S(x_1)) = [2]
   POL(a) = 0
   POL(c(x_1)) = x_1
   POL(c1(x_1)) = x_1
   POL(c19) = 0
   POL(c2(x_1, x_2)) = x_1 + x_2
   POL(c23) = 0
   POL(c24) = 0
   POL(c25) = 0
   POL(c26) = 0
   POL(c27) = 0
   POL(c29) = 0
   POL(c3(x_1, x_2)) = x_1 + x_2
   POL(c31) = 0
   POL(c34) = 0
   POL(c37) = 0
   POL(c4(x_1, x_2)) = x_1 + x_2
   POL(c43) = 0
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1)) = x_1
   POL(c7(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(cons_a) = 0
   POL(cons_f(x_1)) = x_1
   POL(cons_g(x_1)) = [2] + x_1
   POL(cons_h(x_1, x_2)) = [3] + x_1 + x_2
   POL(cons_p(x_1)) = x_1
   POL(cons_r(x_1)) = x_1
   POL(cons_s(x_1)) = [2] + x_1
   POL(encArg(x_1)) = [2]x_1
   POL(f(x_1)) = 0
   POL(g(x_1)) = [1] + x_1
   POL(h(x_1, x_2)) = [1]
   POL(k(x_1)) = x_1
   POL(p(x_1)) = 0
   POL(r(x_1)) = 0
   POL(s(x_1)) = [3] + x_1

----------------------------------------

(18)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(k(z0)) -> k(encArg(z0))
   encArg(cons_f(z0)) -> f(encArg(z0))
   encArg(cons_g(z0)) -> g(encArg(z0))
   encArg(cons_s(z0)) -> s(encArg(z0))
   encArg(cons_h(z0, z1)) -> h(encArg(z0), encArg(z1))
   encArg(cons_r(z0)) -> r(encArg(z0))
   encArg(cons_p(z0)) -> p(encArg(z0))
   encArg(cons_a) -> a
   f(0) -> 0
   g(z0) -> h(h(h(h(z0, z0), z0), z0), z0)
   g(z0) -> r(z0)
   g(z0) -> k(z0)
   s(z0) -> h(0, z0)
   s(z0) -> h(z0, 0)
   s(0) -> r(0)
   s(0) -> p(0)
   s(0) -> k(0)
   s(h(r(k(p(z0))), r(z0))) -> h(r(r(p(z0))), k(z0))
   a -> 0
Tuples:
   ENCARG(k(z0)) -> c1(ENCARG(z0))
   ENCARG(cons_f(z0)) -> c2(F(encArg(z0)), ENCARG(z0))
   ENCARG(cons_g(z0)) -> c3(G(encArg(z0)), ENCARG(z0))
   ENCARG(cons_s(z0)) -> c4(S(encArg(z0)), ENCARG(z0))
   ENCARG(cons_a) -> c8(A)
   F(0) -> c19
   G(z0) -> c25
   S(0) -> c34
   A -> c43
   ENCARG(cons_h(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_r(z0)) -> c6(ENCARG(z0))
   ENCARG(cons_p(z0)) -> c7(ENCARG(z0))
   G(z0) -> c23
   G(z0) -> c24
   S(z0) -> c26
   S(z0) -> c27
   S(0) -> c29
   S(0) -> c31
   S(h(r(k(p(z0))), r(z0))) -> c37
   ENCODE_F(z0) -> c(F(encArg(z0)))
   ENCODE_G(z0) -> c(G(encArg(z0)))
   ENCODE_S(z0) -> c(S(encArg(z0)))
S tuples:
   F(0) -> c19
   G(z0) -> c25
   A -> c43
   G(z0) -> c23
   G(z0) -> c24
K tuples:
   S(0) -> c34
   S(z0) -> c26
   S(z0) -> c27
   S(0) -> c29
   S(0) -> c31
   S(h(r(k(p(z0))), r(z0))) -> c37
Defined Rule Symbols:   encArg_1, f_1, g_1, s_1, a

Defined Pair Symbols:   ENCARG_1, F_1, G_1, S_1, A, ENCODE_F_1, ENCODE_G_1, ENCODE_S_1

Compound Symbols:   c1_1, c2_2, c3_2, c4_2, c8_1, c19, c25, c34, c43, c5_2, c6_1, c7_1, c23, c24, c26, c27, c29, c31, c37, c_1


----------------------------------------

(19) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   F(0) -> c19
   G(z0) -> c25
   A -> c43
   G(z0) -> c23
   G(z0) -> c24
We considered the (Usable) Rules:none
And the Tuples:
   ENCARG(k(z0)) -> c1(ENCARG(z0))
   ENCARG(cons_f(z0)) -> c2(F(encArg(z0)), ENCARG(z0))
   ENCARG(cons_g(z0)) -> c3(G(encArg(z0)), ENCARG(z0))
   ENCARG(cons_s(z0)) -> c4(S(encArg(z0)), ENCARG(z0))
   ENCARG(cons_a) -> c8(A)
   F(0) -> c19
   G(z0) -> c25
   S(0) -> c34
   A -> c43
   ENCARG(cons_h(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_r(z0)) -> c6(ENCARG(z0))
   ENCARG(cons_p(z0)) -> c7(ENCARG(z0))
   G(z0) -> c23
   G(z0) -> c24
   S(z0) -> c26
   S(z0) -> c27
   S(0) -> c29
   S(0) -> c31
   S(h(r(k(p(z0))), r(z0))) -> c37
   ENCODE_F(z0) -> c(F(encArg(z0)))
   ENCODE_G(z0) -> c(G(encArg(z0)))
   ENCODE_S(z0) -> c(S(encArg(z0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(0) = [1]
   POL(A) = [1]
   POL(ENCARG(x_1)) = [1] + x_1
   POL(ENCODE_F(x_1)) = [1]
   POL(ENCODE_G(x_1)) = [1]
   POL(ENCODE_S(x_1)) = [1] + x_1
   POL(F(x_1)) = [1]
   POL(G(x_1)) = [1]
   POL(S(x_1)) = [1]
   POL(a) = [1]
   POL(c(x_1)) = x_1
   POL(c1(x_1)) = x_1
   POL(c19) = 0
   POL(c2(x_1, x_2)) = x_1 + x_2
   POL(c23) = 0
   POL(c24) = 0
   POL(c25) = 0
   POL(c26) = 0
   POL(c27) = 0
   POL(c29) = 0
   POL(c3(x_1, x_2)) = x_1 + x_2
   POL(c31) = 0
   POL(c34) = 0
   POL(c37) = 0
   POL(c4(x_1, x_2)) = x_1 + x_2
   POL(c43) = 0
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1)) = x_1
   POL(c7(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(cons_a) = [1]
   POL(cons_f(x_1)) = [1] + x_1
   POL(cons_g(x_1)) = [1] + x_1
   POL(cons_h(x_1, x_2)) = [1] + x_1 + x_2
   POL(cons_p(x_1)) = [1] + x_1
   POL(cons_r(x_1)) = [1] + x_1
   POL(cons_s(x_1)) = [1] + x_1
   POL(encArg(x_1)) = [1] + x_1
   POL(f(x_1)) = [1] + x_1
   POL(g(x_1)) = [1] + x_1
   POL(h(x_1, x_2)) = [1]
   POL(k(x_1)) = [1] + x_1
   POL(p(x_1)) = [1] + x_1
   POL(r(x_1)) = [1]
   POL(s(x_1)) = [1]

----------------------------------------

(20)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(k(z0)) -> k(encArg(z0))
   encArg(cons_f(z0)) -> f(encArg(z0))
   encArg(cons_g(z0)) -> g(encArg(z0))
   encArg(cons_s(z0)) -> s(encArg(z0))
   encArg(cons_h(z0, z1)) -> h(encArg(z0), encArg(z1))
   encArg(cons_r(z0)) -> r(encArg(z0))
   encArg(cons_p(z0)) -> p(encArg(z0))
   encArg(cons_a) -> a
   f(0) -> 0
   g(z0) -> h(h(h(h(z0, z0), z0), z0), z0)
   g(z0) -> r(z0)
   g(z0) -> k(z0)
   s(z0) -> h(0, z0)
   s(z0) -> h(z0, 0)
   s(0) -> r(0)
   s(0) -> p(0)
   s(0) -> k(0)
   s(h(r(k(p(z0))), r(z0))) -> h(r(r(p(z0))), k(z0))
   a -> 0
Tuples:
   ENCARG(k(z0)) -> c1(ENCARG(z0))
   ENCARG(cons_f(z0)) -> c2(F(encArg(z0)), ENCARG(z0))
   ENCARG(cons_g(z0)) -> c3(G(encArg(z0)), ENCARG(z0))
   ENCARG(cons_s(z0)) -> c4(S(encArg(z0)), ENCARG(z0))
   ENCARG(cons_a) -> c8(A)
   F(0) -> c19
   G(z0) -> c25
   S(0) -> c34
   A -> c43
   ENCARG(cons_h(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_r(z0)) -> c6(ENCARG(z0))
   ENCARG(cons_p(z0)) -> c7(ENCARG(z0))
   G(z0) -> c23
   G(z0) -> c24
   S(z0) -> c26
   S(z0) -> c27
   S(0) -> c29
   S(0) -> c31
   S(h(r(k(p(z0))), r(z0))) -> c37
   ENCODE_F(z0) -> c(F(encArg(z0)))
   ENCODE_G(z0) -> c(G(encArg(z0)))
   ENCODE_S(z0) -> c(S(encArg(z0)))
S tuples:none
K tuples:
   S(0) -> c34
   S(z0) -> c26
   S(z0) -> c27
   S(0) -> c29
   S(0) -> c31
   S(h(r(k(p(z0))), r(z0))) -> c37
   F(0) -> c19
   G(z0) -> c25
   A -> c43
   G(z0) -> c23
   G(z0) -> c24
Defined Rule Symbols:   encArg_1, f_1, g_1, s_1, a

Defined Pair Symbols:   ENCARG_1, F_1, G_1, S_1, A, ENCODE_F_1, ENCODE_G_1, ENCODE_S_1

Compound Symbols:   c1_1, c2_2, c3_2, c4_2, c8_1, c19, c25, c34, c43, c5_2, c6_1, c7_1, c23, c24, c26, c27, c29, c31, c37, c_1


----------------------------------------

(21) SIsEmptyProof (BOTH BOUNDS(ID, ID))
The set S is empty
----------------------------------------

(22)
BOUNDS(1, 1)