WORST_CASE(Omega(n^1), O(n^3))
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^3).

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 186 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), 3 ms]
    (14) CdtProblem
    (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 195 ms]
    (16) CdtProblem
    (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 419 ms]
    (18) CdtProblem
    (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 565 ms]
    (20) CdtProblem
    (21) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 2887 ms]
    (22) CdtProblem
    (23) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 2780 ms]
    (24) CdtProblem
    (25) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 2630 ms]
    (26) CdtProblem
    (27) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 2522 ms]
    (28) CdtProblem
    (29) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 2366 ms]
    (30) CdtProblem
    (31) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
    (32) BOUNDS(1, 1)
(33) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(34) CpxRelTRS
    (35) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (36) typed CpxTrs
    (37) OrderProof [LOWER BOUND(ID), 0 ms]
    (38) typed CpxTrs
    (39) RewriteLemmaProof [LOWER BOUND(ID), 305 ms]
    (40) BEST
        (41) proven lower bound
            (42) LowerBoundPropagationProof [FINISHED, 0 ms]
            (43) BOUNDS(n^1, INF)
        (44) typed CpxTrs
            (45) RewriteLemmaProof [LOWER BOUND(ID), 358 ms]
            (46) BOUNDS(1, INF)


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

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


The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(X)) -> false
   eq(s(X), 0) -> false
   eq(s(X), s(Y)) -> eq(X, Y)
   rm(N, nil) -> nil
   rm(N, add(M, X)) -> ifrm(eq(N, M), N, add(M, X))
   ifrm(true, N, add(M, X)) -> rm(N, X)
   ifrm(false, N, add(M, X)) -> add(M, rm(N, X))
   purge(nil) -> nil
   purge(add(N, X)) -> add(N, purge(rm(N, 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(true) -> true
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2))
   encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
   encArg(cons_rm(x_1, x_2)) -> rm(encArg(x_1), encArg(x_2))
   encArg(cons_ifrm(x_1, x_2, x_3)) -> ifrm(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_purge(x_1)) -> purge(encArg(x_1))
   encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
   encode_0 -> 0
   encode_true -> true
   encode_s(x_1) -> s(encArg(x_1))
   encode_false -> false
   encode_rm(x_1, x_2) -> rm(encArg(x_1), encArg(x_2))
   encode_nil -> nil
   encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2))
   encode_ifrm(x_1, x_2, x_3) -> ifrm(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_purge(x_1) -> purge(encArg(x_1))


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

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


The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(X)) -> false
   eq(s(X), 0) -> false
   eq(s(X), s(Y)) -> eq(X, Y)
   rm(N, nil) -> nil
   rm(N, add(M, X)) -> ifrm(eq(N, M), N, add(M, X))
   ifrm(true, N, add(M, X)) -> rm(N, X)
   ifrm(false, N, add(M, X)) -> add(M, rm(N, X))
   purge(nil) -> nil
   purge(add(N, X)) -> add(N, purge(rm(N, X)))

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

   encArg(0) -> 0
   encArg(true) -> true
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2))
   encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
   encArg(cons_rm(x_1, x_2)) -> rm(encArg(x_1), encArg(x_2))
   encArg(cons_ifrm(x_1, x_2, x_3)) -> ifrm(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_purge(x_1)) -> purge(encArg(x_1))
   encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
   encode_0 -> 0
   encode_true -> true
   encode_s(x_1) -> s(encArg(x_1))
   encode_false -> false
   encode_rm(x_1, x_2) -> rm(encArg(x_1), encArg(x_2))
   encode_nil -> nil
   encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2))
   encode_ifrm(x_1, x_2, x_3) -> ifrm(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_purge(x_1) -> purge(encArg(x_1))

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^3).


The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(X)) -> false
   eq(s(X), 0) -> false
   eq(s(X), s(Y)) -> eq(X, Y)
   rm(N, nil) -> nil
   rm(N, add(M, X)) -> ifrm(eq(N, M), N, add(M, X))
   ifrm(true, N, add(M, X)) -> rm(N, X)
   ifrm(false, N, add(M, X)) -> add(M, rm(N, X))
   purge(nil) -> nil
   purge(add(N, X)) -> add(N, purge(rm(N, X)))

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

   encArg(0) -> 0
   encArg(true) -> true
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2))
   encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
   encArg(cons_rm(x_1, x_2)) -> rm(encArg(x_1), encArg(x_2))
   encArg(cons_ifrm(x_1, x_2, x_3)) -> ifrm(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_purge(x_1)) -> purge(encArg(x_1))
   encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
   encode_0 -> 0
   encode_true -> true
   encode_s(x_1) -> s(encArg(x_1))
   encode_false -> false
   encode_rm(x_1, x_2) -> rm(encArg(x_1), encArg(x_2))
   encode_nil -> nil
   encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2))
   encode_ifrm(x_1, x_2, x_3) -> ifrm(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_purge(x_1) -> purge(encArg(x_1))

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(true) -> true
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   encode_eq(z0, z1) -> eq(encArg(z0), encArg(z1))
   encode_0 -> 0
   encode_true -> true
   encode_s(z0) -> s(encArg(z0))
   encode_false -> false
   encode_rm(z0, z1) -> rm(encArg(z0), encArg(z1))
   encode_nil -> nil
   encode_add(z0, z1) -> add(encArg(z0), encArg(z1))
   encode_ifrm(z0, z1, z2) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encode_purge(z0) -> purge(encArg(z0))
   eq(0, 0) -> true
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   rm(z0, nil) -> nil
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
Tuples:
   ENCARG(0) -> c
   ENCARG(true) -> c1
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(false) -> c3
   ENCARG(nil) -> c4
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   ENCODE_EQ(z0, z1) -> c10(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCODE_0 -> c11
   ENCODE_TRUE -> c12
   ENCODE_S(z0) -> c13(ENCARG(z0))
   ENCODE_FALSE -> c14
   ENCODE_RM(z0, z1) -> c15(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCODE_NIL -> c16
   ENCODE_ADD(z0, z1) -> c17(ENCARG(z0), ENCARG(z1))
   ENCODE_IFRM(z0, z1, z2) -> c18(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCODE_PURGE(z0) -> c19(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
S tuples:
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
K tuples:none
Defined Rule Symbols:   eq_2, rm_2, ifrm_3, purge_1, encArg_1, encode_eq_2, encode_0, encode_true, encode_s_1, encode_false, encode_rm_2, encode_nil, encode_add_2, encode_ifrm_3, encode_purge_1

Defined Pair Symbols:   ENCARG_1, ENCODE_EQ_2, ENCODE_0, ENCODE_TRUE, ENCODE_S_1, ENCODE_FALSE, ENCODE_RM_2, ENCODE_NIL, ENCODE_ADD_2, ENCODE_IFRM_3, ENCODE_PURGE_1, EQ_2, RM_2, IFRM_3, PURGE_1

Compound Symbols:   c, c1, c2_1, c3, c4, c5_2, c6_3, c7_3, c8_4, c9_2, c10_3, c11, c12, c13_1, c14, c15_3, c16, c17_2, c18_4, c19_2, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_1, c28, c29_2


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

(7) CdtLeafRemovalProof (ComplexityIfPolyImplication)
Removed 2 leading nodes:
   ENCODE_S(z0) -> c13(ENCARG(z0))
   ENCODE_ADD(z0, z1) -> c17(ENCARG(z0), ENCARG(z1))
Removed 8 trailing nodes:
   ENCARG(false) -> c3
   ENCARG(0) -> c
   ENCARG(nil) -> c4
   ENCODE_0 -> c11
   ENCODE_NIL -> c16
   ENCODE_FALSE -> c14
   ENCARG(true) -> c1
   ENCODE_TRUE -> c12

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

(8)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(true) -> true
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   encode_eq(z0, z1) -> eq(encArg(z0), encArg(z1))
   encode_0 -> 0
   encode_true -> true
   encode_s(z0) -> s(encArg(z0))
   encode_false -> false
   encode_rm(z0, z1) -> rm(encArg(z0), encArg(z1))
   encode_nil -> nil
   encode_add(z0, z1) -> add(encArg(z0), encArg(z1))
   encode_ifrm(z0, z1, z2) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encode_purge(z0) -> purge(encArg(z0))
   eq(0, 0) -> true
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   rm(z0, nil) -> nil
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   ENCODE_EQ(z0, z1) -> c10(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCODE_RM(z0, z1) -> c15(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCODE_IFRM(z0, z1, z2) -> c18(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCODE_PURGE(z0) -> c19(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
S tuples:
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
K tuples:none
Defined Rule Symbols:   eq_2, rm_2, ifrm_3, purge_1, encArg_1, encode_eq_2, encode_0, encode_true, encode_s_1, encode_false, encode_rm_2, encode_nil, encode_add_2, encode_ifrm_3, encode_purge_1

Defined Pair Symbols:   ENCARG_1, ENCODE_EQ_2, ENCODE_RM_2, ENCODE_IFRM_3, ENCODE_PURGE_1, EQ_2, RM_2, IFRM_3, PURGE_1

Compound Symbols:   c2_1, c5_2, c6_3, c7_3, c8_4, c9_2, c10_3, c15_3, c18_4, c19_2, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_1, c28, c29_2


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

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

(10)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(true) -> true
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   encode_eq(z0, z1) -> eq(encArg(z0), encArg(z1))
   encode_0 -> 0
   encode_true -> true
   encode_s(z0) -> s(encArg(z0))
   encode_false -> false
   encode_rm(z0, z1) -> rm(encArg(z0), encArg(z1))
   encode_nil -> nil
   encode_add(z0, z1) -> add(encArg(z0), encArg(z1))
   encode_ifrm(z0, z1, z2) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encode_purge(z0) -> purge(encArg(z0))
   eq(0, 0) -> true
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   rm(z0, nil) -> nil
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_EQ(z0, z1) -> c(ENCARG(z0))
   ENCODE_EQ(z0, z1) -> c(ENCARG(z1))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(ENCARG(z0))
   ENCODE_RM(z0, z1) -> c(ENCARG(z1))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_IFRM(z0, z1, z2) -> c(ENCARG(z0))
   ENCODE_IFRM(z0, z1, z2) -> c(ENCARG(z1))
   ENCODE_IFRM(z0, z1, z2) -> c(ENCARG(z2))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
   ENCODE_PURGE(z0) -> c(ENCARG(z0))
S tuples:
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
K tuples:none
Defined Rule Symbols:   eq_2, rm_2, ifrm_3, purge_1, encArg_1, encode_eq_2, encode_0, encode_true, encode_s_1, encode_false, encode_rm_2, encode_nil, encode_add_2, encode_ifrm_3, encode_purge_1

Defined Pair Symbols:   ENCARG_1, EQ_2, RM_2, IFRM_3, PURGE_1, ENCODE_EQ_2, ENCODE_RM_2, ENCODE_IFRM_3, ENCODE_PURGE_1

Compound Symbols:   c2_1, c5_2, c6_3, c7_3, c8_4, c9_2, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_1, c28, c29_2, c_1


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

(11) CdtLeafRemovalProof (ComplexityIfPolyImplication)
Removed 8 leading nodes:
   ENCODE_EQ(z0, z1) -> c(ENCARG(z0))
   ENCODE_EQ(z0, z1) -> c(ENCARG(z1))
   ENCODE_RM(z0, z1) -> c(ENCARG(z0))
   ENCODE_RM(z0, z1) -> c(ENCARG(z1))
   ENCODE_IFRM(z0, z1, z2) -> c(ENCARG(z0))
   ENCODE_IFRM(z0, z1, z2) -> c(ENCARG(z1))
   ENCODE_IFRM(z0, z1, z2) -> c(ENCARG(z2))
   ENCODE_PURGE(z0) -> c(ENCARG(z0))

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

(12)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(true) -> true
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   encode_eq(z0, z1) -> eq(encArg(z0), encArg(z1))
   encode_0 -> 0
   encode_true -> true
   encode_s(z0) -> s(encArg(z0))
   encode_false -> false
   encode_rm(z0, z1) -> rm(encArg(z0), encArg(z1))
   encode_nil -> nil
   encode_add(z0, z1) -> add(encArg(z0), encArg(z1))
   encode_ifrm(z0, z1, z2) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encode_purge(z0) -> purge(encArg(z0))
   eq(0, 0) -> true
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   rm(z0, nil) -> nil
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
S tuples:
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
K tuples:none
Defined Rule Symbols:   eq_2, rm_2, ifrm_3, purge_1, encArg_1, encode_eq_2, encode_0, encode_true, encode_s_1, encode_false, encode_rm_2, encode_nil, encode_add_2, encode_ifrm_3, encode_purge_1

Defined Pair Symbols:   ENCARG_1, EQ_2, RM_2, IFRM_3, PURGE_1, ENCODE_EQ_2, ENCODE_RM_2, ENCODE_IFRM_3, ENCODE_PURGE_1

Compound Symbols:   c2_1, c5_2, c6_3, c7_3, c8_4, c9_2, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_1, c28, c29_2, c_1


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

(13) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
The following rules are not usable and were removed:
   encode_eq(z0, z1) -> eq(encArg(z0), encArg(z1))
   encode_0 -> 0
   encode_true -> true
   encode_s(z0) -> s(encArg(z0))
   encode_false -> false
   encode_rm(z0, z1) -> rm(encArg(z0), encArg(z1))
   encode_nil -> nil
   encode_add(z0, z1) -> add(encArg(z0), encArg(z1))
   encode_ifrm(z0, z1, z2) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encode_purge(z0) -> purge(encArg(z0))

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

(14)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(true) -> true
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   eq(0, 0) -> true
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   rm(z0, nil) -> nil
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
S tuples:
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
K tuples:none
Defined Rule Symbols:   encArg_1, eq_2, rm_2, ifrm_3, purge_1

Defined Pair Symbols:   ENCARG_1, EQ_2, RM_2, IFRM_3, PURGE_1, ENCODE_EQ_2, ENCODE_RM_2, ENCODE_IFRM_3, ENCODE_PURGE_1

Compound Symbols:   c2_1, c5_2, c6_3, c7_3, c8_4, c9_2, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_1, c28, c29_2, 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.
   PURGE(nil) -> c28
We considered the (Usable) Rules:none
And the Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(0) = [1]
   POL(ENCARG(x_1)) = x_1
   POL(ENCODE_EQ(x_1, x_2)) = 0
   POL(ENCODE_IFRM(x_1, x_2, x_3)) = 0
   POL(ENCODE_PURGE(x_1)) = [1]
   POL(ENCODE_RM(x_1, x_2)) = 0
   POL(EQ(x_1, x_2)) = 0
   POL(IFRM(x_1, x_2, x_3)) = 0
   POL(PURGE(x_1)) = [1]
   POL(RM(x_1, x_2)) = 0
   POL(add(x_1, x_2)) = x_1 + x_2
   POL(c(x_1)) = x_1
   POL(c2(x_1)) = x_1
   POL(c20) = 0
   POL(c21) = 0
   POL(c22) = 0
   POL(c23(x_1)) = x_1
   POL(c24) = 0
   POL(c25(x_1, x_2)) = x_1 + x_2
   POL(c26(x_1)) = x_1
   POL(c27(x_1)) = x_1
   POL(c28) = 0
   POL(c29(x_1, x_2)) = x_1 + x_2
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c7(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c8(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4
   POL(c9(x_1, x_2)) = x_1 + x_2
   POL(cons_eq(x_1, x_2)) = [1] + x_1 + x_2
   POL(cons_ifrm(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3
   POL(cons_purge(x_1)) = [1] + x_1
   POL(cons_rm(x_1, x_2)) = [1] + x_1 + x_2
   POL(encArg(x_1)) = [1] + x_1
   POL(eq(x_1, x_2)) = x_1
   POL(false) = 0
   POL(ifrm(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3
   POL(nil) = 0
   POL(purge(x_1)) = [1] + x_1
   POL(rm(x_1, x_2)) = 0
   POL(s(x_1)) = x_1
   POL(true) = [1]

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

(16)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(true) -> true
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   eq(0, 0) -> true
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   rm(z0, nil) -> nil
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
S tuples:
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
K tuples:
   PURGE(nil) -> c28
Defined Rule Symbols:   encArg_1, eq_2, rm_2, ifrm_3, purge_1

Defined Pair Symbols:   ENCARG_1, EQ_2, RM_2, IFRM_3, PURGE_1, ENCODE_EQ_2, ENCODE_RM_2, ENCODE_IFRM_3, ENCODE_PURGE_1

Compound Symbols:   c2_1, c5_2, c6_3, c7_3, c8_4, c9_2, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_1, c28, c29_2, c_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.
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
We considered the (Usable) Rules:
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   encArg(nil) -> nil
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   encArg(0) -> 0
   encArg(true) -> true
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   eq(0, 0) -> true
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   rm(z0, nil) -> nil
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
And the Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(0) = 0
   POL(ENCARG(x_1)) = x_1^2
   POL(ENCODE_EQ(x_1, x_2)) = [2] + [2]x_1 + x_2 + [2]x_2^2 + x_1*x_2 + x_1^2
   POL(ENCODE_IFRM(x_1, x_2, x_3)) = [1] + [2]x_1 + [2]x_2 + x_3 + [2]x_3^2 + [2]x_2*x_3 + [2]x_1*x_3 + [2]x_1^2 + x_1*x_2 + [2]x_2^2
   POL(ENCODE_PURGE(x_1)) = [1] + [2]x_1 + [2]x_1^2
   POL(ENCODE_RM(x_1, x_2)) = [2] + [2]x_1 + [2]x_2^2 + x_1*x_2 + [2]x_1^2
   POL(EQ(x_1, x_2)) = 0
   POL(IFRM(x_1, x_2, x_3)) = 0
   POL(PURGE(x_1)) = [1] + x_1
   POL(RM(x_1, x_2)) = 0
   POL(add(x_1, x_2)) = [1] + x_1 + x_2
   POL(c(x_1)) = x_1
   POL(c2(x_1)) = x_1
   POL(c20) = 0
   POL(c21) = 0
   POL(c22) = 0
   POL(c23(x_1)) = x_1
   POL(c24) = 0
   POL(c25(x_1, x_2)) = x_1 + x_2
   POL(c26(x_1)) = x_1
   POL(c27(x_1)) = x_1
   POL(c28) = 0
   POL(c29(x_1, x_2)) = x_1 + x_2
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c7(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c8(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4
   POL(c9(x_1, x_2)) = x_1 + x_2
   POL(cons_eq(x_1, x_2)) = [1] + x_1 + x_2
   POL(cons_ifrm(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(cons_purge(x_1)) = [1] + x_1
   POL(cons_rm(x_1, x_2)) = [1] + x_1 + x_2
   POL(encArg(x_1)) = [2]x_1
   POL(eq(x_1, x_2)) = x_2
   POL(false) = 0
   POL(ifrm(x_1, x_2, x_3)) = x_3
   POL(nil) = 0
   POL(purge(x_1)) = [1] + x_1
   POL(rm(x_1, x_2)) = x_2
   POL(s(x_1)) = [2] + x_1
   POL(true) = 0

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

(18)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(true) -> true
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   eq(0, 0) -> true
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   rm(z0, nil) -> nil
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
S tuples:
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
K tuples:
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
Defined Rule Symbols:   encArg_1, eq_2, rm_2, ifrm_3, purge_1

Defined Pair Symbols:   ENCARG_1, EQ_2, RM_2, IFRM_3, PURGE_1, ENCODE_EQ_2, ENCODE_RM_2, ENCODE_IFRM_3, ENCODE_PURGE_1

Compound Symbols:   c2_1, c5_2, c6_3, c7_3, c8_4, c9_2, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_1, c28, c29_2, c_1


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

(19) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   RM(z0, nil) -> c24
We considered the (Usable) Rules:
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   encArg(nil) -> nil
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   encArg(0) -> 0
   encArg(true) -> true
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   eq(0, 0) -> true
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   rm(z0, nil) -> nil
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
And the Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(0) = 0
   POL(ENCARG(x_1)) = x_1^2
   POL(ENCODE_EQ(x_1, x_2)) = [1] + x_1 + [2]x_2 + [2]x_2^2 + [2]x_1*x_2 + x_1^2
   POL(ENCODE_IFRM(x_1, x_2, x_3)) = [2] + [2]x_1 + [2]x_2 + [2]x_3 + [2]x_3^2 + [2]x_2*x_3 + [2]x_1*x_3 + [2]x_1^2 + x_1*x_2 + [2]x_2^2
   POL(ENCODE_PURGE(x_1)) = [2] + [2]x_1 + [2]x_1^2
   POL(ENCODE_RM(x_1, x_2)) = [2] + [2]x_1 + [2]x_2^2 + [2]x_1*x_2 + x_1^2
   POL(EQ(x_1, x_2)) = 0
   POL(IFRM(x_1, x_2, x_3)) = [1]
   POL(PURGE(x_1)) = x_1
   POL(RM(x_1, x_2)) = [1]
   POL(add(x_1, x_2)) = [1] + x_1 + x_2
   POL(c(x_1)) = x_1
   POL(c2(x_1)) = x_1
   POL(c20) = 0
   POL(c21) = 0
   POL(c22) = 0
   POL(c23(x_1)) = x_1
   POL(c24) = 0
   POL(c25(x_1, x_2)) = x_1 + x_2
   POL(c26(x_1)) = x_1
   POL(c27(x_1)) = x_1
   POL(c28) = 0
   POL(c29(x_1, x_2)) = x_1 + x_2
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c7(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c8(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4
   POL(c9(x_1, x_2)) = x_1 + x_2
   POL(cons_eq(x_1, x_2)) = x_1 + x_2
   POL(cons_ifrm(x_1, x_2, x_3)) = [2] + x_1 + x_2 + x_3
   POL(cons_purge(x_1)) = [2] + x_1
   POL(cons_rm(x_1, x_2)) = [1] + x_1 + x_2
   POL(encArg(x_1)) = [2]x_1
   POL(eq(x_1, x_2)) = 0
   POL(false) = 0
   POL(ifrm(x_1, x_2, x_3)) = x_3
   POL(nil) = 0
   POL(purge(x_1)) = [1] + x_1
   POL(rm(x_1, x_2)) = x_2
   POL(s(x_1)) = x_1
   POL(true) = 0

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

(20)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(true) -> true
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   eq(0, 0) -> true
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   rm(z0, nil) -> nil
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
S tuples:
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
K tuples:
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   RM(z0, nil) -> c24
Defined Rule Symbols:   encArg_1, eq_2, rm_2, ifrm_3, purge_1

Defined Pair Symbols:   ENCARG_1, EQ_2, RM_2, IFRM_3, PURGE_1, ENCODE_EQ_2, ENCODE_RM_2, ENCODE_IFRM_3, ENCODE_PURGE_1

Compound Symbols:   c2_1, c5_2, c6_3, c7_3, c8_4, c9_2, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_1, c28, c29_2, c_1


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

(21) CdtRuleRemovalProof (UPPER BOUND(ADD(n^3)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
We considered the (Usable) Rules:
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   encArg(nil) -> nil
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   encArg(0) -> 0
   encArg(true) -> true
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   eq(0, 0) -> true
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   rm(z0, nil) -> nil
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
And the Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(0) = 0
   POL(ENCARG(x_1)) = x_1^3
   POL(ENCODE_EQ(x_1, x_2)) = x_1 + x_1^3
   POL(ENCODE_IFRM(x_1, x_2, x_3)) = x_2*x_3
   POL(ENCODE_PURGE(x_1)) = x_1 + x_1^2
   POL(ENCODE_RM(x_1, x_2)) = x_1 + x_1*x_2
   POL(EQ(x_1, x_2)) = x_1
   POL(IFRM(x_1, x_2, x_3)) = x_2*x_3
   POL(PURGE(x_1)) = x_1 + x_1^2
   POL(RM(x_1, x_2)) = x_1 + x_1*x_2
   POL(add(x_1, x_2)) = [1] + x_1 + x_2
   POL(c(x_1)) = x_1
   POL(c2(x_1)) = x_1
   POL(c20) = 0
   POL(c21) = 0
   POL(c22) = 0
   POL(c23(x_1)) = x_1
   POL(c24) = 0
   POL(c25(x_1, x_2)) = x_1 + x_2
   POL(c26(x_1)) = x_1
   POL(c27(x_1)) = x_1
   POL(c28) = 0
   POL(c29(x_1, x_2)) = x_1 + x_2
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c7(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c8(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4
   POL(c9(x_1, x_2)) = x_1 + x_2
   POL(cons_eq(x_1, x_2)) = [1] + x_1 + x_2
   POL(cons_ifrm(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3
   POL(cons_purge(x_1)) = [1] + x_1
   POL(cons_rm(x_1, x_2)) = [1] + x_1 + x_2
   POL(encArg(x_1)) = x_1
   POL(eq(x_1, x_2)) = 0
   POL(false) = 0
   POL(ifrm(x_1, x_2, x_3)) = x_3
   POL(nil) = [1]
   POL(purge(x_1)) = [1] + x_1
   POL(rm(x_1, x_2)) = x_2
   POL(s(x_1)) = [1] + x_1
   POL(true) = 0

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

(22)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(true) -> true
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   eq(0, 0) -> true
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   rm(z0, nil) -> nil
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
S tuples:
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
K tuples:
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   RM(z0, nil) -> c24
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
Defined Rule Symbols:   encArg_1, eq_2, rm_2, ifrm_3, purge_1

Defined Pair Symbols:   ENCARG_1, EQ_2, RM_2, IFRM_3, PURGE_1, ENCODE_EQ_2, ENCODE_RM_2, ENCODE_IFRM_3, ENCODE_PURGE_1

Compound Symbols:   c2_1, c5_2, c6_3, c7_3, c8_4, c9_2, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_1, c28, c29_2, c_1


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

(23) CdtRuleRemovalProof (UPPER BOUND(ADD(n^3)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
We considered the (Usable) Rules:
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   encArg(nil) -> nil
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   encArg(0) -> 0
   encArg(true) -> true
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   eq(0, 0) -> true
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   rm(z0, nil) -> nil
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
And the Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(0) = [1]
   POL(ENCARG(x_1)) = x_1^3
   POL(ENCODE_EQ(x_1, x_2)) = 0
   POL(ENCODE_IFRM(x_1, x_2, x_3)) = x_1 + x_2*x_3
   POL(ENCODE_PURGE(x_1)) = x_1^2
   POL(ENCODE_RM(x_1, x_2)) = x_1 + x_1*x_2
   POL(EQ(x_1, x_2)) = 0
   POL(IFRM(x_1, x_2, x_3)) = x_1 + x_2*x_3
   POL(PURGE(x_1)) = x_1^2
   POL(RM(x_1, x_2)) = x_1 + x_1*x_2
   POL(add(x_1, x_2)) = [1] + x_1 + x_2
   POL(c(x_1)) = x_1
   POL(c2(x_1)) = x_1
   POL(c20) = 0
   POL(c21) = 0
   POL(c22) = 0
   POL(c23(x_1)) = x_1
   POL(c24) = 0
   POL(c25(x_1, x_2)) = x_1 + x_2
   POL(c26(x_1)) = x_1
   POL(c27(x_1)) = x_1
   POL(c28) = 0
   POL(c29(x_1, x_2)) = x_1 + x_2
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c7(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c8(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4
   POL(c9(x_1, x_2)) = x_1 + x_2
   POL(cons_eq(x_1, x_2)) = x_1 + x_2
   POL(cons_ifrm(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3
   POL(cons_purge(x_1)) = [1] + x_1
   POL(cons_rm(x_1, x_2)) = [1] + x_1 + x_2
   POL(encArg(x_1)) = x_1
   POL(eq(x_1, x_2)) = x_1
   POL(false) = 0
   POL(ifrm(x_1, x_2, x_3)) = x_3
   POL(nil) = [1]
   POL(purge(x_1)) = x_1
   POL(rm(x_1, x_2)) = x_2
   POL(s(x_1)) = x_1
   POL(true) = [1]

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

(24)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(true) -> true
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   eq(0, 0) -> true
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   rm(z0, nil) -> nil
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
S tuples:
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
K tuples:
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   RM(z0, nil) -> c24
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
Defined Rule Symbols:   encArg_1, eq_2, rm_2, ifrm_3, purge_1

Defined Pair Symbols:   ENCARG_1, EQ_2, RM_2, IFRM_3, PURGE_1, ENCODE_EQ_2, ENCODE_RM_2, ENCODE_IFRM_3, ENCODE_PURGE_1

Compound Symbols:   c2_1, c5_2, c6_3, c7_3, c8_4, c9_2, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_1, c28, c29_2, c_1


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

(25) CdtRuleRemovalProof (UPPER BOUND(ADD(n^3)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
We considered the (Usable) Rules:
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   encArg(nil) -> nil
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   encArg(0) -> 0
   encArg(true) -> true
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   eq(0, 0) -> true
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   rm(z0, nil) -> nil
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
And the Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(0) = [1]
   POL(ENCARG(x_1)) = x_1^3
   POL(ENCODE_EQ(x_1, x_2)) = x_1 + x_1^3
   POL(ENCODE_IFRM(x_1, x_2, x_3)) = x_2*x_3
   POL(ENCODE_PURGE(x_1)) = x_1^2
   POL(ENCODE_RM(x_1, x_2)) = x_1 + x_1*x_2
   POL(EQ(x_1, x_2)) = x_1
   POL(IFRM(x_1, x_2, x_3)) = x_2*x_3
   POL(PURGE(x_1)) = x_1^2
   POL(RM(x_1, x_2)) = x_1 + x_1*x_2
   POL(add(x_1, x_2)) = [1] + x_1 + x_2
   POL(c(x_1)) = x_1
   POL(c2(x_1)) = x_1
   POL(c20) = 0
   POL(c21) = 0
   POL(c22) = 0
   POL(c23(x_1)) = x_1
   POL(c24) = 0
   POL(c25(x_1, x_2)) = x_1 + x_2
   POL(c26(x_1)) = x_1
   POL(c27(x_1)) = x_1
   POL(c28) = 0
   POL(c29(x_1, x_2)) = x_1 + x_2
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c7(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c8(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4
   POL(c9(x_1, x_2)) = x_1 + x_2
   POL(cons_eq(x_1, x_2)) = [1] + x_1 + x_2
   POL(cons_ifrm(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3
   POL(cons_purge(x_1)) = [1] + x_1
   POL(cons_rm(x_1, x_2)) = [1] + x_1 + x_2
   POL(encArg(x_1)) = x_1
   POL(eq(x_1, x_2)) = 0
   POL(false) = 0
   POL(ifrm(x_1, x_2, x_3)) = x_3
   POL(nil) = [1]
   POL(purge(x_1)) = x_1
   POL(rm(x_1, x_2)) = x_2
   POL(s(x_1)) = x_1
   POL(true) = 0

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

(26)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(true) -> true
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   eq(0, 0) -> true
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   rm(z0, nil) -> nil
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
S tuples:
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
K tuples:
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   RM(z0, nil) -> c24
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
Defined Rule Symbols:   encArg_1, eq_2, rm_2, ifrm_3, purge_1

Defined Pair Symbols:   ENCARG_1, EQ_2, RM_2, IFRM_3, PURGE_1, ENCODE_EQ_2, ENCODE_RM_2, ENCODE_IFRM_3, ENCODE_PURGE_1

Compound Symbols:   c2_1, c5_2, c6_3, c7_3, c8_4, c9_2, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_1, c28, c29_2, c_1


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

(27) CdtRuleRemovalProof (UPPER BOUND(ADD(n^3)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
We considered the (Usable) Rules:
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   encArg(nil) -> nil
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   encArg(0) -> 0
   encArg(true) -> true
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   eq(0, 0) -> true
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   rm(z0, nil) -> nil
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
And the Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(0) = 0
   POL(ENCARG(x_1)) = x_1^3
   POL(ENCODE_EQ(x_1, x_2)) = x_1^3
   POL(ENCODE_IFRM(x_1, x_2, x_3)) = x_3 + x_1^3 + x_3^3
   POL(ENCODE_PURGE(x_1)) = [1] + x_1^2
   POL(ENCODE_RM(x_1, x_2)) = x_2
   POL(EQ(x_1, x_2)) = 0
   POL(IFRM(x_1, x_2, x_3)) = x_3
   POL(PURGE(x_1)) = [1] + x_1^2
   POL(RM(x_1, x_2)) = x_2
   POL(add(x_1, x_2)) = [1] + x_1 + x_2
   POL(c(x_1)) = x_1
   POL(c2(x_1)) = x_1
   POL(c20) = 0
   POL(c21) = 0
   POL(c22) = 0
   POL(c23(x_1)) = x_1
   POL(c24) = 0
   POL(c25(x_1, x_2)) = x_1 + x_2
   POL(c26(x_1)) = x_1
   POL(c27(x_1)) = x_1
   POL(c28) = 0
   POL(c29(x_1, x_2)) = x_1 + x_2
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c7(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c8(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4
   POL(c9(x_1, x_2)) = x_1 + x_2
   POL(cons_eq(x_1, x_2)) = x_1 + x_2
   POL(cons_ifrm(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3
   POL(cons_purge(x_1)) = [1] + x_1
   POL(cons_rm(x_1, x_2)) = [1] + x_1 + x_2
   POL(encArg(x_1)) = x_1
   POL(eq(x_1, x_2)) = 0
   POL(false) = 0
   POL(ifrm(x_1, x_2, x_3)) = x_3
   POL(nil) = [1]
   POL(purge(x_1)) = x_1
   POL(rm(x_1, x_2)) = x_2
   POL(s(x_1)) = x_1
   POL(true) = 0

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

(28)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(true) -> true
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   eq(0, 0) -> true
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   rm(z0, nil) -> nil
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
S tuples:
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
K tuples:
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   RM(z0, nil) -> c24
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
Defined Rule Symbols:   encArg_1, eq_2, rm_2, ifrm_3, purge_1

Defined Pair Symbols:   ENCARG_1, EQ_2, RM_2, IFRM_3, PURGE_1, ENCODE_EQ_2, ENCODE_RM_2, ENCODE_IFRM_3, ENCODE_PURGE_1

Compound Symbols:   c2_1, c5_2, c6_3, c7_3, c8_4, c9_2, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_1, c28, c29_2, c_1


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

(29) CdtRuleRemovalProof (UPPER BOUND(ADD(n^3)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
We considered the (Usable) Rules:
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   encArg(nil) -> nil
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   encArg(0) -> 0
   encArg(true) -> true
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   eq(0, 0) -> true
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   rm(z0, nil) -> nil
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
And the Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(0) = [1]
   POL(ENCARG(x_1)) = [1] + x_1^2 + x_1^3
   POL(ENCODE_EQ(x_1, x_2)) = x_1^3 + x_2^3
   POL(ENCODE_IFRM(x_1, x_2, x_3)) = x_1 + x_2*x_3 + x_1^3
   POL(ENCODE_PURGE(x_1)) = [1] + x_1 + x_1^2
   POL(ENCODE_RM(x_1, x_2)) = [1] + x_1 + x_1*x_2
   POL(EQ(x_1, x_2)) = 0
   POL(IFRM(x_1, x_2, x_3)) = x_1 + x_2*x_3
   POL(PURGE(x_1)) = [1] + x_1 + x_1^2
   POL(RM(x_1, x_2)) = [1] + x_1 + x_1*x_2
   POL(add(x_1, x_2)) = [1] + x_1 + x_2
   POL(c(x_1)) = x_1
   POL(c2(x_1)) = x_1
   POL(c20) = 0
   POL(c21) = 0
   POL(c22) = 0
   POL(c23(x_1)) = x_1
   POL(c24) = 0
   POL(c25(x_1, x_2)) = x_1 + x_2
   POL(c26(x_1)) = x_1
   POL(c27(x_1)) = x_1
   POL(c28) = 0
   POL(c29(x_1, x_2)) = x_1 + x_2
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(c6(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c7(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(c8(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4
   POL(c9(x_1, x_2)) = x_1 + x_2
   POL(cons_eq(x_1, x_2)) = [1] + x_1 + x_2
   POL(cons_ifrm(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3
   POL(cons_purge(x_1)) = [1] + x_1
   POL(cons_rm(x_1, x_2)) = [1] + x_1 + x_2
   POL(encArg(x_1)) = x_1
   POL(eq(x_1, x_2)) = x_1
   POL(false) = [1]
   POL(ifrm(x_1, x_2, x_3)) = x_3
   POL(nil) = [1]
   POL(purge(x_1)) = x_1
   POL(rm(x_1, x_2)) = x_2
   POL(s(x_1)) = [1] + x_1
   POL(true) = [1]

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

(30)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   encArg(0) -> 0
   encArg(true) -> true
   encArg(s(z0)) -> s(encArg(z0))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(z0, z1)) -> add(encArg(z0), encArg(z1))
   encArg(cons_eq(z0, z1)) -> eq(encArg(z0), encArg(z1))
   encArg(cons_rm(z0, z1)) -> rm(encArg(z0), encArg(z1))
   encArg(cons_ifrm(z0, z1, z2)) -> ifrm(encArg(z0), encArg(z1), encArg(z2))
   encArg(cons_purge(z0)) -> purge(encArg(z0))
   eq(0, 0) -> true
   eq(0, s(z0)) -> false
   eq(s(z0), 0) -> false
   eq(s(z0), s(z1)) -> eq(z0, z1)
   rm(z0, nil) -> nil
   rm(z0, add(z1, z2)) -> ifrm(eq(z0, z1), z0, add(z1, z2))
   ifrm(true, z0, add(z1, z2)) -> rm(z0, z2)
   ifrm(false, z0, add(z1, z2)) -> add(z1, rm(z0, z2))
   purge(nil) -> nil
   purge(add(z0, z1)) -> add(z0, purge(rm(z0, z1)))
Tuples:
   ENCARG(s(z0)) -> c2(ENCARG(z0))
   ENCARG(add(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1))
   ENCARG(cons_eq(z0, z1)) -> c6(EQ(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_rm(z0, z1)) -> c7(RM(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1))
   ENCARG(cons_ifrm(z0, z1, z2)) -> c8(IFRM(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2))
   ENCARG(cons_purge(z0)) -> c9(PURGE(encArg(z0)), ENCARG(z0))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   RM(z0, nil) -> c24
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   ENCODE_EQ(z0, z1) -> c(EQ(encArg(z0), encArg(z1)))
   ENCODE_RM(z0, z1) -> c(RM(encArg(z0), encArg(z1)))
   ENCODE_IFRM(z0, z1, z2) -> c(IFRM(encArg(z0), encArg(z1), encArg(z2)))
   ENCODE_PURGE(z0) -> c(PURGE(encArg(z0)))
S tuples:none
K tuples:
   PURGE(nil) -> c28
   PURGE(add(z0, z1)) -> c29(PURGE(rm(z0, z1)), RM(z0, z1))
   RM(z0, nil) -> c24
   EQ(s(z0), 0) -> c22
   EQ(s(z0), s(z1)) -> c23(EQ(z0, z1))
   IFRM(true, z0, add(z1, z2)) -> c26(RM(z0, z2))
   EQ(0, 0) -> c20
   EQ(0, s(z0)) -> c21
   IFRM(false, z0, add(z1, z2)) -> c27(RM(z0, z2))
   RM(z0, add(z1, z2)) -> c25(IFRM(eq(z0, z1), z0, add(z1, z2)), EQ(z0, z1))
Defined Rule Symbols:   encArg_1, eq_2, rm_2, ifrm_3, purge_1

Defined Pair Symbols:   ENCARG_1, EQ_2, RM_2, IFRM_3, PURGE_1, ENCODE_EQ_2, ENCODE_RM_2, ENCODE_IFRM_3, ENCODE_PURGE_1

Compound Symbols:   c2_1, c5_2, c6_3, c7_3, c8_4, c9_2, c20, c21, c22, c23_1, c24, c25_2, c26_1, c27_1, c28, c29_2, c_1


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

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

(32)
BOUNDS(1, 1)

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

(33) RenamingProof (BOTH BOUNDS(ID, ID))
Renamed function symbols to avoid clashes with predefined symbol.
----------------------------------------

(34)
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:

   eq(0', 0') -> true
   eq(0', s(X)) -> false
   eq(s(X), 0') -> false
   eq(s(X), s(Y)) -> eq(X, Y)
   rm(N, nil) -> nil
   rm(N, add(M, X)) -> ifrm(eq(N, M), N, add(M, X))
   ifrm(true, N, add(M, X)) -> rm(N, X)
   ifrm(false, N, add(M, X)) -> add(M, rm(N, X))
   purge(nil) -> nil
   purge(add(N, X)) -> add(N, purge(rm(N, X)))

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

   encArg(0') -> 0'
   encArg(true) -> true
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(false) -> false
   encArg(nil) -> nil
   encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2))
   encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
   encArg(cons_rm(x_1, x_2)) -> rm(encArg(x_1), encArg(x_2))
   encArg(cons_ifrm(x_1, x_2, x_3)) -> ifrm(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_purge(x_1)) -> purge(encArg(x_1))
   encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
   encode_0 -> 0'
   encode_true -> true
   encode_s(x_1) -> s(encArg(x_1))
   encode_false -> false
   encode_rm(x_1, x_2) -> rm(encArg(x_1), encArg(x_2))
   encode_nil -> nil
   encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2))
   encode_ifrm(x_1, x_2, x_3) -> ifrm(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_purge(x_1) -> purge(encArg(x_1))

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

(35) TypeInferenceProof (BOTH BOUNDS(ID, ID))
Infered types.
----------------------------------------

(36)
Obligation:
Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(X)) -> false
eq(s(X), 0') -> false
eq(s(X), s(Y)) -> eq(X, Y)
rm(N, nil) -> nil
rm(N, add(M, X)) -> ifrm(eq(N, M), N, add(M, X))
ifrm(true, N, add(M, X)) -> rm(N, X)
ifrm(false, N, add(M, X)) -> add(M, rm(N, X))
purge(nil) -> nil
purge(add(N, X)) -> add(N, purge(rm(N, X)))
encArg(0') -> 0'
encArg(true) -> true
encArg(s(x_1)) -> s(encArg(x_1))
encArg(false) -> false
encArg(nil) -> nil
encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2))
encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
encArg(cons_rm(x_1, x_2)) -> rm(encArg(x_1), encArg(x_2))
encArg(cons_ifrm(x_1, x_2, x_3)) -> ifrm(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_purge(x_1)) -> purge(encArg(x_1))
encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
encode_0 -> 0'
encode_true -> true
encode_s(x_1) -> s(encArg(x_1))
encode_false -> false
encode_rm(x_1, x_2) -> rm(encArg(x_1), encArg(x_2))
encode_nil -> nil
encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2))
encode_ifrm(x_1, x_2, x_3) -> ifrm(encArg(x_1), encArg(x_2), encArg(x_3))
encode_purge(x_1) -> purge(encArg(x_1))

Types:
eq :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
0' :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
true :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
s :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
false :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
rm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
nil :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
add :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
ifrm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
purge :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encArg :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
cons_eq :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
cons_rm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
cons_ifrm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
cons_purge :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_eq :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_0 :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_true :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_s :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_false :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_rm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_nil :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_add :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_ifrm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_purge :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
hole_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge1_4 :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4 :: Nat -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge

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

(37) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
eq, rm, ifrm, purge, encArg

They will be analysed ascendingly in the following order:
eq < rm
eq < encArg
rm = ifrm
rm < purge
rm < encArg
ifrm < encArg
purge < encArg

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

(38)
Obligation:
Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(X)) -> false
eq(s(X), 0') -> false
eq(s(X), s(Y)) -> eq(X, Y)
rm(N, nil) -> nil
rm(N, add(M, X)) -> ifrm(eq(N, M), N, add(M, X))
ifrm(true, N, add(M, X)) -> rm(N, X)
ifrm(false, N, add(M, X)) -> add(M, rm(N, X))
purge(nil) -> nil
purge(add(N, X)) -> add(N, purge(rm(N, X)))
encArg(0') -> 0'
encArg(true) -> true
encArg(s(x_1)) -> s(encArg(x_1))
encArg(false) -> false
encArg(nil) -> nil
encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2))
encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
encArg(cons_rm(x_1, x_2)) -> rm(encArg(x_1), encArg(x_2))
encArg(cons_ifrm(x_1, x_2, x_3)) -> ifrm(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_purge(x_1)) -> purge(encArg(x_1))
encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
encode_0 -> 0'
encode_true -> true
encode_s(x_1) -> s(encArg(x_1))
encode_false -> false
encode_rm(x_1, x_2) -> rm(encArg(x_1), encArg(x_2))
encode_nil -> nil
encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2))
encode_ifrm(x_1, x_2, x_3) -> ifrm(encArg(x_1), encArg(x_2), encArg(x_3))
encode_purge(x_1) -> purge(encArg(x_1))

Types:
eq :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
0' :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
true :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
s :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
false :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
rm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
nil :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
add :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
ifrm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
purge :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encArg :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
cons_eq :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
cons_rm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
cons_ifrm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
cons_purge :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_eq :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_0 :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_true :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_s :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_false :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_rm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_nil :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_add :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_ifrm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_purge :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
hole_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge1_4 :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4 :: Nat -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge


Generator Equations:
gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(0) <=> 0'
gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(+(x, 1)) <=> s(gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(x))


The following defined symbols remain to be analysed:
eq, rm, ifrm, purge, encArg

They will be analysed ascendingly in the following order:
eq < rm
eq < encArg
rm = ifrm
rm < purge
rm < encArg
ifrm < encArg
purge < encArg

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

(39) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
eq(gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(n4_4), gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(n4_4)) -> true, rt in Omega(1 + n4_4)

Induction Base:
eq(gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(0), gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(0)) ->_R^Omega(1)
true

Induction Step:
eq(gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(+(n4_4, 1)), gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(+(n4_4, 1))) ->_R^Omega(1)
eq(gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(n4_4), gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(n4_4)) ->_IH
true

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(40)
Complex Obligation (BEST)

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

(41)
Obligation:
Proved the lower bound n^1 for the following obligation:

Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(X)) -> false
eq(s(X), 0') -> false
eq(s(X), s(Y)) -> eq(X, Y)
rm(N, nil) -> nil
rm(N, add(M, X)) -> ifrm(eq(N, M), N, add(M, X))
ifrm(true, N, add(M, X)) -> rm(N, X)
ifrm(false, N, add(M, X)) -> add(M, rm(N, X))
purge(nil) -> nil
purge(add(N, X)) -> add(N, purge(rm(N, X)))
encArg(0') -> 0'
encArg(true) -> true
encArg(s(x_1)) -> s(encArg(x_1))
encArg(false) -> false
encArg(nil) -> nil
encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2))
encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
encArg(cons_rm(x_1, x_2)) -> rm(encArg(x_1), encArg(x_2))
encArg(cons_ifrm(x_1, x_2, x_3)) -> ifrm(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_purge(x_1)) -> purge(encArg(x_1))
encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
encode_0 -> 0'
encode_true -> true
encode_s(x_1) -> s(encArg(x_1))
encode_false -> false
encode_rm(x_1, x_2) -> rm(encArg(x_1), encArg(x_2))
encode_nil -> nil
encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2))
encode_ifrm(x_1, x_2, x_3) -> ifrm(encArg(x_1), encArg(x_2), encArg(x_3))
encode_purge(x_1) -> purge(encArg(x_1))

Types:
eq :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
0' :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
true :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
s :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
false :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
rm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
nil :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
add :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
ifrm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
purge :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encArg :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
cons_eq :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
cons_rm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
cons_ifrm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
cons_purge :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_eq :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_0 :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_true :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_s :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_false :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_rm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_nil :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_add :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_ifrm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_purge :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
hole_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge1_4 :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4 :: Nat -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge


Generator Equations:
gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(0) <=> 0'
gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(+(x, 1)) <=> s(gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(x))


The following defined symbols remain to be analysed:
eq, rm, ifrm, purge, encArg

They will be analysed ascendingly in the following order:
eq < rm
eq < encArg
rm = ifrm
rm < purge
rm < encArg
ifrm < encArg
purge < encArg

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

(42) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(43)
BOUNDS(n^1, INF)

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

(44)
Obligation:
Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(X)) -> false
eq(s(X), 0') -> false
eq(s(X), s(Y)) -> eq(X, Y)
rm(N, nil) -> nil
rm(N, add(M, X)) -> ifrm(eq(N, M), N, add(M, X))
ifrm(true, N, add(M, X)) -> rm(N, X)
ifrm(false, N, add(M, X)) -> add(M, rm(N, X))
purge(nil) -> nil
purge(add(N, X)) -> add(N, purge(rm(N, X)))
encArg(0') -> 0'
encArg(true) -> true
encArg(s(x_1)) -> s(encArg(x_1))
encArg(false) -> false
encArg(nil) -> nil
encArg(add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2))
encArg(cons_eq(x_1, x_2)) -> eq(encArg(x_1), encArg(x_2))
encArg(cons_rm(x_1, x_2)) -> rm(encArg(x_1), encArg(x_2))
encArg(cons_ifrm(x_1, x_2, x_3)) -> ifrm(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_purge(x_1)) -> purge(encArg(x_1))
encode_eq(x_1, x_2) -> eq(encArg(x_1), encArg(x_2))
encode_0 -> 0'
encode_true -> true
encode_s(x_1) -> s(encArg(x_1))
encode_false -> false
encode_rm(x_1, x_2) -> rm(encArg(x_1), encArg(x_2))
encode_nil -> nil
encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2))
encode_ifrm(x_1, x_2, x_3) -> ifrm(encArg(x_1), encArg(x_2), encArg(x_3))
encode_purge(x_1) -> purge(encArg(x_1))

Types:
eq :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
0' :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
true :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
s :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
false :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
rm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
nil :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
add :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
ifrm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
purge :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encArg :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
cons_eq :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
cons_rm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
cons_ifrm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
cons_purge :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_eq :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_0 :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_true :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_s :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_false :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_rm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_nil :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_add :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_ifrm :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
encode_purge :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
hole_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge1_4 :: 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge
gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4 :: Nat -> 0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge


Lemmas:
eq(gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(n4_4), gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(n4_4)) -> true, rt in Omega(1 + n4_4)


Generator Equations:
gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(0) <=> 0'
gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(+(x, 1)) <=> s(gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(x))


The following defined symbols remain to be analysed:
ifrm, rm, purge, encArg

They will be analysed ascendingly in the following order:
rm = ifrm
rm < purge
rm < encArg
ifrm < encArg
purge < encArg

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

(45) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
encArg(gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(n795_4)) -> gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(n795_4), rt in Omega(0)

Induction Base:
encArg(gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(0)) ->_R^Omega(0)
0'

Induction Step:
encArg(gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(+(n795_4, 1))) ->_R^Omega(0)
s(encArg(gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(n795_4))) ->_IH
s(gen_0':true:s:false:nil:add:cons_eq:cons_rm:cons_ifrm:cons_purge2_4(c796_4))

We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0).
----------------------------------------

(46)
BOUNDS(1, INF)