/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), O(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 CpxRelTRS could be proven to be BOUNDS(n^1, n^1).

(0) CpxRelTRS
(1) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 170 ms]
(2) CpxRelTRS
(3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
(4) CpxWeightedTrs
    (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (6) CpxTypedWeightedTrs
    (7) CompletionProof [UPPER BOUND(ID), 0 ms]
    (8) CpxTypedWeightedCompleteTrs
    (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (10) CpxRNTS
    (11) CompleteCoflocoProof [FINISHED, 549 ms]
    (12) BOUNDS(1, n^1)
(13) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(14) CpxRelTRS
    (15) SlicingProof [LOWER BOUND(ID), 0 ms]
    (16) CpxRelTRS
    (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (18) typed CpxTrs
    (19) OrderProof [LOWER BOUND(ID), 0 ms]
    (20) typed CpxTrs
    (21) RewriteLemmaProof [LOWER BOUND(ID), 277 ms]
    (22) BEST
        (23) proven lower bound
            (24) LowerBoundPropagationProof [FINISHED, 0 ms]
            (25) BOUNDS(n^1, INF)
        (26) typed CpxTrs
            (27) RewriteLemmaProof [LOWER BOUND(ID), 74 ms]
            (28) typed CpxTrs
            (29) RewriteLemmaProof [LOWER BOUND(ID), 0 ms]
            (30) BOUNDS(1, INF)


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

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


The TRS R consists of the following rules:

   lt0(Nil, Cons(x', xs)) -> True
   lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs)
   g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
   f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   lt0(x, Nil) -> False
   g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
   f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
   number4(n) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
   goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil))

The (relative) TRS S consists of the following rules:

   g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y))
   g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs)
   f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y))
   f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs)

Rewrite Strategy: INNERMOST
----------------------------------------

(1) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
proved innermost termination of relative rules
----------------------------------------

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


The TRS R consists of the following rules:

   lt0(Nil, Cons(x', xs)) -> True
   lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs)
   g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
   f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   lt0(x, Nil) -> False
   g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
   f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
   number4(n) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
   goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil))

The (relative) TRS S consists of the following rules:

   g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y))
   g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs)
   f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y))
   f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs)

Rewrite Strategy: INNERMOST
----------------------------------------

(3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
Transformed relative TRS to weighted TRS
----------------------------------------

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


The TRS R consists of the following rules:

   lt0(Nil, Cons(x', xs)) -> True [1]
   lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs) [1]
   g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1]
   f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1]
   notEmpty(Cons(x, xs)) -> True [1]
   notEmpty(Nil) -> False [1]
   lt0(x, Nil) -> False [1]
   g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) [1]
   f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) [1]
   number4(n) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1]
   goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil)) [1]
   g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y)) [0]
   g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs) [0]
   f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y)) [0]
   f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs) [0]

Rewrite Strategy: INNERMOST
----------------------------------------

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

(6)
Obligation:
Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   lt0(Nil, Cons(x', xs)) -> True [1]
   lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs) [1]
   g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1]
   f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1]
   notEmpty(Cons(x, xs)) -> True [1]
   notEmpty(Nil) -> False [1]
   lt0(x, Nil) -> False [1]
   g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) [1]
   f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) [1]
   number4(n) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1]
   goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil)) [1]
   g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y)) [0]
   g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs) [0]
   f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y)) [0]
   f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs) [0]

The TRS has the following type information:
lt0 :: Nil:Cons -> Nil:Cons -> True:False
Nil :: Nil:Cons
Cons :: Nil:Cons -> Nil:Cons -> Nil:Cons
True :: True:False
g :: Nil:Cons -> Nil:Cons -> Nil:Cons
f :: Nil:Cons -> Nil:Cons -> Nil:Cons
notEmpty :: Nil:Cons -> True:False
False :: True:False
g[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons
f[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons
number4 :: a -> Nil:Cons
goal :: Nil:Cons -> Nil:Cons -> Nil:Cons

Rewrite Strategy: INNERMOST
----------------------------------------

(7) CompletionProof (UPPER BOUND(ID))
The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:

   g[Ite][False][Ite](v0, v1, v2) -> null_g[Ite][False][Ite] [0]
   f[Ite][False][Ite](v0, v1, v2) -> null_f[Ite][False][Ite] [0]
   lt0(v0, v1) -> null_lt0 [0]
   g(v0, v1) -> null_g [0]
   f(v0, v1) -> null_f [0]
   notEmpty(v0) -> null_notEmpty [0]

And the following fresh constants:    null_g[Ite][False][Ite], null_f[Ite][False][Ite], null_lt0, null_g, null_f, null_notEmpty, const

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

(8)
Obligation:
Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:

Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   lt0(Nil, Cons(x', xs)) -> True [1]
   lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs) [1]
   g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1]
   f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1]
   notEmpty(Cons(x, xs)) -> True [1]
   notEmpty(Nil) -> False [1]
   lt0(x, Nil) -> False [1]
   g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) [1]
   f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) [1]
   number4(n) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1]
   goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil)) [1]
   g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y)) [0]
   g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs) [0]
   f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y)) [0]
   f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs) [0]
   g[Ite][False][Ite](v0, v1, v2) -> null_g[Ite][False][Ite] [0]
   f[Ite][False][Ite](v0, v1, v2) -> null_f[Ite][False][Ite] [0]
   lt0(v0, v1) -> null_lt0 [0]
   g(v0, v1) -> null_g [0]
   f(v0, v1) -> null_f [0]
   notEmpty(v0) -> null_notEmpty [0]

The TRS has the following type information:
lt0 :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> True:False:null_lt0:null_notEmpty
Nil :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f
Cons :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f
True :: True:False:null_lt0:null_notEmpty
g :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f
f :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f
notEmpty :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> True:False:null_lt0:null_notEmpty
False :: True:False:null_lt0:null_notEmpty
g[Ite][False][Ite] :: True:False:null_lt0:null_notEmpty -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f
f[Ite][False][Ite] :: True:False:null_lt0:null_notEmpty -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f
number4 :: a -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f
goal :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f
null_g[Ite][False][Ite] :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f
null_f[Ite][False][Ite] :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f
null_lt0 :: True:False:null_lt0:null_notEmpty
null_g :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f
null_f :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f
null_notEmpty :: True:False:null_lt0:null_notEmpty
const :: a

Rewrite Strategy: INNERMOST
----------------------------------------

(9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
The constant constructors are abstracted as follows:

   Nil => 0
   True => 2
   False => 1
   null_g[Ite][False][Ite] => 0
   null_f[Ite][False][Ite] => 0
   null_lt0 => 0
   null_g => 0
   null_f => 0
   null_notEmpty => 0
   const => 0

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

(10)
Obligation:
Complexity RNTS consisting of the following rules:

   f(z, z') -{ 1 }-> f[Ite][False][Ite](lt0(x, 1 + 0 + 0), x, 1 + x' + xs) :|: xs >= 0, z' = 1 + x' + xs, x >= 0, x' >= 0, z = x
   f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   f(z, z') -{ 1 }-> 1 + 0 + (1 + 0 + (1 + 0 + (1 + 0 + 0))) :|: x >= 0, z = x, z' = 0
   f[Ite][False][Ite](z, z', z'') -{ 0 }-> f(x', xs) :|: z = 2, z' = x', xs >= 0, x' >= 0, x >= 0, z'' = 1 + x + xs
   f[Ite][False][Ite](z, z', z'') -{ 0 }-> f(xs, 1 + (1 + 0 + 0) + y) :|: xs >= 0, z' = 1 + x + xs, z'' = y, z = 1, x >= 0, y >= 0
   f[Ite][False][Ite](z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
   g(z, z') -{ 1 }-> g[Ite][False][Ite](lt0(x, 1 + 0 + 0), x, 1 + x' + xs) :|: xs >= 0, z' = 1 + x' + xs, x >= 0, x' >= 0, z = x
   g(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   g(z, z') -{ 1 }-> 1 + 0 + (1 + 0 + (1 + 0 + (1 + 0 + 0))) :|: x >= 0, z = x, z' = 0
   g[Ite][False][Ite](z, z', z'') -{ 0 }-> g(x', xs) :|: z = 2, z' = x', xs >= 0, x' >= 0, x >= 0, z'' = 1 + x + xs
   g[Ite][False][Ite](z, z', z'') -{ 0 }-> g(xs, 1 + (1 + 0 + 0) + y) :|: xs >= 0, z' = 1 + x + xs, z'' = y, z = 1, x >= 0, y >= 0
   g[Ite][False][Ite](z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
   goal(z, z') -{ 1 }-> 1 + f(x, y) + (1 + g(x, y) + 0) :|: x >= 0, y >= 0, z = x, z' = y
   lt0(z, z') -{ 1 }-> lt0(xs', xs) :|: xs >= 0, z' = 1 + x + xs, x' >= 0, xs' >= 0, x >= 0, z = 1 + x' + xs'
   lt0(z, z') -{ 1 }-> 2 :|: xs >= 0, z' = 1 + x' + xs, x' >= 0, z = 0
   lt0(z, z') -{ 1 }-> 1 :|: x >= 0, z = x, z' = 0
   lt0(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0
   notEmpty(z) -{ 1 }-> 1 :|: z = 0
   notEmpty(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   number4(z) -{ 1 }-> 1 + 0 + (1 + 0 + (1 + 0 + (1 + 0 + 0))) :|: n >= 0, z = n

Only complete derivations are relevant for the runtime complexity.

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

(11) CompleteCoflocoProof (FINISHED)
Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo:

eq(start(V1, V, V22),0,[lt0(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V22),0,[g(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V22),0,[f(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V22),0,[notEmpty(V1, Out)],[V1 >= 0]).
eq(start(V1, V, V22),0,[number4(V1, Out)],[V1 >= 0]).
eq(start(V1, V, V22),0,[goal(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V22),0,[fun(V1, V, V22, Out)],[V1 >= 0,V >= 0,V22 >= 0]).
eq(start(V1, V, V22),0,[fun1(V1, V, V22, Out)],[V1 >= 0,V >= 0,V22 >= 0]).
eq(lt0(V1, V, Out),1,[],[Out = 2,V2 >= 0,V = 1 + V2 + V3,V3 >= 0,V1 = 0]).
eq(lt0(V1, V, Out),1,[lt0(V4, V5, Ret)],[Out = Ret,V5 >= 0,V = 1 + V5 + V6,V7 >= 0,V4 >= 0,V6 >= 0,V1 = 1 + V4 + V7]).
eq(g(V1, V, Out),1,[],[Out = 4,V8 >= 0,V1 = V8,V = 0]).
eq(f(V1, V, Out),1,[],[Out = 4,V9 >= 0,V1 = V9,V = 0]).
eq(notEmpty(V1, Out),1,[],[Out = 2,V1 = 1 + V10 + V11,V11 >= 0,V10 >= 0]).
eq(notEmpty(V1, Out),1,[],[Out = 1,V1 = 0]).
eq(lt0(V1, V, Out),1,[],[Out = 1,V12 >= 0,V1 = V12,V = 0]).
eq(g(V1, V, Out),1,[lt0(V13, 1 + 0 + 0, Ret0),fun(Ret0, V13, 1 + V15 + V14, Ret1)],[Out = Ret1,V14 >= 0,V = 1 + V14 + V15,V13 >= 0,V15 >= 0,V1 = V13]).
eq(f(V1, V, Out),1,[lt0(V17, 1 + 0 + 0, Ret01),fun1(Ret01, V17, 1 + V18 + V16, Ret2)],[Out = Ret2,V16 >= 0,V = 1 + V16 + V18,V17 >= 0,V18 >= 0,V1 = V17]).
eq(number4(V1, Out),1,[],[Out = 4,V19 >= 0,V1 = V19]).
eq(goal(V1, V, Out),1,[f(V20, V21, Ret011),g(V20, V21, Ret101)],[Out = 2 + Ret011 + Ret101,V20 >= 0,V21 >= 0,V1 = V20,V = V21]).
eq(fun(V1, V, V22, Out),0,[g(V23, 1 + (1 + 0 + 0) + V25, Ret3)],[Out = Ret3,V23 >= 0,V = 1 + V23 + V24,V22 = V25,V1 = 1,V24 >= 0,V25 >= 0]).
eq(fun(V1, V, V22, Out),0,[g(V27, V26, Ret4)],[Out = Ret4,V1 = 2,V = V27,V26 >= 0,V27 >= 0,V28 >= 0,V22 = 1 + V26 + V28]).
eq(fun1(V1, V, V22, Out),0,[f(V30, 1 + (1 + 0 + 0) + V29, Ret5)],[Out = Ret5,V30 >= 0,V = 1 + V30 + V31,V22 = V29,V1 = 1,V31 >= 0,V29 >= 0]).
eq(fun1(V1, V, V22, Out),0,[f(V33, V32, Ret6)],[Out = Ret6,V1 = 2,V = V33,V32 >= 0,V33 >= 0,V34 >= 0,V22 = 1 + V32 + V34]).
eq(fun(V1, V, V22, Out),0,[],[Out = 0,V36 >= 0,V22 = V37,V35 >= 0,V1 = V36,V = V35,V37 >= 0]).
eq(fun1(V1, V, V22, Out),0,[],[Out = 0,V40 >= 0,V22 = V38,V39 >= 0,V1 = V40,V = V39,V38 >= 0]).
eq(lt0(V1, V, Out),0,[],[Out = 0,V42 >= 0,V41 >= 0,V1 = V42,V = V41]).
eq(g(V1, V, Out),0,[],[Out = 0,V43 >= 0,V44 >= 0,V1 = V43,V = V44]).
eq(f(V1, V, Out),0,[],[Out = 0,V46 >= 0,V45 >= 0,V1 = V46,V = V45]).
eq(notEmpty(V1, Out),0,[],[Out = 0,V47 >= 0,V1 = V47]).
input_output_vars(lt0(V1,V,Out),[V1,V],[Out]).
input_output_vars(g(V1,V,Out),[V1,V],[Out]).
input_output_vars(f(V1,V,Out),[V1,V],[Out]).
input_output_vars(notEmpty(V1,Out),[V1],[Out]).
input_output_vars(number4(V1,Out),[V1],[Out]).
input_output_vars(goal(V1,V,Out),[V1,V],[Out]).
input_output_vars(fun(V1,V,V22,Out),[V1,V,V22],[Out]).
input_output_vars(fun1(V1,V,V22,Out),[V1,V,V22],[Out]).


CoFloCo proof output:
Preprocessing Cost Relations
=====================================

#### Computed strongly connected components 
0. recursive  : [lt0/3]
1. recursive  : [f/3,fun1/4]
2. recursive  : [fun/4,g/3]
3. non_recursive  : [goal/3]
4. non_recursive  : [notEmpty/2]
5. non_recursive  : [number4/2]
6. non_recursive  : [start/3]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into lt0/3
1. SCC is partially evaluated into f/3
2. SCC is partially evaluated into g/3
3. SCC is partially evaluated into goal/3
4. SCC is partially evaluated into notEmpty/2
5. SCC is completely evaluated into other SCCs
6. SCC is partially evaluated into start/3

Control-Flow Refinement of Cost Relations
=====================================

### Specialization of cost equations lt0/3 
* CE 25 is refined into CE [30] 
* CE 24 is refined into CE [31] 
* CE 22 is refined into CE [32] 
* CE 23 is refined into CE [33] 


### Cost equations --> "Loop" of lt0/3 
* CEs [33] --> Loop 19 
* CEs [30] --> Loop 20 
* CEs [31] --> Loop 21 
* CEs [32] --> Loop 22 

### Ranking functions of CR lt0(V1,V,Out) 
* RF of phase [19]: [V,V1]

#### Partial ranking functions of CR lt0(V1,V,Out) 
* Partial RF of phase [19]:
  - RF of loop [19:1]:
    V
    V1


### Specialization of cost equations f/3 
* CE 17 is refined into CE [34,35,36] 
* CE 21 is refined into CE [37] 
* CE 20 is refined into CE [38] 
* CE 19 is refined into CE [39] 
* CE 18 is refined into CE [40] 


### Cost equations --> "Loop" of f/3 
* CEs [39] --> Loop 23 
* CEs [40] --> Loop 24 
* CEs [38] --> Loop 25 
* CEs [34,35,36,37] --> Loop 26 

### Ranking functions of CR f(V1,V,Out) 
* RF of phase [23]: [V1]
* RF of phase [24]: [V]

#### Partial ranking functions of CR f(V1,V,Out) 
* Partial RF of phase [23]:
  - RF of loop [23:1]:
    V1
* Partial RF of phase [24]:
  - RF of loop [24:1]:
    V


### Specialization of cost equations g/3 
* CE 12 is refined into CE [41,42,43] 
* CE 16 is refined into CE [44] 
* CE 15 is refined into CE [45] 
* CE 14 is refined into CE [46] 
* CE 13 is refined into CE [47] 


### Cost equations --> "Loop" of g/3 
* CEs [46] --> Loop 27 
* CEs [47] --> Loop 28 
* CEs [45] --> Loop 29 
* CEs [41,42,43,44] --> Loop 30 

### Ranking functions of CR g(V1,V,Out) 
* RF of phase [27]: [V1]
* RF of phase [28]: [V]

#### Partial ranking functions of CR g(V1,V,Out) 
* Partial RF of phase [27]:
  - RF of loop [27:1]:
    V1
* Partial RF of phase [28]:
  - RF of loop [28:1]:
    V


### Specialization of cost equations goal/3 
* CE 29 is refined into CE [48,49,50,51,52,53,54,55,56,57] 


### Cost equations --> "Loop" of goal/3 
* CEs [57] --> Loop 31 
* CEs [51,56] --> Loop 32 
* CEs [48] --> Loop 33 
* CEs [55] --> Loop 34 
* CEs [50,54] --> Loop 35 
* CEs [53] --> Loop 36 
* CEs [49,52] --> Loop 37 

### Ranking functions of CR goal(V1,V,Out) 

#### Partial ranking functions of CR goal(V1,V,Out) 


### Specialization of cost equations notEmpty/2 
* CE 26 is refined into CE [58] 
* CE 28 is refined into CE [59] 
* CE 27 is refined into CE [60] 


### Cost equations --> "Loop" of notEmpty/2 
* CEs [58] --> Loop 38 
* CEs [59] --> Loop 39 
* CEs [60] --> Loop 40 

### Ranking functions of CR notEmpty(V1,Out) 

#### Partial ranking functions of CR notEmpty(V1,Out) 


### Specialization of cost equations start/3 
* CE 2 is refined into CE [61,62,63,64] 
* CE 4 is refined into CE [65,66,67,68] 
* CE 1 is refined into CE [69] 
* CE 3 is refined into CE [70,71,72] 
* CE 5 is refined into CE [73,74,75] 
* CE 6 is refined into CE [76,77,78,79,80] 
* CE 7 is refined into CE [81,82,83,84] 
* CE 8 is refined into CE [85,86,87,88] 
* CE 9 is refined into CE [89,90,91] 
* CE 10 is refined into CE [92] 
* CE 11 is refined into CE [93,94,95,96,97,98,99] 


### Cost equations --> "Loop" of start/3 
* CEs [77,83,87,95,96] --> Loop 41 
* CEs [61,62,63,64,65,66,67,68] --> Loop 42 
* CEs [70,71,72,73,74,75] --> Loop 43 
* CEs [69,76,78,79,80,81,82,84,85,86,88,89,90,91,92,93,94,97,98,99] --> Loop 44 

### Ranking functions of CR start(V1,V,V22) 

#### Partial ranking functions of CR start(V1,V,V22) 


Computing Bounds
=====================================

#### Cost of chains of lt0(V1,V,Out):
* Chain [[19],22]: 1*it(19)+1
  Such that:it(19) =< V

  with precondition: [Out=2,V1>=1,V>=2] 

* Chain [[19],21]: 1*it(19)+1
  Such that:it(19) =< V

  with precondition: [Out=1,V1>=1,V>=1] 

* Chain [[19],20]: 1*it(19)+0
  Such that:it(19) =< V

  with precondition: [Out=0,V1>=1,V>=1] 

* Chain [22]: 1
  with precondition: [V1=0,Out=2,V>=1] 

* Chain [21]: 1
  with precondition: [V=0,Out=1,V1>=0] 

* Chain [20]: 0
  with precondition: [Out=0,V1>=0,V>=0] 


#### Cost of chains of f(V1,V,Out):
* Chain [[24],26]: 2*it(24)+4
  Such that:it(24) =< V

  with precondition: [V1=0,Out=0,V>=1] 

* Chain [[24],25]: 2*it(24)+1
  Such that:it(24) =< V

  with precondition: [V1=0,Out=4,V>=1] 

* Chain [[23],[24],26]: 3*it(23)+2*it(24)+4
  Such that:it(24) =< 2*V1+V
aux(5) =< V1
it(23) =< aux(5)

  with precondition: [Out=0,V1>=1,V>=1] 

* Chain [[23],[24],25]: 3*it(23)+2*it(24)+1
  Such that:it(24) =< 2*V1+V
aux(6) =< V1
it(23) =< aux(6)

  with precondition: [Out=4,V1>=1,V>=1] 

* Chain [[23],26]: 3*it(23)+4
  Such that:aux(7) =< V1
it(23) =< aux(7)

  with precondition: [Out=0,V1>=1,V>=1] 

* Chain [26]: 4
  with precondition: [Out=0,V1>=0,V>=0] 

* Chain [25]: 1
  with precondition: [V=0,Out=4,V1>=0] 


#### Cost of chains of g(V1,V,Out):
* Chain [[28],30]: 2*it(28)+4
  Such that:it(28) =< V

  with precondition: [V1=0,Out=0,V>=1] 

* Chain [[28],29]: 2*it(28)+1
  Such that:it(28) =< V

  with precondition: [V1=0,Out=4,V>=1] 

* Chain [[27],[28],30]: 3*it(27)+2*it(28)+4
  Such that:it(28) =< 2*V1+V
aux(13) =< V1
it(27) =< aux(13)

  with precondition: [Out=0,V1>=1,V>=1] 

* Chain [[27],[28],29]: 3*it(27)+2*it(28)+1
  Such that:it(28) =< 2*V1+V
aux(14) =< V1
it(27) =< aux(14)

  with precondition: [Out=4,V1>=1,V>=1] 

* Chain [[27],30]: 3*it(27)+4
  Such that:aux(15) =< V1
it(27) =< aux(15)

  with precondition: [Out=0,V1>=1,V>=1] 

* Chain [30]: 4
  with precondition: [Out=0,V1>=0,V>=0] 

* Chain [29]: 1
  with precondition: [V=0,Out=4,V1>=0] 


#### Cost of chains of goal(V1,V,Out):
* Chain [37]: 12*s(24)+6
  Such that:aux(19) =< V
s(24) =< aux(19)

  with precondition: [V1=0,Out=6,V>=1] 

* Chain [36]: 4*s(34)+3
  Such that:aux(20) =< V
s(34) =< aux(20)

  with precondition: [V1=0,Out=10,V>=1] 

* Chain [35]: 4*s(36)+12*s(39)+6
  Such that:aux(21) =< V1
aux(22) =< 2*V1
s(36) =< aux(22)
s(39) =< aux(21)

  with precondition: [V=0,Out=6,V1>=0] 

* Chain [34]: 3
  with precondition: [V=0,Out=10,V1>=0] 

* Chain [33]: 4*s(44)+4*s(45)+12*s(47)+9
  Such that:aux(23) =< V1
aux(24) =< 2*V1+V
aux(25) =< V
s(44) =< aux(24)
s(45) =< aux(25)
s(47) =< aux(23)

  with precondition: [Out=2,V1>=0,V>=0] 

* Chain [32]: 8*s(52)+4*s(53)+18*s(55)+6
  Such that:aux(30) =< V1
aux(31) =< 2*V1+V
aux(32) =< V
s(53) =< aux(32)
s(52) =< aux(31)
s(55) =< aux(30)

  with precondition: [Out=6,V1>=1,V>=1] 

* Chain [31]: 4*s(66)+6*s(68)+3
  Such that:aux(33) =< V1
aux(34) =< 2*V1+V
s(66) =< aux(34)
s(68) =< aux(33)

  with precondition: [Out=10,V1>=1,V>=1] 


#### Cost of chains of notEmpty(V1,Out):
* Chain [40]: 1
  with precondition: [V1=0,Out=1] 

* Chain [39]: 0
  with precondition: [Out=0,V1>=0] 

* Chain [38]: 1
  with precondition: [Out=2,V1>=1] 


#### Cost of chains of start(V1,V,V22):
* Chain [44]: 35*s(72)+24*s(75)+54*s(78)+9
  Such that:aux(35) =< V1
aux(36) =< 2*V1+V
aux(37) =< V
s(75) =< aux(36)
s(72) =< aux(37)
s(78) =< aux(35)

  with precondition: [V1>=0] 

* Chain [43]: 8*s(111)+8*s(112)+18*s(114)+4
  Such that:aux(38) =< V
aux(39) =< 2*V+V22
aux(40) =< V22+2
s(111) =< aux(39)
s(112) =< aux(40)
s(114) =< aux(38)

  with precondition: [V1=1,V>=1,V22>=0] 

* Chain [42]: 8*s(127)+8*s(128)+18*s(130)+4
  Such that:aux(41) =< V
aux(42) =< 2*V+V22
aux(43) =< V22
s(127) =< aux(42)
s(128) =< aux(43)
s(130) =< aux(41)

  with precondition: [V1=2,V>=0,V22>=1] 

* Chain [41]: 4*s(145)+12*s(146)+6
  Such that:s(143) =< V1
s(144) =< 2*V1
s(145) =< s(144)
s(146) =< s(143)

  with precondition: [V=0,V1>=0] 


Closed-form bounds of start(V1,V,V22): 
-------------------------------------
* Chain [44] with precondition: [V1>=0] 
    - Upper bound: 54*V1+9+nat(V)*35+nat(2*V1+V)*24 
    - Complexity: n 
* Chain [43] with precondition: [V1=1,V>=1,V22>=0] 
    - Upper bound: 34*V+16*V22+20 
    - Complexity: n 
* Chain [42] with precondition: [V1=2,V>=0,V22>=1] 
    - Upper bound: 34*V+16*V22+4 
    - Complexity: n 
* Chain [41] with precondition: [V=0,V1>=0] 
    - Upper bound: 20*V1+6 
    - Complexity: n 

### Maximum cost of start(V1,V,V22): max([20*V1+2,nat(V)*18+max([nat(2*V+V22)*8+max([nat(V22)*8,nat(V22+2)*8]),54*V1+5+nat(V)*17+nat(2*V1+V)*24])])+4 
Asymptotic class: n 
* Total analysis performed in 465 ms.


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

(12)
BOUNDS(1, n^1)

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

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

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


The TRS R consists of the following rules:

   lt0(Nil, Cons(x', xs)) -> True
   lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs)
   g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
   f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   lt0(x, Nil) -> False
   g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
   f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
   number4(n) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
   goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil))

The (relative) TRS S consists of the following rules:

   g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y))
   g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs)
   f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y))
   f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs)

Rewrite Strategy: INNERMOST
----------------------------------------

(15) SlicingProof (LOWER BOUND(ID))
Sliced the following arguments:
number4/0

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

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


The TRS R consists of the following rules:

   lt0(Nil, Cons(x', xs)) -> True
   lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs)
   g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
   f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   lt0(x, Nil) -> False
   g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
   f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
   number4 -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
   goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil))

The (relative) TRS S consists of the following rules:

   g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y))
   g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs)
   f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y))
   f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs)

Rewrite Strategy: INNERMOST
----------------------------------------

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

(18)
Obligation:
Innermost TRS:
Rules:
lt0(Nil, Cons(x', xs)) -> True
lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs)
g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
lt0(x, Nil) -> False
g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
number4 -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil))
g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y))
g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs)
f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y))
f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs)

Types:
lt0 :: Nil:Cons -> Nil:Cons -> True:False
Nil :: Nil:Cons
Cons :: Nil:Cons -> Nil:Cons -> Nil:Cons
True :: True:False
g :: Nil:Cons -> Nil:Cons -> Nil:Cons
f :: Nil:Cons -> Nil:Cons -> Nil:Cons
notEmpty :: Nil:Cons -> True:False
False :: True:False
g[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons
f[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons
number4 :: Nil:Cons
goal :: Nil:Cons -> Nil:Cons -> Nil:Cons
hole_True:False1_1 :: True:False
hole_Nil:Cons2_1 :: Nil:Cons
gen_Nil:Cons3_1 :: Nat -> Nil:Cons

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

(19) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
lt0, g, f

They will be analysed ascendingly in the following order:
lt0 < g
lt0 < f

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

(20)
Obligation:
Innermost TRS:
Rules:
lt0(Nil, Cons(x', xs)) -> True
lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs)
g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
lt0(x, Nil) -> False
g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
number4 -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil))
g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y))
g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs)
f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y))
f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs)

Types:
lt0 :: Nil:Cons -> Nil:Cons -> True:False
Nil :: Nil:Cons
Cons :: Nil:Cons -> Nil:Cons -> Nil:Cons
True :: True:False
g :: Nil:Cons -> Nil:Cons -> Nil:Cons
f :: Nil:Cons -> Nil:Cons -> Nil:Cons
notEmpty :: Nil:Cons -> True:False
False :: True:False
g[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons
f[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons
number4 :: Nil:Cons
goal :: Nil:Cons -> Nil:Cons -> Nil:Cons
hole_True:False1_1 :: True:False
hole_Nil:Cons2_1 :: Nil:Cons
gen_Nil:Cons3_1 :: Nat -> Nil:Cons


Generator Equations:
gen_Nil:Cons3_1(0) <=> Nil
gen_Nil:Cons3_1(+(x, 1)) <=> Cons(Nil, gen_Nil:Cons3_1(x))


The following defined symbols remain to be analysed:
lt0, g, f

They will be analysed ascendingly in the following order:
lt0 < g
lt0 < f

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

(21) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
lt0(gen_Nil:Cons3_1(n5_1), gen_Nil:Cons3_1(+(1, n5_1))) -> True, rt in Omega(1 + n5_1)

Induction Base:
lt0(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(+(1, 0))) ->_R^Omega(1)
True

Induction Step:
lt0(gen_Nil:Cons3_1(+(n5_1, 1)), gen_Nil:Cons3_1(+(1, +(n5_1, 1)))) ->_R^Omega(1)
lt0(gen_Nil:Cons3_1(n5_1), gen_Nil:Cons3_1(+(1, n5_1))) ->_IH
True

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

(22)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
lt0(Nil, Cons(x', xs)) -> True
lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs)
g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
lt0(x, Nil) -> False
g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
number4 -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil))
g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y))
g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs)
f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y))
f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs)

Types:
lt0 :: Nil:Cons -> Nil:Cons -> True:False
Nil :: Nil:Cons
Cons :: Nil:Cons -> Nil:Cons -> Nil:Cons
True :: True:False
g :: Nil:Cons -> Nil:Cons -> Nil:Cons
f :: Nil:Cons -> Nil:Cons -> Nil:Cons
notEmpty :: Nil:Cons -> True:False
False :: True:False
g[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons
f[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons
number4 :: Nil:Cons
goal :: Nil:Cons -> Nil:Cons -> Nil:Cons
hole_True:False1_1 :: True:False
hole_Nil:Cons2_1 :: Nil:Cons
gen_Nil:Cons3_1 :: Nat -> Nil:Cons


Generator Equations:
gen_Nil:Cons3_1(0) <=> Nil
gen_Nil:Cons3_1(+(x, 1)) <=> Cons(Nil, gen_Nil:Cons3_1(x))


The following defined symbols remain to be analysed:
lt0, g, f

They will be analysed ascendingly in the following order:
lt0 < g
lt0 < f

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

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

(25)
BOUNDS(n^1, INF)

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

(26)
Obligation:
Innermost TRS:
Rules:
lt0(Nil, Cons(x', xs)) -> True
lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs)
g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
lt0(x, Nil) -> False
g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
number4 -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil))
g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y))
g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs)
f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y))
f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs)

Types:
lt0 :: Nil:Cons -> Nil:Cons -> True:False
Nil :: Nil:Cons
Cons :: Nil:Cons -> Nil:Cons -> Nil:Cons
True :: True:False
g :: Nil:Cons -> Nil:Cons -> Nil:Cons
f :: Nil:Cons -> Nil:Cons -> Nil:Cons
notEmpty :: Nil:Cons -> True:False
False :: True:False
g[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons
f[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons
number4 :: Nil:Cons
goal :: Nil:Cons -> Nil:Cons -> Nil:Cons
hole_True:False1_1 :: True:False
hole_Nil:Cons2_1 :: Nil:Cons
gen_Nil:Cons3_1 :: Nat -> Nil:Cons


Lemmas:
lt0(gen_Nil:Cons3_1(n5_1), gen_Nil:Cons3_1(+(1, n5_1))) -> True, rt in Omega(1 + n5_1)


Generator Equations:
gen_Nil:Cons3_1(0) <=> Nil
gen_Nil:Cons3_1(+(x, 1)) <=> Cons(Nil, gen_Nil:Cons3_1(x))


The following defined symbols remain to be analysed:
g, f
----------------------------------------

(27) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
g(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(n359_1)) -> gen_Nil:Cons3_1(4), rt in Omega(1 + n359_1)

Induction Base:
g(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(0)) ->_R^Omega(1)
Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))

Induction Step:
g(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(+(n359_1, 1))) ->_R^Omega(1)
g[Ite][False][Ite](lt0(gen_Nil:Cons3_1(0), Cons(Nil, Nil)), gen_Nil:Cons3_1(0), Cons(Nil, gen_Nil:Cons3_1(n359_1))) ->_L^Omega(1)
g[Ite][False][Ite](True, gen_Nil:Cons3_1(0), Cons(Nil, gen_Nil:Cons3_1(n359_1))) ->_R^Omega(0)
g(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(n359_1)) ->_IH
gen_Nil:Cons3_1(4)

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

(28)
Obligation:
Innermost TRS:
Rules:
lt0(Nil, Cons(x', xs)) -> True
lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs)
g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
lt0(x, Nil) -> False
g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs))
number4 -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))
goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil))
g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y))
g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs)
f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y))
f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs)

Types:
lt0 :: Nil:Cons -> Nil:Cons -> True:False
Nil :: Nil:Cons
Cons :: Nil:Cons -> Nil:Cons -> Nil:Cons
True :: True:False
g :: Nil:Cons -> Nil:Cons -> Nil:Cons
f :: Nil:Cons -> Nil:Cons -> Nil:Cons
notEmpty :: Nil:Cons -> True:False
False :: True:False
g[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons
f[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons
number4 :: Nil:Cons
goal :: Nil:Cons -> Nil:Cons -> Nil:Cons
hole_True:False1_1 :: True:False
hole_Nil:Cons2_1 :: Nil:Cons
gen_Nil:Cons3_1 :: Nat -> Nil:Cons


Lemmas:
lt0(gen_Nil:Cons3_1(n5_1), gen_Nil:Cons3_1(+(1, n5_1))) -> True, rt in Omega(1 + n5_1)
g(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(n359_1)) -> gen_Nil:Cons3_1(4), rt in Omega(1 + n359_1)


Generator Equations:
gen_Nil:Cons3_1(0) <=> Nil
gen_Nil:Cons3_1(+(x, 1)) <=> Cons(Nil, gen_Nil:Cons3_1(x))


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

(29) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
f(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(n1010_1)) -> gen_Nil:Cons3_1(4), rt in Omega(1 + n1010_1)

Induction Base:
f(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(0)) ->_R^Omega(1)
Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil))))

Induction Step:
f(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(+(n1010_1, 1))) ->_R^Omega(1)
f[Ite][False][Ite](lt0(gen_Nil:Cons3_1(0), Cons(Nil, Nil)), gen_Nil:Cons3_1(0), Cons(Nil, gen_Nil:Cons3_1(n1010_1))) ->_L^Omega(1)
f[Ite][False][Ite](True, gen_Nil:Cons3_1(0), Cons(Nil, gen_Nil:Cons3_1(n1010_1))) ->_R^Omega(0)
f(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(n1010_1)) ->_IH
gen_Nil:Cons3_1(4)

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

(30)
BOUNDS(1, INF)