1133.74/291.58	WORST_CASE(Omega(n^1), ?)
1135.17/291.89	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
1135.17/291.89	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).
1135.17/291.89	
1135.17/291.89	(0) CpxRelTRS
1135.17/291.89	(1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 179 ms]
1135.17/291.89	(2) CpxRelTRS
1135.17/291.89	(3) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
1135.17/291.89	(4) CpxRelTRS
1135.17/291.89	(5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
1135.17/291.89	(6) typed CpxTrs
1135.17/291.89	(7) OrderProof [LOWER BOUND(ID), 0 ms]
1135.17/291.89	(8) typed CpxTrs
1135.17/291.89	(9) RewriteLemmaProof [LOWER BOUND(ID), 273 ms]
1135.17/291.89	(10) typed CpxTrs
1135.17/291.89	(11) RewriteLemmaProof [LOWER BOUND(ID), 53 ms]
1135.17/291.89	(12) BEST
1135.17/291.89	    (13) proven lower bound
1135.17/291.89	        (14) LowerBoundPropagationProof [FINISHED, 0 ms]
1135.17/291.89	        (15) BOUNDS(n^1, INF)
1135.17/291.89	    (16) typed CpxTrs
1135.17/291.89	        (17) RewriteLemmaProof [LOWER BOUND(ID), 28 ms]
1135.17/291.89	        (18) typed CpxTrs
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(0)
1135.17/291.89	Obligation:
1135.17/291.89	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	The TRS R consists of the following rules:
1135.17/291.89	
1135.17/291.89	   remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
1135.17/291.89	   remove(x, Nil) -> Nil
1135.17/291.89	   minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
1135.17/291.89	   minsort(Nil) -> Nil
1135.17/291.89	   appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
1135.17/291.89	   appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
1135.17/291.89	   notEmpty(Cons(x, xs)) -> True
1135.17/291.89	   notEmpty(Nil) -> False
1135.17/291.89	   goal(xs) -> minsort(xs)
1135.17/291.89	
1135.17/291.89	The (relative) TRS S consists of the following rules:
1135.17/291.89	
1135.17/291.89	   !EQ(S(x), S(y)) -> !EQ(x, y)
1135.17/291.89	   !EQ(0, S(y)) -> False
1135.17/291.89	   !EQ(S(x), 0) -> False
1135.17/291.89	   !EQ(0, 0) -> True
1135.17/291.89	   <(S(x), S(y)) -> <(x, y)
1135.17/291.89	   <(0, S(y)) -> True
1135.17/291.89	   <(x, 0) -> False
1135.17/291.89	   remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
1135.17/291.89	   appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
1135.17/291.89	   remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
1135.17/291.89	   appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')
1135.17/291.89	
1135.17/291.89	Rewrite Strategy: INNERMOST
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
1135.17/291.89	proved termination of relative rules
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(2)
1135.17/291.89	Obligation:
1135.17/291.89	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	The TRS R consists of the following rules:
1135.17/291.89	
1135.17/291.89	   remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
1135.17/291.89	   remove(x, Nil) -> Nil
1135.17/291.89	   minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
1135.17/291.89	   minsort(Nil) -> Nil
1135.17/291.89	   appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
1135.17/291.89	   appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
1135.17/291.89	   notEmpty(Cons(x, xs)) -> True
1135.17/291.89	   notEmpty(Nil) -> False
1135.17/291.89	   goal(xs) -> minsort(xs)
1135.17/291.89	
1135.17/291.89	The (relative) TRS S consists of the following rules:
1135.17/291.89	
1135.17/291.89	   !EQ(S(x), S(y)) -> !EQ(x, y)
1135.17/291.89	   !EQ(0, S(y)) -> False
1135.17/291.89	   !EQ(S(x), 0) -> False
1135.17/291.89	   !EQ(0, 0) -> True
1135.17/291.89	   <(S(x), S(y)) -> <(x, y)
1135.17/291.89	   <(0, S(y)) -> True
1135.17/291.89	   <(x, 0) -> False
1135.17/291.89	   remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
1135.17/291.89	   appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
1135.17/291.89	   remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
1135.17/291.89	   appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')
1135.17/291.89	
1135.17/291.89	Rewrite Strategy: INNERMOST
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(3) RenamingProof (BOTH BOUNDS(ID, ID))
1135.17/291.89	Renamed function symbols to avoid clashes with predefined symbol.
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(4)
1135.17/291.89	Obligation:
1135.17/291.89	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	The TRS R consists of the following rules:
1135.17/291.89	
1135.17/291.89	   remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
1135.17/291.89	   remove(x, Nil) -> Nil
1135.17/291.89	   minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
1135.17/291.89	   minsort(Nil) -> Nil
1135.17/291.89	   appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
1135.17/291.89	   appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
1135.17/291.89	   notEmpty(Cons(x, xs)) -> True
1135.17/291.89	   notEmpty(Nil) -> False
1135.17/291.89	   goal(xs) -> minsort(xs)
1135.17/291.89	
1135.17/291.89	The (relative) TRS S consists of the following rules:
1135.17/291.89	
1135.17/291.89	   !EQ(S(x), S(y)) -> !EQ(x, y)
1135.17/291.89	   !EQ(0', S(y)) -> False
1135.17/291.89	   !EQ(S(x), 0') -> False
1135.17/291.89	   !EQ(0', 0') -> True
1135.17/291.89	   <(S(x), S(y)) -> <(x, y)
1135.17/291.89	   <(0', S(y)) -> True
1135.17/291.89	   <(x, 0') -> False
1135.17/291.89	   remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
1135.17/291.89	   appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
1135.17/291.89	   remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
1135.17/291.89	   appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')
1135.17/291.89	
1135.17/291.89	Rewrite Strategy: INNERMOST
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(5) TypeInferenceProof (BOTH BOUNDS(ID, ID))
1135.17/291.89	Infered types.
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(6)
1135.17/291.89	Obligation:
1135.17/291.89	Innermost TRS:
1135.17/291.89	Rules:
1135.17/291.89	remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
1135.17/291.89	remove(x, Nil) -> Nil
1135.17/291.89	minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
1135.17/291.89	minsort(Nil) -> Nil
1135.17/291.89	appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
1135.17/291.89	appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
1135.17/291.89	notEmpty(Cons(x, xs)) -> True
1135.17/291.89	notEmpty(Nil) -> False
1135.17/291.89	goal(xs) -> minsort(xs)
1135.17/291.89	!EQ(S(x), S(y)) -> !EQ(x, y)
1135.17/291.89	!EQ(0', S(y)) -> False
1135.17/291.89	!EQ(S(x), 0') -> False
1135.17/291.89	!EQ(0', 0') -> True
1135.17/291.89	<(S(x), S(y)) -> <(x, y)
1135.17/291.89	<(0', S(y)) -> True
1135.17/291.89	<(x, 0') -> False
1135.17/291.89	remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
1135.17/291.89	appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
1135.17/291.89	remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
1135.17/291.89	appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')
1135.17/291.89	
1135.17/291.89	Types:
1135.17/291.89	remove :: S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	Cons :: S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	remove[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	!EQ :: S:0' -> S:0' -> True:False
1135.17/291.89	Nil :: Cons:Nil
1135.17/291.89	minsort :: Cons:Nil -> Cons:Nil
1135.17/291.89	appmin :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
1135.17/291.89	appmin[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
1135.17/291.89	< :: S:0' -> S:0' -> True:False
1135.17/291.89	notEmpty :: Cons:Nil -> True:False
1135.17/291.89	True :: True:False
1135.17/291.89	False :: True:False
1135.17/291.89	goal :: Cons:Nil -> Cons:Nil
1135.17/291.89	S :: S:0' -> S:0'
1135.17/291.89	0' :: S:0'
1135.17/291.89	hole_Cons:Nil1_0 :: Cons:Nil
1135.17/291.89	hole_S:0'2_0 :: S:0'
1135.17/291.89	hole_True:False3_0 :: True:False
1135.17/291.89	gen_Cons:Nil4_0 :: Nat -> Cons:Nil
1135.17/291.89	gen_S:0'5_0 :: Nat -> S:0'
1135.17/291.89	
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(7) OrderProof (LOWER BOUND(ID))
1135.17/291.89	Heuristically decided to analyse the following defined symbols:
1135.17/291.89	remove, !EQ, minsort, appmin, <
1135.17/291.89	
1135.17/291.89	They will be analysed ascendingly in the following order:
1135.17/291.89	!EQ < remove
1135.17/291.89	remove < appmin
1135.17/291.89	minsort = appmin
1135.17/291.89	< < appmin
1135.17/291.89	
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(8)
1135.17/291.89	Obligation:
1135.17/291.89	Innermost TRS:
1135.17/291.89	Rules:
1135.17/291.89	remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
1135.17/291.89	remove(x, Nil) -> Nil
1135.17/291.89	minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
1135.17/291.89	minsort(Nil) -> Nil
1135.17/291.89	appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
1135.17/291.89	appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
1135.17/291.89	notEmpty(Cons(x, xs)) -> True
1135.17/291.89	notEmpty(Nil) -> False
1135.17/291.89	goal(xs) -> minsort(xs)
1135.17/291.89	!EQ(S(x), S(y)) -> !EQ(x, y)
1135.17/291.89	!EQ(0', S(y)) -> False
1135.17/291.89	!EQ(S(x), 0') -> False
1135.17/291.89	!EQ(0', 0') -> True
1135.17/291.89	<(S(x), S(y)) -> <(x, y)
1135.17/291.89	<(0', S(y)) -> True
1135.17/291.89	<(x, 0') -> False
1135.17/291.89	remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
1135.17/291.89	appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
1135.17/291.89	remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
1135.17/291.89	appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')
1135.17/291.89	
1135.17/291.89	Types:
1135.17/291.89	remove :: S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	Cons :: S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	remove[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	!EQ :: S:0' -> S:0' -> True:False
1135.17/291.89	Nil :: Cons:Nil
1135.17/291.89	minsort :: Cons:Nil -> Cons:Nil
1135.17/291.89	appmin :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
1135.17/291.89	appmin[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
1135.17/291.89	< :: S:0' -> S:0' -> True:False
1135.17/291.89	notEmpty :: Cons:Nil -> True:False
1135.17/291.89	True :: True:False
1135.17/291.89	False :: True:False
1135.17/291.89	goal :: Cons:Nil -> Cons:Nil
1135.17/291.89	S :: S:0' -> S:0'
1135.17/291.89	0' :: S:0'
1135.17/291.89	hole_Cons:Nil1_0 :: Cons:Nil
1135.17/291.89	hole_S:0'2_0 :: S:0'
1135.17/291.89	hole_True:False3_0 :: True:False
1135.17/291.89	gen_Cons:Nil4_0 :: Nat -> Cons:Nil
1135.17/291.89	gen_S:0'5_0 :: Nat -> S:0'
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	Generator Equations:
1135.17/291.89	gen_Cons:Nil4_0(0) <=> Nil
1135.17/291.89	gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x))
1135.17/291.89	gen_S:0'5_0(0) <=> 0'
1135.17/291.89	gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x))
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	The following defined symbols remain to be analysed:
1135.17/291.89	!EQ, remove, minsort, appmin, <
1135.17/291.89	
1135.17/291.89	They will be analysed ascendingly in the following order:
1135.17/291.89	!EQ < remove
1135.17/291.89	remove < appmin
1135.17/291.89	minsort = appmin
1135.17/291.89	< < appmin
1135.17/291.89	
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(9) RewriteLemmaProof (LOWER BOUND(ID))
1135.17/291.89	Proved the following rewrite lemma:
1135.17/291.89	!EQ(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) -> False, rt in Omega(0)
1135.17/291.89	
1135.17/291.89	Induction Base:
1135.17/291.89	!EQ(gen_S:0'5_0(0), gen_S:0'5_0(+(1, 0))) ->_R^Omega(0)
1135.17/291.89	False
1135.17/291.89	
1135.17/291.89	Induction Step:
1135.17/291.89	!EQ(gen_S:0'5_0(+(n7_0, 1)), gen_S:0'5_0(+(1, +(n7_0, 1)))) ->_R^Omega(0)
1135.17/291.89	!EQ(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) ->_IH
1135.17/291.89	False
1135.17/291.89	
1135.17/291.89	We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0).
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(10)
1135.17/291.89	Obligation:
1135.17/291.89	Innermost TRS:
1135.17/291.89	Rules:
1135.17/291.89	remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
1135.17/291.89	remove(x, Nil) -> Nil
1135.17/291.89	minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
1135.17/291.89	minsort(Nil) -> Nil
1135.17/291.89	appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
1135.17/291.89	appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
1135.17/291.89	notEmpty(Cons(x, xs)) -> True
1135.17/291.89	notEmpty(Nil) -> False
1135.17/291.89	goal(xs) -> minsort(xs)
1135.17/291.89	!EQ(S(x), S(y)) -> !EQ(x, y)
1135.17/291.89	!EQ(0', S(y)) -> False
1135.17/291.89	!EQ(S(x), 0') -> False
1135.17/291.89	!EQ(0', 0') -> True
1135.17/291.89	<(S(x), S(y)) -> <(x, y)
1135.17/291.89	<(0', S(y)) -> True
1135.17/291.89	<(x, 0') -> False
1135.17/291.89	remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
1135.17/291.89	appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
1135.17/291.89	remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
1135.17/291.89	appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')
1135.17/291.89	
1135.17/291.89	Types:
1135.17/291.89	remove :: S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	Cons :: S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	remove[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	!EQ :: S:0' -> S:0' -> True:False
1135.17/291.89	Nil :: Cons:Nil
1135.17/291.89	minsort :: Cons:Nil -> Cons:Nil
1135.17/291.89	appmin :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
1135.17/291.89	appmin[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
1135.17/291.89	< :: S:0' -> S:0' -> True:False
1135.17/291.89	notEmpty :: Cons:Nil -> True:False
1135.17/291.89	True :: True:False
1135.17/291.89	False :: True:False
1135.17/291.89	goal :: Cons:Nil -> Cons:Nil
1135.17/291.89	S :: S:0' -> S:0'
1135.17/291.89	0' :: S:0'
1135.17/291.89	hole_Cons:Nil1_0 :: Cons:Nil
1135.17/291.89	hole_S:0'2_0 :: S:0'
1135.17/291.89	hole_True:False3_0 :: True:False
1135.17/291.89	gen_Cons:Nil4_0 :: Nat -> Cons:Nil
1135.17/291.89	gen_S:0'5_0 :: Nat -> S:0'
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	Lemmas:
1135.17/291.89	!EQ(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) -> False, rt in Omega(0)
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	Generator Equations:
1135.17/291.89	gen_Cons:Nil4_0(0) <=> Nil
1135.17/291.89	gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x))
1135.17/291.89	gen_S:0'5_0(0) <=> 0'
1135.17/291.89	gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x))
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	The following defined symbols remain to be analysed:
1135.17/291.89	remove, minsort, appmin, <
1135.17/291.89	
1135.17/291.89	They will be analysed ascendingly in the following order:
1135.17/291.89	remove < appmin
1135.17/291.89	minsort = appmin
1135.17/291.89	< < appmin
1135.17/291.89	
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(11) RewriteLemmaProof (LOWER BOUND(ID))
1135.17/291.89	Proved the following rewrite lemma:
1135.17/291.89	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)
1135.17/291.89	
1135.17/291.89	Induction Base:
1135.17/291.89	remove(gen_S:0'5_0(1), gen_Cons:Nil4_0(0)) ->_R^Omega(1)
1135.17/291.89	Nil
1135.17/291.89	
1135.17/291.89	Induction Step:
1135.17/291.89	remove(gen_S:0'5_0(1), gen_Cons:Nil4_0(+(n316_0, 1))) ->_R^Omega(1)
1135.17/291.89	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)
1135.17/291.89	remove[Ite][True][Ite](False, gen_S:0'5_0(1), Cons(0', gen_Cons:Nil4_0(n316_0))) ->_R^Omega(0)
1135.17/291.89	Cons(0', remove(gen_S:0'5_0(1), gen_Cons:Nil4_0(n316_0))) ->_IH
1135.17/291.89	Cons(0', gen_Cons:Nil4_0(c317_0))
1135.17/291.89	
1135.17/291.89	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(12)
1135.17/291.89	Complex Obligation (BEST)
1135.17/291.89	
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(13)
1135.17/291.89	Obligation:
1135.17/291.89	Proved the lower bound n^1 for the following obligation:
1135.17/291.89	
1135.17/291.89	Innermost TRS:
1135.17/291.89	Rules:
1135.17/291.89	remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
1135.17/291.89	remove(x, Nil) -> Nil
1135.17/291.89	minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
1135.17/291.89	minsort(Nil) -> Nil
1135.17/291.89	appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
1135.17/291.89	appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
1135.17/291.89	notEmpty(Cons(x, xs)) -> True
1135.17/291.89	notEmpty(Nil) -> False
1135.17/291.89	goal(xs) -> minsort(xs)
1135.17/291.89	!EQ(S(x), S(y)) -> !EQ(x, y)
1135.17/291.89	!EQ(0', S(y)) -> False
1135.17/291.89	!EQ(S(x), 0') -> False
1135.17/291.89	!EQ(0', 0') -> True
1135.17/291.89	<(S(x), S(y)) -> <(x, y)
1135.17/291.89	<(0', S(y)) -> True
1135.17/291.89	<(x, 0') -> False
1135.17/291.89	remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
1135.17/291.89	appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
1135.17/291.89	remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
1135.17/291.89	appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')
1135.17/291.89	
1135.17/291.89	Types:
1135.17/291.89	remove :: S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	Cons :: S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	remove[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	!EQ :: S:0' -> S:0' -> True:False
1135.17/291.89	Nil :: Cons:Nil
1135.17/291.89	minsort :: Cons:Nil -> Cons:Nil
1135.17/291.89	appmin :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
1135.17/291.89	appmin[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
1135.17/291.89	< :: S:0' -> S:0' -> True:False
1135.17/291.89	notEmpty :: Cons:Nil -> True:False
1135.17/291.89	True :: True:False
1135.17/291.89	False :: True:False
1135.17/291.89	goal :: Cons:Nil -> Cons:Nil
1135.17/291.89	S :: S:0' -> S:0'
1135.17/291.89	0' :: S:0'
1135.17/291.89	hole_Cons:Nil1_0 :: Cons:Nil
1135.17/291.89	hole_S:0'2_0 :: S:0'
1135.17/291.89	hole_True:False3_0 :: True:False
1135.17/291.89	gen_Cons:Nil4_0 :: Nat -> Cons:Nil
1135.17/291.89	gen_S:0'5_0 :: Nat -> S:0'
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	Lemmas:
1135.17/291.89	!EQ(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) -> False, rt in Omega(0)
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	Generator Equations:
1135.17/291.89	gen_Cons:Nil4_0(0) <=> Nil
1135.17/291.89	gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x))
1135.17/291.89	gen_S:0'5_0(0) <=> 0'
1135.17/291.89	gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x))
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	The following defined symbols remain to be analysed:
1135.17/291.89	remove, minsort, appmin, <
1135.17/291.89	
1135.17/291.89	They will be analysed ascendingly in the following order:
1135.17/291.89	remove < appmin
1135.17/291.89	minsort = appmin
1135.17/291.89	< < appmin
1135.17/291.89	
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(14) LowerBoundPropagationProof (FINISHED)
1135.17/291.89	Propagated lower bound.
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(15)
1135.17/291.89	BOUNDS(n^1, INF)
1135.17/291.89	
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(16)
1135.17/291.89	Obligation:
1135.17/291.89	Innermost TRS:
1135.17/291.89	Rules:
1135.17/291.89	remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
1135.17/291.89	remove(x, Nil) -> Nil
1135.17/291.89	minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
1135.17/291.89	minsort(Nil) -> Nil
1135.17/291.89	appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
1135.17/291.89	appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
1135.17/291.89	notEmpty(Cons(x, xs)) -> True
1135.17/291.89	notEmpty(Nil) -> False
1135.17/291.89	goal(xs) -> minsort(xs)
1135.17/291.89	!EQ(S(x), S(y)) -> !EQ(x, y)
1135.17/291.89	!EQ(0', S(y)) -> False
1135.17/291.89	!EQ(S(x), 0') -> False
1135.17/291.89	!EQ(0', 0') -> True
1135.17/291.89	<(S(x), S(y)) -> <(x, y)
1135.17/291.89	<(0', S(y)) -> True
1135.17/291.89	<(x, 0') -> False
1135.17/291.89	remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
1135.17/291.89	appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
1135.17/291.89	remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
1135.17/291.89	appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')
1135.17/291.89	
1135.17/291.89	Types:
1135.17/291.89	remove :: S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	Cons :: S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	remove[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	!EQ :: S:0' -> S:0' -> True:False
1135.17/291.89	Nil :: Cons:Nil
1135.17/291.89	minsort :: Cons:Nil -> Cons:Nil
1135.17/291.89	appmin :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
1135.17/291.89	appmin[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
1135.17/291.89	< :: S:0' -> S:0' -> True:False
1135.17/291.89	notEmpty :: Cons:Nil -> True:False
1135.17/291.89	True :: True:False
1135.17/291.89	False :: True:False
1135.17/291.89	goal :: Cons:Nil -> Cons:Nil
1135.17/291.89	S :: S:0' -> S:0'
1135.17/291.89	0' :: S:0'
1135.17/291.89	hole_Cons:Nil1_0 :: Cons:Nil
1135.17/291.89	hole_S:0'2_0 :: S:0'
1135.17/291.89	hole_True:False3_0 :: True:False
1135.17/291.89	gen_Cons:Nil4_0 :: Nat -> Cons:Nil
1135.17/291.89	gen_S:0'5_0 :: Nat -> S:0'
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	Lemmas:
1135.17/291.89	!EQ(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) -> False, rt in Omega(0)
1135.17/291.89	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)
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	Generator Equations:
1135.17/291.89	gen_Cons:Nil4_0(0) <=> Nil
1135.17/291.89	gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x))
1135.17/291.89	gen_S:0'5_0(0) <=> 0'
1135.17/291.89	gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x))
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	The following defined symbols remain to be analysed:
1135.17/291.89	<, minsort, appmin
1135.17/291.89	
1135.17/291.89	They will be analysed ascendingly in the following order:
1135.17/291.89	minsort = appmin
1135.17/291.89	< < appmin
1135.17/291.89	
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(17) RewriteLemmaProof (LOWER BOUND(ID))
1135.17/291.89	Proved the following rewrite lemma:
1135.17/291.89	<(gen_S:0'5_0(n819_0), gen_S:0'5_0(+(1, n819_0))) -> True, rt in Omega(0)
1135.17/291.89	
1135.17/291.89	Induction Base:
1135.17/291.89	<(gen_S:0'5_0(0), gen_S:0'5_0(+(1, 0))) ->_R^Omega(0)
1135.17/291.89	True
1135.17/291.89	
1135.17/291.89	Induction Step:
1135.17/291.89	<(gen_S:0'5_0(+(n819_0, 1)), gen_S:0'5_0(+(1, +(n819_0, 1)))) ->_R^Omega(0)
1135.17/291.89	<(gen_S:0'5_0(n819_0), gen_S:0'5_0(+(1, n819_0))) ->_IH
1135.17/291.89	True
1135.17/291.89	
1135.17/291.89	We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0).
1135.17/291.89	----------------------------------------
1135.17/291.89	
1135.17/291.89	(18)
1135.17/291.89	Obligation:
1135.17/291.89	Innermost TRS:
1135.17/291.89	Rules:
1135.17/291.89	remove(x', Cons(x, xs)) -> remove[Ite][True][Ite](!EQ(x', x), x', Cons(x, xs))
1135.17/291.89	remove(x, Nil) -> Nil
1135.17/291.89	minsort(Cons(x, xs)) -> appmin(x, xs, Cons(x, xs))
1135.17/291.89	minsort(Nil) -> Nil
1135.17/291.89	appmin(min, Cons(x, xs), xs') -> appmin[Ite][True][Ite](<(x, min), min, Cons(x, xs), xs')
1135.17/291.89	appmin(min, Nil, xs) -> Cons(min, minsort(remove(min, xs)))
1135.17/291.89	notEmpty(Cons(x, xs)) -> True
1135.17/291.89	notEmpty(Nil) -> False
1135.17/291.89	goal(xs) -> minsort(xs)
1135.17/291.89	!EQ(S(x), S(y)) -> !EQ(x, y)
1135.17/291.89	!EQ(0', S(y)) -> False
1135.17/291.89	!EQ(S(x), 0') -> False
1135.17/291.89	!EQ(0', 0') -> True
1135.17/291.89	<(S(x), S(y)) -> <(x, y)
1135.17/291.89	<(0', S(y)) -> True
1135.17/291.89	<(x, 0') -> False
1135.17/291.89	remove[Ite][True][Ite](False, x', Cons(x, xs)) -> Cons(x, remove(x', xs))
1135.17/291.89	appmin[Ite][True][Ite](True, min, Cons(x, xs), xs') -> appmin(x, xs, xs')
1135.17/291.89	remove[Ite][True][Ite](True, x', Cons(x, xs)) -> xs
1135.17/291.89	appmin[Ite][True][Ite](False, min, Cons(x, xs), xs') -> appmin(min, xs, xs')
1135.17/291.89	
1135.17/291.89	Types:
1135.17/291.89	remove :: S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	Cons :: S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	remove[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil
1135.17/291.89	!EQ :: S:0' -> S:0' -> True:False
1135.17/291.89	Nil :: Cons:Nil
1135.17/291.89	minsort :: Cons:Nil -> Cons:Nil
1135.17/291.89	appmin :: S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
1135.17/291.89	appmin[Ite][True][Ite] :: True:False -> S:0' -> Cons:Nil -> Cons:Nil -> Cons:Nil
1135.17/291.89	< :: S:0' -> S:0' -> True:False
1135.17/291.89	notEmpty :: Cons:Nil -> True:False
1135.17/291.89	True :: True:False
1135.17/291.89	False :: True:False
1135.17/291.89	goal :: Cons:Nil -> Cons:Nil
1135.17/291.89	S :: S:0' -> S:0'
1135.17/291.89	0' :: S:0'
1135.17/291.89	hole_Cons:Nil1_0 :: Cons:Nil
1135.17/291.89	hole_S:0'2_0 :: S:0'
1135.17/291.89	hole_True:False3_0 :: True:False
1135.17/291.89	gen_Cons:Nil4_0 :: Nat -> Cons:Nil
1135.17/291.89	gen_S:0'5_0 :: Nat -> S:0'
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	Lemmas:
1135.17/291.89	!EQ(gen_S:0'5_0(n7_0), gen_S:0'5_0(+(1, n7_0))) -> False, rt in Omega(0)
1135.17/291.89	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)
1135.17/291.89	<(gen_S:0'5_0(n819_0), gen_S:0'5_0(+(1, n819_0))) -> True, rt in Omega(0)
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	Generator Equations:
1135.17/291.89	gen_Cons:Nil4_0(0) <=> Nil
1135.17/291.89	gen_Cons:Nil4_0(+(x, 1)) <=> Cons(0', gen_Cons:Nil4_0(x))
1135.17/291.89	gen_S:0'5_0(0) <=> 0'
1135.17/291.89	gen_S:0'5_0(+(x, 1)) <=> S(gen_S:0'5_0(x))
1135.17/291.89	
1135.17/291.89	
1135.17/291.89	The following defined symbols remain to be analysed:
1135.17/291.89	appmin, minsort
1135.17/291.89	
1135.17/291.89	They will be analysed ascendingly in the following order:
1135.17/291.89	minsort = appmin
1135.50/291.98	EOF