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


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

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


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

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


The TRS R consists of the following rules:

   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   reverse(nil) -> nil
   reverse(add(n, x)) -> app(reverse(x), add(n, nil))
   shuffle(nil) -> nil
   shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))

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

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

(2)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   app(nil, z0) -> z0
   app(add(z0, z1), z2) -> add(z0, app(z1, z2))
   reverse(nil) -> nil
   reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil))
   shuffle(nil) -> nil
   shuffle(add(z0, z1)) -> add(z0, shuffle(reverse(z1)))
Tuples:
   APP(nil, z0) -> c
   APP(add(z0, z1), z2) -> c1(APP(z1, z2))
   REVERSE(nil) -> c2
   REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1))
   SHUFFLE(nil) -> c4
   SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1))
S tuples:
   APP(nil, z0) -> c
   APP(add(z0, z1), z2) -> c1(APP(z1, z2))
   REVERSE(nil) -> c2
   REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1))
   SHUFFLE(nil) -> c4
   SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1))
K tuples:none
Defined Rule Symbols:   app_2, reverse_1, shuffle_1

Defined Pair Symbols:   APP_2, REVERSE_1, SHUFFLE_1

Compound Symbols:   c, c1_1, c2, c3_2, c4, c5_2


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

(3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
Removed 3 trailing nodes:
   SHUFFLE(nil) -> c4
   REVERSE(nil) -> c2
   APP(nil, z0) -> c

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

(4)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   app(nil, z0) -> z0
   app(add(z0, z1), z2) -> add(z0, app(z1, z2))
   reverse(nil) -> nil
   reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil))
   shuffle(nil) -> nil
   shuffle(add(z0, z1)) -> add(z0, shuffle(reverse(z1)))
Tuples:
   APP(add(z0, z1), z2) -> c1(APP(z1, z2))
   REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1))
   SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1))
S tuples:
   APP(add(z0, z1), z2) -> c1(APP(z1, z2))
   REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1))
   SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1))
K tuples:none
Defined Rule Symbols:   app_2, reverse_1, shuffle_1

Defined Pair Symbols:   APP_2, REVERSE_1, SHUFFLE_1

Compound Symbols:   c1_1, c3_2, c5_2


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

(5) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
The following rules are not usable and were removed:
   shuffle(nil) -> nil
   shuffle(add(z0, z1)) -> add(z0, shuffle(reverse(z1)))

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

(6)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   reverse(nil) -> nil
   reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil))
   app(nil, z0) -> z0
   app(add(z0, z1), z2) -> add(z0, app(z1, z2))
Tuples:
   APP(add(z0, z1), z2) -> c1(APP(z1, z2))
   REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1))
   SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1))
S tuples:
   APP(add(z0, z1), z2) -> c1(APP(z1, z2))
   REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1))
   SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1))
K tuples:none
Defined Rule Symbols:   reverse_1, app_2

Defined Pair Symbols:   APP_2, REVERSE_1, SHUFFLE_1

Compound Symbols:   c1_1, c3_2, c5_2


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

(7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1))
We considered the (Usable) Rules:
   reverse(nil) -> nil
   app(add(z0, z1), z2) -> add(z0, app(z1, z2))
   app(nil, z0) -> z0
   reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil))
And the Tuples:
   APP(add(z0, z1), z2) -> c1(APP(z1, z2))
   REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1))
   SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(APP(x_1, x_2)) = 0
   POL(REVERSE(x_1)) = 0
   POL(SHUFFLE(x_1)) = x_1
   POL(add(x_1, x_2)) = [1] + x_1 + x_2
   POL(app(x_1, x_2)) = x_1 + x_2
   POL(c1(x_1)) = x_1
   POL(c3(x_1, x_2)) = x_1 + x_2
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(nil) = 0
   POL(reverse(x_1)) = x_1

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

(8)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   reverse(nil) -> nil
   reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil))
   app(nil, z0) -> z0
   app(add(z0, z1), z2) -> add(z0, app(z1, z2))
Tuples:
   APP(add(z0, z1), z2) -> c1(APP(z1, z2))
   REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1))
   SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1))
S tuples:
   APP(add(z0, z1), z2) -> c1(APP(z1, z2))
   REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1))
K tuples:
   SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1))
Defined Rule Symbols:   reverse_1, app_2

Defined Pair Symbols:   APP_2, REVERSE_1, SHUFFLE_1

Compound Symbols:   c1_1, c3_2, c5_2


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

(9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1))
We considered the (Usable) Rules:
   reverse(nil) -> nil
   app(add(z0, z1), z2) -> add(z0, app(z1, z2))
   app(nil, z0) -> z0
   reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil))
And the Tuples:
   APP(add(z0, z1), z2) -> c1(APP(z1, z2))
   REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1))
   SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(APP(x_1, x_2)) = 0
   POL(REVERSE(x_1)) = x_1
   POL(SHUFFLE(x_1)) = x_1^2
   POL(add(x_1, x_2)) = [1] + x_2
   POL(app(x_1, x_2)) = x_1 + x_2
   POL(c1(x_1)) = x_1
   POL(c3(x_1, x_2)) = x_1 + x_2
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(nil) = 0
   POL(reverse(x_1)) = x_1

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

(10)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   reverse(nil) -> nil
   reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil))
   app(nil, z0) -> z0
   app(add(z0, z1), z2) -> add(z0, app(z1, z2))
Tuples:
   APP(add(z0, z1), z2) -> c1(APP(z1, z2))
   REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1))
   SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1))
S tuples:
   APP(add(z0, z1), z2) -> c1(APP(z1, z2))
K tuples:
   SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1))
   REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1))
Defined Rule Symbols:   reverse_1, app_2

Defined Pair Symbols:   APP_2, REVERSE_1, SHUFFLE_1

Compound Symbols:   c1_1, c3_2, c5_2


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

(11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^3)))
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
   APP(add(z0, z1), z2) -> c1(APP(z1, z2))
We considered the (Usable) Rules:
   reverse(nil) -> nil
   app(add(z0, z1), z2) -> add(z0, app(z1, z2))
   app(nil, z0) -> z0
   reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil))
And the Tuples:
   APP(add(z0, z1), z2) -> c1(APP(z1, z2))
   REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1))
   SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1))
The order we found is given by the following interpretation:

Polynomial interpretation :

   POL(APP(x_1, x_2)) = x_1 + x_1*x_2^2
   POL(REVERSE(x_1)) = x_1^2
   POL(SHUFFLE(x_1)) = x_1^3
   POL(add(x_1, x_2)) = [1] + x_2
   POL(app(x_1, x_2)) = x_1 + x_2
   POL(c1(x_1)) = x_1
   POL(c3(x_1, x_2)) = x_1 + x_2
   POL(c5(x_1, x_2)) = x_1 + x_2
   POL(nil) = 0
   POL(reverse(x_1)) = x_1

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

(12)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   reverse(nil) -> nil
   reverse(add(z0, z1)) -> app(reverse(z1), add(z0, nil))
   app(nil, z0) -> z0
   app(add(z0, z1), z2) -> add(z0, app(z1, z2))
Tuples:
   APP(add(z0, z1), z2) -> c1(APP(z1, z2))
   REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1))
   SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1))
S tuples:none
K tuples:
   SHUFFLE(add(z0, z1)) -> c5(SHUFFLE(reverse(z1)), REVERSE(z1))
   REVERSE(add(z0, z1)) -> c3(APP(reverse(z1), add(z0, nil)), REVERSE(z1))
   APP(add(z0, z1), z2) -> c1(APP(z1, z2))
Defined Rule Symbols:   reverse_1, app_2

Defined Pair Symbols:   APP_2, REVERSE_1, SHUFFLE_1

Compound Symbols:   c1_1, c3_2, c5_2


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

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

(14)
BOUNDS(1, 1)

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

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

(16)
Obligation:
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF).


The TRS R consists of the following rules:

   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   reverse(nil) -> nil
   reverse(add(n, x)) -> app(reverse(x), add(n, nil))
   shuffle(nil) -> nil
   shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))

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

(17) SlicingProof (LOWER BOUND(ID))
Sliced the following arguments:
add/0

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

(18)
Obligation:
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF).


The TRS R consists of the following rules:

   app(nil, y) -> y
   app(add(x), y) -> add(app(x, y))
   reverse(nil) -> nil
   reverse(add(x)) -> app(reverse(x), add(nil))
   shuffle(nil) -> nil
   shuffle(add(x)) -> add(shuffle(reverse(x)))

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

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

(20)
Obligation:
Innermost TRS:
Rules:
app(nil, y) -> y
app(add(x), y) -> add(app(x, y))
reverse(nil) -> nil
reverse(add(x)) -> app(reverse(x), add(nil))
shuffle(nil) -> nil
shuffle(add(x)) -> add(shuffle(reverse(x)))

Types:
app :: nil:add -> nil:add -> nil:add
nil :: nil:add
add :: nil:add -> nil:add
reverse :: nil:add -> nil:add
shuffle :: nil:add -> nil:add
hole_nil:add1_0 :: nil:add
gen_nil:add2_0 :: Nat -> nil:add

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

(21) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
app, reverse, shuffle

They will be analysed ascendingly in the following order:
app < reverse
reverse < shuffle

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

(22)
Obligation:
Innermost TRS:
Rules:
app(nil, y) -> y
app(add(x), y) -> add(app(x, y))
reverse(nil) -> nil
reverse(add(x)) -> app(reverse(x), add(nil))
shuffle(nil) -> nil
shuffle(add(x)) -> add(shuffle(reverse(x)))

Types:
app :: nil:add -> nil:add -> nil:add
nil :: nil:add
add :: nil:add -> nil:add
reverse :: nil:add -> nil:add
shuffle :: nil:add -> nil:add
hole_nil:add1_0 :: nil:add
gen_nil:add2_0 :: Nat -> nil:add


Generator Equations:
gen_nil:add2_0(0) <=> nil
gen_nil:add2_0(+(x, 1)) <=> add(gen_nil:add2_0(x))


The following defined symbols remain to be analysed:
app, reverse, shuffle

They will be analysed ascendingly in the following order:
app < reverse
reverse < shuffle

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

(23) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
app(gen_nil:add2_0(n4_0), gen_nil:add2_0(b)) -> gen_nil:add2_0(+(n4_0, b)), rt in Omega(1 + n4_0)

Induction Base:
app(gen_nil:add2_0(0), gen_nil:add2_0(b)) ->_R^Omega(1)
gen_nil:add2_0(b)

Induction Step:
app(gen_nil:add2_0(+(n4_0, 1)), gen_nil:add2_0(b)) ->_R^Omega(1)
add(app(gen_nil:add2_0(n4_0), gen_nil:add2_0(b))) ->_IH
add(gen_nil:add2_0(+(b, c5_0)))

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

(24)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
app(nil, y) -> y
app(add(x), y) -> add(app(x, y))
reverse(nil) -> nil
reverse(add(x)) -> app(reverse(x), add(nil))
shuffle(nil) -> nil
shuffle(add(x)) -> add(shuffle(reverse(x)))

Types:
app :: nil:add -> nil:add -> nil:add
nil :: nil:add
add :: nil:add -> nil:add
reverse :: nil:add -> nil:add
shuffle :: nil:add -> nil:add
hole_nil:add1_0 :: nil:add
gen_nil:add2_0 :: Nat -> nil:add


Generator Equations:
gen_nil:add2_0(0) <=> nil
gen_nil:add2_0(+(x, 1)) <=> add(gen_nil:add2_0(x))


The following defined symbols remain to be analysed:
app, reverse, shuffle

They will be analysed ascendingly in the following order:
app < reverse
reverse < shuffle

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

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

(27)
BOUNDS(n^1, INF)

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

(28)
Obligation:
Innermost TRS:
Rules:
app(nil, y) -> y
app(add(x), y) -> add(app(x, y))
reverse(nil) -> nil
reverse(add(x)) -> app(reverse(x), add(nil))
shuffle(nil) -> nil
shuffle(add(x)) -> add(shuffle(reverse(x)))

Types:
app :: nil:add -> nil:add -> nil:add
nil :: nil:add
add :: nil:add -> nil:add
reverse :: nil:add -> nil:add
shuffle :: nil:add -> nil:add
hole_nil:add1_0 :: nil:add
gen_nil:add2_0 :: Nat -> nil:add


Lemmas:
app(gen_nil:add2_0(n4_0), gen_nil:add2_0(b)) -> gen_nil:add2_0(+(n4_0, b)), rt in Omega(1 + n4_0)


Generator Equations:
gen_nil:add2_0(0) <=> nil
gen_nil:add2_0(+(x, 1)) <=> add(gen_nil:add2_0(x))


The following defined symbols remain to be analysed:
reverse, shuffle

They will be analysed ascendingly in the following order:
reverse < shuffle

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

(29) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
reverse(gen_nil:add2_0(n487_0)) -> gen_nil:add2_0(n487_0), rt in Omega(1 + n487_0 + n487_0^2)

Induction Base:
reverse(gen_nil:add2_0(0)) ->_R^Omega(1)
nil

Induction Step:
reverse(gen_nil:add2_0(+(n487_0, 1))) ->_R^Omega(1)
app(reverse(gen_nil:add2_0(n487_0)), add(nil)) ->_IH
app(gen_nil:add2_0(c488_0), add(nil)) ->_L^Omega(1 + n487_0)
gen_nil:add2_0(+(n487_0, +(0, 1)))

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

(30)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
app(nil, y) -> y
app(add(x), y) -> add(app(x, y))
reverse(nil) -> nil
reverse(add(x)) -> app(reverse(x), add(nil))
shuffle(nil) -> nil
shuffle(add(x)) -> add(shuffle(reverse(x)))

Types:
app :: nil:add -> nil:add -> nil:add
nil :: nil:add
add :: nil:add -> nil:add
reverse :: nil:add -> nil:add
shuffle :: nil:add -> nil:add
hole_nil:add1_0 :: nil:add
gen_nil:add2_0 :: Nat -> nil:add


Lemmas:
app(gen_nil:add2_0(n4_0), gen_nil:add2_0(b)) -> gen_nil:add2_0(+(n4_0, b)), rt in Omega(1 + n4_0)


Generator Equations:
gen_nil:add2_0(0) <=> nil
gen_nil:add2_0(+(x, 1)) <=> add(gen_nil:add2_0(x))


The following defined symbols remain to be analysed:
reverse, shuffle

They will be analysed ascendingly in the following order:
reverse < shuffle

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

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

(33)
BOUNDS(n^2, INF)

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

(34)
Obligation:
Innermost TRS:
Rules:
app(nil, y) -> y
app(add(x), y) -> add(app(x, y))
reverse(nil) -> nil
reverse(add(x)) -> app(reverse(x), add(nil))
shuffle(nil) -> nil
shuffle(add(x)) -> add(shuffle(reverse(x)))

Types:
app :: nil:add -> nil:add -> nil:add
nil :: nil:add
add :: nil:add -> nil:add
reverse :: nil:add -> nil:add
shuffle :: nil:add -> nil:add
hole_nil:add1_0 :: nil:add
gen_nil:add2_0 :: Nat -> nil:add


Lemmas:
app(gen_nil:add2_0(n4_0), gen_nil:add2_0(b)) -> gen_nil:add2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
reverse(gen_nil:add2_0(n487_0)) -> gen_nil:add2_0(n487_0), rt in Omega(1 + n487_0 + n487_0^2)


Generator Equations:
gen_nil:add2_0(0) <=> nil
gen_nil:add2_0(+(x, 1)) <=> add(gen_nil:add2_0(x))


The following defined symbols remain to be analysed:
shuffle
----------------------------------------

(35) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
shuffle(gen_nil:add2_0(n701_0)) -> gen_nil:add2_0(n701_0), rt in Omega(1 + n701_0 + n701_0^2 + n701_0^3)

Induction Base:
shuffle(gen_nil:add2_0(0)) ->_R^Omega(1)
nil

Induction Step:
shuffle(gen_nil:add2_0(+(n701_0, 1))) ->_R^Omega(1)
add(shuffle(reverse(gen_nil:add2_0(n701_0)))) ->_L^Omega(1 + n701_0 + n701_0^2)
add(shuffle(gen_nil:add2_0(n701_0))) ->_IH
add(gen_nil:add2_0(c702_0))

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

(36)
Obligation:
Proved the lower bound n^3 for the following obligation:

Innermost TRS:
Rules:
app(nil, y) -> y
app(add(x), y) -> add(app(x, y))
reverse(nil) -> nil
reverse(add(x)) -> app(reverse(x), add(nil))
shuffle(nil) -> nil
shuffle(add(x)) -> add(shuffle(reverse(x)))

Types:
app :: nil:add -> nil:add -> nil:add
nil :: nil:add
add :: nil:add -> nil:add
reverse :: nil:add -> nil:add
shuffle :: nil:add -> nil:add
hole_nil:add1_0 :: nil:add
gen_nil:add2_0 :: Nat -> nil:add


Lemmas:
app(gen_nil:add2_0(n4_0), gen_nil:add2_0(b)) -> gen_nil:add2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
reverse(gen_nil:add2_0(n487_0)) -> gen_nil:add2_0(n487_0), rt in Omega(1 + n487_0 + n487_0^2)


Generator Equations:
gen_nil:add2_0(0) <=> nil
gen_nil:add2_0(+(x, 1)) <=> add(gen_nil:add2_0(x))


The following defined symbols remain to be analysed:
shuffle
----------------------------------------

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

(38)
BOUNDS(n^3, INF)