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


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


WORST_CASE(Omega(n^1), ?)
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^1, INF).

(0) CpxTRS
(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxTRS
(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
(4) typed CpxTrs
(5) OrderProof [LOWER BOUND(ID), 0 ms]
(6) typed CpxTrs
(7) RewriteLemmaProof [LOWER BOUND(ID), 321 ms]
(8) BEST
    (9) proven lower bound
        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
        (11) BOUNDS(n^1, INF)
    (12) typed CpxTrs
        (13) RewriteLemmaProof [LOWER BOUND(ID), 83 ms]
        (14) typed CpxTrs
        (15) RewriteLemmaProof [LOWER BOUND(ID), 112 ms]
        (16) typed CpxTrs
        (17) RewriteLemmaProof [LOWER BOUND(ID), 84 ms]
        (18) typed CpxTrs
        (19) RewriteLemmaProof [LOWER BOUND(ID), 0 ms]
        (20) BOUNDS(1, INF)


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

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


The TRS R consists of the following rules:

   cond_scanr_f_z_xs_1(Cons(0, x11), 0) -> Cons(0, Cons(0, x11))
   cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0) -> Cons(S(x2), Cons(S(x2), x11))
   cond_scanr_f_z_xs_1(Cons(0, x11), M(x2)) -> Cons(0, Cons(0, x11))
   cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0)) -> Cons(S(x40), Cons(S(x40), x23))
   cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23))
   cond_scanr_f_z_xs_1(Cons(0, x11), S(x2)) -> Cons(S(x2), Cons(0, x11))
   cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11))
   scanr#3(Nil) -> Cons(0, Nil)
   scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4)
   foldl#3(x2, Nil) -> x2
   foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2)
   minus#2(0, x16) -> 0
   minus#2(S(x20), 0) -> S(x20)
   minus#2(S(x4), S(x2)) -> minus#2(x4, x2)
   plus#2(0, S(x2)) -> S(x2)
   plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2)))
   max#2(0, x8) -> x8
   max#2(S(x12), 0) -> S(x12)
   max#2(S(x4), S(x2)) -> S(max#2(x4, x2))
   main(x1) -> foldl#3(0, scanr#3(x1))

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

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

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


The TRS R consists of the following rules:

   cond_scanr_f_z_xs_1(Cons(0', x11), 0') -> Cons(0', Cons(0', x11))
   cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0') -> Cons(S(x2), Cons(S(x2), x11))
   cond_scanr_f_z_xs_1(Cons(0', x11), M(x2)) -> Cons(0', Cons(0', x11))
   cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0')) -> Cons(S(x40), Cons(S(x40), x23))
   cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23))
   cond_scanr_f_z_xs_1(Cons(0', x11), S(x2)) -> Cons(S(x2), Cons(0', x11))
   cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11))
   scanr#3(Nil) -> Cons(0', Nil)
   scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4)
   foldl#3(x2, Nil) -> x2
   foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2)
   minus#2(0', x16) -> 0'
   minus#2(S(x20), 0') -> S(x20)
   minus#2(S(x4), S(x2)) -> minus#2(x4, x2)
   plus#2(0', S(x2)) -> S(x2)
   plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2)))
   max#2(0', x8) -> x8
   max#2(S(x12), 0') -> S(x12)
   max#2(S(x4), S(x2)) -> S(max#2(x4, x2))
   main(x1) -> foldl#3(0', scanr#3(x1))

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

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

(4)
Obligation:
Innermost TRS:
Rules:
cond_scanr_f_z_xs_1(Cons(0', x11), 0') -> Cons(0', Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0') -> Cons(S(x2), Cons(S(x2), x11))
cond_scanr_f_z_xs_1(Cons(0', x11), M(x2)) -> Cons(0', Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0')) -> Cons(S(x40), Cons(S(x40), x23))
cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23))
cond_scanr_f_z_xs_1(Cons(0', x11), S(x2)) -> Cons(S(x2), Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11))
scanr#3(Nil) -> Cons(0', Nil)
scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4)
foldl#3(x2, Nil) -> x2
foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2)
minus#2(0', x16) -> 0'
minus#2(S(x20), 0') -> S(x20)
minus#2(S(x4), S(x2)) -> minus#2(x4, x2)
plus#2(0', S(x2)) -> S(x2)
plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2)))
max#2(0', x8) -> x8
max#2(S(x12), 0') -> S(x12)
max#2(S(x4), S(x2)) -> S(max#2(x4, x2))
main(x1) -> foldl#3(0', scanr#3(x1))

Types:
cond_scanr_f_z_xs_1 :: Cons:Nil -> 0':S:M -> Cons:Nil
Cons :: 0':S:M -> Cons:Nil -> Cons:Nil
0' :: 0':S:M
S :: 0':S:M -> 0':S:M
M :: 0':S:M -> 0':S:M
minus#2 :: 0':S:M -> 0':S:M -> 0':S:M
plus#2 :: 0':S:M -> 0':S:M -> 0':S:M
scanr#3 :: Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
foldl#3 :: 0':S:M -> Cons:Nil -> 0':S:M
max#2 :: 0':S:M -> 0':S:M -> 0':S:M
main :: Cons:Nil -> 0':S:M
hole_Cons:Nil1_5 :: Cons:Nil
hole_0':S:M2_5 :: 0':S:M
gen_Cons:Nil3_5 :: Nat -> Cons:Nil
gen_0':S:M4_5 :: Nat -> 0':S:M

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

(5) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
minus#2, plus#2, scanr#3, foldl#3, max#2

They will be analysed ascendingly in the following order:
max#2 < foldl#3

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

(6)
Obligation:
Innermost TRS:
Rules:
cond_scanr_f_z_xs_1(Cons(0', x11), 0') -> Cons(0', Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0') -> Cons(S(x2), Cons(S(x2), x11))
cond_scanr_f_z_xs_1(Cons(0', x11), M(x2)) -> Cons(0', Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0')) -> Cons(S(x40), Cons(S(x40), x23))
cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23))
cond_scanr_f_z_xs_1(Cons(0', x11), S(x2)) -> Cons(S(x2), Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11))
scanr#3(Nil) -> Cons(0', Nil)
scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4)
foldl#3(x2, Nil) -> x2
foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2)
minus#2(0', x16) -> 0'
minus#2(S(x20), 0') -> S(x20)
minus#2(S(x4), S(x2)) -> minus#2(x4, x2)
plus#2(0', S(x2)) -> S(x2)
plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2)))
max#2(0', x8) -> x8
max#2(S(x12), 0') -> S(x12)
max#2(S(x4), S(x2)) -> S(max#2(x4, x2))
main(x1) -> foldl#3(0', scanr#3(x1))

Types:
cond_scanr_f_z_xs_1 :: Cons:Nil -> 0':S:M -> Cons:Nil
Cons :: 0':S:M -> Cons:Nil -> Cons:Nil
0' :: 0':S:M
S :: 0':S:M -> 0':S:M
M :: 0':S:M -> 0':S:M
minus#2 :: 0':S:M -> 0':S:M -> 0':S:M
plus#2 :: 0':S:M -> 0':S:M -> 0':S:M
scanr#3 :: Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
foldl#3 :: 0':S:M -> Cons:Nil -> 0':S:M
max#2 :: 0':S:M -> 0':S:M -> 0':S:M
main :: Cons:Nil -> 0':S:M
hole_Cons:Nil1_5 :: Cons:Nil
hole_0':S:M2_5 :: 0':S:M
gen_Cons:Nil3_5 :: Nat -> Cons:Nil
gen_0':S:M4_5 :: Nat -> 0':S:M


Generator Equations:
gen_Cons:Nil3_5(0) <=> Nil
gen_Cons:Nil3_5(+(x, 1)) <=> Cons(0', gen_Cons:Nil3_5(x))
gen_0':S:M4_5(0) <=> 0'
gen_0':S:M4_5(+(x, 1)) <=> S(gen_0':S:M4_5(x))


The following defined symbols remain to be analysed:
minus#2, plus#2, scanr#3, foldl#3, max#2

They will be analysed ascendingly in the following order:
max#2 < foldl#3

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

(7) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
minus#2(gen_0':S:M4_5(n6_5), gen_0':S:M4_5(n6_5)) -> gen_0':S:M4_5(0), rt in Omega(1 + n6_5)

Induction Base:
minus#2(gen_0':S:M4_5(0), gen_0':S:M4_5(0)) ->_R^Omega(1)
0'

Induction Step:
minus#2(gen_0':S:M4_5(+(n6_5, 1)), gen_0':S:M4_5(+(n6_5, 1))) ->_R^Omega(1)
minus#2(gen_0':S:M4_5(n6_5), gen_0':S:M4_5(n6_5)) ->_IH
gen_0':S:M4_5(0)

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

(8)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
cond_scanr_f_z_xs_1(Cons(0', x11), 0') -> Cons(0', Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0') -> Cons(S(x2), Cons(S(x2), x11))
cond_scanr_f_z_xs_1(Cons(0', x11), M(x2)) -> Cons(0', Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0')) -> Cons(S(x40), Cons(S(x40), x23))
cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23))
cond_scanr_f_z_xs_1(Cons(0', x11), S(x2)) -> Cons(S(x2), Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11))
scanr#3(Nil) -> Cons(0', Nil)
scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4)
foldl#3(x2, Nil) -> x2
foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2)
minus#2(0', x16) -> 0'
minus#2(S(x20), 0') -> S(x20)
minus#2(S(x4), S(x2)) -> minus#2(x4, x2)
plus#2(0', S(x2)) -> S(x2)
plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2)))
max#2(0', x8) -> x8
max#2(S(x12), 0') -> S(x12)
max#2(S(x4), S(x2)) -> S(max#2(x4, x2))
main(x1) -> foldl#3(0', scanr#3(x1))

Types:
cond_scanr_f_z_xs_1 :: Cons:Nil -> 0':S:M -> Cons:Nil
Cons :: 0':S:M -> Cons:Nil -> Cons:Nil
0' :: 0':S:M
S :: 0':S:M -> 0':S:M
M :: 0':S:M -> 0':S:M
minus#2 :: 0':S:M -> 0':S:M -> 0':S:M
plus#2 :: 0':S:M -> 0':S:M -> 0':S:M
scanr#3 :: Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
foldl#3 :: 0':S:M -> Cons:Nil -> 0':S:M
max#2 :: 0':S:M -> 0':S:M -> 0':S:M
main :: Cons:Nil -> 0':S:M
hole_Cons:Nil1_5 :: Cons:Nil
hole_0':S:M2_5 :: 0':S:M
gen_Cons:Nil3_5 :: Nat -> Cons:Nil
gen_0':S:M4_5 :: Nat -> 0':S:M


Generator Equations:
gen_Cons:Nil3_5(0) <=> Nil
gen_Cons:Nil3_5(+(x, 1)) <=> Cons(0', gen_Cons:Nil3_5(x))
gen_0':S:M4_5(0) <=> 0'
gen_0':S:M4_5(+(x, 1)) <=> S(gen_0':S:M4_5(x))


The following defined symbols remain to be analysed:
minus#2, plus#2, scanr#3, foldl#3, max#2

They will be analysed ascendingly in the following order:
max#2 < foldl#3

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

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

(11)
BOUNDS(n^1, INF)

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

(12)
Obligation:
Innermost TRS:
Rules:
cond_scanr_f_z_xs_1(Cons(0', x11), 0') -> Cons(0', Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0') -> Cons(S(x2), Cons(S(x2), x11))
cond_scanr_f_z_xs_1(Cons(0', x11), M(x2)) -> Cons(0', Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0')) -> Cons(S(x40), Cons(S(x40), x23))
cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23))
cond_scanr_f_z_xs_1(Cons(0', x11), S(x2)) -> Cons(S(x2), Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11))
scanr#3(Nil) -> Cons(0', Nil)
scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4)
foldl#3(x2, Nil) -> x2
foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2)
minus#2(0', x16) -> 0'
minus#2(S(x20), 0') -> S(x20)
minus#2(S(x4), S(x2)) -> minus#2(x4, x2)
plus#2(0', S(x2)) -> S(x2)
plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2)))
max#2(0', x8) -> x8
max#2(S(x12), 0') -> S(x12)
max#2(S(x4), S(x2)) -> S(max#2(x4, x2))
main(x1) -> foldl#3(0', scanr#3(x1))

Types:
cond_scanr_f_z_xs_1 :: Cons:Nil -> 0':S:M -> Cons:Nil
Cons :: 0':S:M -> Cons:Nil -> Cons:Nil
0' :: 0':S:M
S :: 0':S:M -> 0':S:M
M :: 0':S:M -> 0':S:M
minus#2 :: 0':S:M -> 0':S:M -> 0':S:M
plus#2 :: 0':S:M -> 0':S:M -> 0':S:M
scanr#3 :: Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
foldl#3 :: 0':S:M -> Cons:Nil -> 0':S:M
max#2 :: 0':S:M -> 0':S:M -> 0':S:M
main :: Cons:Nil -> 0':S:M
hole_Cons:Nil1_5 :: Cons:Nil
hole_0':S:M2_5 :: 0':S:M
gen_Cons:Nil3_5 :: Nat -> Cons:Nil
gen_0':S:M4_5 :: Nat -> 0':S:M


Lemmas:
minus#2(gen_0':S:M4_5(n6_5), gen_0':S:M4_5(n6_5)) -> gen_0':S:M4_5(0), rt in Omega(1 + n6_5)


Generator Equations:
gen_Cons:Nil3_5(0) <=> Nil
gen_Cons:Nil3_5(+(x, 1)) <=> Cons(0', gen_Cons:Nil3_5(x))
gen_0':S:M4_5(0) <=> 0'
gen_0':S:M4_5(+(x, 1)) <=> S(gen_0':S:M4_5(x))


The following defined symbols remain to be analysed:
plus#2, scanr#3, foldl#3, max#2

They will be analysed ascendingly in the following order:
max#2 < foldl#3

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

(13) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
plus#2(gen_0':S:M4_5(n655_5), gen_0':S:M4_5(1)) -> gen_0':S:M4_5(+(1, n655_5)), rt in Omega(1 + n655_5)

Induction Base:
plus#2(gen_0':S:M4_5(0), gen_0':S:M4_5(1)) ->_R^Omega(1)
S(gen_0':S:M4_5(0))

Induction Step:
plus#2(gen_0':S:M4_5(+(n655_5, 1)), gen_0':S:M4_5(1)) ->_R^Omega(1)
S(plus#2(gen_0':S:M4_5(n655_5), S(gen_0':S:M4_5(0)))) ->_IH
S(gen_0':S:M4_5(+(1, c656_5)))

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

(14)
Obligation:
Innermost TRS:
Rules:
cond_scanr_f_z_xs_1(Cons(0', x11), 0') -> Cons(0', Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0') -> Cons(S(x2), Cons(S(x2), x11))
cond_scanr_f_z_xs_1(Cons(0', x11), M(x2)) -> Cons(0', Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0')) -> Cons(S(x40), Cons(S(x40), x23))
cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23))
cond_scanr_f_z_xs_1(Cons(0', x11), S(x2)) -> Cons(S(x2), Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11))
scanr#3(Nil) -> Cons(0', Nil)
scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4)
foldl#3(x2, Nil) -> x2
foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2)
minus#2(0', x16) -> 0'
minus#2(S(x20), 0') -> S(x20)
minus#2(S(x4), S(x2)) -> minus#2(x4, x2)
plus#2(0', S(x2)) -> S(x2)
plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2)))
max#2(0', x8) -> x8
max#2(S(x12), 0') -> S(x12)
max#2(S(x4), S(x2)) -> S(max#2(x4, x2))
main(x1) -> foldl#3(0', scanr#3(x1))

Types:
cond_scanr_f_z_xs_1 :: Cons:Nil -> 0':S:M -> Cons:Nil
Cons :: 0':S:M -> Cons:Nil -> Cons:Nil
0' :: 0':S:M
S :: 0':S:M -> 0':S:M
M :: 0':S:M -> 0':S:M
minus#2 :: 0':S:M -> 0':S:M -> 0':S:M
plus#2 :: 0':S:M -> 0':S:M -> 0':S:M
scanr#3 :: Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
foldl#3 :: 0':S:M -> Cons:Nil -> 0':S:M
max#2 :: 0':S:M -> 0':S:M -> 0':S:M
main :: Cons:Nil -> 0':S:M
hole_Cons:Nil1_5 :: Cons:Nil
hole_0':S:M2_5 :: 0':S:M
gen_Cons:Nil3_5 :: Nat -> Cons:Nil
gen_0':S:M4_5 :: Nat -> 0':S:M


Lemmas:
minus#2(gen_0':S:M4_5(n6_5), gen_0':S:M4_5(n6_5)) -> gen_0':S:M4_5(0), rt in Omega(1 + n6_5)
plus#2(gen_0':S:M4_5(n655_5), gen_0':S:M4_5(1)) -> gen_0':S:M4_5(+(1, n655_5)), rt in Omega(1 + n655_5)


Generator Equations:
gen_Cons:Nil3_5(0) <=> Nil
gen_Cons:Nil3_5(+(x, 1)) <=> Cons(0', gen_Cons:Nil3_5(x))
gen_0':S:M4_5(0) <=> 0'
gen_0':S:M4_5(+(x, 1)) <=> S(gen_0':S:M4_5(x))


The following defined symbols remain to be analysed:
scanr#3, foldl#3, max#2

They will be analysed ascendingly in the following order:
max#2 < foldl#3

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

(15) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
scanr#3(gen_Cons:Nil3_5(n1267_5)) -> gen_Cons:Nil3_5(+(1, n1267_5)), rt in Omega(1 + n1267_5)

Induction Base:
scanr#3(gen_Cons:Nil3_5(0)) ->_R^Omega(1)
Cons(0', Nil)

Induction Step:
scanr#3(gen_Cons:Nil3_5(+(n1267_5, 1))) ->_R^Omega(1)
cond_scanr_f_z_xs_1(scanr#3(gen_Cons:Nil3_5(n1267_5)), 0') ->_IH
cond_scanr_f_z_xs_1(gen_Cons:Nil3_5(+(1, c1268_5)), 0') ->_R^Omega(1)
Cons(0', Cons(0', gen_Cons:Nil3_5(n1267_5)))

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

(16)
Obligation:
Innermost TRS:
Rules:
cond_scanr_f_z_xs_1(Cons(0', x11), 0') -> Cons(0', Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0') -> Cons(S(x2), Cons(S(x2), x11))
cond_scanr_f_z_xs_1(Cons(0', x11), M(x2)) -> Cons(0', Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0')) -> Cons(S(x40), Cons(S(x40), x23))
cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23))
cond_scanr_f_z_xs_1(Cons(0', x11), S(x2)) -> Cons(S(x2), Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11))
scanr#3(Nil) -> Cons(0', Nil)
scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4)
foldl#3(x2, Nil) -> x2
foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2)
minus#2(0', x16) -> 0'
minus#2(S(x20), 0') -> S(x20)
minus#2(S(x4), S(x2)) -> minus#2(x4, x2)
plus#2(0', S(x2)) -> S(x2)
plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2)))
max#2(0', x8) -> x8
max#2(S(x12), 0') -> S(x12)
max#2(S(x4), S(x2)) -> S(max#2(x4, x2))
main(x1) -> foldl#3(0', scanr#3(x1))

Types:
cond_scanr_f_z_xs_1 :: Cons:Nil -> 0':S:M -> Cons:Nil
Cons :: 0':S:M -> Cons:Nil -> Cons:Nil
0' :: 0':S:M
S :: 0':S:M -> 0':S:M
M :: 0':S:M -> 0':S:M
minus#2 :: 0':S:M -> 0':S:M -> 0':S:M
plus#2 :: 0':S:M -> 0':S:M -> 0':S:M
scanr#3 :: Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
foldl#3 :: 0':S:M -> Cons:Nil -> 0':S:M
max#2 :: 0':S:M -> 0':S:M -> 0':S:M
main :: Cons:Nil -> 0':S:M
hole_Cons:Nil1_5 :: Cons:Nil
hole_0':S:M2_5 :: 0':S:M
gen_Cons:Nil3_5 :: Nat -> Cons:Nil
gen_0':S:M4_5 :: Nat -> 0':S:M


Lemmas:
minus#2(gen_0':S:M4_5(n6_5), gen_0':S:M4_5(n6_5)) -> gen_0':S:M4_5(0), rt in Omega(1 + n6_5)
plus#2(gen_0':S:M4_5(n655_5), gen_0':S:M4_5(1)) -> gen_0':S:M4_5(+(1, n655_5)), rt in Omega(1 + n655_5)
scanr#3(gen_Cons:Nil3_5(n1267_5)) -> gen_Cons:Nil3_5(+(1, n1267_5)), rt in Omega(1 + n1267_5)


Generator Equations:
gen_Cons:Nil3_5(0) <=> Nil
gen_Cons:Nil3_5(+(x, 1)) <=> Cons(0', gen_Cons:Nil3_5(x))
gen_0':S:M4_5(0) <=> 0'
gen_0':S:M4_5(+(x, 1)) <=> S(gen_0':S:M4_5(x))


The following defined symbols remain to be analysed:
max#2, foldl#3

They will be analysed ascendingly in the following order:
max#2 < foldl#3

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

(17) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
max#2(gen_0':S:M4_5(n15636_5), gen_0':S:M4_5(n15636_5)) -> gen_0':S:M4_5(n15636_5), rt in Omega(1 + n15636_5)

Induction Base:
max#2(gen_0':S:M4_5(0), gen_0':S:M4_5(0)) ->_R^Omega(1)
gen_0':S:M4_5(0)

Induction Step:
max#2(gen_0':S:M4_5(+(n15636_5, 1)), gen_0':S:M4_5(+(n15636_5, 1))) ->_R^Omega(1)
S(max#2(gen_0':S:M4_5(n15636_5), gen_0':S:M4_5(n15636_5))) ->_IH
S(gen_0':S:M4_5(c15637_5))

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

(18)
Obligation:
Innermost TRS:
Rules:
cond_scanr_f_z_xs_1(Cons(0', x11), 0') -> Cons(0', Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0') -> Cons(S(x2), Cons(S(x2), x11))
cond_scanr_f_z_xs_1(Cons(0', x11), M(x2)) -> Cons(0', Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0')) -> Cons(S(x40), Cons(S(x40), x23))
cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23))
cond_scanr_f_z_xs_1(Cons(0', x11), S(x2)) -> Cons(S(x2), Cons(0', x11))
cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11))
scanr#3(Nil) -> Cons(0', Nil)
scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4)
foldl#3(x2, Nil) -> x2
foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2)
minus#2(0', x16) -> 0'
minus#2(S(x20), 0') -> S(x20)
minus#2(S(x4), S(x2)) -> minus#2(x4, x2)
plus#2(0', S(x2)) -> S(x2)
plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2)))
max#2(0', x8) -> x8
max#2(S(x12), 0') -> S(x12)
max#2(S(x4), S(x2)) -> S(max#2(x4, x2))
main(x1) -> foldl#3(0', scanr#3(x1))

Types:
cond_scanr_f_z_xs_1 :: Cons:Nil -> 0':S:M -> Cons:Nil
Cons :: 0':S:M -> Cons:Nil -> Cons:Nil
0' :: 0':S:M
S :: 0':S:M -> 0':S:M
M :: 0':S:M -> 0':S:M
minus#2 :: 0':S:M -> 0':S:M -> 0':S:M
plus#2 :: 0':S:M -> 0':S:M -> 0':S:M
scanr#3 :: Cons:Nil -> Cons:Nil
Nil :: Cons:Nil
foldl#3 :: 0':S:M -> Cons:Nil -> 0':S:M
max#2 :: 0':S:M -> 0':S:M -> 0':S:M
main :: Cons:Nil -> 0':S:M
hole_Cons:Nil1_5 :: Cons:Nil
hole_0':S:M2_5 :: 0':S:M
gen_Cons:Nil3_5 :: Nat -> Cons:Nil
gen_0':S:M4_5 :: Nat -> 0':S:M


Lemmas:
minus#2(gen_0':S:M4_5(n6_5), gen_0':S:M4_5(n6_5)) -> gen_0':S:M4_5(0), rt in Omega(1 + n6_5)
plus#2(gen_0':S:M4_5(n655_5), gen_0':S:M4_5(1)) -> gen_0':S:M4_5(+(1, n655_5)), rt in Omega(1 + n655_5)
scanr#3(gen_Cons:Nil3_5(n1267_5)) -> gen_Cons:Nil3_5(+(1, n1267_5)), rt in Omega(1 + n1267_5)
max#2(gen_0':S:M4_5(n15636_5), gen_0':S:M4_5(n15636_5)) -> gen_0':S:M4_5(n15636_5), rt in Omega(1 + n15636_5)


Generator Equations:
gen_Cons:Nil3_5(0) <=> Nil
gen_Cons:Nil3_5(+(x, 1)) <=> Cons(0', gen_Cons:Nil3_5(x))
gen_0':S:M4_5(0) <=> 0'
gen_0':S:M4_5(+(x, 1)) <=> S(gen_0':S:M4_5(x))


The following defined symbols remain to be analysed:
foldl#3
----------------------------------------

(19) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
foldl#3(gen_0':S:M4_5(0), gen_Cons:Nil3_5(n16539_5)) -> gen_0':S:M4_5(0), rt in Omega(1 + n16539_5)

Induction Base:
foldl#3(gen_0':S:M4_5(0), gen_Cons:Nil3_5(0)) ->_R^Omega(1)
gen_0':S:M4_5(0)

Induction Step:
foldl#3(gen_0':S:M4_5(0), gen_Cons:Nil3_5(+(n16539_5, 1))) ->_R^Omega(1)
foldl#3(max#2(gen_0':S:M4_5(0), 0'), gen_Cons:Nil3_5(n16539_5)) ->_L^Omega(1)
foldl#3(gen_0':S:M4_5(0), gen_Cons:Nil3_5(n16539_5)) ->_IH
gen_0':S:M4_5(0)

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

(20)
BOUNDS(1, INF)