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


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


WORST_CASE(Omega(n^1), O(n^3))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


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

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 287 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), 10 ms]
    (14) CdtProblem
    (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 165 ms]
    (16) CdtProblem
    (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 489 ms]
    (18) CdtProblem
    (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 625 ms]
    (20) CdtProblem
    (21) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 2668 ms]
    (22) CdtProblem
    (23) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 2467 ms]
    (24) CdtProblem
    (25) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 2387 ms]
    (26) CdtProblem
    (27) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 2448 ms]
    (28) CdtProblem
    (29) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 2527 ms]
    (30) CdtProblem
    (31) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
    (32) BOUNDS(1, 1)
(33) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
(34) TRS for Loop Detection
    (35) DecreasingLoopProof [LOWER BOUND(ID), 1 ms]
    (36) BEST
        (37) proven lower bound
            (38) LowerBoundPropagationProof [FINISHED, 0 ms]
            (39) BOUNDS(n^1, INF)
        (40) TRS for Loop Detection


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

(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:
   ENCODE_0 -> c11
   ENCARG(nil) -> c4
   ENCARG(true) -> c1
   ENCARG(false) -> c3
   ENCODE_FALSE -> c14
   ENCODE_NIL -> c16
   ENCODE_TRUE -> c12
   ENCARG(0) -> c

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

(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) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
Transformed a relative TRS into a decreasing-loop problem.
----------------------------------------

(34)
Obligation:
Analyzing the following TRS for decreasing loops:

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
----------------------------------------

(35) DecreasingLoopProof (LOWER BOUND(ID))
The following loop(s) give(s) rise to the lower bound Omega(n^1):

The rewrite sequence

eq(s(X), s(Y)) ->^+ eq(X, Y)

gives rise to a decreasing loop by considering the right hand sides subterm at position [].

The pumping substitution is [X / s(X), Y / s(Y)].

The result substitution is [ ].




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

(36)
Complex Obligation (BEST)

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

(37)
Obligation:
Proved the lower bound n^1 for the following 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
----------------------------------------

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

(39)
BOUNDS(n^1, INF)

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

(40)
Obligation:
Analyzing the following TRS for decreasing loops:

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