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


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

(0) CpxTRS
(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxTRS
(3) SlicingProof [LOWER BOUND(ID), 0 ms]
(4) CpxTRS
(5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) typed CpxTrs
(7) OrderProof [LOWER BOUND(ID), 0 ms]
(8) typed CpxTrs
(9) RewriteLemmaProof [LOWER BOUND(ID), 303 ms]
(10) BEST
    (11) proven lower bound
        (12) LowerBoundPropagationProof [FINISHED, 0 ms]
        (13) BOUNDS(n^1, INF)
    (14) typed CpxTrs
        (15) RewriteLemmaProof [LOWER BOUND(ID), 64 ms]
        (16) typed CpxTrs
        (17) RewriteLemmaProof [LOWER BOUND(ID), 46 ms]
        (18) typed CpxTrs
        (19) RewriteLemmaProof [LOWER BOUND(ID), 38 ms]
        (20) typed CpxTrs
        (21) RewriteLemmaProof [LOWER BOUND(ID), 43 ms]
        (22) typed CpxTrs
        (23) RewriteLemmaProof [LOWER BOUND(ID), 2112 ms]
        (24) typed CpxTrs


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

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


The TRS R consists of the following rules:

   fstsplit(0, x) -> nil
   fstsplit(s(n), nil) -> nil
   fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t))
   sndsplit(0, x) -> x
   sndsplit(s(n), nil) -> nil
   sndsplit(s(n), cons(h, t)) -> sndsplit(n, t)
   empty(nil) -> true
   empty(cons(h, t)) -> false
   leq(0, m) -> true
   leq(s(n), 0) -> false
   leq(s(n), s(m)) -> leq(n, m)
   length(nil) -> 0
   length(cons(h, t)) -> s(length(t))
   app(nil, x) -> x
   app(cons(h, t), x) -> cons(h, app(t, x))
   map_f(pid, nil) -> nil
   map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t))
   head(cons(h, t)) -> h
   tail(cons(h, t)) -> t
   ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1)))
   if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m)
   ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2)))
   if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2)))
   if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m)
   if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(two, head(in_2)), st_2))))
   if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(two, head(in_2)), st_2)), cons(fstsplit(m, app(map_f(two, head(in_2)), st_2)), in_3), st_3, m)
   ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(two, head(in_2))))
   if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m)
   ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3)))
   if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3)))
   if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m)
   if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(three, head(in_3)), st_3))))
   if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(three, head(in_3)), st_3)), m)
   ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(three, head(in_3))))
   if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m)

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

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

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


The TRS R consists of the following rules:

   fstsplit(0', x) -> nil
   fstsplit(s(n), nil) -> nil
   fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t))
   sndsplit(0', x) -> x
   sndsplit(s(n), nil) -> nil
   sndsplit(s(n), cons(h, t)) -> sndsplit(n, t)
   empty(nil) -> true
   empty(cons(h, t)) -> false
   leq(0', m) -> true
   leq(s(n), 0') -> false
   leq(s(n), s(m)) -> leq(n, m)
   length(nil) -> 0'
   length(cons(h, t)) -> s(length(t))
   app(nil, x) -> x
   app(cons(h, t), x) -> cons(h, app(t, x))
   map_f(pid, nil) -> nil
   map_f(pid, cons(h, t)) -> app(f(pid, h), map_f(pid, t))
   head(cons(h, t)) -> h
   tail(cons(h, t)) -> t
   ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1)))
   if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m)
   ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2)))
   if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2)))
   if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m)
   if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(two, head(in_2)), st_2))))
   if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(two, head(in_2)), st_2)), cons(fstsplit(m, app(map_f(two, head(in_2)), st_2)), in_3), st_3, m)
   ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(two, head(in_2))))
   if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m)
   ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3)))
   if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3)))
   if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m)
   if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(three, head(in_3)), st_3))))
   if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(three, head(in_3)), st_3)), m)
   ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(three, head(in_3))))
   if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m)

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

(3) SlicingProof (LOWER BOUND(ID))
Sliced the following arguments:
map_f/0
f/0
f/1

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

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


The TRS R consists of the following rules:

   fstsplit(0', x) -> nil
   fstsplit(s(n), nil) -> nil
   fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t))
   sndsplit(0', x) -> x
   sndsplit(s(n), nil) -> nil
   sndsplit(s(n), cons(h, t)) -> sndsplit(n, t)
   empty(nil) -> true
   empty(cons(h, t)) -> false
   leq(0', m) -> true
   leq(s(n), 0') -> false
   leq(s(n), s(m)) -> leq(n, m)
   length(nil) -> 0'
   length(cons(h, t)) -> s(length(t))
   app(nil, x) -> x
   app(cons(h, t), x) -> cons(h, app(t, x))
   map_f(nil) -> nil
   map_f(cons(h, t)) -> app(f, map_f(t))
   head(cons(h, t)) -> h
   tail(cons(h, t)) -> t
   ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1)))
   if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m)
   ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2)))
   if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2)))
   if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m)
   if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2))))
   if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m)
   ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2))))
   if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m)
   ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3)))
   if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3)))
   if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m)
   if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3))))
   if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m)
   ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3))))
   if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m)

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

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

(6)
Obligation:
TRS:
Rules:
fstsplit(0', x) -> nil
fstsplit(s(n), nil) -> nil
fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t))
sndsplit(0', x) -> x
sndsplit(s(n), nil) -> nil
sndsplit(s(n), cons(h, t)) -> sndsplit(n, t)
empty(nil) -> true
empty(cons(h, t)) -> false
leq(0', m) -> true
leq(s(n), 0') -> false
leq(s(n), s(m)) -> leq(n, m)
length(nil) -> 0'
length(cons(h, t)) -> s(length(t))
app(nil, x) -> x
app(cons(h, t), x) -> cons(h, app(t, x))
map_f(nil) -> nil
map_f(cons(h, t)) -> app(f, map_f(t))
head(cons(h, t)) -> h
tail(cons(h, t)) -> t
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1)))
if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2)))
if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2)))
if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m)
if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2))))
if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2))))
if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3)))
if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3)))
if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m)
if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3))))
if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3))))
if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m)

Types:
fstsplit :: 0':s -> nil:cons:f -> nil:cons:f
0' :: 0':s
nil :: nil:cons:f
s :: 0':s -> 0':s
cons :: nil:cons:f -> nil:cons:f -> nil:cons:f
sndsplit :: 0':s -> nil:cons:f -> nil:cons:f
empty :: nil:cons:f -> true:false
true :: true:false
false :: true:false
leq :: 0':s -> 0':s -> true:false
length :: nil:cons:f -> 0':s
app :: nil:cons:f -> nil:cons:f -> nil:cons:f
map_f :: nil:cons:f -> nil:cons:f
f :: nil:cons:f
head :: nil:cons:f -> nil:cons:f
tail :: nil:cons:f -> nil:cons:f
ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
hole_nil:cons:f1_0 :: nil:cons:f
hole_0':s2_0 :: 0':s
hole_true:false3_0 :: true:false
hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
gen_nil:cons:f5_0 :: Nat -> nil:cons:f
gen_0':s6_0 :: Nat -> 0':s

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

(7) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
fstsplit, sndsplit, leq, length, app, map_f, ring

They will be analysed ascendingly in the following order:
fstsplit < ring
sndsplit < ring
leq < ring
length < ring
app < map_f
app < ring
map_f < ring

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

(8)
Obligation:
TRS:
Rules:
fstsplit(0', x) -> nil
fstsplit(s(n), nil) -> nil
fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t))
sndsplit(0', x) -> x
sndsplit(s(n), nil) -> nil
sndsplit(s(n), cons(h, t)) -> sndsplit(n, t)
empty(nil) -> true
empty(cons(h, t)) -> false
leq(0', m) -> true
leq(s(n), 0') -> false
leq(s(n), s(m)) -> leq(n, m)
length(nil) -> 0'
length(cons(h, t)) -> s(length(t))
app(nil, x) -> x
app(cons(h, t), x) -> cons(h, app(t, x))
map_f(nil) -> nil
map_f(cons(h, t)) -> app(f, map_f(t))
head(cons(h, t)) -> h
tail(cons(h, t)) -> t
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1)))
if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2)))
if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2)))
if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m)
if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2))))
if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2))))
if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3)))
if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3)))
if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m)
if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3))))
if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3))))
if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m)

Types:
fstsplit :: 0':s -> nil:cons:f -> nil:cons:f
0' :: 0':s
nil :: nil:cons:f
s :: 0':s -> 0':s
cons :: nil:cons:f -> nil:cons:f -> nil:cons:f
sndsplit :: 0':s -> nil:cons:f -> nil:cons:f
empty :: nil:cons:f -> true:false
true :: true:false
false :: true:false
leq :: 0':s -> 0':s -> true:false
length :: nil:cons:f -> 0':s
app :: nil:cons:f -> nil:cons:f -> nil:cons:f
map_f :: nil:cons:f -> nil:cons:f
f :: nil:cons:f
head :: nil:cons:f -> nil:cons:f
tail :: nil:cons:f -> nil:cons:f
ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
hole_nil:cons:f1_0 :: nil:cons:f
hole_0':s2_0 :: 0':s
hole_true:false3_0 :: true:false
hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
gen_nil:cons:f5_0 :: Nat -> nil:cons:f
gen_0':s6_0 :: Nat -> 0':s


Generator Equations:
gen_nil:cons:f5_0(0) <=> nil
gen_nil:cons:f5_0(+(x, 1)) <=> cons(nil, gen_nil:cons:f5_0(x))
gen_0':s6_0(0) <=> 0'
gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x))


The following defined symbols remain to be analysed:
fstsplit, sndsplit, leq, length, app, map_f, ring

They will be analysed ascendingly in the following order:
fstsplit < ring
sndsplit < ring
leq < ring
length < ring
app < map_f
app < ring
map_f < ring

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

(9) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
fstsplit(gen_0':s6_0(n8_0), gen_nil:cons:f5_0(n8_0)) -> gen_nil:cons:f5_0(n8_0), rt in Omega(1 + n8_0)

Induction Base:
fstsplit(gen_0':s6_0(0), gen_nil:cons:f5_0(0)) ->_R^Omega(1)
nil

Induction Step:
fstsplit(gen_0':s6_0(+(n8_0, 1)), gen_nil:cons:f5_0(+(n8_0, 1))) ->_R^Omega(1)
cons(nil, fstsplit(gen_0':s6_0(n8_0), gen_nil:cons:f5_0(n8_0))) ->_IH
cons(nil, gen_nil:cons:f5_0(c9_0))

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

(10)
Complex Obligation (BEST)

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

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

TRS:
Rules:
fstsplit(0', x) -> nil
fstsplit(s(n), nil) -> nil
fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t))
sndsplit(0', x) -> x
sndsplit(s(n), nil) -> nil
sndsplit(s(n), cons(h, t)) -> sndsplit(n, t)
empty(nil) -> true
empty(cons(h, t)) -> false
leq(0', m) -> true
leq(s(n), 0') -> false
leq(s(n), s(m)) -> leq(n, m)
length(nil) -> 0'
length(cons(h, t)) -> s(length(t))
app(nil, x) -> x
app(cons(h, t), x) -> cons(h, app(t, x))
map_f(nil) -> nil
map_f(cons(h, t)) -> app(f, map_f(t))
head(cons(h, t)) -> h
tail(cons(h, t)) -> t
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1)))
if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2)))
if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2)))
if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m)
if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2))))
if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2))))
if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3)))
if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3)))
if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m)
if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3))))
if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3))))
if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m)

Types:
fstsplit :: 0':s -> nil:cons:f -> nil:cons:f
0' :: 0':s
nil :: nil:cons:f
s :: 0':s -> 0':s
cons :: nil:cons:f -> nil:cons:f -> nil:cons:f
sndsplit :: 0':s -> nil:cons:f -> nil:cons:f
empty :: nil:cons:f -> true:false
true :: true:false
false :: true:false
leq :: 0':s -> 0':s -> true:false
length :: nil:cons:f -> 0':s
app :: nil:cons:f -> nil:cons:f -> nil:cons:f
map_f :: nil:cons:f -> nil:cons:f
f :: nil:cons:f
head :: nil:cons:f -> nil:cons:f
tail :: nil:cons:f -> nil:cons:f
ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
hole_nil:cons:f1_0 :: nil:cons:f
hole_0':s2_0 :: 0':s
hole_true:false3_0 :: true:false
hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
gen_nil:cons:f5_0 :: Nat -> nil:cons:f
gen_0':s6_0 :: Nat -> 0':s


Generator Equations:
gen_nil:cons:f5_0(0) <=> nil
gen_nil:cons:f5_0(+(x, 1)) <=> cons(nil, gen_nil:cons:f5_0(x))
gen_0':s6_0(0) <=> 0'
gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x))


The following defined symbols remain to be analysed:
fstsplit, sndsplit, leq, length, app, map_f, ring

They will be analysed ascendingly in the following order:
fstsplit < ring
sndsplit < ring
leq < ring
length < ring
app < map_f
app < ring
map_f < ring

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

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

(13)
BOUNDS(n^1, INF)

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

(14)
Obligation:
TRS:
Rules:
fstsplit(0', x) -> nil
fstsplit(s(n), nil) -> nil
fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t))
sndsplit(0', x) -> x
sndsplit(s(n), nil) -> nil
sndsplit(s(n), cons(h, t)) -> sndsplit(n, t)
empty(nil) -> true
empty(cons(h, t)) -> false
leq(0', m) -> true
leq(s(n), 0') -> false
leq(s(n), s(m)) -> leq(n, m)
length(nil) -> 0'
length(cons(h, t)) -> s(length(t))
app(nil, x) -> x
app(cons(h, t), x) -> cons(h, app(t, x))
map_f(nil) -> nil
map_f(cons(h, t)) -> app(f, map_f(t))
head(cons(h, t)) -> h
tail(cons(h, t)) -> t
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1)))
if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2)))
if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2)))
if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m)
if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2))))
if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2))))
if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3)))
if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3)))
if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m)
if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3))))
if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3))))
if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m)

Types:
fstsplit :: 0':s -> nil:cons:f -> nil:cons:f
0' :: 0':s
nil :: nil:cons:f
s :: 0':s -> 0':s
cons :: nil:cons:f -> nil:cons:f -> nil:cons:f
sndsplit :: 0':s -> nil:cons:f -> nil:cons:f
empty :: nil:cons:f -> true:false
true :: true:false
false :: true:false
leq :: 0':s -> 0':s -> true:false
length :: nil:cons:f -> 0':s
app :: nil:cons:f -> nil:cons:f -> nil:cons:f
map_f :: nil:cons:f -> nil:cons:f
f :: nil:cons:f
head :: nil:cons:f -> nil:cons:f
tail :: nil:cons:f -> nil:cons:f
ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
hole_nil:cons:f1_0 :: nil:cons:f
hole_0':s2_0 :: 0':s
hole_true:false3_0 :: true:false
hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
gen_nil:cons:f5_0 :: Nat -> nil:cons:f
gen_0':s6_0 :: Nat -> 0':s


Lemmas:
fstsplit(gen_0':s6_0(n8_0), gen_nil:cons:f5_0(n8_0)) -> gen_nil:cons:f5_0(n8_0), rt in Omega(1 + n8_0)


Generator Equations:
gen_nil:cons:f5_0(0) <=> nil
gen_nil:cons:f5_0(+(x, 1)) <=> cons(nil, gen_nil:cons:f5_0(x))
gen_0':s6_0(0) <=> 0'
gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x))


The following defined symbols remain to be analysed:
sndsplit, leq, length, app, map_f, ring

They will be analysed ascendingly in the following order:
sndsplit < ring
leq < ring
length < ring
app < map_f
app < ring
map_f < ring

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

(15) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
sndsplit(gen_0':s6_0(n638_0), gen_nil:cons:f5_0(n638_0)) -> gen_nil:cons:f5_0(0), rt in Omega(1 + n638_0)

Induction Base:
sndsplit(gen_0':s6_0(0), gen_nil:cons:f5_0(0)) ->_R^Omega(1)
gen_nil:cons:f5_0(0)

Induction Step:
sndsplit(gen_0':s6_0(+(n638_0, 1)), gen_nil:cons:f5_0(+(n638_0, 1))) ->_R^Omega(1)
sndsplit(gen_0':s6_0(n638_0), gen_nil:cons:f5_0(n638_0)) ->_IH
gen_nil:cons:f5_0(0)

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

(16)
Obligation:
TRS:
Rules:
fstsplit(0', x) -> nil
fstsplit(s(n), nil) -> nil
fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t))
sndsplit(0', x) -> x
sndsplit(s(n), nil) -> nil
sndsplit(s(n), cons(h, t)) -> sndsplit(n, t)
empty(nil) -> true
empty(cons(h, t)) -> false
leq(0', m) -> true
leq(s(n), 0') -> false
leq(s(n), s(m)) -> leq(n, m)
length(nil) -> 0'
length(cons(h, t)) -> s(length(t))
app(nil, x) -> x
app(cons(h, t), x) -> cons(h, app(t, x))
map_f(nil) -> nil
map_f(cons(h, t)) -> app(f, map_f(t))
head(cons(h, t)) -> h
tail(cons(h, t)) -> t
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1)))
if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2)))
if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2)))
if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m)
if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2))))
if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2))))
if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3)))
if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3)))
if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m)
if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3))))
if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3))))
if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m)

Types:
fstsplit :: 0':s -> nil:cons:f -> nil:cons:f
0' :: 0':s
nil :: nil:cons:f
s :: 0':s -> 0':s
cons :: nil:cons:f -> nil:cons:f -> nil:cons:f
sndsplit :: 0':s -> nil:cons:f -> nil:cons:f
empty :: nil:cons:f -> true:false
true :: true:false
false :: true:false
leq :: 0':s -> 0':s -> true:false
length :: nil:cons:f -> 0':s
app :: nil:cons:f -> nil:cons:f -> nil:cons:f
map_f :: nil:cons:f -> nil:cons:f
f :: nil:cons:f
head :: nil:cons:f -> nil:cons:f
tail :: nil:cons:f -> nil:cons:f
ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
hole_nil:cons:f1_0 :: nil:cons:f
hole_0':s2_0 :: 0':s
hole_true:false3_0 :: true:false
hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
gen_nil:cons:f5_0 :: Nat -> nil:cons:f
gen_0':s6_0 :: Nat -> 0':s


Lemmas:
fstsplit(gen_0':s6_0(n8_0), gen_nil:cons:f5_0(n8_0)) -> gen_nil:cons:f5_0(n8_0), rt in Omega(1 + n8_0)
sndsplit(gen_0':s6_0(n638_0), gen_nil:cons:f5_0(n638_0)) -> gen_nil:cons:f5_0(0), rt in Omega(1 + n638_0)


Generator Equations:
gen_nil:cons:f5_0(0) <=> nil
gen_nil:cons:f5_0(+(x, 1)) <=> cons(nil, gen_nil:cons:f5_0(x))
gen_0':s6_0(0) <=> 0'
gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x))


The following defined symbols remain to be analysed:
leq, length, app, map_f, ring

They will be analysed ascendingly in the following order:
leq < ring
length < ring
app < map_f
app < ring
map_f < ring

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

(17) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
leq(gen_0':s6_0(n1339_0), gen_0':s6_0(n1339_0)) -> true, rt in Omega(1 + n1339_0)

Induction Base:
leq(gen_0':s6_0(0), gen_0':s6_0(0)) ->_R^Omega(1)
true

Induction Step:
leq(gen_0':s6_0(+(n1339_0, 1)), gen_0':s6_0(+(n1339_0, 1))) ->_R^Omega(1)
leq(gen_0':s6_0(n1339_0), gen_0':s6_0(n1339_0)) ->_IH
true

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

(18)
Obligation:
TRS:
Rules:
fstsplit(0', x) -> nil
fstsplit(s(n), nil) -> nil
fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t))
sndsplit(0', x) -> x
sndsplit(s(n), nil) -> nil
sndsplit(s(n), cons(h, t)) -> sndsplit(n, t)
empty(nil) -> true
empty(cons(h, t)) -> false
leq(0', m) -> true
leq(s(n), 0') -> false
leq(s(n), s(m)) -> leq(n, m)
length(nil) -> 0'
length(cons(h, t)) -> s(length(t))
app(nil, x) -> x
app(cons(h, t), x) -> cons(h, app(t, x))
map_f(nil) -> nil
map_f(cons(h, t)) -> app(f, map_f(t))
head(cons(h, t)) -> h
tail(cons(h, t)) -> t
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1)))
if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2)))
if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2)))
if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m)
if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2))))
if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2))))
if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3)))
if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3)))
if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m)
if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3))))
if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3))))
if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m)

Types:
fstsplit :: 0':s -> nil:cons:f -> nil:cons:f
0' :: 0':s
nil :: nil:cons:f
s :: 0':s -> 0':s
cons :: nil:cons:f -> nil:cons:f -> nil:cons:f
sndsplit :: 0':s -> nil:cons:f -> nil:cons:f
empty :: nil:cons:f -> true:false
true :: true:false
false :: true:false
leq :: 0':s -> 0':s -> true:false
length :: nil:cons:f -> 0':s
app :: nil:cons:f -> nil:cons:f -> nil:cons:f
map_f :: nil:cons:f -> nil:cons:f
f :: nil:cons:f
head :: nil:cons:f -> nil:cons:f
tail :: nil:cons:f -> nil:cons:f
ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
hole_nil:cons:f1_0 :: nil:cons:f
hole_0':s2_0 :: 0':s
hole_true:false3_0 :: true:false
hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
gen_nil:cons:f5_0 :: Nat -> nil:cons:f
gen_0':s6_0 :: Nat -> 0':s


Lemmas:
fstsplit(gen_0':s6_0(n8_0), gen_nil:cons:f5_0(n8_0)) -> gen_nil:cons:f5_0(n8_0), rt in Omega(1 + n8_0)
sndsplit(gen_0':s6_0(n638_0), gen_nil:cons:f5_0(n638_0)) -> gen_nil:cons:f5_0(0), rt in Omega(1 + n638_0)
leq(gen_0':s6_0(n1339_0), gen_0':s6_0(n1339_0)) -> true, rt in Omega(1 + n1339_0)


Generator Equations:
gen_nil:cons:f5_0(0) <=> nil
gen_nil:cons:f5_0(+(x, 1)) <=> cons(nil, gen_nil:cons:f5_0(x))
gen_0':s6_0(0) <=> 0'
gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x))


The following defined symbols remain to be analysed:
length, app, map_f, ring

They will be analysed ascendingly in the following order:
length < ring
app < map_f
app < ring
map_f < ring

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

(19) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
length(gen_nil:cons:f5_0(n1752_0)) -> gen_0':s6_0(n1752_0), rt in Omega(1 + n1752_0)

Induction Base:
length(gen_nil:cons:f5_0(0)) ->_R^Omega(1)
0'

Induction Step:
length(gen_nil:cons:f5_0(+(n1752_0, 1))) ->_R^Omega(1)
s(length(gen_nil:cons:f5_0(n1752_0))) ->_IH
s(gen_0':s6_0(c1753_0))

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

(20)
Obligation:
TRS:
Rules:
fstsplit(0', x) -> nil
fstsplit(s(n), nil) -> nil
fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t))
sndsplit(0', x) -> x
sndsplit(s(n), nil) -> nil
sndsplit(s(n), cons(h, t)) -> sndsplit(n, t)
empty(nil) -> true
empty(cons(h, t)) -> false
leq(0', m) -> true
leq(s(n), 0') -> false
leq(s(n), s(m)) -> leq(n, m)
length(nil) -> 0'
length(cons(h, t)) -> s(length(t))
app(nil, x) -> x
app(cons(h, t), x) -> cons(h, app(t, x))
map_f(nil) -> nil
map_f(cons(h, t)) -> app(f, map_f(t))
head(cons(h, t)) -> h
tail(cons(h, t)) -> t
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1)))
if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2)))
if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2)))
if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m)
if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2))))
if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2))))
if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3)))
if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3)))
if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m)
if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3))))
if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3))))
if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m)

Types:
fstsplit :: 0':s -> nil:cons:f -> nil:cons:f
0' :: 0':s
nil :: nil:cons:f
s :: 0':s -> 0':s
cons :: nil:cons:f -> nil:cons:f -> nil:cons:f
sndsplit :: 0':s -> nil:cons:f -> nil:cons:f
empty :: nil:cons:f -> true:false
true :: true:false
false :: true:false
leq :: 0':s -> 0':s -> true:false
length :: nil:cons:f -> 0':s
app :: nil:cons:f -> nil:cons:f -> nil:cons:f
map_f :: nil:cons:f -> nil:cons:f
f :: nil:cons:f
head :: nil:cons:f -> nil:cons:f
tail :: nil:cons:f -> nil:cons:f
ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
hole_nil:cons:f1_0 :: nil:cons:f
hole_0':s2_0 :: 0':s
hole_true:false3_0 :: true:false
hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
gen_nil:cons:f5_0 :: Nat -> nil:cons:f
gen_0':s6_0 :: Nat -> 0':s


Lemmas:
fstsplit(gen_0':s6_0(n8_0), gen_nil:cons:f5_0(n8_0)) -> gen_nil:cons:f5_0(n8_0), rt in Omega(1 + n8_0)
sndsplit(gen_0':s6_0(n638_0), gen_nil:cons:f5_0(n638_0)) -> gen_nil:cons:f5_0(0), rt in Omega(1 + n638_0)
leq(gen_0':s6_0(n1339_0), gen_0':s6_0(n1339_0)) -> true, rt in Omega(1 + n1339_0)
length(gen_nil:cons:f5_0(n1752_0)) -> gen_0':s6_0(n1752_0), rt in Omega(1 + n1752_0)


Generator Equations:
gen_nil:cons:f5_0(0) <=> nil
gen_nil:cons:f5_0(+(x, 1)) <=> cons(nil, gen_nil:cons:f5_0(x))
gen_0':s6_0(0) <=> 0'
gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x))


The following defined symbols remain to be analysed:
app, map_f, ring

They will be analysed ascendingly in the following order:
app < map_f
app < ring
map_f < ring

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

(21) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
app(gen_nil:cons:f5_0(n2110_0), gen_nil:cons:f5_0(b)) -> gen_nil:cons:f5_0(+(n2110_0, b)), rt in Omega(1 + n2110_0)

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

Induction Step:
app(gen_nil:cons:f5_0(+(n2110_0, 1)), gen_nil:cons:f5_0(b)) ->_R^Omega(1)
cons(nil, app(gen_nil:cons:f5_0(n2110_0), gen_nil:cons:f5_0(b))) ->_IH
cons(nil, gen_nil:cons:f5_0(+(b, c2111_0)))

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

(22)
Obligation:
TRS:
Rules:
fstsplit(0', x) -> nil
fstsplit(s(n), nil) -> nil
fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t))
sndsplit(0', x) -> x
sndsplit(s(n), nil) -> nil
sndsplit(s(n), cons(h, t)) -> sndsplit(n, t)
empty(nil) -> true
empty(cons(h, t)) -> false
leq(0', m) -> true
leq(s(n), 0') -> false
leq(s(n), s(m)) -> leq(n, m)
length(nil) -> 0'
length(cons(h, t)) -> s(length(t))
app(nil, x) -> x
app(cons(h, t), x) -> cons(h, app(t, x))
map_f(nil) -> nil
map_f(cons(h, t)) -> app(f, map_f(t))
head(cons(h, t)) -> h
tail(cons(h, t)) -> t
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1)))
if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2)))
if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2)))
if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m)
if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2))))
if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2))))
if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3)))
if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3)))
if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m)
if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3))))
if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3))))
if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m)

Types:
fstsplit :: 0':s -> nil:cons:f -> nil:cons:f
0' :: 0':s
nil :: nil:cons:f
s :: 0':s -> 0':s
cons :: nil:cons:f -> nil:cons:f -> nil:cons:f
sndsplit :: 0':s -> nil:cons:f -> nil:cons:f
empty :: nil:cons:f -> true:false
true :: true:false
false :: true:false
leq :: 0':s -> 0':s -> true:false
length :: nil:cons:f -> 0':s
app :: nil:cons:f -> nil:cons:f -> nil:cons:f
map_f :: nil:cons:f -> nil:cons:f
f :: nil:cons:f
head :: nil:cons:f -> nil:cons:f
tail :: nil:cons:f -> nil:cons:f
ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
hole_nil:cons:f1_0 :: nil:cons:f
hole_0':s2_0 :: 0':s
hole_true:false3_0 :: true:false
hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
gen_nil:cons:f5_0 :: Nat -> nil:cons:f
gen_0':s6_0 :: Nat -> 0':s


Lemmas:
fstsplit(gen_0':s6_0(n8_0), gen_nil:cons:f5_0(n8_0)) -> gen_nil:cons:f5_0(n8_0), rt in Omega(1 + n8_0)
sndsplit(gen_0':s6_0(n638_0), gen_nil:cons:f5_0(n638_0)) -> gen_nil:cons:f5_0(0), rt in Omega(1 + n638_0)
leq(gen_0':s6_0(n1339_0), gen_0':s6_0(n1339_0)) -> true, rt in Omega(1 + n1339_0)
length(gen_nil:cons:f5_0(n1752_0)) -> gen_0':s6_0(n1752_0), rt in Omega(1 + n1752_0)
app(gen_nil:cons:f5_0(n2110_0), gen_nil:cons:f5_0(b)) -> gen_nil:cons:f5_0(+(n2110_0, b)), rt in Omega(1 + n2110_0)


Generator Equations:
gen_nil:cons:f5_0(0) <=> nil
gen_nil:cons:f5_0(+(x, 1)) <=> cons(nil, gen_nil:cons:f5_0(x))
gen_0':s6_0(0) <=> 0'
gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x))


The following defined symbols remain to be analysed:
map_f, ring

They will be analysed ascendingly in the following order:
map_f < ring

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

(23) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
map_f(gen_nil:cons:f5_0(+(1, n3259_0))) -> *7_0, rt in Omega(n3259_0)

Induction Base:
map_f(gen_nil:cons:f5_0(+(1, 0)))

Induction Step:
map_f(gen_nil:cons:f5_0(+(1, +(n3259_0, 1)))) ->_R^Omega(1)
app(f, map_f(gen_nil:cons:f5_0(+(1, n3259_0)))) ->_IH
app(f, *7_0)

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

(24)
Obligation:
TRS:
Rules:
fstsplit(0', x) -> nil
fstsplit(s(n), nil) -> nil
fstsplit(s(n), cons(h, t)) -> cons(h, fstsplit(n, t))
sndsplit(0', x) -> x
sndsplit(s(n), nil) -> nil
sndsplit(s(n), cons(h, t)) -> sndsplit(n, t)
empty(nil) -> true
empty(cons(h, t)) -> false
leq(0', m) -> true
leq(s(n), 0') -> false
leq(s(n), s(m)) -> leq(n, m)
length(nil) -> 0'
length(cons(h, t)) -> s(length(t))
app(nil, x) -> x
app(cons(h, t), x) -> cons(h, app(t, x))
map_f(nil) -> nil
map_f(cons(h, t)) -> app(f, map_f(t))
head(cons(h, t)) -> h
tail(cons(h, t)) -> t
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_1(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_1)))
if_1(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(sndsplit(m, st_1), cons(fstsplit(m, st_1), in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_2(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_2)))
if_2(st_1, in_2, st_2, in_3, st_3, m, true) -> if_3(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_2)))
if_3(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, sndsplit(m, st_2), cons(fstsplit(m, st_2), in_3), st_3, m)
if_2(st_1, in_2, st_2, in_3, st_3, m, false) -> if_4(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_2)), st_2))))
if_4(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, tail(in_2), sndsplit(m, app(map_f(head(in_2)), st_2)), cons(fstsplit(m, app(map_f(head(in_2)), st_2)), in_3), st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_5(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_2))))
if_5(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, tail(in_2), st_2, in_3, st_3, m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_6(st_1, in_2, st_2, in_3, st_3, m, leq(m, length(st_3)))
if_6(st_1, in_2, st_2, in_3, st_3, m, true) -> if_7(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, st_3)))
if_7(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, in_3, sndsplit(m, st_3), m)
if_6(st_1, in_2, st_2, in_3, st_3, m, false) -> if_8(st_1, in_2, st_2, in_3, st_3, m, empty(fstsplit(m, app(map_f(head(in_3)), st_3))))
if_8(st_1, in_2, st_2, in_3, st_3, m, false) -> ring(st_1, in_2, st_2, tail(in_3), sndsplit(m, app(map_f(head(in_3)), st_3)), m)
ring(st_1, in_2, st_2, in_3, st_3, m) -> if_9(st_1, in_2, st_2, in_3, st_3, m, empty(map_f(head(in_3))))
if_9(st_1, in_2, st_2, in_3, st_3, m, true) -> ring(st_1, in_2, st_2, tail(in_3), st_3, m)

Types:
fstsplit :: 0':s -> nil:cons:f -> nil:cons:f
0' :: 0':s
nil :: nil:cons:f
s :: 0':s -> 0':s
cons :: nil:cons:f -> nil:cons:f -> nil:cons:f
sndsplit :: 0':s -> nil:cons:f -> nil:cons:f
empty :: nil:cons:f -> true:false
true :: true:false
false :: true:false
leq :: 0':s -> 0':s -> true:false
length :: nil:cons:f -> 0':s
app :: nil:cons:f -> nil:cons:f -> nil:cons:f
map_f :: nil:cons:f -> nil:cons:f
f :: nil:cons:f
head :: nil:cons:f -> nil:cons:f
tail :: nil:cons:f -> nil:cons:f
ring :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_1 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_2 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_3 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_4 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_5 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_6 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_7 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_8 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
if_9 :: nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> nil:cons:f -> 0':s -> true:false -> ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
hole_nil:cons:f1_0 :: nil:cons:f
hole_0':s2_0 :: 0':s
hole_true:false3_0 :: true:false
hole_ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_94_0 :: ring:if_1:if_2:if_3:if_4:if_5:if_6:if_7:if_8:if_9
gen_nil:cons:f5_0 :: Nat -> nil:cons:f
gen_0':s6_0 :: Nat -> 0':s


Lemmas:
fstsplit(gen_0':s6_0(n8_0), gen_nil:cons:f5_0(n8_0)) -> gen_nil:cons:f5_0(n8_0), rt in Omega(1 + n8_0)
sndsplit(gen_0':s6_0(n638_0), gen_nil:cons:f5_0(n638_0)) -> gen_nil:cons:f5_0(0), rt in Omega(1 + n638_0)
leq(gen_0':s6_0(n1339_0), gen_0':s6_0(n1339_0)) -> true, rt in Omega(1 + n1339_0)
length(gen_nil:cons:f5_0(n1752_0)) -> gen_0':s6_0(n1752_0), rt in Omega(1 + n1752_0)
app(gen_nil:cons:f5_0(n2110_0), gen_nil:cons:f5_0(b)) -> gen_nil:cons:f5_0(+(n2110_0, b)), rt in Omega(1 + n2110_0)
map_f(gen_nil:cons:f5_0(+(1, n3259_0))) -> *7_0, rt in Omega(n3259_0)


Generator Equations:
gen_nil:cons:f5_0(0) <=> nil
gen_nil:cons:f5_0(+(x, 1)) <=> cons(nil, gen_nil:cons:f5_0(x))
gen_0':s6_0(0) <=> 0'
gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x))


The following defined symbols remain to be analysed:
ring