### (0) Obligation:

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

The TRS R consists of the following rules:

concat(leaf, Y) → Y
concat(cons(U, V), Y) → cons(U, concat(V, Y))
lessleaves(X, leaf) → false
lessleaves(leaf, cons(W, Z)) → true
lessleaves(cons(U, V), cons(W, Z)) → lessleaves(concat(U, V), concat(W, Z))

Rewrite Strategy: FULL

### (1) RcToIrcProof (BOTH BOUNDS(ID, ID) transformation)

Converted rc-obligation to irc-obligation.

As the TRS is a non-duplicating overlay system, we have rc = irc.

### (2) Obligation:

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

The TRS R consists of the following rules:

concat(leaf, Y) → Y
concat(cons(U, V), Y) → cons(U, concat(V, Y))
lessleaves(X, leaf) → false
lessleaves(leaf, cons(W, Z)) → true
lessleaves(cons(U, V), cons(W, Z)) → lessleaves(concat(U, V), concat(W, Z))

Rewrite Strategy: INNERMOST

### (3) CpxTrsMatchBoundsTAProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 2.

The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by:
final states : [1, 2]
transitions:
leaf0() → 0
cons0(0, 0) → 0
false0() → 0
true0() → 0
concat0(0, 0) → 1
lessleaves0(0, 0) → 2
concat1(0, 0) → 3
cons1(0, 3) → 1
false1() → 2
true1() → 2
concat1(0, 0) → 4
concat1(0, 0) → 5
lessleaves1(4, 5) → 2
cons1(0, 3) → 3
cons1(0, 3) → 4
cons1(0, 3) → 5
concat1(0, 3) → 5
concat1(0, 3) → 4
concat2(0, 3) → 6
concat2(0, 3) → 7
lessleaves2(6, 7) → 2
concat1(0, 3) → 3
0 → 1
0 → 3
0 → 4
0 → 5
3 → 4
3 → 5
3 → 6
3 → 7