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


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


WORST_CASE(Omega(n^2), O(n^3))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


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

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


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

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


The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(Y)) -> false
   eq(s(X), 0) -> false
   eq(s(X), s(Y)) -> eq(X, Y)
   le(0, Y) -> true
   le(s(X), 0) -> false
   le(s(X), s(Y)) -> le(X, Y)
   min(cons(0, nil)) -> 0
   min(cons(s(N), nil)) -> s(N)
   min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L)))
   ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L))
   ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L))
   replace(N, M, nil) -> nil
   replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L))
   ifrepl(true, N, M, cons(K, L)) -> cons(M, L)
   ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L))
   selsort(nil) -> nil
   selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L))
   ifselsort(true, cons(N, L)) -> cons(N, selsort(L))
   ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L)))

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

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

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


The TRS R consists of the following rules:

   eq(0, 0) -> true [1]
   eq(0, s(Y)) -> false [1]
   eq(s(X), 0) -> false [1]
   eq(s(X), s(Y)) -> eq(X, Y) [1]
   le(0, Y) -> true [1]
   le(s(X), 0) -> false [1]
   le(s(X), s(Y)) -> le(X, Y) [1]
   min(cons(0, nil)) -> 0 [1]
   min(cons(s(N), nil)) -> s(N) [1]
   min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L))) [1]
   ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L)) [1]
   ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L)) [1]
   replace(N, M, nil) -> nil [1]
   replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L)) [1]
   ifrepl(true, N, M, cons(K, L)) -> cons(M, L) [1]
   ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L)) [1]
   selsort(nil) -> nil [1]
   selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L)) [1]
   ifselsort(true, cons(N, L)) -> cons(N, selsort(L)) [1]
   ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L))) [1]

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

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

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

   eq(0, 0) -> true [1]
   eq(0, s(Y)) -> false [1]
   eq(s(X), 0) -> false [1]
   eq(s(X), s(Y)) -> eq(X, Y) [1]
   le(0, Y) -> true [1]
   le(s(X), 0) -> false [1]
   le(s(X), s(Y)) -> le(X, Y) [1]
   min(cons(0, nil)) -> 0 [1]
   min(cons(s(N), nil)) -> s(N) [1]
   min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L))) [1]
   ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L)) [1]
   ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L)) [1]
   replace(N, M, nil) -> nil [1]
   replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L)) [1]
   ifrepl(true, N, M, cons(K, L)) -> cons(M, L) [1]
   ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L)) [1]
   selsort(nil) -> nil [1]
   selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L)) [1]
   ifselsort(true, cons(N, L)) -> cons(N, selsort(L)) [1]
   ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L))) [1]

The TRS has the following type information:
eq :: 0:s -> 0:s -> true:false
0 :: 0:s
true :: true:false
s :: 0:s -> 0:s
false :: true:false
le :: 0:s -> 0:s -> true:false
min :: nil:cons -> 0:s
cons :: 0:s -> nil:cons -> nil:cons
nil :: nil:cons
ifmin :: true:false -> nil:cons -> 0:s
replace :: 0:s -> 0:s -> nil:cons -> nil:cons
ifrepl :: true:false -> 0:s -> 0:s -> nil:cons -> nil:cons
selsort :: nil:cons -> nil:cons
ifselsort :: true:false -> nil:cons -> nil:cons

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

(5) 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:

   min(v0) -> null_min [0]
   ifmin(v0, v1) -> null_ifmin [0]
   ifrepl(v0, v1, v2, v3) -> null_ifrepl [0]
   ifselsort(v0, v1) -> null_ifselsort [0]
   eq(v0, v1) -> null_eq [0]
   le(v0, v1) -> null_le [0]
   replace(v0, v1, v2) -> null_replace [0]
   selsort(v0) -> null_selsort [0]

And the following fresh constants:    null_min, null_ifmin, null_ifrepl, null_ifselsort, null_eq, null_le, null_replace, null_selsort

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

(6)
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:

   eq(0, 0) -> true [1]
   eq(0, s(Y)) -> false [1]
   eq(s(X), 0) -> false [1]
   eq(s(X), s(Y)) -> eq(X, Y) [1]
   le(0, Y) -> true [1]
   le(s(X), 0) -> false [1]
   le(s(X), s(Y)) -> le(X, Y) [1]
   min(cons(0, nil)) -> 0 [1]
   min(cons(s(N), nil)) -> s(N) [1]
   min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L))) [1]
   ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L)) [1]
   ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L)) [1]
   replace(N, M, nil) -> nil [1]
   replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L)) [1]
   ifrepl(true, N, M, cons(K, L)) -> cons(M, L) [1]
   ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L)) [1]
   selsort(nil) -> nil [1]
   selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L)) [1]
   ifselsort(true, cons(N, L)) -> cons(N, selsort(L)) [1]
   ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L))) [1]
   min(v0) -> null_min [0]
   ifmin(v0, v1) -> null_ifmin [0]
   ifrepl(v0, v1, v2, v3) -> null_ifrepl [0]
   ifselsort(v0, v1) -> null_ifselsort [0]
   eq(v0, v1) -> null_eq [0]
   le(v0, v1) -> null_le [0]
   replace(v0, v1, v2) -> null_replace [0]
   selsort(v0) -> null_selsort [0]

The TRS has the following type information:
eq :: 0:s:null_min:null_ifmin -> 0:s:null_min:null_ifmin -> true:false:null_eq:null_le
0 :: 0:s:null_min:null_ifmin
true :: true:false:null_eq:null_le
s :: 0:s:null_min:null_ifmin -> 0:s:null_min:null_ifmin
false :: true:false:null_eq:null_le
le :: 0:s:null_min:null_ifmin -> 0:s:null_min:null_ifmin -> true:false:null_eq:null_le
min :: nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort -> 0:s:null_min:null_ifmin
cons :: 0:s:null_min:null_ifmin -> nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort -> nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort
nil :: nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort
ifmin :: true:false:null_eq:null_le -> nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort -> 0:s:null_min:null_ifmin
replace :: 0:s:null_min:null_ifmin -> 0:s:null_min:null_ifmin -> nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort -> nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort
ifrepl :: true:false:null_eq:null_le -> 0:s:null_min:null_ifmin -> 0:s:null_min:null_ifmin -> nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort -> nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort
selsort :: nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort -> nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort
ifselsort :: true:false:null_eq:null_le -> nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort -> nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort
null_min :: 0:s:null_min:null_ifmin
null_ifmin :: 0:s:null_min:null_ifmin
null_ifrepl :: nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort
null_ifselsort :: nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort
null_eq :: true:false:null_eq:null_le
null_le :: true:false:null_eq:null_le
null_replace :: nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort
null_selsort :: nil:cons:null_ifrepl:null_ifselsort:null_replace:null_selsort

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

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

   0 => 0
   true => 2
   false => 1
   nil => 0
   null_min => 0
   null_ifmin => 0
   null_ifrepl => 0
   null_ifselsort => 0
   null_eq => 0
   null_le => 0
   null_replace => 0
   null_selsort => 0

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

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

   eq(z, z') -{ 1 }-> eq(X, Y) :|: z = 1 + X, Y >= 0, z' = 1 + Y, X >= 0
   eq(z, z') -{ 1 }-> 2 :|: z = 0, z' = 0
   eq(z, z') -{ 1 }-> 1 :|: Y >= 0, z' = 1 + Y, z = 0
   eq(z, z') -{ 1 }-> 1 :|: z = 1 + X, X >= 0, z' = 0
   eq(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   ifmin(z, z') -{ 1 }-> min(1 + M + L) :|: z = 1, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0
   ifmin(z, z') -{ 1 }-> min(1 + N + L) :|: z = 2, z' = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0
   ifmin(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   ifrepl(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0
   ifrepl(z, z', z'', z1) -{ 1 }-> 1 + K + replace(N, M, L) :|: z = 1, K >= 0, z' = N, L >= 0, M >= 0, z'' = M, z1 = 1 + K + L, N >= 0
   ifrepl(z, z', z'', z1) -{ 1 }-> 1 + M + L :|: z = 2, K >= 0, z' = N, L >= 0, M >= 0, z'' = M, z1 = 1 + K + L, N >= 0
   ifselsort(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   ifselsort(z, z') -{ 1 }-> 1 + N + selsort(L) :|: z = 2, L >= 0, z' = 1 + N + L, N >= 0
   ifselsort(z, z') -{ 1 }-> 1 + min(1 + N + L) + selsort(replace(min(1 + N + L), N, L)) :|: z = 1, L >= 0, z' = 1 + N + L, N >= 0
   le(z, z') -{ 1 }-> le(X, Y) :|: z = 1 + X, Y >= 0, z' = 1 + Y, X >= 0
   le(z, z') -{ 1 }-> 2 :|: z' = Y, Y >= 0, z = 0
   le(z, z') -{ 1 }-> 1 :|: z = 1 + X, X >= 0, z' = 0
   le(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
   min(z) -{ 1 }-> ifmin(le(N, M), 1 + N + (1 + M + L)) :|: z = 1 + N + (1 + M + L), L >= 0, M >= 0, N >= 0
   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
   min(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
   min(z) -{ 1 }-> 1 + N :|: z = 1 + (1 + N) + 0, N >= 0
   replace(z, z', z'') -{ 1 }-> ifrepl(eq(N, K), N, M, 1 + K + L) :|: z' = M, K >= 0, z = N, z'' = 1 + K + L, L >= 0, M >= 0, N >= 0
   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = M, z = N, M >= 0, N >= 0
   replace(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0
   selsort(z) -{ 1 }-> ifselsort(eq(N, min(1 + N + L)), 1 + N + L) :|: z = 1 + N + L, L >= 0, N >= 0
   selsort(z) -{ 1 }-> 0 :|: z = 0
   selsort(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0

Only complete derivations are relevant for the runtime complexity.

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

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

eq(start(V1, V, V2, V3),0,[eq(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V2, V3),0,[le(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V2, V3),0,[min(V1, Out)],[V1 >= 0]).
eq(start(V1, V, V2, V3),0,[ifmin(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(start(V1, V, V2, V3),0,[replace(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]).
eq(start(V1, V, V2, V3),0,[ifrepl(V1, V, V2, V3, Out)],[V1 >= 0,V >= 0,V2 >= 0,V3 >= 0]).
eq(start(V1, V, V2, V3),0,[selsort(V1, Out)],[V1 >= 0]).
eq(start(V1, V, V2, V3),0,[ifselsort(V1, V, Out)],[V1 >= 0,V >= 0]).
eq(eq(V1, V, Out),1,[],[Out = 2,V1 = 0,V = 0]).
eq(eq(V1, V, Out),1,[],[Out = 1,Y1 >= 0,V = 1 + Y1,V1 = 0]).
eq(eq(V1, V, Out),1,[],[Out = 1,V1 = 1 + X1,X1 >= 0,V = 0]).
eq(eq(V1, V, Out),1,[eq(X2, Y2, Ret)],[Out = Ret,V1 = 1 + X2,Y2 >= 0,V = 1 + Y2,X2 >= 0]).
eq(le(V1, V, Out),1,[],[Out = 2,V = Y3,Y3 >= 0,V1 = 0]).
eq(le(V1, V, Out),1,[],[Out = 1,V1 = 1 + X3,X3 >= 0,V = 0]).
eq(le(V1, V, Out),1,[le(X4, Y4, Ret1)],[Out = Ret1,V1 = 1 + X4,Y4 >= 0,V = 1 + Y4,X4 >= 0]).
eq(min(V1, Out),1,[],[Out = 0,V1 = 1]).
eq(min(V1, Out),1,[],[Out = 1 + N1,V1 = 2 + N1,N1 >= 0]).
eq(min(V1, Out),1,[le(N2, M1, Ret0),ifmin(Ret0, 1 + N2 + (1 + M1 + L1), Ret2)],[Out = Ret2,V1 = 2 + L1 + M1 + N2,L1 >= 0,M1 >= 0,N2 >= 0]).
eq(ifmin(V1, V, Out),1,[min(1 + N3 + L2, Ret3)],[Out = Ret3,V1 = 2,V = 2 + L2 + M2 + N3,L2 >= 0,M2 >= 0,N3 >= 0]).
eq(ifmin(V1, V, Out),1,[min(1 + M3 + L3, Ret4)],[Out = Ret4,V1 = 1,V = 2 + L3 + M3 + N4,L3 >= 0,M3 >= 0,N4 >= 0]).
eq(replace(V1, V, V2, Out),1,[],[Out = 0,V2 = 0,V = M4,V1 = N5,M4 >= 0,N5 >= 0]).
eq(replace(V1, V, V2, Out),1,[eq(N6, K1, Ret01),ifrepl(Ret01, N6, M5, 1 + K1 + L4, Ret5)],[Out = Ret5,V = M5,K1 >= 0,V1 = N6,V2 = 1 + K1 + L4,L4 >= 0,M5 >= 0,N6 >= 0]).
eq(ifrepl(V1, V, V2, V3, Out),1,[],[Out = 1 + L5 + M6,V1 = 2,K2 >= 0,V = N7,L5 >= 0,M6 >= 0,V2 = M6,V3 = 1 + K2 + L5,N7 >= 0]).
eq(ifrepl(V1, V, V2, V3, Out),1,[replace(N8, M7, L6, Ret11)],[Out = 1 + K3 + Ret11,V1 = 1,K3 >= 0,V = N8,L6 >= 0,M7 >= 0,V2 = M7,V3 = 1 + K3 + L6,N8 >= 0]).
eq(selsort(V1, Out),1,[],[Out = 0,V1 = 0]).
eq(selsort(V1, Out),1,[min(1 + N9 + L7, Ret011),eq(N9, Ret011, Ret02),ifselsort(Ret02, 1 + N9 + L7, Ret6)],[Out = Ret6,V1 = 1 + L7 + N9,L7 >= 0,N9 >= 0]).
eq(ifselsort(V1, V, Out),1,[selsort(L8, Ret12)],[Out = 1 + N10 + Ret12,V1 = 2,L8 >= 0,V = 1 + L8 + N10,N10 >= 0]).
eq(ifselsort(V1, V, Out),1,[min(1 + N11 + L9, Ret012),min(1 + N11 + L9, Ret100),replace(Ret100, N11, L9, Ret10),selsort(Ret10, Ret13)],[Out = 1 + Ret012 + Ret13,V1 = 1,L9 >= 0,V = 1 + L9 + N11,N11 >= 0]).
eq(min(V1, Out),0,[],[Out = 0,V4 >= 0,V1 = V4]).
eq(ifmin(V1, V, Out),0,[],[Out = 0,V6 >= 0,V5 >= 0,V1 = V6,V = V5]).
eq(ifrepl(V1, V, V2, V3, Out),0,[],[Out = 0,V3 = V9,V8 >= 0,V2 = V10,V7 >= 0,V1 = V8,V = V7,V10 >= 0,V9 >= 0]).
eq(ifselsort(V1, V, Out),0,[],[Out = 0,V11 >= 0,V12 >= 0,V1 = V11,V = V12]).
eq(eq(V1, V, Out),0,[],[Out = 0,V13 >= 0,V14 >= 0,V1 = V13,V = V14]).
eq(le(V1, V, Out),0,[],[Out = 0,V16 >= 0,V15 >= 0,V1 = V16,V = V15]).
eq(replace(V1, V, V2, Out),0,[],[Out = 0,V18 >= 0,V2 = V19,V17 >= 0,V1 = V18,V = V17,V19 >= 0]).
eq(selsort(V1, Out),0,[],[Out = 0,V20 >= 0,V1 = V20]).
input_output_vars(eq(V1,V,Out),[V1,V],[Out]).
input_output_vars(le(V1,V,Out),[V1,V],[Out]).
input_output_vars(min(V1,Out),[V1],[Out]).
input_output_vars(ifmin(V1,V,Out),[V1,V],[Out]).
input_output_vars(replace(V1,V,V2,Out),[V1,V,V2],[Out]).
input_output_vars(ifrepl(V1,V,V2,V3,Out),[V1,V,V2,V3],[Out]).
input_output_vars(selsort(V1,Out),[V1],[Out]).
input_output_vars(ifselsort(V1,V,Out),[V1,V],[Out]).


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

#### Computed strongly connected components 
0. recursive  : [eq/3]
1. recursive  : [le/3]
2. recursive  : [ifmin/3,min/2]
3. recursive  : [ifrepl/5,replace/4]
4. recursive  : [ifselsort/3,selsort/2]
5. non_recursive  : [start/4]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into eq/3
1. SCC is partially evaluated into le/3
2. SCC is partially evaluated into min/2
3. SCC is partially evaluated into replace/4
4. SCC is partially evaluated into selsort/2
5. SCC is partially evaluated into start/4

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

### Specialization of cost equations eq/3 
* CE 33 is refined into CE [38] 
* CE 31 is refined into CE [39] 
* CE 30 is refined into CE [40] 
* CE 29 is refined into CE [41] 
* CE 32 is refined into CE [42] 


### Cost equations --> "Loop" of eq/3 
* CEs [42] --> Loop 22 
* CEs [38] --> Loop 23 
* CEs [39] --> Loop 24 
* CEs [40] --> Loop 25 
* CEs [41] --> Loop 26 

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

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


### Specialization of cost equations le/3 
* CE 37 is refined into CE [43] 
* CE 35 is refined into CE [44] 
* CE 34 is refined into CE [45] 
* CE 36 is refined into CE [46] 


### Cost equations --> "Loop" of le/3 
* CEs [46] --> Loop 27 
* CEs [43] --> Loop 28 
* CEs [44] --> Loop 29 
* CEs [45] --> Loop 30 

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

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


### Specialization of cost equations min/2 
* CE 17 is refined into CE [47] 
* CE 13 is refined into CE [48,49,50,51,52] 
* CE 16 is refined into CE [53] 
* CE 18 is refined into CE [54] 
* CE 14 is refined into CE [55,56] 
* CE 15 is refined into CE [57,58] 


### Cost equations --> "Loop" of min/2 
* CEs [55,56,57,58] --> Loop 31 
* CEs [47] --> Loop 32 
* CEs [48,49,50,51,52,53,54] --> Loop 33 

### Ranking functions of CR min(V1,Out) 
* RF of phase [31]: [V1-1]

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


### Specialization of cost equations replace/4 
* CE 21 is refined into CE [59,60] 
* CE 19 is refined into CE [61,62,63,64,65,66,67] 
* CE 22 is refined into CE [68] 
* CE 23 is refined into CE [69] 
* CE 20 is refined into CE [70,71,72,73] 


### Cost equations --> "Loop" of replace/4 
* CEs [71,72,73] --> Loop 34 
* CEs [70] --> Loop 35 
* CEs [60] --> Loop 36 
* CEs [68] --> Loop 37 
* CEs [59] --> Loop 38 
* CEs [61,62,63,64,65,66,67,69] --> Loop 39 

### Ranking functions of CR replace(V1,V,V2,Out) 
* RF of phase [34]: [V2]
* RF of phase [35]: [V2-1]

#### Partial ranking functions of CR replace(V1,V,V2,Out) 
* Partial RF of phase [34]:
  - RF of loop [34:1]:
    V2
* Partial RF of phase [35]:
  - RF of loop [35:1]:
    V2-1


### Specialization of cost equations selsort/2 
* CE 24 is refined into CE [74,75,76,77,78,79,80,81,82,83,84,85] 
* CE 27 is refined into CE [86] 
* CE 28 is refined into CE [87] 
* CE 25 is refined into CE [88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231] 
* CE 26 is refined into CE [232,233,234] 


### Cost equations --> "Loop" of selsort/2 
* CEs [104,105,108,110,111,128,129,132,134,135,152,153,156,158,159,176,177,180,182,183,200,201,204,206,207,224,225,228,230,231] --> Loop 40 
* CEs [96,97,100,102,103,120,121,124,126,127,144,145,148,150,151,168,169,172,174,175,192,193,196,198,199,216,217,220,222,223] --> Loop 41 
* CEs [88,89,92,94,95,112,113,116,118,119,136,137,140,142,143,160,161,164,166,167,184,185,188,190,191,208,209,212,214,215] --> Loop 42 
* CEs [106,107,109,130,131,133,154,155,157,178,179,181,202,203,205,226,227,229] --> Loop 43 
* CEs [98,99,101,122,123,125,146,147,149,170,171,173,194,195,197,218,219,221,232,233,234] --> Loop 44 
* CEs [90,91,93,114,115,117,138,139,141,162,163,165,186,187,189,210,211,213] --> Loop 45 
* CEs [74,75,76,77,78,79,80,81,82,83,84,85,86,87] --> Loop 46 

### Ranking functions of CR selsort(V1,Out) 
* RF of phase [40,41,42,44]: [V1]

#### Partial ranking functions of CR selsort(V1,Out) 
* Partial RF of phase [40,41,42,44]:
  - RF of loop [40:1]:
    V1-2
  - RF of loop [41:1,42:1]:
    V1-1
  - RF of loop [44:1]:
    V1


### Specialization of cost equations start/4 
* CE 3 is refined into CE [235,236] 
* CE 7 is refined into CE [237,238,239] 
* CE 5 is refined into CE [240] 
* CE 2 is refined into CE [241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279] 
* CE 6 is refined into CE [280,281,282] 
* CE 1 is refined into CE [283] 
* CE 4 is refined into CE [284,285,286,287,288] 
* CE 8 is refined into CE [289,290,291,292,293,294,295] 
* CE 9 is refined into CE [296,297,298,299,300] 
* CE 10 is refined into CE [301,302,303] 
* CE 11 is refined into CE [304,305,306,307,308] 
* CE 12 is refined into CE [309,310] 


### Cost equations --> "Loop" of start/4 
* CEs [295] --> Loop 47 
* CEs [291,297] --> Loop 48 
* CEs [235,236,237,238,239] --> Loop 49 
* CEs [240] --> Loop 50 
* CEs [241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282] --> Loop 51 
* CEs [284,285,286,287,288] --> Loop 52 
* CEs [283,289,290,292,293,294,296,298,299,300,301,302,303,304,305,306,307,308,309,310] --> Loop 53 

### Ranking functions of CR start(V1,V,V2,V3) 

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


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

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

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

* Chain [[22],25]: 1*it(22)+1
  Such that:it(22) =< V1

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

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

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

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

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

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

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

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

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


#### Cost of chains of le(V1,V,Out):
* Chain [[27],30]: 1*it(27)+1
  Such that:it(27) =< V1

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

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

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

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

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

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

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

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


#### Cost of chains of min(V1,Out):
* Chain [[31],33]: 6*it(31)+2*s(10)+2
  Such that:aux(3) =< V1/2
aux(4) =< V1
it(31) =< aux(4)
s(11) =< it(31)*aux(3)
s(10) =< s(11)

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

* Chain [[31],32]: 3*it(31)+2*s(10)+1
  Such that:it(31) =< V1-Out
aux(3) =< V1/2
s(11) =< it(31)*aux(3)
s(10) =< s(11)

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

* Chain [33]: 1*s(3)+2*s(4)+2
  Such that:s(3) =< V1
aux(1) =< V1/2
s(4) =< aux(1)

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

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


#### Cost of chains of replace(V1,V,V2,Out):
* Chain [[35],39]: 3*it(35)+2*s(20)+2
  Such that:aux(8) =< V2-Out
it(35) =< Out
s(20) =< aux(8)

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

* Chain [[35],38]: 3*it(35)+3
  Such that:it(35) =< -V+Out

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

* Chain [[35],37]: 3*it(35)+1
  Such that:it(35) =< Out

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

* Chain [[34],39]: 3*it(34)+2*s(20)+2*s(21)+1*s(28)+1*s(29)+2
  Such that:aux(11) =< V2
aux(8) =< V2-Out
it(34) =< Out
aux(12) =< V1
s(21) =< aux(12)
s(20) =< aux(8)
it(34) =< aux(11)
s(28) =< it(34)*aux(12)
s(29) =< it(34)*aux(11)

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

* Chain [[34],37]: 3*it(34)+1*s(28)+1*s(29)+1
  Such that:aux(10) =< V1
aux(13) =< Out
it(34) =< aux(13)
s(28) =< it(34)*aux(10)
s(29) =< it(34)*aux(13)

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

* Chain [[34],36]: 3*it(34)+1*s(28)+1*s(29)+1*s(30)+3
  Such that:it(34) =< -V1+V2
aux(11) =< V2
aux(14) =< V1
s(30) =< aux(14)
it(34) =< aux(11)
s(28) =< it(34)*aux(14)
s(29) =< it(34)*aux(11)

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

* Chain [39]: 2*s(20)+2*s(21)+2
  Such that:aux(7) =< V1
aux(8) =< V2
s(21) =< aux(7)
s(20) =< aux(8)

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

* Chain [38]: 3
  with precondition: [V1=0,V>=0,Out>=V+1,V+V2>=Out] 

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

* Chain [36]: 1*s(30)+3
  Such that:s(30) =< V1

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


#### Cost of chains of selsort(V1,Out):
* Chain [[40,41,42,44],46]: 201*it(40)+16*s(65)+1296*s(1969)+182*s(1970)+436*s(1971)+270*s(1972)+108*s(1974)+36*s(1975)+12*s(1976)+72*s(1977)+36*s(1978)+24*s(1991)+4
  Such that:aux(239) =< V1
it(40) =< aux(239)
s(64) =< it(40)*aux(239)
s(65) =< s(64)
aux(226) =< aux(239)+1
aux(228) =< aux(239)
s(663) =< aux(239)*(1/2)+1/2
aux(227) =< it(40)*aux(226)
s(1980) =< it(40)*aux(228)
s(1982) =< aux(227)*(1/2)
s(1969) =< aux(227)
s(1970) =< s(1982)
s(1983) =< s(1969)*s(663)
s(1971) =< s(1983)
s(1972) =< s(1980)
s(1978) =< s(1969)*aux(226)
s(1974) =< s(1980)
s(1975) =< s(1972)*aux(226)
s(1991) =< s(1972)*aux(228)
s(1974) =< aux(227)
s(1977) =< s(1974)*aux(226)
s(1976) =< s(1972)*aux(239)

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

* Chain [[40,41,42,44],45,46]: 509*it(40)+1296*s(1969)+182*s(1970)+436*s(1971)+270*s(1972)+108*s(1974)+36*s(1975)+12*s(1976)+72*s(1977)+36*s(1978)+24*s(1991)+84*s(2025)+15
  Such that:aux(277) =< V1
it(40) =< aux(277)
s(2024) =< it(40)*aux(277)
s(2025) =< s(2024)
aux(226) =< aux(277)+1
aux(228) =< aux(277)
s(663) =< aux(277)*(1/2)+1/2
aux(227) =< it(40)*aux(226)
s(1980) =< it(40)*aux(228)
s(1982) =< aux(227)*(1/2)
s(1969) =< aux(227)
s(1970) =< s(1982)
s(1983) =< s(1969)*s(663)
s(1971) =< s(1983)
s(1972) =< s(1980)
s(1978) =< s(1969)*aux(226)
s(1974) =< s(1980)
s(1975) =< s(1972)*aux(226)
s(1991) =< s(1972)*aux(228)
s(1974) =< aux(227)
s(1977) =< s(1974)*aux(226)
s(1976) =< s(1972)*aux(277)

  with precondition: [V1>=3,Out>=2] 

* Chain [[40,41,42,44],43,46]: 401*it(40)+1296*s(1969)+182*s(1970)+436*s(1971)+270*s(1972)+108*s(1974)+36*s(1975)+12*s(1976)+72*s(1977)+36*s(1978)+24*s(1991)+84*s(2328)+14
  Such that:aux(315) =< V1
it(40) =< aux(315)
s(2327) =< it(40)*aux(315)
s(2328) =< s(2327)
aux(226) =< aux(315)+1
aux(228) =< aux(315)
s(663) =< aux(315)*(1/2)+1/2
aux(227) =< it(40)*aux(226)
s(1980) =< it(40)*aux(228)
s(1982) =< aux(227)*(1/2)
s(1969) =< aux(227)
s(1970) =< s(1982)
s(1983) =< s(1969)*s(663)
s(1971) =< s(1983)
s(1972) =< s(1980)
s(1978) =< s(1969)*aux(226)
s(1974) =< s(1980)
s(1975) =< s(1972)*aux(226)
s(1991) =< s(1972)*aux(228)
s(1974) =< aux(227)
s(1977) =< s(1974)*aux(226)
s(1976) =< s(1972)*aux(315)

  with precondition: [V1>=4,Out>=3] 

* Chain [46]: 43*s(62)+6*s(63)+16*s(65)+4
  Such that:aux(23) =< V1
aux(24) =< V1/2
s(62) =< aux(23)
s(63) =< aux(24)
s(64) =< s(62)*aux(24)
s(65) =< s(64)

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

* Chain [45,46]: 303*s(2022)+54*s(2023)+84*s(2025)+15
  Such that:aux(274) =< V1
aux(275) =< V1/2
s(2022) =< aux(274)
s(2023) =< aux(275)
s(2024) =< s(2022)*aux(275)
s(2025) =< s(2024)

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

* Chain [43,46]: 231*s(2325)+18*s(2326)+84*s(2328)+14
  Such that:aux(312) =< V1
aux(313) =< V1/2
s(2325) =< aux(312)
s(2326) =< aux(313)
s(2327) =< s(2325)*aux(313)
s(2328) =< s(2327)

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


#### Cost of chains of start(V1,V,V2,V3):
* Chain [53]: 4*s(2665)+1706*s(2666)+80*s(2674)+188*s(2676)+21*s(2683)+2*s(2696)+2*s(2697)+3*s(2702)+1*s(2706)+1*s(2707)+184*s(2721)+3888*s(2728)+546*s(2729)+1308*s(2731)+810*s(2732)+108*s(2733)+324*s(2734)+108*s(2735)+72*s(2736)+216*s(2737)+36*s(2738)+15
  Such that:s(2702) =< -V1+V2
aux(320) =< V1
aux(321) =< V1/2
aux(322) =< V
aux(323) =< V2
s(2666) =< aux(320)
s(2665) =< aux(322)
s(2683) =< aux(323)
s(2702) =< aux(323)
s(2706) =< s(2702)*aux(320)
s(2707) =< s(2702)*aux(323)
s(2674) =< aux(321)
s(2675) =< s(2666)*aux(321)
s(2676) =< s(2675)
s(2696) =< s(2683)*aux(320)
s(2697) =< s(2683)*aux(323)
s(2720) =< s(2666)*aux(320)
s(2721) =< s(2720)
s(2722) =< aux(320)+1
s(2723) =< aux(320)
s(2724) =< aux(320)*(1/2)+1/2
s(2725) =< s(2666)*s(2722)
s(2726) =< s(2666)*s(2723)
s(2727) =< s(2725)*(1/2)
s(2728) =< s(2725)
s(2729) =< s(2727)
s(2730) =< s(2728)*s(2724)
s(2731) =< s(2730)
s(2732) =< s(2726)
s(2733) =< s(2728)*s(2722)
s(2734) =< s(2726)
s(2735) =< s(2732)*s(2722)
s(2736) =< s(2732)*s(2723)
s(2734) =< s(2725)
s(2737) =< s(2734)*s(2722)
s(2738) =< s(2732)*aux(320)

  with precondition: [V1>=0] 

* Chain [52]: 21*s(2741)+6*s(2746)+2*s(2754)+2*s(2755)+3*s(2760)+1*s(2764)+1*s(2765)+4
  Such that:s(2760) =< -V+V3
aux(326) =< V
aux(327) =< V3
s(2741) =< aux(327)
s(2746) =< aux(326)
s(2760) =< aux(327)
s(2764) =< s(2760)*aux(326)
s(2765) =< s(2760)*aux(327)
s(2754) =< s(2741)*aux(326)
s(2755) =< s(2741)*aux(327)

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

* Chain [51]: 26558*s(2768)+526*s(2769)+1220*s(2771)+4416*s(2787)+58320*s(2818)+8190*s(2819)+19620*s(2821)+12150*s(2822)+1620*s(2823)+4860*s(2824)+1620*s(2825)+1080*s(2826)+3240*s(2827)+540*s(2828)+60*s(2936)+23
  Such that:aux(400) =< V
aux(401) =< V/2
s(2768) =< aux(400)
s(2786) =< s(2768)*aux(400)
s(2787) =< s(2786)
s(2769) =< aux(401)
s(2770) =< s(2768)*aux(401)
s(2771) =< s(2770)
s(2812) =< aux(400)+1
s(2813) =< aux(400)
s(2814) =< aux(400)*(1/2)+1/2
s(2815) =< s(2768)*s(2812)
s(2816) =< s(2768)*s(2813)
s(2817) =< s(2815)*(1/2)
s(2818) =< s(2815)
s(2819) =< s(2817)
s(2820) =< s(2818)*s(2814)
s(2821) =< s(2820)
s(2822) =< s(2816)
s(2823) =< s(2818)*s(2812)
s(2824) =< s(2816)
s(2825) =< s(2822)*s(2812)
s(2826) =< s(2822)*s(2813)
s(2824) =< s(2815)
s(2827) =< s(2824)*s(2812)
s(2828) =< s(2822)*aux(400)
s(2936) =< s(2768)*aux(400)

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

* Chain [50]: 1
  with precondition: [V1=2,V>=0,V2>=0,V3>=1] 

* Chain [49]: 1698*s(3823)+80*s(3824)+188*s(3826)+184*s(3834)+3888*s(3841)+546*s(3842)+1308*s(3844)+810*s(3845)+108*s(3846)+324*s(3847)+108*s(3848)+72*s(3849)+216*s(3850)+36*s(3851)+16
  Such that:aux(402) =< V
aux(403) =< V/2
s(3823) =< aux(402)
s(3824) =< aux(403)
s(3825) =< s(3823)*aux(403)
s(3826) =< s(3825)
s(3833) =< s(3823)*aux(402)
s(3834) =< s(3833)
s(3835) =< aux(402)+1
s(3836) =< aux(402)
s(3837) =< aux(402)*(1/2)+1/2
s(3838) =< s(3823)*s(3835)
s(3839) =< s(3823)*s(3836)
s(3840) =< s(3838)*(1/2)
s(3841) =< s(3838)
s(3842) =< s(3840)
s(3843) =< s(3841)*s(3837)
s(3844) =< s(3843)
s(3845) =< s(3839)
s(3846) =< s(3841)*s(3835)
s(3847) =< s(3839)
s(3848) =< s(3845)*s(3835)
s(3849) =< s(3845)*s(3836)
s(3847) =< s(3838)
s(3850) =< s(3847)*s(3835)
s(3851) =< s(3845)*aux(402)

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

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

* Chain [47]: 1*s(3862)+1
  Such that:s(3862) =< V

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


Closed-form bounds of start(V1,V,V2,V3): 
-------------------------------------
* Chain [53] with precondition: [V1>=0] 
    - Upper bound: 6629*V1+15+7327*V1*V1+1194*V1*V1*V1+2*V1*nat(V2)+nat(-V1+V2)*V1+V1/2*(188*V1)+nat(V)*4+nat(V2)*21+nat(V2)*2*nat(V2)+nat(-V1+V2)*nat(V2)+nat(-V1+V2)*3+40*V1 
    - Complexity: n^3 
* Chain [52] with precondition: [V1=1,V>=0,V2>=0,V3>=1] 
    - Upper bound: 6*V+4+2*V*V3+nat(-V+V3)*V+21*V3+2*V3*V3+nat(-V+V3)*V3+nat(-V+V3)*3 
    - Complexity: n^2 
* Chain [51] with precondition: [V1=1,V>=1] 
    - Upper bound: 100403*V+23+111621*V*V+17910*V*V*V+V/2*(1220*V)+263*V 
    - Complexity: n^3 
* Chain [50] with precondition: [V1=2,V>=0,V2>=0,V3>=1] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [49] with precondition: [V1=2,V>=1] 
    - Upper bound: 6621*V+16+7327*V*V+1194*V*V*V+V/2*(188*V)+40*V 
    - Complexity: n^3 
* Chain [48] with precondition: [V=0,V1>=1] 
    - Upper bound: 1 
    - Complexity: constant 
* Chain [47] with precondition: [V1=V,V1>=1] 
    - Upper bound: V+1 
    - Complexity: n 

### Maximum cost of start(V1,V,V2,V3): nat(V)*3+3+max([nat(V)*2+max([nat(V)*2*nat(V3)+nat(-V+V3)*nat(V)+nat(V3)*21+nat(V3)*2*nat(V3)+nat(-V+V3)*nat(V3)+nat(-V+V3)*3,nat(V)*93782+7+nat(V)*104294*nat(V)+nat(V)*16716*nat(V)*nat(V)+nat(V)*1032*nat(V/2)+nat(V/2)*446+(nat(V)*6615+12+nat(V)*7327*nat(V)+nat(V)*1194*nat(V)*nat(V)+nat(V)*188*nat(V/2)+nat(V/2)*80)]),6629*V1+11+7327*V1*V1+1194*V1*V1*V1+2*V1*nat(V2)+nat(-V1+V2)*V1+V1/2*(188*V1)+nat(V2)*21+nat(V2)*2*nat(V2)+nat(-V1+V2)*nat(V2)+nat(-V1+V2)*3+40*V1])+nat(V)+1 
Asymptotic class: n^3 
* Total analysis performed in 5497 ms.


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

(10)
BOUNDS(1, n^3)

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

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

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


The TRS R consists of the following rules:

   eq(0', 0') -> true
   eq(0', s(Y)) -> false
   eq(s(X), 0') -> false
   eq(s(X), s(Y)) -> eq(X, Y)
   le(0', Y) -> true
   le(s(X), 0') -> false
   le(s(X), s(Y)) -> le(X, Y)
   min(cons(0', nil)) -> 0'
   min(cons(s(N), nil)) -> s(N)
   min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L)))
   ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L))
   ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L))
   replace(N, M, nil) -> nil
   replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L))
   ifrepl(true, N, M, cons(K, L)) -> cons(M, L)
   ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L))
   selsort(nil) -> nil
   selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L))
   ifselsort(true, cons(N, L)) -> cons(N, selsort(L))
   ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L)))

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

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

(14)
Obligation:
Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(Y)) -> false
eq(s(X), 0') -> false
eq(s(X), s(Y)) -> eq(X, Y)
le(0', Y) -> true
le(s(X), 0') -> false
le(s(X), s(Y)) -> le(X, Y)
min(cons(0', nil)) -> 0'
min(cons(s(N), nil)) -> s(N)
min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L)))
ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L))
ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L))
replace(N, M, nil) -> nil
replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L))
ifrepl(true, N, M, cons(K, L)) -> cons(M, L)
ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L))
selsort(nil) -> nil
selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L))
ifselsort(true, cons(N, L)) -> cons(N, selsort(L))
ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L)))

Types:
eq :: 0':s -> 0':s -> true:false
0' :: 0':s
true :: true:false
s :: 0':s -> 0':s
false :: true:false
le :: 0':s -> 0':s -> true:false
min :: nil:cons -> 0':s
cons :: 0':s -> nil:cons -> nil:cons
nil :: nil:cons
ifmin :: true:false -> nil:cons -> 0':s
replace :: 0':s -> 0':s -> nil:cons -> nil:cons
ifrepl :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
selsort :: nil:cons -> nil:cons
ifselsort :: true:false -> nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_0':s2_0 :: 0':s
hole_nil:cons3_0 :: nil:cons
gen_0':s4_0 :: Nat -> 0':s
gen_nil:cons5_0 :: Nat -> nil:cons

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

(15) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
eq, le, min, replace, selsort

They will be analysed ascendingly in the following order:
eq < replace
eq < selsort
le < min
min < selsort
replace < selsort

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

(16)
Obligation:
Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(Y)) -> false
eq(s(X), 0') -> false
eq(s(X), s(Y)) -> eq(X, Y)
le(0', Y) -> true
le(s(X), 0') -> false
le(s(X), s(Y)) -> le(X, Y)
min(cons(0', nil)) -> 0'
min(cons(s(N), nil)) -> s(N)
min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L)))
ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L))
ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L))
replace(N, M, nil) -> nil
replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L))
ifrepl(true, N, M, cons(K, L)) -> cons(M, L)
ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L))
selsort(nil) -> nil
selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L))
ifselsort(true, cons(N, L)) -> cons(N, selsort(L))
ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L)))

Types:
eq :: 0':s -> 0':s -> true:false
0' :: 0':s
true :: true:false
s :: 0':s -> 0':s
false :: true:false
le :: 0':s -> 0':s -> true:false
min :: nil:cons -> 0':s
cons :: 0':s -> nil:cons -> nil:cons
nil :: nil:cons
ifmin :: true:false -> nil:cons -> 0':s
replace :: 0':s -> 0':s -> nil:cons -> nil:cons
ifrepl :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
selsort :: nil:cons -> nil:cons
ifselsort :: true:false -> nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_0':s2_0 :: 0':s
hole_nil:cons3_0 :: nil:cons
gen_0':s4_0 :: Nat -> 0':s
gen_nil:cons5_0 :: Nat -> nil:cons


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


The following defined symbols remain to be analysed:
eq, le, min, replace, selsort

They will be analysed ascendingly in the following order:
eq < replace
eq < selsort
le < min
min < selsort
replace < selsort

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

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

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

Induction Step:
eq(gen_0':s4_0(+(n7_0, 1)), gen_0':s4_0(+(n7_0, 1))) ->_R^Omega(1)
eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) ->_IH
true

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

(18)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(Y)) -> false
eq(s(X), 0') -> false
eq(s(X), s(Y)) -> eq(X, Y)
le(0', Y) -> true
le(s(X), 0') -> false
le(s(X), s(Y)) -> le(X, Y)
min(cons(0', nil)) -> 0'
min(cons(s(N), nil)) -> s(N)
min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L)))
ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L))
ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L))
replace(N, M, nil) -> nil
replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L))
ifrepl(true, N, M, cons(K, L)) -> cons(M, L)
ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L))
selsort(nil) -> nil
selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L))
ifselsort(true, cons(N, L)) -> cons(N, selsort(L))
ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L)))

Types:
eq :: 0':s -> 0':s -> true:false
0' :: 0':s
true :: true:false
s :: 0':s -> 0':s
false :: true:false
le :: 0':s -> 0':s -> true:false
min :: nil:cons -> 0':s
cons :: 0':s -> nil:cons -> nil:cons
nil :: nil:cons
ifmin :: true:false -> nil:cons -> 0':s
replace :: 0':s -> 0':s -> nil:cons -> nil:cons
ifrepl :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
selsort :: nil:cons -> nil:cons
ifselsort :: true:false -> nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_0':s2_0 :: 0':s
hole_nil:cons3_0 :: nil:cons
gen_0':s4_0 :: Nat -> 0':s
gen_nil:cons5_0 :: Nat -> nil:cons


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


The following defined symbols remain to be analysed:
eq, le, min, replace, selsort

They will be analysed ascendingly in the following order:
eq < replace
eq < selsort
le < min
min < selsort
replace < selsort

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

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

(21)
BOUNDS(n^1, INF)

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

(22)
Obligation:
Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(Y)) -> false
eq(s(X), 0') -> false
eq(s(X), s(Y)) -> eq(X, Y)
le(0', Y) -> true
le(s(X), 0') -> false
le(s(X), s(Y)) -> le(X, Y)
min(cons(0', nil)) -> 0'
min(cons(s(N), nil)) -> s(N)
min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L)))
ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L))
ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L))
replace(N, M, nil) -> nil
replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L))
ifrepl(true, N, M, cons(K, L)) -> cons(M, L)
ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L))
selsort(nil) -> nil
selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L))
ifselsort(true, cons(N, L)) -> cons(N, selsort(L))
ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L)))

Types:
eq :: 0':s -> 0':s -> true:false
0' :: 0':s
true :: true:false
s :: 0':s -> 0':s
false :: true:false
le :: 0':s -> 0':s -> true:false
min :: nil:cons -> 0':s
cons :: 0':s -> nil:cons -> nil:cons
nil :: nil:cons
ifmin :: true:false -> nil:cons -> 0':s
replace :: 0':s -> 0':s -> nil:cons -> nil:cons
ifrepl :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
selsort :: nil:cons -> nil:cons
ifselsort :: true:false -> nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_0':s2_0 :: 0':s
hole_nil:cons3_0 :: nil:cons
gen_0':s4_0 :: Nat -> 0':s
gen_nil:cons5_0 :: Nat -> nil:cons


Lemmas:
eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0)


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


The following defined symbols remain to be analysed:
le, min, replace, selsort

They will be analysed ascendingly in the following order:
le < min
min < selsort
replace < selsort

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

(23) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
le(gen_0':s4_0(n560_0), gen_0':s4_0(n560_0)) -> true, rt in Omega(1 + n560_0)

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

Induction Step:
le(gen_0':s4_0(+(n560_0, 1)), gen_0':s4_0(+(n560_0, 1))) ->_R^Omega(1)
le(gen_0':s4_0(n560_0), gen_0':s4_0(n560_0)) ->_IH
true

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

(24)
Obligation:
Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(Y)) -> false
eq(s(X), 0') -> false
eq(s(X), s(Y)) -> eq(X, Y)
le(0', Y) -> true
le(s(X), 0') -> false
le(s(X), s(Y)) -> le(X, Y)
min(cons(0', nil)) -> 0'
min(cons(s(N), nil)) -> s(N)
min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L)))
ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L))
ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L))
replace(N, M, nil) -> nil
replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L))
ifrepl(true, N, M, cons(K, L)) -> cons(M, L)
ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L))
selsort(nil) -> nil
selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L))
ifselsort(true, cons(N, L)) -> cons(N, selsort(L))
ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L)))

Types:
eq :: 0':s -> 0':s -> true:false
0' :: 0':s
true :: true:false
s :: 0':s -> 0':s
false :: true:false
le :: 0':s -> 0':s -> true:false
min :: nil:cons -> 0':s
cons :: 0':s -> nil:cons -> nil:cons
nil :: nil:cons
ifmin :: true:false -> nil:cons -> 0':s
replace :: 0':s -> 0':s -> nil:cons -> nil:cons
ifrepl :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
selsort :: nil:cons -> nil:cons
ifselsort :: true:false -> nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_0':s2_0 :: 0':s
hole_nil:cons3_0 :: nil:cons
gen_0':s4_0 :: Nat -> 0':s
gen_nil:cons5_0 :: Nat -> nil:cons


Lemmas:
eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0)
le(gen_0':s4_0(n560_0), gen_0':s4_0(n560_0)) -> true, rt in Omega(1 + n560_0)


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


The following defined symbols remain to be analysed:
min, replace, selsort

They will be analysed ascendingly in the following order:
min < selsort
replace < selsort

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

(25) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
min(gen_nil:cons5_0(+(1, n907_0))) -> gen_0':s4_0(0), rt in Omega(1 + n907_0)

Induction Base:
min(gen_nil:cons5_0(+(1, 0))) ->_R^Omega(1)
0'

Induction Step:
min(gen_nil:cons5_0(+(1, +(n907_0, 1)))) ->_R^Omega(1)
ifmin(le(0', 0'), cons(0', cons(0', gen_nil:cons5_0(n907_0)))) ->_L^Omega(1)
ifmin(true, cons(0', cons(0', gen_nil:cons5_0(n907_0)))) ->_R^Omega(1)
min(cons(0', gen_nil:cons5_0(n907_0))) ->_IH
gen_0':s4_0(0)

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

(26)
Obligation:
Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(Y)) -> false
eq(s(X), 0') -> false
eq(s(X), s(Y)) -> eq(X, Y)
le(0', Y) -> true
le(s(X), 0') -> false
le(s(X), s(Y)) -> le(X, Y)
min(cons(0', nil)) -> 0'
min(cons(s(N), nil)) -> s(N)
min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L)))
ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L))
ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L))
replace(N, M, nil) -> nil
replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L))
ifrepl(true, N, M, cons(K, L)) -> cons(M, L)
ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L))
selsort(nil) -> nil
selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L))
ifselsort(true, cons(N, L)) -> cons(N, selsort(L))
ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L)))

Types:
eq :: 0':s -> 0':s -> true:false
0' :: 0':s
true :: true:false
s :: 0':s -> 0':s
false :: true:false
le :: 0':s -> 0':s -> true:false
min :: nil:cons -> 0':s
cons :: 0':s -> nil:cons -> nil:cons
nil :: nil:cons
ifmin :: true:false -> nil:cons -> 0':s
replace :: 0':s -> 0':s -> nil:cons -> nil:cons
ifrepl :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
selsort :: nil:cons -> nil:cons
ifselsort :: true:false -> nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_0':s2_0 :: 0':s
hole_nil:cons3_0 :: nil:cons
gen_0':s4_0 :: Nat -> 0':s
gen_nil:cons5_0 :: Nat -> nil:cons


Lemmas:
eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0)
le(gen_0':s4_0(n560_0), gen_0':s4_0(n560_0)) -> true, rt in Omega(1 + n560_0)
min(gen_nil:cons5_0(+(1, n907_0))) -> gen_0':s4_0(0), rt in Omega(1 + n907_0)


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


The following defined symbols remain to be analysed:
replace, selsort

They will be analysed ascendingly in the following order:
replace < selsort

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

(27) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
selsort(gen_nil:cons5_0(n1660_0)) -> gen_nil:cons5_0(n1660_0), rt in Omega(1 + n1660_0 + n1660_0^2)

Induction Base:
selsort(gen_nil:cons5_0(0)) ->_R^Omega(1)
nil

Induction Step:
selsort(gen_nil:cons5_0(+(n1660_0, 1))) ->_R^Omega(1)
ifselsort(eq(0', min(cons(0', gen_nil:cons5_0(n1660_0)))), cons(0', gen_nil:cons5_0(n1660_0))) ->_L^Omega(1 + n1660_0)
ifselsort(eq(0', gen_0':s4_0(0)), cons(0', gen_nil:cons5_0(n1660_0))) ->_L^Omega(1)
ifselsort(true, cons(0', gen_nil:cons5_0(n1660_0))) ->_R^Omega(1)
cons(0', selsort(gen_nil:cons5_0(n1660_0))) ->_IH
cons(0', gen_nil:cons5_0(c1661_0))

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

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

Innermost TRS:
Rules:
eq(0', 0') -> true
eq(0', s(Y)) -> false
eq(s(X), 0') -> false
eq(s(X), s(Y)) -> eq(X, Y)
le(0', Y) -> true
le(s(X), 0') -> false
le(s(X), s(Y)) -> le(X, Y)
min(cons(0', nil)) -> 0'
min(cons(s(N), nil)) -> s(N)
min(cons(N, cons(M, L))) -> ifmin(le(N, M), cons(N, cons(M, L)))
ifmin(true, cons(N, cons(M, L))) -> min(cons(N, L))
ifmin(false, cons(N, cons(M, L))) -> min(cons(M, L))
replace(N, M, nil) -> nil
replace(N, M, cons(K, L)) -> ifrepl(eq(N, K), N, M, cons(K, L))
ifrepl(true, N, M, cons(K, L)) -> cons(M, L)
ifrepl(false, N, M, cons(K, L)) -> cons(K, replace(N, M, L))
selsort(nil) -> nil
selsort(cons(N, L)) -> ifselsort(eq(N, min(cons(N, L))), cons(N, L))
ifselsort(true, cons(N, L)) -> cons(N, selsort(L))
ifselsort(false, cons(N, L)) -> cons(min(cons(N, L)), selsort(replace(min(cons(N, L)), N, L)))

Types:
eq :: 0':s -> 0':s -> true:false
0' :: 0':s
true :: true:false
s :: 0':s -> 0':s
false :: true:false
le :: 0':s -> 0':s -> true:false
min :: nil:cons -> 0':s
cons :: 0':s -> nil:cons -> nil:cons
nil :: nil:cons
ifmin :: true:false -> nil:cons -> 0':s
replace :: 0':s -> 0':s -> nil:cons -> nil:cons
ifrepl :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
selsort :: nil:cons -> nil:cons
ifselsort :: true:false -> nil:cons -> nil:cons
hole_true:false1_0 :: true:false
hole_0':s2_0 :: 0':s
hole_nil:cons3_0 :: nil:cons
gen_0':s4_0 :: Nat -> 0':s
gen_nil:cons5_0 :: Nat -> nil:cons


Lemmas:
eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0)
le(gen_0':s4_0(n560_0), gen_0':s4_0(n560_0)) -> true, rt in Omega(1 + n560_0)
min(gen_nil:cons5_0(+(1, n907_0))) -> gen_0':s4_0(0), rt in Omega(1 + n907_0)


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


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

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

(30)
BOUNDS(n^2, INF)