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


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


WORST_CASE(Omega(n^2), O(n^2))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2).

(0) CpxTRS
(1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms]
(2) CpxTRS
    (3) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
    (4) CpxTRS
    (5) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
    (6) CdtProblem
    (7) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
    (8) CdtProblem
    (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
    (10) CdtProblem
    (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 117 ms]
    (12) CdtProblem
    (13) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms]
    (14) CdtProblem
    (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 74 ms]
    (16) CdtProblem
    (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 82 ms]
    (18) CdtProblem
    (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 46 ms]
    (20) CdtProblem
    (21) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 48 ms]
    (22) CdtProblem
    (23) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
    (24) BOUNDS(1, 1)
(25) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(26) CpxTRS
    (27) SlicingProof [LOWER BOUND(ID), 0 ms]
    (28) CpxTRS
    (29) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (30) typed CpxTrs
    (31) OrderProof [LOWER BOUND(ID), 0 ms]
    (32) typed CpxTrs
    (33) RewriteLemmaProof [LOWER BOUND(ID), 194 ms]
    (34) BEST
        (35) proven lower bound
            (36) LowerBoundPropagationProof [FINISHED, 0 ms]
            (37) BOUNDS(n^1, INF)
        (38) typed CpxTrs
            (39) RewriteLemmaProof [LOWER BOUND(ID), 695 ms]
            (40) typed CpxTrs
            (41) RewriteLemmaProof [LOWER BOUND(ID), 693 ms]
            (42) typed CpxTrs
            (43) RewriteLemmaProof [LOWER BOUND(ID), 19 ms]
            (44) proven lower bound
            (45) LowerBoundPropagationProof [FINISHED, 0 ms]
            (46) BOUNDS(n^2, INF)


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

(0)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2).


The TRS R consists of the following rules:

   Term_sub(Case(m, xi, n), s) -> Frozen(m, Sum_sub(xi, s), n, s)
   Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s)
   Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s)
   Frozen(m, Sum_term_var(xi), n, s) -> Case(Term_sub(m, s), xi, Term_sub(n, s))
   Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s))
   Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s))
   Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s))
   Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s))
   Term_sub(Term_var(x), Id) -> Term_var(x)
   Term_sub(Term_var(x), Cons_usual(y, m, s)) -> m
   Term_sub(Term_var(x), Cons_usual(y, m, s)) -> Term_sub(Term_var(x), s)
   Term_sub(Term_var(x), Cons_sum(xi, k, s)) -> Term_sub(Term_var(x), s)
   Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t))
   Sum_sub(xi, Id) -> Sum_term_var(xi)
   Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_constant(k)
   Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_sub(xi, s)
   Sum_sub(xi, Cons_usual(y, m, s)) -> Sum_sub(xi, s)
   Concat(Concat(s, t), u) -> Concat(s, Concat(t, u))
   Concat(Cons_usual(x, m, s), t) -> Cons_usual(x, Term_sub(m, t), Concat(s, t))
   Concat(Cons_sum(xi, k, s), t) -> Cons_sum(xi, k, Concat(s, t))
   Concat(Id, s) -> s

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(1) NestedDefinedSymbolProof (UPPER BOUND(ID))
The following defined symbols can occur below the 1th argument of Frozen: Sum_sub

Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t))
Concat(Concat(s, t), u) -> Concat(s, Concat(t, u))

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

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


The TRS R consists of the following rules:

   Term_sub(Case(m, xi, n), s) -> Frozen(m, Sum_sub(xi, s), n, s)
   Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s)
   Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s)
   Frozen(m, Sum_term_var(xi), n, s) -> Case(Term_sub(m, s), xi, Term_sub(n, s))
   Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s))
   Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s))
   Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s))
   Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s))
   Term_sub(Term_var(x), Id) -> Term_var(x)
   Term_sub(Term_var(x), Cons_usual(y, m, s)) -> m
   Term_sub(Term_var(x), Cons_usual(y, m, s)) -> Term_sub(Term_var(x), s)
   Term_sub(Term_var(x), Cons_sum(xi, k, s)) -> Term_sub(Term_var(x), s)
   Sum_sub(xi, Id) -> Sum_term_var(xi)
   Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_constant(k)
   Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_sub(xi, s)
   Sum_sub(xi, Cons_usual(y, m, s)) -> Sum_sub(xi, s)
   Concat(Cons_usual(x, m, s), t) -> Cons_usual(x, Term_sub(m, t), Concat(s, t))
   Concat(Cons_sum(xi, k, s), t) -> Cons_sum(xi, k, Concat(s, t))
   Concat(Id, s) -> s

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(3) RcToIrcProof (BOTH BOUNDS(ID, ID))
Converted rc-obligation to irc-obligation.

The duplicating contexts are:
Term_sub(Case(m, xi, n), [])
Frozen(m, Sum_term_var(xi), n, [])
Term_sub(Term_app(m, n), [])
Term_sub(Term_pair(m, n), [])
Concat(Cons_usual(x, m, s), [])


The defined contexts are:
Frozen(x0, [], x2, x3)


[] just represents basic- or constructor-terms in the following defined contexts:
Frozen(x0, [], x2, x3)


As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc.
----------------------------------------

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


The TRS R consists of the following rules:

   Term_sub(Case(m, xi, n), s) -> Frozen(m, Sum_sub(xi, s), n, s)
   Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s)
   Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s)
   Frozen(m, Sum_term_var(xi), n, s) -> Case(Term_sub(m, s), xi, Term_sub(n, s))
   Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s))
   Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s))
   Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s))
   Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s))
   Term_sub(Term_var(x), Id) -> Term_var(x)
   Term_sub(Term_var(x), Cons_usual(y, m, s)) -> m
   Term_sub(Term_var(x), Cons_usual(y, m, s)) -> Term_sub(Term_var(x), s)
   Term_sub(Term_var(x), Cons_sum(xi, k, s)) -> Term_sub(Term_var(x), s)
   Sum_sub(xi, Id) -> Sum_term_var(xi)
   Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_constant(k)
   Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_sub(xi, s)
   Sum_sub(xi, Cons_usual(y, m, s)) -> Sum_sub(xi, s)
   Concat(Cons_usual(x, m, s), t) -> Cons_usual(x, Term_sub(m, t), Concat(s, t))
   Concat(Cons_sum(xi, k, s), t) -> Cons_sum(xi, k, Concat(s, t))
   Concat(Id, s) -> s

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

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

(6)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   Term_sub(Case(z0, z1, z2), z3) -> Frozen(z0, Sum_sub(z1, z3), z2, z3)
   Term_sub(Term_app(z0, z1), z2) -> Term_app(Term_sub(z0, z2), Term_sub(z1, z2))
   Term_sub(Term_pair(z0, z1), z2) -> Term_pair(Term_sub(z0, z2), Term_sub(z1, z2))
   Term_sub(Term_inl(z0), z1) -> Term_inl(Term_sub(z0, z1))
   Term_sub(Term_inr(z0), z1) -> Term_inr(Term_sub(z0, z1))
   Term_sub(Term_var(z0), Id) -> Term_var(z0)
   Term_sub(Term_var(z0), Cons_usual(z1, z2, z3)) -> z2
   Term_sub(Term_var(z0), Cons_usual(z1, z2, z3)) -> Term_sub(Term_var(z0), z3)
   Term_sub(Term_var(z0), Cons_sum(z1, z2, z3)) -> Term_sub(Term_var(z0), z3)
   Frozen(z0, Sum_constant(Left), z1, z2) -> Term_sub(z0, z2)
   Frozen(z0, Sum_constant(Right), z1, z2) -> Term_sub(z1, z2)
   Frozen(z0, Sum_term_var(z1), z2, z3) -> Case(Term_sub(z0, z3), z1, Term_sub(z2, z3))
   Sum_sub(z0, Id) -> Sum_term_var(z0)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_constant(z2)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_sub(z0, z3)
   Sum_sub(z0, Cons_usual(z1, z2, z3)) -> Sum_sub(z0, z3)
   Concat(Cons_usual(z0, z1, z2), z3) -> Cons_usual(z0, Term_sub(z1, z3), Concat(z2, z3))
   Concat(Cons_sum(z0, z1, z2), z3) -> Cons_sum(z0, z1, Concat(z2, z3))
   Concat(Id, z0) -> z0
Tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Id) -> c5
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c6
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Id) -> c12
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c13
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
   CONCAT(Id, z0) -> c18
S tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Id) -> c5
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c6
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Id) -> c12
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c13
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
   CONCAT(Id, z0) -> c18
K tuples:none
Defined Rule Symbols:   Term_sub_2, Frozen_4, Sum_sub_2, Concat_2

Defined Pair Symbols:   TERM_SUB_2, FROZEN_4, SUM_SUB_2, CONCAT_2

Compound Symbols:   c_2, c1_2, c2_2, c3_1, c4_1, c5, c6, c7_1, c8_1, c9_1, c10_1, c11_2, c12, c13, c14_1, c15_1, c16_2, c17_1, c18


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

(7) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
Removed 5 trailing nodes:
   CONCAT(Id, z0) -> c18
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c6
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c13
   TERM_SUB(Term_var(z0), Id) -> c5
   SUM_SUB(z0, Id) -> c12

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

(8)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   Term_sub(Case(z0, z1, z2), z3) -> Frozen(z0, Sum_sub(z1, z3), z2, z3)
   Term_sub(Term_app(z0, z1), z2) -> Term_app(Term_sub(z0, z2), Term_sub(z1, z2))
   Term_sub(Term_pair(z0, z1), z2) -> Term_pair(Term_sub(z0, z2), Term_sub(z1, z2))
   Term_sub(Term_inl(z0), z1) -> Term_inl(Term_sub(z0, z1))
   Term_sub(Term_inr(z0), z1) -> Term_inr(Term_sub(z0, z1))
   Term_sub(Term_var(z0), Id) -> Term_var(z0)
   Term_sub(Term_var(z0), Cons_usual(z1, z2, z3)) -> z2
   Term_sub(Term_var(z0), Cons_usual(z1, z2, z3)) -> Term_sub(Term_var(z0), z3)
   Term_sub(Term_var(z0), Cons_sum(z1, z2, z3)) -> Term_sub(Term_var(z0), z3)
   Frozen(z0, Sum_constant(Left), z1, z2) -> Term_sub(z0, z2)
   Frozen(z0, Sum_constant(Right), z1, z2) -> Term_sub(z1, z2)
   Frozen(z0, Sum_term_var(z1), z2, z3) -> Case(Term_sub(z0, z3), z1, Term_sub(z2, z3))
   Sum_sub(z0, Id) -> Sum_term_var(z0)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_constant(z2)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_sub(z0, z3)
   Sum_sub(z0, Cons_usual(z1, z2, z3)) -> Sum_sub(z0, z3)
   Concat(Cons_usual(z0, z1, z2), z3) -> Cons_usual(z0, Term_sub(z1, z3), Concat(z2, z3))
   Concat(Cons_sum(z0, z1, z2), z3) -> Cons_sum(z0, z1, Concat(z2, z3))
   Concat(Id, z0) -> z0
Tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
S tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
K tuples:none
Defined Rule Symbols:   Term_sub_2, Frozen_4, Sum_sub_2, Concat_2

Defined Pair Symbols:   TERM_SUB_2, FROZEN_4, SUM_SUB_2, CONCAT_2

Compound Symbols:   c_2, c1_2, c2_2, c3_1, c4_1, c7_1, c8_1, c9_1, c10_1, c11_2, c14_1, c15_1, c16_2, c17_1


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

(9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
The following rules are not usable and were removed:
   Term_sub(Case(z0, z1, z2), z3) -> Frozen(z0, Sum_sub(z1, z3), z2, z3)
   Term_sub(Term_app(z0, z1), z2) -> Term_app(Term_sub(z0, z2), Term_sub(z1, z2))
   Term_sub(Term_pair(z0, z1), z2) -> Term_pair(Term_sub(z0, z2), Term_sub(z1, z2))
   Term_sub(Term_inl(z0), z1) -> Term_inl(Term_sub(z0, z1))
   Term_sub(Term_inr(z0), z1) -> Term_inr(Term_sub(z0, z1))
   Term_sub(Term_var(z0), Id) -> Term_var(z0)
   Term_sub(Term_var(z0), Cons_usual(z1, z2, z3)) -> z2
   Term_sub(Term_var(z0), Cons_usual(z1, z2, z3)) -> Term_sub(Term_var(z0), z3)
   Term_sub(Term_var(z0), Cons_sum(z1, z2, z3)) -> Term_sub(Term_var(z0), z3)
   Frozen(z0, Sum_constant(Left), z1, z2) -> Term_sub(z0, z2)
   Frozen(z0, Sum_constant(Right), z1, z2) -> Term_sub(z1, z2)
   Frozen(z0, Sum_term_var(z1), z2, z3) -> Case(Term_sub(z0, z3), z1, Term_sub(z2, z3))
   Concat(Cons_usual(z0, z1, z2), z3) -> Cons_usual(z0, Term_sub(z1, z3), Concat(z2, z3))
   Concat(Cons_sum(z0, z1, z2), z3) -> Cons_sum(z0, z1, Concat(z2, z3))
   Concat(Id, z0) -> z0

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

(10)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   Sum_sub(z0, Id) -> Sum_term_var(z0)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_constant(z2)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_sub(z0, z3)
   Sum_sub(z0, Cons_usual(z1, z2, z3)) -> Sum_sub(z0, z3)
Tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
S tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
K tuples:none
Defined Rule Symbols:   Sum_sub_2

Defined Pair Symbols:   TERM_SUB_2, FROZEN_4, SUM_SUB_2, CONCAT_2

Compound Symbols:   c_2, c1_2, c2_2, c3_1, c4_1, c7_1, c8_1, c9_1, c10_1, c11_2, c14_1, c15_1, c16_2, c17_1


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

(11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
We considered the (Usable) Rules:
   Sum_sub(z0, Cons_usual(z1, z2, z3)) -> Sum_sub(z0, z3)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_sub(z0, z3)
   Sum_sub(z0, Id) -> Sum_term_var(z0)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_constant(z2)
And the Tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(CONCAT(x_1, x_2)) = x_1
   POL(Case(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3
   POL(Cons_sum(x_1, x_2, x_3)) = [1] + x_2 + x_3
   POL(Cons_usual(x_1, x_2, x_3)) = [1] + x_2 + x_3
   POL(FROZEN(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3
   POL(Id) = [1]
   POL(Left) = [1]
   POL(Right) = [1]
   POL(SUM_SUB(x_1, x_2)) = 0
   POL(Sum_constant(x_1)) = 0
   POL(Sum_sub(x_1, x_2)) = x_1
   POL(Sum_term_var(x_1)) = x_1
   POL(TERM_SUB(x_1, x_2)) = x_1
   POL(Term_app(x_1, x_2)) = [1] + x_1 + x_2
   POL(Term_inl(x_1)) = [1] + x_1
   POL(Term_inr(x_1)) = [1] + x_1
   POL(Term_pair(x_1, x_2)) = [1] + x_1 + x_2
   POL(Term_var(x_1)) = 0
   POL(c(x_1, x_2)) = x_1 + x_2
   POL(c1(x_1, x_2)) = x_1 + x_2
   POL(c10(x_1)) = x_1
   POL(c11(x_1, x_2)) = x_1 + x_2
   POL(c14(x_1)) = x_1
   POL(c15(x_1)) = x_1
   POL(c16(x_1, x_2)) = x_1 + x_2
   POL(c17(x_1)) = x_1
   POL(c2(x_1, x_2)) = x_1 + x_2
   POL(c3(x_1)) = x_1
   POL(c4(x_1)) = x_1
   POL(c7(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(c9(x_1)) = x_1

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

(12)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   Sum_sub(z0, Id) -> Sum_term_var(z0)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_constant(z2)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_sub(z0, z3)
   Sum_sub(z0, Cons_usual(z1, z2, z3)) -> Sum_sub(z0, z3)
Tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
S tuples:
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
K tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
Defined Rule Symbols:   Sum_sub_2

Defined Pair Symbols:   TERM_SUB_2, FROZEN_4, SUM_SUB_2, CONCAT_2

Compound Symbols:   c_2, c1_2, c2_2, c3_1, c4_1, c7_1, c8_1, c9_1, c10_1, c11_2, c14_1, c15_1, c16_2, c17_1


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

(13) CdtKnowledgeProof (BOTH BOUNDS(ID, ID))
The following tuples could be moved from S to K by knowledge propagation:
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))

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

(14)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   Sum_sub(z0, Id) -> Sum_term_var(z0)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_constant(z2)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_sub(z0, z3)
   Sum_sub(z0, Cons_usual(z1, z2, z3)) -> Sum_sub(z0, z3)
Tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
S tuples:
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
K tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
Defined Rule Symbols:   Sum_sub_2

Defined Pair Symbols:   TERM_SUB_2, FROZEN_4, SUM_SUB_2, CONCAT_2

Compound Symbols:   c_2, c1_2, c2_2, c3_1, c4_1, c7_1, c8_1, c9_1, c10_1, c11_2, c14_1, c15_1, c16_2, c17_1


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

(15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
We considered the (Usable) Rules:none
And the Tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(CONCAT(x_1, x_2)) = [2]x_1*x_2
   POL(Case(x_1, x_2, x_3)) = x_1 + x_3
   POL(Cons_sum(x_1, x_2, x_3)) = [2] + x_2 + x_3
   POL(Cons_usual(x_1, x_2, x_3)) = x_2 + x_3
   POL(FROZEN(x_1, x_2, x_3, x_4)) = [2]x_3*x_4 + [2]x_1*x_4
   POL(Id) = 0
   POL(Left) = 0
   POL(Right) = 0
   POL(SUM_SUB(x_1, x_2)) = 0
   POL(Sum_constant(x_1)) = 0
   POL(Sum_sub(x_1, x_2)) = x_2^2
   POL(Sum_term_var(x_1)) = x_1
   POL(TERM_SUB(x_1, x_2)) = [2]x_1*x_2
   POL(Term_app(x_1, x_2)) = x_1 + x_2
   POL(Term_inl(x_1)) = [2] + x_1
   POL(Term_inr(x_1)) = [2] + x_1
   POL(Term_pair(x_1, x_2)) = x_1 + x_2
   POL(Term_var(x_1)) = [2] + x_1
   POL(c(x_1, x_2)) = x_1 + x_2
   POL(c1(x_1, x_2)) = x_1 + x_2
   POL(c10(x_1)) = x_1
   POL(c11(x_1, x_2)) = x_1 + x_2
   POL(c14(x_1)) = x_1
   POL(c15(x_1)) = x_1
   POL(c16(x_1, x_2)) = x_1 + x_2
   POL(c17(x_1)) = x_1
   POL(c2(x_1, x_2)) = x_1 + x_2
   POL(c3(x_1)) = x_1
   POL(c4(x_1)) = x_1
   POL(c7(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(c9(x_1)) = x_1

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

(16)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   Sum_sub(z0, Id) -> Sum_term_var(z0)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_constant(z2)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_sub(z0, z3)
   Sum_sub(z0, Cons_usual(z1, z2, z3)) -> Sum_sub(z0, z3)
Tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
S tuples:
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
K tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
Defined Rule Symbols:   Sum_sub_2

Defined Pair Symbols:   TERM_SUB_2, FROZEN_4, SUM_SUB_2, CONCAT_2

Compound Symbols:   c_2, c1_2, c2_2, c3_1, c4_1, c7_1, c8_1, c9_1, c10_1, c11_2, c14_1, c15_1, c16_2, c17_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.
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
We considered the (Usable) Rules:none
And the Tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(CONCAT(x_1, x_2)) = [2]x_1*x_2 + [2]x_1^2
   POL(Case(x_1, x_2, x_3)) = [1] + x_1 + x_3
   POL(Cons_sum(x_1, x_2, x_3)) = [1] + x_2 + x_3
   POL(Cons_usual(x_1, x_2, x_3)) = x_2 + x_3
   POL(FROZEN(x_1, x_2, x_3, x_4)) = [2]x_3*x_4 + [2]x_1*x_4 + [2]x_1^2 + [2]x_3^2
   POL(Id) = 0
   POL(Left) = 0
   POL(Right) = 0
   POL(SUM_SUB(x_1, x_2)) = [2] + x_2
   POL(Sum_constant(x_1)) = 0
   POL(Sum_sub(x_1, x_2)) = x_2^2
   POL(Sum_term_var(x_1)) = x_1
   POL(TERM_SUB(x_1, x_2)) = [2]x_1*x_2 + [2]x_1^2
   POL(Term_app(x_1, x_2)) = x_1 + x_2
   POL(Term_inl(x_1)) = [1] + x_1
   POL(Term_inr(x_1)) = [2] + x_1
   POL(Term_pair(x_1, x_2)) = x_1 + x_2
   POL(Term_var(x_1)) = x_1
   POL(c(x_1, x_2)) = x_1 + x_2
   POL(c1(x_1, x_2)) = x_1 + x_2
   POL(c10(x_1)) = x_1
   POL(c11(x_1, x_2)) = x_1 + x_2
   POL(c14(x_1)) = x_1
   POL(c15(x_1)) = x_1
   POL(c16(x_1, x_2)) = x_1 + x_2
   POL(c17(x_1)) = x_1
   POL(c2(x_1, x_2)) = x_1 + x_2
   POL(c3(x_1)) = x_1
   POL(c4(x_1)) = x_1
   POL(c7(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(c9(x_1)) = x_1

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

(18)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   Sum_sub(z0, Id) -> Sum_term_var(z0)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_constant(z2)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_sub(z0, z3)
   Sum_sub(z0, Cons_usual(z1, z2, z3)) -> Sum_sub(z0, z3)
Tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
S tuples:
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
K tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
Defined Rule Symbols:   Sum_sub_2

Defined Pair Symbols:   TERM_SUB_2, FROZEN_4, SUM_SUB_2, CONCAT_2

Compound Symbols:   c_2, c1_2, c2_2, c3_1, c4_1, c7_1, c8_1, c9_1, c10_1, c11_2, c14_1, c15_1, c16_2, c17_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.
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
We considered the (Usable) Rules:none
And the Tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(CONCAT(x_1, x_2)) = [2]x_1*x_2
   POL(Case(x_1, x_2, x_3)) = [2] + x_1 + x_3
   POL(Cons_sum(x_1, x_2, x_3)) = x_2 + x_3
   POL(Cons_usual(x_1, x_2, x_3)) = [2] + x_2 + x_3
   POL(FROZEN(x_1, x_2, x_3, x_4)) = x_3*x_4 + x_1*x_4
   POL(Id) = 0
   POL(Left) = 0
   POL(Right) = 0
   POL(SUM_SUB(x_1, x_2)) = x_2
   POL(Sum_constant(x_1)) = 0
   POL(Sum_sub(x_1, x_2)) = x_2^2
   POL(Sum_term_var(x_1)) = x_1
   POL(TERM_SUB(x_1, x_2)) = x_1*x_2
   POL(Term_app(x_1, x_2)) = x_1 + x_2
   POL(Term_inl(x_1)) = [2] + x_1
   POL(Term_inr(x_1)) = [2] + x_1
   POL(Term_pair(x_1, x_2)) = x_1 + x_2
   POL(Term_var(x_1)) = x_1
   POL(c(x_1, x_2)) = x_1 + x_2
   POL(c1(x_1, x_2)) = x_1 + x_2
   POL(c10(x_1)) = x_1
   POL(c11(x_1, x_2)) = x_1 + x_2
   POL(c14(x_1)) = x_1
   POL(c15(x_1)) = x_1
   POL(c16(x_1, x_2)) = x_1 + x_2
   POL(c17(x_1)) = x_1
   POL(c2(x_1, x_2)) = x_1 + x_2
   POL(c3(x_1)) = x_1
   POL(c4(x_1)) = x_1
   POL(c7(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(c9(x_1)) = x_1

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

(20)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   Sum_sub(z0, Id) -> Sum_term_var(z0)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_constant(z2)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_sub(z0, z3)
   Sum_sub(z0, Cons_usual(z1, z2, z3)) -> Sum_sub(z0, z3)
Tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
S tuples:
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
K tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
Defined Rule Symbols:   Sum_sub_2

Defined Pair Symbols:   TERM_SUB_2, FROZEN_4, SUM_SUB_2, CONCAT_2

Compound Symbols:   c_2, c1_2, c2_2, c3_1, c4_1, c7_1, c8_1, c9_1, c10_1, c11_2, c14_1, c15_1, c16_2, c17_1


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

(21) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
We considered the (Usable) Rules:none
And the Tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(CONCAT(x_1, x_2)) = [2]x_1*x_2
   POL(Case(x_1, x_2, x_3)) = [2] + x_1 + x_3
   POL(Cons_sum(x_1, x_2, x_3)) = x_2 + x_3
   POL(Cons_usual(x_1, x_2, x_3)) = [1] + x_2 + x_3
   POL(FROZEN(x_1, x_2, x_3, x_4)) = [2]x_4 + [2]x_3*x_4 + [2]x_1*x_4
   POL(Id) = 0
   POL(Left) = 0
   POL(Right) = 0
   POL(SUM_SUB(x_1, x_2)) = [2]x_2
   POL(Sum_constant(x_1)) = 0
   POL(Sum_sub(x_1, x_2)) = x_2^2
   POL(Sum_term_var(x_1)) = x_1
   POL(TERM_SUB(x_1, x_2)) = x_2 + [2]x_1*x_2
   POL(Term_app(x_1, x_2)) = [2] + x_1 + x_2
   POL(Term_inl(x_1)) = [2] + x_1
   POL(Term_inr(x_1)) = [2] + x_1
   POL(Term_pair(x_1, x_2)) = [2] + x_1 + x_2
   POL(Term_var(x_1)) = x_1
   POL(c(x_1, x_2)) = x_1 + x_2
   POL(c1(x_1, x_2)) = x_1 + x_2
   POL(c10(x_1)) = x_1
   POL(c11(x_1, x_2)) = x_1 + x_2
   POL(c14(x_1)) = x_1
   POL(c15(x_1)) = x_1
   POL(c16(x_1, x_2)) = x_1 + x_2
   POL(c17(x_1)) = x_1
   POL(c2(x_1, x_2)) = x_1 + x_2
   POL(c3(x_1)) = x_1
   POL(c4(x_1)) = x_1
   POL(c7(x_1)) = x_1
   POL(c8(x_1)) = x_1
   POL(c9(x_1)) = x_1

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

(22)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   Sum_sub(z0, Id) -> Sum_term_var(z0)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_constant(z2)
   Sum_sub(z0, Cons_sum(z1, z2, z3)) -> Sum_sub(z0, z3)
   Sum_sub(z0, Cons_usual(z1, z2, z3)) -> Sum_sub(z0, z3)
Tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
S tuples:none
K tuples:
   TERM_SUB(Case(z0, z1, z2), z3) -> c(FROZEN(z0, Sum_sub(z1, z3), z2, z3), SUM_SUB(z1, z3))
   TERM_SUB(Term_app(z0, z1), z2) -> c1(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_pair(z0, z1), z2) -> c2(TERM_SUB(z0, z2), TERM_SUB(z1, z2))
   TERM_SUB(Term_inl(z0), z1) -> c3(TERM_SUB(z0, z1))
   TERM_SUB(Term_inr(z0), z1) -> c4(TERM_SUB(z0, z1))
   CONCAT(Cons_usual(z0, z1, z2), z3) -> c16(TERM_SUB(z1, z3), CONCAT(z2, z3))
   CONCAT(Cons_sum(z0, z1, z2), z3) -> c17(CONCAT(z2, z3))
   FROZEN(z0, Sum_constant(Left), z1, z2) -> c9(TERM_SUB(z0, z2))
   FROZEN(z0, Sum_constant(Right), z1, z2) -> c10(TERM_SUB(z1, z2))
   FROZEN(z0, Sum_term_var(z1), z2, z3) -> c11(TERM_SUB(z0, z3), TERM_SUB(z2, z3))
   TERM_SUB(Term_var(z0), Cons_sum(z1, z2, z3)) -> c8(TERM_SUB(Term_var(z0), z3))
   SUM_SUB(z0, Cons_sum(z1, z2, z3)) -> c14(SUM_SUB(z0, z3))
   SUM_SUB(z0, Cons_usual(z1, z2, z3)) -> c15(SUM_SUB(z0, z3))
   TERM_SUB(Term_var(z0), Cons_usual(z1, z2, z3)) -> c7(TERM_SUB(Term_var(z0), z3))
Defined Rule Symbols:   Sum_sub_2

Defined Pair Symbols:   TERM_SUB_2, FROZEN_4, SUM_SUB_2, CONCAT_2

Compound Symbols:   c_2, c1_2, c2_2, c3_1, c4_1, c7_1, c8_1, c9_1, c10_1, c11_2, c14_1, c15_1, c16_2, c17_1


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

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

(24)
BOUNDS(1, 1)

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

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

(26)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).


The TRS R consists of the following rules:

   Term_sub(Case(m, xi, n), s) -> Frozen(m, Sum_sub(xi, s), n, s)
   Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s)
   Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s)
   Frozen(m, Sum_term_var(xi), n, s) -> Case(Term_sub(m, s), xi, Term_sub(n, s))
   Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s))
   Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s))
   Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s))
   Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s))
   Term_sub(Term_var(x), Id) -> Term_var(x)
   Term_sub(Term_var(x), Cons_usual(y, m, s)) -> m
   Term_sub(Term_var(x), Cons_usual(y, m, s)) -> Term_sub(Term_var(x), s)
   Term_sub(Term_var(x), Cons_sum(xi, k, s)) -> Term_sub(Term_var(x), s)
   Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t))
   Sum_sub(xi, Id) -> Sum_term_var(xi)
   Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_constant(k)
   Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_sub(xi, s)
   Sum_sub(xi, Cons_usual(y, m, s)) -> Sum_sub(xi, s)
   Concat(Concat(s, t), u) -> Concat(s, Concat(t, u))
   Concat(Cons_usual(x, m, s), t) -> Cons_usual(x, Term_sub(m, t), Concat(s, t))
   Concat(Cons_sum(xi, k, s), t) -> Cons_sum(xi, k, Concat(s, t))
   Concat(Id, s) -> s

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(27) SlicingProof (LOWER BOUND(ID))
Sliced the following arguments:
Case/1
Sum_sub/0
Sum_term_var/0
Term_var/0
Cons_usual/0
Cons_sum/0

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

(28)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).


The TRS R consists of the following rules:

   Term_sub(Case(m, n), s) -> Frozen(m, Sum_sub(s), n, s)
   Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s)
   Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s)
   Frozen(m, Sum_term_var, n, s) -> Case(Term_sub(m, s), Term_sub(n, s))
   Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s))
   Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s))
   Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s))
   Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s))
   Term_sub(Term_var, Id) -> Term_var
   Term_sub(Term_var, Cons_usual(m, s)) -> m
   Term_sub(Term_var, Cons_usual(m, s)) -> Term_sub(Term_var, s)
   Term_sub(Term_var, Cons_sum(k, s)) -> Term_sub(Term_var, s)
   Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t))
   Sum_sub(Id) -> Sum_term_var
   Sum_sub(Cons_sum(k, s)) -> Sum_constant(k)
   Sum_sub(Cons_sum(k, s)) -> Sum_sub(s)
   Sum_sub(Cons_usual(m, s)) -> Sum_sub(s)
   Concat(Concat(s, t), u) -> Concat(s, Concat(t, u))
   Concat(Cons_usual(m, s), t) -> Cons_usual(Term_sub(m, t), Concat(s, t))
   Concat(Cons_sum(k, s), t) -> Cons_sum(k, Concat(s, t))
   Concat(Id, s) -> s

S is empty.
Rewrite Strategy: FULL
----------------------------------------

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

(30)
Obligation:
TRS:
Rules:
Term_sub(Case(m, n), s) -> Frozen(m, Sum_sub(s), n, s)
Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s)
Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s)
Frozen(m, Sum_term_var, n, s) -> Case(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s))
Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s))
Term_sub(Term_var, Id) -> Term_var
Term_sub(Term_var, Cons_usual(m, s)) -> m
Term_sub(Term_var, Cons_usual(m, s)) -> Term_sub(Term_var, s)
Term_sub(Term_var, Cons_sum(k, s)) -> Term_sub(Term_var, s)
Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t))
Sum_sub(Id) -> Sum_term_var
Sum_sub(Cons_sum(k, s)) -> Sum_constant(k)
Sum_sub(Cons_sum(k, s)) -> Sum_sub(s)
Sum_sub(Cons_usual(m, s)) -> Sum_sub(s)
Concat(Concat(s, t), u) -> Concat(s, Concat(t, u))
Concat(Cons_usual(m, s), t) -> Cons_usual(Term_sub(m, t), Concat(s, t))
Concat(Cons_sum(k, s), t) -> Cons_sum(k, Concat(s, t))
Concat(Id, s) -> s

Types:
Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Case :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Sum_constant:Sum_term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Sum_sub :: Id:Cons_usual:Cons_sum -> Sum_constant:Sum_term_var
Sum_constant :: Left:Right -> Sum_constant:Sum_term_var
Left :: Left:Right
Right :: Left:Right
Sum_term_var :: Sum_constant:Sum_term_var
Term_app :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_pair :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_inl :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_inr :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_var :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Id :: Id:Cons_usual:Cons_sum
Cons_usual :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
Cons_sum :: Left:Right -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
Concat :: Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
hole_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var1_0 :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
hole_Id:Cons_usual:Cons_sum2_0 :: Id:Cons_usual:Cons_sum
hole_Sum_constant:Sum_term_var3_0 :: Sum_constant:Sum_term_var
hole_Left:Right4_0 :: Left:Right
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0 :: Nat -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
gen_Id:Cons_usual:Cons_sum6_0 :: Nat -> Id:Cons_usual:Cons_sum

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

(31) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
Term_sub, Sum_sub, Concat

They will be analysed ascendingly in the following order:
Sum_sub < Term_sub
Term_sub = Concat

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

(32)
Obligation:
TRS:
Rules:
Term_sub(Case(m, n), s) -> Frozen(m, Sum_sub(s), n, s)
Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s)
Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s)
Frozen(m, Sum_term_var, n, s) -> Case(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s))
Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s))
Term_sub(Term_var, Id) -> Term_var
Term_sub(Term_var, Cons_usual(m, s)) -> m
Term_sub(Term_var, Cons_usual(m, s)) -> Term_sub(Term_var, s)
Term_sub(Term_var, Cons_sum(k, s)) -> Term_sub(Term_var, s)
Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t))
Sum_sub(Id) -> Sum_term_var
Sum_sub(Cons_sum(k, s)) -> Sum_constant(k)
Sum_sub(Cons_sum(k, s)) -> Sum_sub(s)
Sum_sub(Cons_usual(m, s)) -> Sum_sub(s)
Concat(Concat(s, t), u) -> Concat(s, Concat(t, u))
Concat(Cons_usual(m, s), t) -> Cons_usual(Term_sub(m, t), Concat(s, t))
Concat(Cons_sum(k, s), t) -> Cons_sum(k, Concat(s, t))
Concat(Id, s) -> s

Types:
Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Case :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Sum_constant:Sum_term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Sum_sub :: Id:Cons_usual:Cons_sum -> Sum_constant:Sum_term_var
Sum_constant :: Left:Right -> Sum_constant:Sum_term_var
Left :: Left:Right
Right :: Left:Right
Sum_term_var :: Sum_constant:Sum_term_var
Term_app :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_pair :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_inl :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_inr :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_var :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Id :: Id:Cons_usual:Cons_sum
Cons_usual :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
Cons_sum :: Left:Right -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
Concat :: Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
hole_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var1_0 :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
hole_Id:Cons_usual:Cons_sum2_0 :: Id:Cons_usual:Cons_sum
hole_Sum_constant:Sum_term_var3_0 :: Sum_constant:Sum_term_var
hole_Left:Right4_0 :: Left:Right
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0 :: Nat -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
gen_Id:Cons_usual:Cons_sum6_0 :: Nat -> Id:Cons_usual:Cons_sum


Generator Equations:
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0) <=> Term_var
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(+(x, 1)) <=> Case(Term_var, gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(x))
gen_Id:Cons_usual:Cons_sum6_0(0) <=> Id
gen_Id:Cons_usual:Cons_sum6_0(+(x, 1)) <=> Cons_usual(Term_var, gen_Id:Cons_usual:Cons_sum6_0(x))


The following defined symbols remain to be analysed:
Sum_sub, Term_sub, Concat

They will be analysed ascendingly in the following order:
Sum_sub < Term_sub
Term_sub = Concat

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

(33) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
Sum_sub(gen_Id:Cons_usual:Cons_sum6_0(n8_0)) -> Sum_term_var, rt in Omega(1 + n8_0)

Induction Base:
Sum_sub(gen_Id:Cons_usual:Cons_sum6_0(0)) ->_R^Omega(1)
Sum_term_var

Induction Step:
Sum_sub(gen_Id:Cons_usual:Cons_sum6_0(+(n8_0, 1))) ->_R^Omega(1)
Sum_sub(gen_Id:Cons_usual:Cons_sum6_0(n8_0)) ->_IH
Sum_term_var

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

(34)
Complex Obligation (BEST)

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

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

TRS:
Rules:
Term_sub(Case(m, n), s) -> Frozen(m, Sum_sub(s), n, s)
Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s)
Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s)
Frozen(m, Sum_term_var, n, s) -> Case(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s))
Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s))
Term_sub(Term_var, Id) -> Term_var
Term_sub(Term_var, Cons_usual(m, s)) -> m
Term_sub(Term_var, Cons_usual(m, s)) -> Term_sub(Term_var, s)
Term_sub(Term_var, Cons_sum(k, s)) -> Term_sub(Term_var, s)
Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t))
Sum_sub(Id) -> Sum_term_var
Sum_sub(Cons_sum(k, s)) -> Sum_constant(k)
Sum_sub(Cons_sum(k, s)) -> Sum_sub(s)
Sum_sub(Cons_usual(m, s)) -> Sum_sub(s)
Concat(Concat(s, t), u) -> Concat(s, Concat(t, u))
Concat(Cons_usual(m, s), t) -> Cons_usual(Term_sub(m, t), Concat(s, t))
Concat(Cons_sum(k, s), t) -> Cons_sum(k, Concat(s, t))
Concat(Id, s) -> s

Types:
Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Case :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Sum_constant:Sum_term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Sum_sub :: Id:Cons_usual:Cons_sum -> Sum_constant:Sum_term_var
Sum_constant :: Left:Right -> Sum_constant:Sum_term_var
Left :: Left:Right
Right :: Left:Right
Sum_term_var :: Sum_constant:Sum_term_var
Term_app :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_pair :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_inl :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_inr :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_var :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Id :: Id:Cons_usual:Cons_sum
Cons_usual :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
Cons_sum :: Left:Right -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
Concat :: Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
hole_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var1_0 :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
hole_Id:Cons_usual:Cons_sum2_0 :: Id:Cons_usual:Cons_sum
hole_Sum_constant:Sum_term_var3_0 :: Sum_constant:Sum_term_var
hole_Left:Right4_0 :: Left:Right
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0 :: Nat -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
gen_Id:Cons_usual:Cons_sum6_0 :: Nat -> Id:Cons_usual:Cons_sum


Generator Equations:
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0) <=> Term_var
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(+(x, 1)) <=> Case(Term_var, gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(x))
gen_Id:Cons_usual:Cons_sum6_0(0) <=> Id
gen_Id:Cons_usual:Cons_sum6_0(+(x, 1)) <=> Cons_usual(Term_var, gen_Id:Cons_usual:Cons_sum6_0(x))


The following defined symbols remain to be analysed:
Sum_sub, Term_sub, Concat

They will be analysed ascendingly in the following order:
Sum_sub < Term_sub
Term_sub = Concat

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

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

(37)
BOUNDS(n^1, INF)

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

(38)
Obligation:
TRS:
Rules:
Term_sub(Case(m, n), s) -> Frozen(m, Sum_sub(s), n, s)
Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s)
Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s)
Frozen(m, Sum_term_var, n, s) -> Case(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s))
Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s))
Term_sub(Term_var, Id) -> Term_var
Term_sub(Term_var, Cons_usual(m, s)) -> m
Term_sub(Term_var, Cons_usual(m, s)) -> Term_sub(Term_var, s)
Term_sub(Term_var, Cons_sum(k, s)) -> Term_sub(Term_var, s)
Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t))
Sum_sub(Id) -> Sum_term_var
Sum_sub(Cons_sum(k, s)) -> Sum_constant(k)
Sum_sub(Cons_sum(k, s)) -> Sum_sub(s)
Sum_sub(Cons_usual(m, s)) -> Sum_sub(s)
Concat(Concat(s, t), u) -> Concat(s, Concat(t, u))
Concat(Cons_usual(m, s), t) -> Cons_usual(Term_sub(m, t), Concat(s, t))
Concat(Cons_sum(k, s), t) -> Cons_sum(k, Concat(s, t))
Concat(Id, s) -> s

Types:
Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Case :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Sum_constant:Sum_term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Sum_sub :: Id:Cons_usual:Cons_sum -> Sum_constant:Sum_term_var
Sum_constant :: Left:Right -> Sum_constant:Sum_term_var
Left :: Left:Right
Right :: Left:Right
Sum_term_var :: Sum_constant:Sum_term_var
Term_app :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_pair :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_inl :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_inr :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_var :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Id :: Id:Cons_usual:Cons_sum
Cons_usual :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
Cons_sum :: Left:Right -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
Concat :: Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
hole_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var1_0 :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
hole_Id:Cons_usual:Cons_sum2_0 :: Id:Cons_usual:Cons_sum
hole_Sum_constant:Sum_term_var3_0 :: Sum_constant:Sum_term_var
hole_Left:Right4_0 :: Left:Right
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0 :: Nat -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
gen_Id:Cons_usual:Cons_sum6_0 :: Nat -> Id:Cons_usual:Cons_sum


Lemmas:
Sum_sub(gen_Id:Cons_usual:Cons_sum6_0(n8_0)) -> Sum_term_var, rt in Omega(1 + n8_0)


Generator Equations:
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0) <=> Term_var
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(+(x, 1)) <=> Case(Term_var, gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(x))
gen_Id:Cons_usual:Cons_sum6_0(0) <=> Id
gen_Id:Cons_usual:Cons_sum6_0(+(x, 1)) <=> Cons_usual(Term_var, gen_Id:Cons_usual:Cons_sum6_0(x))


The following defined symbols remain to be analysed:
Concat, Term_sub

They will be analysed ascendingly in the following order:
Term_sub = Concat

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

(39) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
Concat(gen_Id:Cons_usual:Cons_sum6_0(n370_0), gen_Id:Cons_usual:Cons_sum6_0(0)) -> gen_Id:Cons_usual:Cons_sum6_0(n370_0), rt in Omega(1 + n370_0)

Induction Base:
Concat(gen_Id:Cons_usual:Cons_sum6_0(0), gen_Id:Cons_usual:Cons_sum6_0(0)) ->_R^Omega(1)
gen_Id:Cons_usual:Cons_sum6_0(0)

Induction Step:
Concat(gen_Id:Cons_usual:Cons_sum6_0(+(n370_0, 1)), gen_Id:Cons_usual:Cons_sum6_0(0)) ->_R^Omega(1)
Cons_usual(Term_sub(Term_var, gen_Id:Cons_usual:Cons_sum6_0(0)), Concat(gen_Id:Cons_usual:Cons_sum6_0(n370_0), gen_Id:Cons_usual:Cons_sum6_0(0))) ->_R^Omega(1)
Cons_usual(Term_var, Concat(gen_Id:Cons_usual:Cons_sum6_0(n370_0), gen_Id:Cons_usual:Cons_sum6_0(0))) ->_IH
Cons_usual(Term_var, gen_Id:Cons_usual:Cons_sum6_0(c371_0))

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

(40)
Obligation:
TRS:
Rules:
Term_sub(Case(m, n), s) -> Frozen(m, Sum_sub(s), n, s)
Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s)
Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s)
Frozen(m, Sum_term_var, n, s) -> Case(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s))
Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s))
Term_sub(Term_var, Id) -> Term_var
Term_sub(Term_var, Cons_usual(m, s)) -> m
Term_sub(Term_var, Cons_usual(m, s)) -> Term_sub(Term_var, s)
Term_sub(Term_var, Cons_sum(k, s)) -> Term_sub(Term_var, s)
Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t))
Sum_sub(Id) -> Sum_term_var
Sum_sub(Cons_sum(k, s)) -> Sum_constant(k)
Sum_sub(Cons_sum(k, s)) -> Sum_sub(s)
Sum_sub(Cons_usual(m, s)) -> Sum_sub(s)
Concat(Concat(s, t), u) -> Concat(s, Concat(t, u))
Concat(Cons_usual(m, s), t) -> Cons_usual(Term_sub(m, t), Concat(s, t))
Concat(Cons_sum(k, s), t) -> Cons_sum(k, Concat(s, t))
Concat(Id, s) -> s

Types:
Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Case :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Sum_constant:Sum_term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Sum_sub :: Id:Cons_usual:Cons_sum -> Sum_constant:Sum_term_var
Sum_constant :: Left:Right -> Sum_constant:Sum_term_var
Left :: Left:Right
Right :: Left:Right
Sum_term_var :: Sum_constant:Sum_term_var
Term_app :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_pair :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_inl :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_inr :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_var :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Id :: Id:Cons_usual:Cons_sum
Cons_usual :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
Cons_sum :: Left:Right -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
Concat :: Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
hole_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var1_0 :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
hole_Id:Cons_usual:Cons_sum2_0 :: Id:Cons_usual:Cons_sum
hole_Sum_constant:Sum_term_var3_0 :: Sum_constant:Sum_term_var
hole_Left:Right4_0 :: Left:Right
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0 :: Nat -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
gen_Id:Cons_usual:Cons_sum6_0 :: Nat -> Id:Cons_usual:Cons_sum


Lemmas:
Sum_sub(gen_Id:Cons_usual:Cons_sum6_0(n8_0)) -> Sum_term_var, rt in Omega(1 + n8_0)
Concat(gen_Id:Cons_usual:Cons_sum6_0(n370_0), gen_Id:Cons_usual:Cons_sum6_0(0)) -> gen_Id:Cons_usual:Cons_sum6_0(n370_0), rt in Omega(1 + n370_0)


Generator Equations:
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0) <=> Term_var
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(+(x, 1)) <=> Case(Term_var, gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(x))
gen_Id:Cons_usual:Cons_sum6_0(0) <=> Id
gen_Id:Cons_usual:Cons_sum6_0(+(x, 1)) <=> Cons_usual(Term_var, gen_Id:Cons_usual:Cons_sum6_0(x))


The following defined symbols remain to be analysed:
Term_sub

They will be analysed ascendingly in the following order:
Term_sub = Concat

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

(41) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
Term_sub(gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), gen_Id:Cons_usual:Cons_sum6_0(n183948_0)) -> gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), rt in Omega(1 + n183948_0)

Induction Base:
Term_sub(gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), gen_Id:Cons_usual:Cons_sum6_0(0)) ->_R^Omega(1)
Term_var

Induction Step:
Term_sub(gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), gen_Id:Cons_usual:Cons_sum6_0(+(n183948_0, 1))) ->_R^Omega(1)
Term_sub(Term_var, gen_Id:Cons_usual:Cons_sum6_0(n183948_0)) ->_IH
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0)

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

(42)
Obligation:
TRS:
Rules:
Term_sub(Case(m, n), s) -> Frozen(m, Sum_sub(s), n, s)
Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s)
Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s)
Frozen(m, Sum_term_var, n, s) -> Case(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s))
Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s))
Term_sub(Term_var, Id) -> Term_var
Term_sub(Term_var, Cons_usual(m, s)) -> m
Term_sub(Term_var, Cons_usual(m, s)) -> Term_sub(Term_var, s)
Term_sub(Term_var, Cons_sum(k, s)) -> Term_sub(Term_var, s)
Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t))
Sum_sub(Id) -> Sum_term_var
Sum_sub(Cons_sum(k, s)) -> Sum_constant(k)
Sum_sub(Cons_sum(k, s)) -> Sum_sub(s)
Sum_sub(Cons_usual(m, s)) -> Sum_sub(s)
Concat(Concat(s, t), u) -> Concat(s, Concat(t, u))
Concat(Cons_usual(m, s), t) -> Cons_usual(Term_sub(m, t), Concat(s, t))
Concat(Cons_sum(k, s), t) -> Cons_sum(k, Concat(s, t))
Concat(Id, s) -> s

Types:
Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Case :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Sum_constant:Sum_term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Sum_sub :: Id:Cons_usual:Cons_sum -> Sum_constant:Sum_term_var
Sum_constant :: Left:Right -> Sum_constant:Sum_term_var
Left :: Left:Right
Right :: Left:Right
Sum_term_var :: Sum_constant:Sum_term_var
Term_app :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_pair :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_inl :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_inr :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_var :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Id :: Id:Cons_usual:Cons_sum
Cons_usual :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
Cons_sum :: Left:Right -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
Concat :: Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
hole_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var1_0 :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
hole_Id:Cons_usual:Cons_sum2_0 :: Id:Cons_usual:Cons_sum
hole_Sum_constant:Sum_term_var3_0 :: Sum_constant:Sum_term_var
hole_Left:Right4_0 :: Left:Right
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0 :: Nat -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
gen_Id:Cons_usual:Cons_sum6_0 :: Nat -> Id:Cons_usual:Cons_sum


Lemmas:
Sum_sub(gen_Id:Cons_usual:Cons_sum6_0(n8_0)) -> Sum_term_var, rt in Omega(1 + n8_0)
Concat(gen_Id:Cons_usual:Cons_sum6_0(n370_0), gen_Id:Cons_usual:Cons_sum6_0(0)) -> gen_Id:Cons_usual:Cons_sum6_0(n370_0), rt in Omega(1 + n370_0)
Term_sub(gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), gen_Id:Cons_usual:Cons_sum6_0(n183948_0)) -> gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), rt in Omega(1 + n183948_0)


Generator Equations:
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0) <=> Term_var
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(+(x, 1)) <=> Case(Term_var, gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(x))
gen_Id:Cons_usual:Cons_sum6_0(0) <=> Id
gen_Id:Cons_usual:Cons_sum6_0(+(x, 1)) <=> Cons_usual(Term_var, gen_Id:Cons_usual:Cons_sum6_0(x))


The following defined symbols remain to be analysed:
Concat

They will be analysed ascendingly in the following order:
Term_sub = Concat

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

(43) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
Concat(gen_Id:Cons_usual:Cons_sum6_0(n390037_0), gen_Id:Cons_usual:Cons_sum6_0(b)) -> gen_Id:Cons_usual:Cons_sum6_0(+(n390037_0, b)), rt in Omega(1 + b*n390037_0 + n390037_0)

Induction Base:
Concat(gen_Id:Cons_usual:Cons_sum6_0(0), gen_Id:Cons_usual:Cons_sum6_0(b)) ->_R^Omega(1)
gen_Id:Cons_usual:Cons_sum6_0(b)

Induction Step:
Concat(gen_Id:Cons_usual:Cons_sum6_0(+(n390037_0, 1)), gen_Id:Cons_usual:Cons_sum6_0(b)) ->_R^Omega(1)
Cons_usual(Term_sub(Term_var, gen_Id:Cons_usual:Cons_sum6_0(b)), Concat(gen_Id:Cons_usual:Cons_sum6_0(n390037_0), gen_Id:Cons_usual:Cons_sum6_0(b))) ->_L^Omega(1 + b)
Cons_usual(gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), Concat(gen_Id:Cons_usual:Cons_sum6_0(n390037_0), gen_Id:Cons_usual:Cons_sum6_0(b))) ->_IH
Cons_usual(gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), gen_Id:Cons_usual:Cons_sum6_0(+(b, c390038_0)))

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

(44)
Obligation:
Proved the lower bound n^2 for the following obligation:

TRS:
Rules:
Term_sub(Case(m, n), s) -> Frozen(m, Sum_sub(s), n, s)
Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s)
Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s)
Frozen(m, Sum_term_var, n, s) -> Case(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s))
Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s))
Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s))
Term_sub(Term_var, Id) -> Term_var
Term_sub(Term_var, Cons_usual(m, s)) -> m
Term_sub(Term_var, Cons_usual(m, s)) -> Term_sub(Term_var, s)
Term_sub(Term_var, Cons_sum(k, s)) -> Term_sub(Term_var, s)
Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t))
Sum_sub(Id) -> Sum_term_var
Sum_sub(Cons_sum(k, s)) -> Sum_constant(k)
Sum_sub(Cons_sum(k, s)) -> Sum_sub(s)
Sum_sub(Cons_usual(m, s)) -> Sum_sub(s)
Concat(Concat(s, t), u) -> Concat(s, Concat(t, u))
Concat(Cons_usual(m, s), t) -> Cons_usual(Term_sub(m, t), Concat(s, t))
Concat(Cons_sum(k, s), t) -> Cons_sum(k, Concat(s, t))
Concat(Id, s) -> s

Types:
Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Case :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Sum_constant:Sum_term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Sum_sub :: Id:Cons_usual:Cons_sum -> Sum_constant:Sum_term_var
Sum_constant :: Left:Right -> Sum_constant:Sum_term_var
Left :: Left:Right
Right :: Left:Right
Sum_term_var :: Sum_constant:Sum_term_var
Term_app :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_pair :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_inl :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_inr :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Term_var :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
Id :: Id:Cons_usual:Cons_sum
Cons_usual :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
Cons_sum :: Left:Right -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
Concat :: Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum
hole_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var1_0 :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
hole_Id:Cons_usual:Cons_sum2_0 :: Id:Cons_usual:Cons_sum
hole_Sum_constant:Sum_term_var3_0 :: Sum_constant:Sum_term_var
hole_Left:Right4_0 :: Left:Right
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0 :: Nat -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var
gen_Id:Cons_usual:Cons_sum6_0 :: Nat -> Id:Cons_usual:Cons_sum


Lemmas:
Sum_sub(gen_Id:Cons_usual:Cons_sum6_0(n8_0)) -> Sum_term_var, rt in Omega(1 + n8_0)
Concat(gen_Id:Cons_usual:Cons_sum6_0(n370_0), gen_Id:Cons_usual:Cons_sum6_0(0)) -> gen_Id:Cons_usual:Cons_sum6_0(n370_0), rt in Omega(1 + n370_0)
Term_sub(gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), gen_Id:Cons_usual:Cons_sum6_0(n183948_0)) -> gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), rt in Omega(1 + n183948_0)


Generator Equations:
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0) <=> Term_var
gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(+(x, 1)) <=> Case(Term_var, gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(x))
gen_Id:Cons_usual:Cons_sum6_0(0) <=> Id
gen_Id:Cons_usual:Cons_sum6_0(+(x, 1)) <=> Cons_usual(Term_var, gen_Id:Cons_usual:Cons_sum6_0(x))


The following defined symbols remain to be analysed:
Concat

They will be analysed ascendingly in the following order:
Term_sub = Concat

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

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

(46)
BOUNDS(n^2, INF)