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

(0) CpxRelTRS
(1) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 178 ms]
(2) CpxRelTRS
(3) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(4) CpxRelTRS
(5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) typed CpxTrs
(7) OrderProof [LOWER BOUND(ID), 0 ms]
(8) typed CpxTrs
(9) RewriteLemmaProof [LOWER BOUND(ID), 283 ms]
(10) typed CpxTrs
(11) RewriteLemmaProof [LOWER BOUND(ID), 53 ms]
(12) BEST
    (13) proven lower bound
        (14) LowerBoundPropagationProof [FINISHED, 0 ms]
        (15) BOUNDS(n^1, INF)
    (16) typed CpxTrs
        (17) RewriteLemmaProof [LOWER BOUND(ID), 32 ms]
        (18) typed CpxTrs


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

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

   remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
   remove(x, Nil) -> Nil
   minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
   minsort(Nil) -> Nil
   appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
   appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   goal(xs) -> minsort(xs)

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

   !EQ(S(x), S(y)) -> !EQ(x, y)
   !EQ(0, S(y)) -> False
   !EQ(S(x), 0) -> False
   !EQ(0, 0) -> True
   <(S(x), S(y)) -> <(x, y)
   <(0, S(y)) -> True
   <(x, 0) -> False
   remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
   appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
   remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
   appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, 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, INF).


The TRS R consists of the following rules:

   remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
   remove(x, Nil) -> Nil
   minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
   minsort(Nil) -> Nil
   appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
   appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   goal(xs) -> minsort(xs)

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

   !EQ(S(x), S(y)) -> !EQ(x, y)
   !EQ(0, S(y)) -> False
   !EQ(S(x), 0) -> False
   !EQ(0, 0) -> True
   <(S(x), S(y)) -> <(x, y)
   <(0, S(y)) -> True
   <(x, 0) -> False
   remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
   appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
   remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
   appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')

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

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

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

   remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
   remove(x, Nil) -> Nil
   minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
   minsort(Nil) -> Nil
   appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
   appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
   notEmpty(Cons(x, xs)) -> True
   notEmpty(Nil) -> False
   goal(xs) -> minsort(xs)

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

   !EQ(S(x), S(y)) -> !EQ(x, y)
   !EQ(0', S(y)) -> False
   !EQ(S(x), 0') -> False
   !EQ(0', 0') -> True
   <(S(x), S(y)) -> <(x, y)
   <(0', S(y)) -> True
   <(x, 0') -> False
   remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
   appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
   remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
   appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')

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

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

(6)
Obligation:
Innermost TRS:
Rules:
remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
remove(x, Nil) -> Nil
minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
minsort(Nil) -> Nil
appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
goal(xs) -> minsort(xs)
!EQ(S(x), S(y)) -> !EQ(x, y)
!EQ(0', S(y)) -> False
!EQ(S(x), 0') -> False
!EQ(0', 0') -> True
<(S(x), S(y)) -> <(x, y)
<(0', S(y)) -> True
<(x, 0') -> False
remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')

Types:
remove :: S:0' -> Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
remove[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
!EQ :: S:0' -> S:0' -> True:False
Nil :: Cons:Nil
minsort :: Cons:Nil -> Cons:Nil
appmin :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
appmin[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
< :: S:0' -> S:0' -> True:False
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
goal :: Cons:Nil -> Cons:Nil
S :: S:0' -> S:0'
0' :: S:0'
hole_Cons:Nil1_0 :: Cons:Nil
hole_S:0'2_0 :: S:0'
hole_True:False3_0 :: True:False
gen_Cons:Nil4_0 :: Nat -> Cons:Nil
gen_S:0'5_0 :: Nat -> S:0'

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

(7) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
remove, !EQ, minsort, appmin, <

They will be analysed ascendingly in the following order:
!EQ < remove
remove < appmin
minsort = appmin
< < appmin

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

(8)
Obligation:
Innermost TRS:
Rules:
remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
remove(x, Nil) -> Nil
minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
minsort(Nil) -> Nil
appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
goal(xs) -> minsort(xs)
!EQ(S(x), S(y)) -> !EQ(x, y)
!EQ(0', S(y)) -> False
!EQ(S(x), 0') -> False
!EQ(0', 0') -> True
<(S(x), S(y)) -> <(x, y)
<(0', S(y)) -> True
<(x, 0') -> False
remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')

Types:
remove :: S:0' -> Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
remove[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
!EQ :: S:0' -> S:0' -> True:False
Nil :: Cons:Nil
minsort :: Cons:Nil -> Cons:Nil
appmin :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
appmin[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
< :: S:0' -> S:0' -> True:False
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
goal :: Cons:Nil -> Cons:Nil
S :: S:0' -> S:0'
0' :: S:0'
hole_Cons:Nil1_0 :: Cons:Nil
hole_S:0'2_0 :: S:0'
hole_True:False3_0 :: True:False
gen_Cons:Nil4_0 :: Nat -> Cons:Nil
gen_S:0'5_0 :: Nat -> S:0'


Generator Equations:
gen_Cons:Nil4_0(0) <=> Nil
gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x))
gen_S:0'5_0(0) <=> 0'
gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x))


The following defined symbols remain to be analysed:
!EQ, remove, minsort, appmin, <

They will be analysed ascendingly in the following order:
!EQ < remove
remove < appmin
minsort = appmin
< < appmin

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

(9) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
!EQ(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) -> False, rt in Omega(0)

Induction Base:
!EQ(gen_S:0'5_0(0), gen_S:0'5_0(+(1, 0))) ->_R^Omega(0)
False

Induction Step:
!EQ(gen_S:0'5_0(+(n7_0, 1)), gen_S:0'5_0(+(1, +(n7_0, 1)))) ->_R^Omega(0)
!EQ(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) ->_IH
False

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

(10)
Obligation:
Innermost TRS:
Rules:
remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
remove(x, Nil) -> Nil
minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
minsort(Nil) -> Nil
appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
goal(xs) -> minsort(xs)
!EQ(S(x), S(y)) -> !EQ(x, y)
!EQ(0', S(y)) -> False
!EQ(S(x), 0') -> False
!EQ(0', 0') -> True
<(S(x), S(y)) -> <(x, y)
<(0', S(y)) -> True
<(x, 0') -> False
remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')

Types:
remove :: S:0' -> Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
remove[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
!EQ :: S:0' -> S:0' -> True:False
Nil :: Cons:Nil
minsort :: Cons:Nil -> Cons:Nil
appmin :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
appmin[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
< :: S:0' -> S:0' -> True:False
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
goal :: Cons:Nil -> Cons:Nil
S :: S:0' -> S:0'
0' :: S:0'
hole_Cons:Nil1_0 :: Cons:Nil
hole_S:0'2_0 :: S:0'
hole_True:False3_0 :: True:False
gen_Cons:Nil4_0 :: Nat -> Cons:Nil
gen_S:0'5_0 :: Nat -> S:0'


Lemmas:
!EQ(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) -> False, rt in Omega(0)


Generator Equations:
gen_Cons:Nil4_0(0) <=> Nil
gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x))
gen_S:0'5_0(0) <=> 0'
gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x))


The following defined symbols remain to be analysed:
remove, minsort, appmin, <

They will be analysed ascendingly in the following order:
remove < appmin
minsort = appmin
< < appmin

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

(11) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
remove(gen_S:0'5_0(1), gen_Cons:Nil4_0(n316_0)) -> gen_Cons:Nil4_0(n316_0), rt in Omega(1 + n316_0)

Induction Base:
remove(gen_S:0'5_0(1), gen_Cons:Nil4_0(0)) ->_R^Omega(1)
Nil

Induction Step:
remove(gen_S:0'5_0(1), gen_Cons:Nil4_0(+(n316_0, 1))) ->_R^Omega(1)
remove[Ite][True][Ite](!EQ(gen_S:0'5_0(1), 0'), gen_S:0'5_0(1), Cons(0', gen_Cons:Nil4_0(n316_0))) ->_R^Omega(0)
remove[Ite][True][Ite](False, gen_S:0'5_0(1), Cons(0', gen_Cons:Nil4_0(n316_0))) ->_R^Omega(0)
Cons(0', remove(gen_S:0'5_0(1), gen_Cons:Nil4_0(n316_0))) ->_IH
Cons(0', gen_Cons:Nil4_0(c317_0))

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

(12)
Complex Obligation (BEST)

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

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

Innermost TRS:
Rules:
remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
remove(x, Nil) -> Nil
minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
minsort(Nil) -> Nil
appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
goal(xs) -> minsort(xs)
!EQ(S(x), S(y)) -> !EQ(x, y)
!EQ(0', S(y)) -> False
!EQ(S(x), 0') -> False
!EQ(0', 0') -> True
<(S(x), S(y)) -> <(x, y)
<(0', S(y)) -> True
<(x, 0') -> False
remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')

Types:
remove :: S:0' -> Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
remove[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
!EQ :: S:0' -> S:0' -> True:False
Nil :: Cons:Nil
minsort :: Cons:Nil -> Cons:Nil
appmin :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
appmin[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
< :: S:0' -> S:0' -> True:False
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
goal :: Cons:Nil -> Cons:Nil
S :: S:0' -> S:0'
0' :: S:0'
hole_Cons:Nil1_0 :: Cons:Nil
hole_S:0'2_0 :: S:0'
hole_True:False3_0 :: True:False
gen_Cons:Nil4_0 :: Nat -> Cons:Nil
gen_S:0'5_0 :: Nat -> S:0'


Lemmas:
!EQ(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) -> False, rt in Omega(0)


Generator Equations:
gen_Cons:Nil4_0(0) <=> Nil
gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x))
gen_S:0'5_0(0) <=> 0'
gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x))


The following defined symbols remain to be analysed:
remove, minsort, appmin, <

They will be analysed ascendingly in the following order:
remove < appmin
minsort = appmin
< < appmin

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

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

(15)
BOUNDS(n^1, INF)

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

(16)
Obligation:
Innermost TRS:
Rules:
remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
remove(x, Nil) -> Nil
minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
minsort(Nil) -> Nil
appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
goal(xs) -> minsort(xs)
!EQ(S(x), S(y)) -> !EQ(x, y)
!EQ(0', S(y)) -> False
!EQ(S(x), 0') -> False
!EQ(0', 0') -> True
<(S(x), S(y)) -> <(x, y)
<(0', S(y)) -> True
<(x, 0') -> False
remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')

Types:
remove :: S:0' -> Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
remove[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
!EQ :: S:0' -> S:0' -> True:False
Nil :: Cons:Nil
minsort :: Cons:Nil -> Cons:Nil
appmin :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
appmin[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
< :: S:0' -> S:0' -> True:False
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
goal :: Cons:Nil -> Cons:Nil
S :: S:0' -> S:0'
0' :: S:0'
hole_Cons:Nil1_0 :: Cons:Nil
hole_S:0'2_0 :: S:0'
hole_True:False3_0 :: True:False
gen_Cons:Nil4_0 :: Nat -> Cons:Nil
gen_S:0'5_0 :: Nat -> S:0'


Lemmas:
!EQ(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) -> False, rt in Omega(0)
remove(gen_S:0'5_0(1), gen_Cons:Nil4_0(n316_0)) -> gen_Cons:Nil4_0(n316_0), rt in Omega(1 + n316_0)


Generator Equations:
gen_Cons:Nil4_0(0) <=> Nil
gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x))
gen_S:0'5_0(0) <=> 0'
gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x))


The following defined symbols remain to be analysed:
<, minsort, appmin

They will be analysed ascendingly in the following order:
minsort = appmin
< < appmin

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

(17) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
<(gen_S:0'5_0(n819_0), gen_S:0'5_0(+(1, n819_0))) -> True, rt in Omega(0)

Induction Base:
<(gen_S:0'5_0(0), gen_S:0'5_0(+(1, 0))) ->_R^Omega(0)
True

Induction Step:
<(gen_S:0'5_0(+(n819_0, 1)), gen_S:0'5_0(+(1, +(n819_0, 1)))) ->_R^Omega(0)
<(gen_S:0'5_0(n819_0), gen_S:0'5_0(+(1, n819_0))) ->_IH
True

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

(18)
Obligation:
Innermost TRS:
Rules:
remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
remove(x, Nil) -> Nil
minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
minsort(Nil) -> Nil
appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
notEmpty(Cons(x, xs)) -> True
notEmpty(Nil) -> False
goal(xs) -> minsort(xs)
!EQ(S(x), S(y)) -> !EQ(x, y)
!EQ(0', S(y)) -> False
!EQ(S(x), 0') -> False
!EQ(0', 0') -> True
<(S(x), S(y)) -> <(x, y)
<(0', S(y)) -> True
<(x, 0') -> False
remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')

Types:
remove :: S:0' -> Cons:Nil -> Cons:Nil
Cons :: S:0' -> Cons:Nil -> Cons:Nil
remove[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
!EQ :: S:0' -> S:0' -> True:False
Nil :: Cons:Nil
minsort :: Cons:Nil -> Cons:Nil
appmin :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
appmin[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
< :: S:0' -> S:0' -> True:False
notEmpty :: Cons:Nil -> True:False
True :: True:False
False :: True:False
goal :: Cons:Nil -> Cons:Nil
S :: S:0' -> S:0'
0' :: S:0'
hole_Cons:Nil1_0 :: Cons:Nil
hole_S:0'2_0 :: S:0'
hole_True:False3_0 :: True:False
gen_Cons:Nil4_0 :: Nat -> Cons:Nil
gen_S:0'5_0 :: Nat -> S:0'


Lemmas:
!EQ(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) -> False, rt in Omega(0)
remove(gen_S:0'5_0(1), gen_Cons:Nil4_0(n316_0)) -> gen_Cons:Nil4_0(n316_0), rt in Omega(1 + n316_0)
<(gen_S:0'5_0(n819_0), gen_S:0'5_0(+(1, n819_0))) -> True, rt in Omega(0)


Generator Equations:
gen_Cons:Nil4_0(0) <=> Nil
gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x))
gen_S:0'5_0(0) <=> 0'
gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x))


The following defined symbols remain to be analysed:
appmin, minsort

They will be analysed ascendingly in the following order:
minsort = appmin