308.41/291.57	WORST_CASE(Omega(n^2), ?)
308.41/291.58	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
308.41/291.58	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
308.41/291.58	
308.41/291.58	
308.41/291.58	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
308.41/291.58	
308.41/291.58	(0) CpxTRS
308.41/291.58	(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
308.41/291.58	(2) CpxTRS
308.41/291.58	(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
308.41/291.58	(4) typed CpxTrs
308.41/291.58	(5) OrderProof [LOWER BOUND(ID), 0 ms]
308.41/291.58	(6) typed CpxTrs
308.41/291.58	(7) RewriteLemmaProof [LOWER BOUND(ID), 313 ms]
308.41/291.58	(8) BEST
308.41/291.58	    (9) proven lower bound
308.41/291.58	        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
308.41/291.58	        (11) BOUNDS(n^1, INF)
308.41/291.58	    (12) typed CpxTrs
308.41/291.58	        (13) RewriteLemmaProof [LOWER BOUND(ID), 74 ms]
308.41/291.58	        (14) typed CpxTrs
308.41/291.58	        (15) RewriteLemmaProof [LOWER BOUND(ID), 27 ms]
308.41/291.58	        (16) typed CpxTrs
308.41/291.58	        (17) RewriteLemmaProof [LOWER BOUND(ID), 0 ms]
308.41/291.58	        (18) typed CpxTrs
308.41/291.58	        (19) RewriteLemmaProof [LOWER BOUND(ID), 60 ms]
308.41/291.58	        (20) BEST
308.41/291.58	            (21) proven lower bound
308.41/291.58	                (22) LowerBoundPropagationProof [FINISHED, 0 ms]
308.48/291.58	                (23) BOUNDS(n^2, INF)
308.48/291.58	            (24) typed CpxTrs
308.48/291.58	
308.48/291.58	
308.48/291.58	----------------------------------------
308.48/291.58	
308.48/291.58	(0)
308.48/291.58	Obligation:
308.48/291.58	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
308.48/291.58	
308.48/291.58	
308.48/291.58	The TRS R consists of the following rules:
308.48/291.58	
308.48/291.58	   min(0, y) -> 0
308.48/291.58	   min(x, 0) -> 0
308.48/291.58	   min(s(x), s(y)) -> s(min(x, y))
308.48/291.58	   max(0, y) -> y
308.48/291.58	   max(x, 0) -> x
308.48/291.58	   max(s(x), s(y)) -> s(max(x, y))
308.48/291.58	   +(0, y) -> y
308.48/291.58	   +(s(x), y) -> s(+(x, y))
308.48/291.58	   -(x, 0) -> x
308.48/291.58	   -(s(x), s(y)) -> -(x, y)
308.48/291.58	   *(x, 0) -> 0
308.48/291.58	   *(x, s(y)) -> +(x, *(x, y))
308.48/291.58	   f(s(x)) -> f(-(max(*(s(x), s(x)), +(s(x), s(s(s(0))))), max(s(*(s(x), s(x))), +(s(x), s(s(s(s(0))))))))
308.48/291.58	
308.48/291.58	S is empty.
308.48/291.58	Rewrite Strategy: FULL
308.48/291.58	----------------------------------------
308.48/291.58	
308.48/291.58	(1) RenamingProof (BOTH BOUNDS(ID, ID))
308.48/291.58	Renamed function symbols to avoid clashes with predefined symbol.
308.48/291.58	----------------------------------------
308.48/291.58	
308.48/291.58	(2)
308.48/291.58	Obligation:
308.48/291.58	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
308.48/291.58	
308.48/291.58	
308.48/291.58	The TRS R consists of the following rules:
308.48/291.58	
308.48/291.58	   min(0', y) -> 0'
308.48/291.58	   min(x, 0') -> 0'
308.48/291.58	   min(s(x), s(y)) -> s(min(x, y))
308.48/291.58	   max(0', y) -> y
308.48/291.58	   max(x, 0') -> x
308.48/291.58	   max(s(x), s(y)) -> s(max(x, y))
308.48/291.58	   +'(0', y) -> y
308.48/291.58	   +'(s(x), y) -> s(+'(x, y))
308.48/291.58	   -(x, 0') -> x
308.48/291.58	   -(s(x), s(y)) -> -(x, y)
308.48/291.58	   *'(x, 0') -> 0'
308.48/291.58	   *'(x, s(y)) -> +'(x, *'(x, y))
308.48/291.58	   f(s(x)) -> f(-(max(*'(s(x), s(x)), +'(s(x), s(s(s(0'))))), max(s(*'(s(x), s(x))), +'(s(x), s(s(s(s(0'))))))))
308.48/291.58	
308.48/291.58	S is empty.
308.48/291.58	Rewrite Strategy: FULL
308.48/291.58	----------------------------------------
308.48/291.58	
308.48/291.58	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
308.48/291.58	Infered types.
308.48/291.58	----------------------------------------
308.48/291.58	
308.48/291.58	(4)
308.48/291.58	Obligation:
308.48/291.58	TRS:
308.48/291.58	Rules:
308.48/291.58	min(0', y) -> 0'
308.48/291.58	min(x, 0') -> 0'
308.48/291.58	min(s(x), s(y)) -> s(min(x, y))
308.48/291.58	max(0', y) -> y
308.48/291.58	max(x, 0') -> x
308.48/291.58	max(s(x), s(y)) -> s(max(x, y))
308.48/291.58	+'(0', y) -> y
308.48/291.58	+'(s(x), y) -> s(+'(x, y))
308.48/291.58	-(x, 0') -> x
308.48/291.58	-(s(x), s(y)) -> -(x, y)
308.48/291.58	*'(x, 0') -> 0'
308.48/291.58	*'(x, s(y)) -> +'(x, *'(x, y))
308.48/291.58	f(s(x)) -> f(-(max(*'(s(x), s(x)), +'(s(x), s(s(s(0'))))), max(s(*'(s(x), s(x))), +'(s(x), s(s(s(s(0'))))))))
308.48/291.58	
308.48/291.58	Types:
308.48/291.58	min :: 0':s -> 0':s -> 0':s
308.48/291.58	0' :: 0':s
308.48/291.58	s :: 0':s -> 0':s
308.48/291.58	max :: 0':s -> 0':s -> 0':s
308.48/291.58	+' :: 0':s -> 0':s -> 0':s
308.48/291.58	- :: 0':s -> 0':s -> 0':s
308.48/291.58	*' :: 0':s -> 0':s -> 0':s
308.48/291.58	f :: 0':s -> f
308.48/291.58	hole_0':s1_0 :: 0':s
308.48/291.58	hole_f2_0 :: f
308.48/291.58	gen_0':s3_0 :: Nat -> 0':s
308.48/291.58	
308.48/291.58	----------------------------------------
308.48/291.58	
308.48/291.58	(5) OrderProof (LOWER BOUND(ID))
308.48/291.58	Heuristically decided to analyse the following defined symbols:
308.48/291.58	min, max, +', -, *', f
308.48/291.58	
308.48/291.58	They will be analysed ascendingly in the following order:
308.48/291.58	max < f
308.48/291.58	+' < *'
308.48/291.58	+' < f
308.48/291.58	- < f
308.48/291.58	*' < f
308.48/291.58	
308.48/291.58	----------------------------------------
308.48/291.58	
308.48/291.58	(6)
308.48/291.58	Obligation:
308.48/291.58	TRS:
308.48/291.58	Rules:
308.48/291.58	min(0', y) -> 0'
308.48/291.58	min(x, 0') -> 0'
308.48/291.58	min(s(x), s(y)) -> s(min(x, y))
308.48/291.58	max(0', y) -> y
308.48/291.58	max(x, 0') -> x
308.48/291.58	max(s(x), s(y)) -> s(max(x, y))
308.48/291.58	+'(0', y) -> y
308.48/291.58	+'(s(x), y) -> s(+'(x, y))
308.48/291.58	-(x, 0') -> x
308.48/291.58	-(s(x), s(y)) -> -(x, y)
308.48/291.58	*'(x, 0') -> 0'
308.48/291.58	*'(x, s(y)) -> +'(x, *'(x, y))
308.48/291.58	f(s(x)) -> f(-(max(*'(s(x), s(x)), +'(s(x), s(s(s(0'))))), max(s(*'(s(x), s(x))), +'(s(x), s(s(s(s(0'))))))))
308.48/291.58	
308.48/291.58	Types:
308.48/291.58	min :: 0':s -> 0':s -> 0':s
308.48/291.58	0' :: 0':s
308.48/291.58	s :: 0':s -> 0':s
308.48/291.58	max :: 0':s -> 0':s -> 0':s
308.48/291.58	+' :: 0':s -> 0':s -> 0':s
308.48/291.58	- :: 0':s -> 0':s -> 0':s
308.48/291.58	*' :: 0':s -> 0':s -> 0':s
308.48/291.58	f :: 0':s -> f
308.48/291.58	hole_0':s1_0 :: 0':s
308.48/291.58	hole_f2_0 :: f
308.48/291.58	gen_0':s3_0 :: Nat -> 0':s
308.48/291.58	
308.48/291.58	
308.48/291.58	Generator Equations:
308.48/291.58	gen_0':s3_0(0) <=> 0'
308.48/291.58	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
308.48/291.58	
308.48/291.58	
308.48/291.58	The following defined symbols remain to be analysed:
308.48/291.58	min, max, +', -, *', f
308.48/291.58	
308.48/291.58	They will be analysed ascendingly in the following order:
308.48/291.58	max < f
308.48/291.58	+' < *'
308.48/291.58	+' < f
308.48/291.58	- < f
308.48/291.58	*' < f
308.48/291.58	
308.48/291.58	----------------------------------------
308.48/291.58	
308.48/291.58	(7) RewriteLemmaProof (LOWER BOUND(ID))
308.48/291.58	Proved the following rewrite lemma:
308.48/291.58	min(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0)
308.48/291.58	
308.48/291.58	Induction Base:
308.48/291.58	min(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1)
308.48/291.58	0'
308.48/291.58	
308.48/291.58	Induction Step:
308.48/291.58	min(gen_0':s3_0(+(n5_0, 1)), gen_0':s3_0(+(n5_0, 1))) ->_R^Omega(1)
308.48/291.58	s(min(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0))) ->_IH
308.48/291.58	s(gen_0':s3_0(c6_0))
308.48/291.58	
308.48/291.58	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
308.48/291.58	----------------------------------------
308.48/291.58	
308.48/291.58	(8)
308.48/291.58	Complex Obligation (BEST)
308.48/291.58	
308.48/291.58	----------------------------------------
308.48/291.58	
308.48/291.58	(9)
308.48/291.58	Obligation:
308.48/291.58	Proved the lower bound n^1 for the following obligation:
308.48/291.58	
308.48/291.58	TRS:
308.48/291.58	Rules:
308.48/291.58	min(0', y) -> 0'
308.48/291.58	min(x, 0') -> 0'
308.48/291.58	min(s(x), s(y)) -> s(min(x, y))
308.48/291.58	max(0', y) -> y
308.48/291.58	max(x, 0') -> x
308.48/291.58	max(s(x), s(y)) -> s(max(x, y))
308.48/291.58	+'(0', y) -> y
308.48/291.58	+'(s(x), y) -> s(+'(x, y))
308.48/291.58	-(x, 0') -> x
308.48/291.58	-(s(x), s(y)) -> -(x, y)
308.48/291.58	*'(x, 0') -> 0'
308.48/291.58	*'(x, s(y)) -> +'(x, *'(x, y))
308.48/291.58	f(s(x)) -> f(-(max(*'(s(x), s(x)), +'(s(x), s(s(s(0'))))), max(s(*'(s(x), s(x))), +'(s(x), s(s(s(s(0'))))))))
308.48/291.58	
308.48/291.58	Types:
308.48/291.58	min :: 0':s -> 0':s -> 0':s
308.48/291.58	0' :: 0':s
308.48/291.58	s :: 0':s -> 0':s
308.48/291.58	max :: 0':s -> 0':s -> 0':s
308.48/291.58	+' :: 0':s -> 0':s -> 0':s
308.48/291.58	- :: 0':s -> 0':s -> 0':s
308.48/291.58	*' :: 0':s -> 0':s -> 0':s
308.48/291.58	f :: 0':s -> f
308.48/291.58	hole_0':s1_0 :: 0':s
308.48/291.58	hole_f2_0 :: f
308.48/291.58	gen_0':s3_0 :: Nat -> 0':s
308.48/291.58	
308.48/291.58	
308.48/291.58	Generator Equations:
308.48/291.58	gen_0':s3_0(0) <=> 0'
308.48/291.58	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
308.48/291.58	
308.48/291.58	
308.48/291.58	The following defined symbols remain to be analysed:
308.48/291.58	min, max, +', -, *', f
308.48/291.58	
308.48/291.58	They will be analysed ascendingly in the following order:
308.48/291.58	max < f
308.48/291.58	+' < *'
308.48/291.58	+' < f
308.48/291.58	- < f
308.48/291.58	*' < f
308.48/291.58	
308.48/291.58	----------------------------------------
308.48/291.59	
308.48/291.59	(10) LowerBoundPropagationProof (FINISHED)
308.48/291.59	Propagated lower bound.
308.48/291.59	----------------------------------------
308.48/291.59	
308.48/291.59	(11)
308.48/291.59	BOUNDS(n^1, INF)
308.48/291.59	
308.48/291.59	----------------------------------------
308.48/291.59	
308.48/291.59	(12)
308.48/291.59	Obligation:
308.48/291.59	TRS:
308.48/291.59	Rules:
308.48/291.59	min(0', y) -> 0'
308.48/291.59	min(x, 0') -> 0'
308.48/291.59	min(s(x), s(y)) -> s(min(x, y))
308.48/291.59	max(0', y) -> y
308.48/291.59	max(x, 0') -> x
308.48/291.59	max(s(x), s(y)) -> s(max(x, y))
308.48/291.59	+'(0', y) -> y
308.48/291.59	+'(s(x), y) -> s(+'(x, y))
308.48/291.59	-(x, 0') -> x
308.48/291.59	-(s(x), s(y)) -> -(x, y)
308.48/291.59	*'(x, 0') -> 0'
308.48/291.59	*'(x, s(y)) -> +'(x, *'(x, y))
308.48/291.59	f(s(x)) -> f(-(max(*'(s(x), s(x)), +'(s(x), s(s(s(0'))))), max(s(*'(s(x), s(x))), +'(s(x), s(s(s(s(0'))))))))
308.48/291.59	
308.48/291.59	Types:
308.48/291.59	min :: 0':s -> 0':s -> 0':s
308.48/291.59	0' :: 0':s
308.48/291.59	s :: 0':s -> 0':s
308.48/291.59	max :: 0':s -> 0':s -> 0':s
308.48/291.59	+' :: 0':s -> 0':s -> 0':s
308.48/291.59	- :: 0':s -> 0':s -> 0':s
308.48/291.59	*' :: 0':s -> 0':s -> 0':s
308.48/291.59	f :: 0':s -> f
308.48/291.59	hole_0':s1_0 :: 0':s
308.48/291.59	hole_f2_0 :: f
308.48/291.59	gen_0':s3_0 :: Nat -> 0':s
308.48/291.59	
308.48/291.59	
308.48/291.59	Lemmas:
308.48/291.59	min(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0)
308.48/291.59	
308.48/291.59	
308.48/291.59	Generator Equations:
308.48/291.59	gen_0':s3_0(0) <=> 0'
308.48/291.59	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
308.48/291.59	
308.48/291.59	
308.48/291.59	The following defined symbols remain to be analysed:
308.48/291.59	max, +', -, *', f
308.48/291.59	
308.48/291.59	They will be analysed ascendingly in the following order:
308.48/291.59	max < f
308.48/291.59	+' < *'
308.48/291.59	+' < f
308.48/291.59	- < f
308.48/291.59	*' < f
308.48/291.59	
308.48/291.59	----------------------------------------
308.48/291.59	
308.48/291.59	(13) RewriteLemmaProof (LOWER BOUND(ID))
308.48/291.59	Proved the following rewrite lemma:
308.48/291.59	max(gen_0':s3_0(n315_0), gen_0':s3_0(n315_0)) -> gen_0':s3_0(n315_0), rt in Omega(1 + n315_0)
308.48/291.59	
308.48/291.59	Induction Base:
308.48/291.59	max(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1)
308.48/291.59	gen_0':s3_0(0)
308.48/291.59	
308.48/291.59	Induction Step:
308.48/291.59	max(gen_0':s3_0(+(n315_0, 1)), gen_0':s3_0(+(n315_0, 1))) ->_R^Omega(1)
308.48/291.59	s(max(gen_0':s3_0(n315_0), gen_0':s3_0(n315_0))) ->_IH
308.48/291.59	s(gen_0':s3_0(c316_0))
308.48/291.59	
308.48/291.59	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
308.48/291.59	----------------------------------------
308.48/291.59	
308.48/291.59	(14)
308.48/291.59	Obligation:
308.48/291.59	TRS:
308.48/291.59	Rules:
308.48/291.59	min(0', y) -> 0'
308.48/291.59	min(x, 0') -> 0'
308.48/291.59	min(s(x), s(y)) -> s(min(x, y))
308.48/291.59	max(0', y) -> y
308.48/291.59	max(x, 0') -> x
308.48/291.59	max(s(x), s(y)) -> s(max(x, y))
308.48/291.59	+'(0', y) -> y
308.48/291.59	+'(s(x), y) -> s(+'(x, y))
308.48/291.59	-(x, 0') -> x
308.48/291.59	-(s(x), s(y)) -> -(x, y)
308.48/291.59	*'(x, 0') -> 0'
308.48/291.59	*'(x, s(y)) -> +'(x, *'(x, y))
308.48/291.59	f(s(x)) -> f(-(max(*'(s(x), s(x)), +'(s(x), s(s(s(0'))))), max(s(*'(s(x), s(x))), +'(s(x), s(s(s(s(0'))))))))
308.48/291.59	
308.48/291.59	Types:
308.48/291.59	min :: 0':s -> 0':s -> 0':s
308.48/291.59	0' :: 0':s
308.48/291.59	s :: 0':s -> 0':s
308.48/291.59	max :: 0':s -> 0':s -> 0':s
308.48/291.59	+' :: 0':s -> 0':s -> 0':s
308.48/291.59	- :: 0':s -> 0':s -> 0':s
308.48/291.59	*' :: 0':s -> 0':s -> 0':s
308.48/291.59	f :: 0':s -> f
308.48/291.59	hole_0':s1_0 :: 0':s
308.48/291.59	hole_f2_0 :: f
308.48/291.59	gen_0':s3_0 :: Nat -> 0':s
308.48/291.59	
308.48/291.59	
308.48/291.59	Lemmas:
308.48/291.59	min(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0)
308.48/291.59	max(gen_0':s3_0(n315_0), gen_0':s3_0(n315_0)) -> gen_0':s3_0(n315_0), rt in Omega(1 + n315_0)
308.48/291.59	
308.48/291.59	
308.48/291.59	Generator Equations:
308.48/291.59	gen_0':s3_0(0) <=> 0'
308.48/291.59	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
308.48/291.59	
308.48/291.59	
308.48/291.59	The following defined symbols remain to be analysed:
308.48/291.59	+', -, *', f
308.48/291.59	
308.48/291.59	They will be analysed ascendingly in the following order:
308.48/291.59	+' < *'
308.48/291.59	+' < f
308.48/291.59	- < f
308.48/291.59	*' < f
308.48/291.59	
308.48/291.59	----------------------------------------
308.48/291.59	
308.48/291.59	(15) RewriteLemmaProof (LOWER BOUND(ID))
308.48/291.59	Proved the following rewrite lemma:
308.48/291.59	+'(gen_0':s3_0(n709_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n709_0, b)), rt in Omega(1 + n709_0)
308.48/291.59	
308.48/291.59	Induction Base:
308.48/291.59	+'(gen_0':s3_0(0), gen_0':s3_0(b)) ->_R^Omega(1)
308.48/291.59	gen_0':s3_0(b)
308.48/291.59	
308.48/291.59	Induction Step:
308.48/291.59	+'(gen_0':s3_0(+(n709_0, 1)), gen_0':s3_0(b)) ->_R^Omega(1)
308.48/291.59	s(+'(gen_0':s3_0(n709_0), gen_0':s3_0(b))) ->_IH
308.48/291.59	s(gen_0':s3_0(+(b, c710_0)))
308.48/291.59	
308.48/291.59	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
308.48/291.59	----------------------------------------
308.48/291.59	
308.48/291.59	(16)
308.48/291.59	Obligation:
308.48/291.59	TRS:
308.48/291.59	Rules:
308.48/291.59	min(0', y) -> 0'
308.48/291.59	min(x, 0') -> 0'
308.48/291.59	min(s(x), s(y)) -> s(min(x, y))
308.48/291.59	max(0', y) -> y
308.48/291.59	max(x, 0') -> x
308.48/291.59	max(s(x), s(y)) -> s(max(x, y))
308.48/291.59	+'(0', y) -> y
308.48/291.59	+'(s(x), y) -> s(+'(x, y))
308.48/291.59	-(x, 0') -> x
308.48/291.59	-(s(x), s(y)) -> -(x, y)
308.48/291.59	*'(x, 0') -> 0'
308.48/291.59	*'(x, s(y)) -> +'(x, *'(x, y))
308.48/291.59	f(s(x)) -> f(-(max(*'(s(x), s(x)), +'(s(x), s(s(s(0'))))), max(s(*'(s(x), s(x))), +'(s(x), s(s(s(s(0'))))))))
308.48/291.59	
308.48/291.59	Types:
308.48/291.59	min :: 0':s -> 0':s -> 0':s
308.48/291.59	0' :: 0':s
308.48/291.59	s :: 0':s -> 0':s
308.48/291.59	max :: 0':s -> 0':s -> 0':s
308.48/291.59	+' :: 0':s -> 0':s -> 0':s
308.48/291.59	- :: 0':s -> 0':s -> 0':s
308.48/291.59	*' :: 0':s -> 0':s -> 0':s
308.48/291.59	f :: 0':s -> f
308.48/291.59	hole_0':s1_0 :: 0':s
308.48/291.59	hole_f2_0 :: f
308.48/291.59	gen_0':s3_0 :: Nat -> 0':s
308.48/291.59	
308.48/291.59	
308.48/291.59	Lemmas:
308.48/291.59	min(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0)
308.48/291.59	max(gen_0':s3_0(n315_0), gen_0':s3_0(n315_0)) -> gen_0':s3_0(n315_0), rt in Omega(1 + n315_0)
308.48/291.59	+'(gen_0':s3_0(n709_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n709_0, b)), rt in Omega(1 + n709_0)
308.48/291.59	
308.48/291.59	
308.48/291.59	Generator Equations:
308.48/291.59	gen_0':s3_0(0) <=> 0'
308.48/291.59	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
308.48/291.59	
308.48/291.59	
308.48/291.59	The following defined symbols remain to be analysed:
308.48/291.59	-, *', f
308.48/291.59	
308.48/291.59	They will be analysed ascendingly in the following order:
308.48/291.59	- < f
308.48/291.59	*' < f
308.48/291.59	
308.48/291.59	----------------------------------------
308.48/291.59	
308.48/291.59	(17) RewriteLemmaProof (LOWER BOUND(ID))
308.48/291.59	Proved the following rewrite lemma:
308.48/291.59	-(gen_0':s3_0(n1306_0), gen_0':s3_0(n1306_0)) -> gen_0':s3_0(0), rt in Omega(1 + n1306_0)
308.48/291.59	
308.48/291.59	Induction Base:
308.48/291.59	-(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1)
308.48/291.59	gen_0':s3_0(0)
308.48/291.59	
308.48/291.59	Induction Step:
308.48/291.59	-(gen_0':s3_0(+(n1306_0, 1)), gen_0':s3_0(+(n1306_0, 1))) ->_R^Omega(1)
308.48/291.59	-(gen_0':s3_0(n1306_0), gen_0':s3_0(n1306_0)) ->_IH
308.48/291.59	gen_0':s3_0(0)
308.48/291.59	
308.48/291.59	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
308.48/291.59	----------------------------------------
308.48/291.59	
308.48/291.59	(18)
308.48/291.59	Obligation:
308.48/291.59	TRS:
308.48/291.59	Rules:
308.48/291.59	min(0', y) -> 0'
308.48/291.59	min(x, 0') -> 0'
308.48/291.59	min(s(x), s(y)) -> s(min(x, y))
308.48/291.59	max(0', y) -> y
308.48/291.59	max(x, 0') -> x
308.48/291.59	max(s(x), s(y)) -> s(max(x, y))
308.48/291.59	+'(0', y) -> y
308.48/291.59	+'(s(x), y) -> s(+'(x, y))
308.48/291.59	-(x, 0') -> x
308.48/291.59	-(s(x), s(y)) -> -(x, y)
308.48/291.59	*'(x, 0') -> 0'
308.48/291.59	*'(x, s(y)) -> +'(x, *'(x, y))
308.48/291.59	f(s(x)) -> f(-(max(*'(s(x), s(x)), +'(s(x), s(s(s(0'))))), max(s(*'(s(x), s(x))), +'(s(x), s(s(s(s(0'))))))))
308.48/291.59	
308.48/291.59	Types:
308.48/291.59	min :: 0':s -> 0':s -> 0':s
308.48/291.59	0' :: 0':s
308.48/291.59	s :: 0':s -> 0':s
308.48/291.59	max :: 0':s -> 0':s -> 0':s
308.48/291.59	+' :: 0':s -> 0':s -> 0':s
308.48/291.59	- :: 0':s -> 0':s -> 0':s
308.48/291.59	*' :: 0':s -> 0':s -> 0':s
308.48/291.59	f :: 0':s -> f
308.48/291.59	hole_0':s1_0 :: 0':s
308.48/291.59	hole_f2_0 :: f
308.48/291.59	gen_0':s3_0 :: Nat -> 0':s
308.48/291.59	
308.48/291.59	
308.48/291.59	Lemmas:
308.48/291.59	min(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0)
308.48/291.59	max(gen_0':s3_0(n315_0), gen_0':s3_0(n315_0)) -> gen_0':s3_0(n315_0), rt in Omega(1 + n315_0)
308.48/291.59	+'(gen_0':s3_0(n709_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n709_0, b)), rt in Omega(1 + n709_0)
308.48/291.59	-(gen_0':s3_0(n1306_0), gen_0':s3_0(n1306_0)) -> gen_0':s3_0(0), rt in Omega(1 + n1306_0)
308.48/291.59	
308.48/291.59	
308.48/291.59	Generator Equations:
308.48/291.59	gen_0':s3_0(0) <=> 0'
308.48/291.59	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
308.48/291.59	
308.48/291.59	
308.48/291.59	The following defined symbols remain to be analysed:
308.48/291.59	*', f
308.48/291.59	
308.48/291.59	They will be analysed ascendingly in the following order:
308.48/291.59	*' < f
308.48/291.59	
308.48/291.59	----------------------------------------
308.48/291.59	
308.48/291.59	(19) RewriteLemmaProof (LOWER BOUND(ID))
308.48/291.59	Proved the following rewrite lemma:
308.48/291.59	*'(gen_0':s3_0(a), gen_0':s3_0(n1598_0)) -> gen_0':s3_0(*(n1598_0, a)), rt in Omega(1 + a*n1598_0 + n1598_0)
308.48/291.59	
308.48/291.59	Induction Base:
308.48/291.59	*'(gen_0':s3_0(a), gen_0':s3_0(0)) ->_R^Omega(1)
308.48/291.59	0'
308.48/291.59	
308.48/291.59	Induction Step:
308.48/291.59	*'(gen_0':s3_0(a), gen_0':s3_0(+(n1598_0, 1))) ->_R^Omega(1)
308.48/291.59	+'(gen_0':s3_0(a), *'(gen_0':s3_0(a), gen_0':s3_0(n1598_0))) ->_IH
308.48/291.59	+'(gen_0':s3_0(a), gen_0':s3_0(*(c1599_0, a))) ->_L^Omega(1 + a)
308.48/291.59	gen_0':s3_0(+(a, *(n1598_0, a)))
308.48/291.59	
308.48/291.59	We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2).
308.48/291.59	----------------------------------------
308.48/291.59	
308.48/291.59	(20)
308.48/291.59	Complex Obligation (BEST)
308.48/291.59	
308.48/291.59	----------------------------------------
308.48/291.59	
308.48/291.59	(21)
308.48/291.59	Obligation:
308.48/291.59	Proved the lower bound n^2 for the following obligation:
308.48/291.59	
308.48/291.59	TRS:
308.48/291.59	Rules:
308.48/291.59	min(0', y) -> 0'
308.48/291.59	min(x, 0') -> 0'
308.48/291.59	min(s(x), s(y)) -> s(min(x, y))
308.48/291.59	max(0', y) -> y
308.48/291.59	max(x, 0') -> x
308.48/291.59	max(s(x), s(y)) -> s(max(x, y))
308.48/291.59	+'(0', y) -> y
308.48/291.59	+'(s(x), y) -> s(+'(x, y))
308.48/291.59	-(x, 0') -> x
308.48/291.59	-(s(x), s(y)) -> -(x, y)
308.48/291.59	*'(x, 0') -> 0'
308.48/291.59	*'(x, s(y)) -> +'(x, *'(x, y))
308.48/291.59	f(s(x)) -> f(-(max(*'(s(x), s(x)), +'(s(x), s(s(s(0'))))), max(s(*'(s(x), s(x))), +'(s(x), s(s(s(s(0'))))))))
308.48/291.59	
308.48/291.59	Types:
308.48/291.59	min :: 0':s -> 0':s -> 0':s
308.48/291.59	0' :: 0':s
308.48/291.59	s :: 0':s -> 0':s
308.48/291.59	max :: 0':s -> 0':s -> 0':s
308.48/291.59	+' :: 0':s -> 0':s -> 0':s
308.48/291.59	- :: 0':s -> 0':s -> 0':s
308.48/291.59	*' :: 0':s -> 0':s -> 0':s
308.48/291.59	f :: 0':s -> f
308.48/291.59	hole_0':s1_0 :: 0':s
308.48/291.59	hole_f2_0 :: f
308.48/291.59	gen_0':s3_0 :: Nat -> 0':s
308.48/291.59	
308.48/291.59	
308.48/291.59	Lemmas:
308.48/291.59	min(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0)
308.48/291.59	max(gen_0':s3_0(n315_0), gen_0':s3_0(n315_0)) -> gen_0':s3_0(n315_0), rt in Omega(1 + n315_0)
308.48/291.59	+'(gen_0':s3_0(n709_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n709_0, b)), rt in Omega(1 + n709_0)
308.48/291.59	-(gen_0':s3_0(n1306_0), gen_0':s3_0(n1306_0)) -> gen_0':s3_0(0), rt in Omega(1 + n1306_0)
308.48/291.59	
308.48/291.59	
308.48/291.59	Generator Equations:
308.48/291.59	gen_0':s3_0(0) <=> 0'
308.48/291.59	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
308.48/291.59	
308.48/291.59	
308.48/291.59	The following defined symbols remain to be analysed:
308.48/291.59	*', f
308.48/291.59	
308.48/291.59	They will be analysed ascendingly in the following order:
308.48/291.59	*' < f
308.48/291.59	
308.48/291.59	----------------------------------------
308.48/291.59	
308.48/291.59	(22) LowerBoundPropagationProof (FINISHED)
308.48/291.59	Propagated lower bound.
308.48/291.59	----------------------------------------
308.48/291.59	
308.48/291.59	(23)
308.48/291.59	BOUNDS(n^2, INF)
308.48/291.59	
308.48/291.59	----------------------------------------
308.48/291.59	
308.48/291.59	(24)
308.48/291.59	Obligation:
308.48/291.59	TRS:
308.48/291.59	Rules:
308.48/291.59	min(0', y) -> 0'
308.48/291.59	min(x, 0') -> 0'
308.48/291.59	min(s(x), s(y)) -> s(min(x, y))
308.48/291.59	max(0', y) -> y
308.48/291.59	max(x, 0') -> x
308.48/291.59	max(s(x), s(y)) -> s(max(x, y))
308.48/291.59	+'(0', y) -> y
308.48/291.59	+'(s(x), y) -> s(+'(x, y))
308.48/291.59	-(x, 0') -> x
308.48/291.59	-(s(x), s(y)) -> -(x, y)
308.48/291.59	*'(x, 0') -> 0'
308.48/291.59	*'(x, s(y)) -> +'(x, *'(x, y))
308.48/291.59	f(s(x)) -> f(-(max(*'(s(x), s(x)), +'(s(x), s(s(s(0'))))), max(s(*'(s(x), s(x))), +'(s(x), s(s(s(s(0'))))))))
308.48/291.59	
308.48/291.59	Types:
308.48/291.59	min :: 0':s -> 0':s -> 0':s
308.48/291.59	0' :: 0':s
308.48/291.59	s :: 0':s -> 0':s
308.48/291.59	max :: 0':s -> 0':s -> 0':s
308.48/291.59	+' :: 0':s -> 0':s -> 0':s
308.48/291.59	- :: 0':s -> 0':s -> 0':s
308.48/291.59	*' :: 0':s -> 0':s -> 0':s
308.48/291.59	f :: 0':s -> f
308.48/291.59	hole_0':s1_0 :: 0':s
308.48/291.59	hole_f2_0 :: f
308.48/291.59	gen_0':s3_0 :: Nat -> 0':s
308.48/291.59	
308.48/291.59	
308.48/291.59	Lemmas:
308.48/291.59	min(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0)
308.48/291.59	max(gen_0':s3_0(n315_0), gen_0':s3_0(n315_0)) -> gen_0':s3_0(n315_0), rt in Omega(1 + n315_0)
308.48/291.59	+'(gen_0':s3_0(n709_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n709_0, b)), rt in Omega(1 + n709_0)
308.48/291.59	-(gen_0':s3_0(n1306_0), gen_0':s3_0(n1306_0)) -> gen_0':s3_0(0), rt in Omega(1 + n1306_0)
308.48/291.59	*'(gen_0':s3_0(a), gen_0':s3_0(n1598_0)) -> gen_0':s3_0(*(n1598_0, a)), rt in Omega(1 + a*n1598_0 + n1598_0)
308.48/291.59	
308.48/291.59	
308.48/291.59	Generator Equations:
308.48/291.59	gen_0':s3_0(0) <=> 0'
308.48/291.59	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
308.48/291.59	
308.48/291.59	
308.48/291.59	The following defined symbols remain to be analysed:
308.48/291.59	f
308.48/291.62	EOF