313.29/291.47	WORST_CASE(Omega(n^2), ?)
313.29/291.48	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
313.29/291.48	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
313.29/291.48	
313.29/291.48	
313.29/291.48	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
313.29/291.48	
313.29/291.48	(0) CpxTRS
313.29/291.48	(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
313.29/291.48	(2) CpxTRS
313.29/291.48	(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
313.29/291.48	(4) typed CpxTrs
313.29/291.48	(5) OrderProof [LOWER BOUND(ID), 0 ms]
313.29/291.48	(6) typed CpxTrs
313.29/291.48	(7) RewriteLemmaProof [LOWER BOUND(ID), 309 ms]
313.29/291.48	(8) BEST
313.29/291.48	    (9) proven lower bound
313.29/291.48	        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
313.29/291.48	        (11) BOUNDS(n^1, INF)
313.29/291.48	    (12) typed CpxTrs
313.29/291.48	        (13) RewriteLemmaProof [LOWER BOUND(ID), 68 ms]
313.29/291.48	        (14) BEST
313.29/291.48	            (15) proven lower bound
313.29/291.48	                (16) LowerBoundPropagationProof [FINISHED, 0 ms]
313.29/291.48	                (17) BOUNDS(n^2, INF)
313.29/291.48	            (18) typed CpxTrs
313.29/291.48	                (19) RewriteLemmaProof [LOWER BOUND(ID), 31 ms]
313.29/291.48	                (20) typed CpxTrs
313.29/291.48	                (21) RewriteLemmaProof [LOWER BOUND(ID), 25 ms]
313.29/291.48	                (22) typed CpxTrs
313.29/291.48	
313.29/291.48	
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(0)
313.29/291.48	Obligation:
313.29/291.48	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
313.29/291.48	
313.29/291.48	
313.29/291.48	The TRS R consists of the following rules:
313.29/291.48	
313.29/291.48	   +(x, 0) -> x
313.29/291.48	   +(x, s(y)) -> s(+(x, y))
313.29/291.48	   *(x, 0) -> 0
313.29/291.48	   *(x, s(y)) -> +(*(x, y), x)
313.29/291.48	   ge(x, 0) -> true
313.29/291.48	   ge(0, s(y)) -> false
313.29/291.48	   ge(s(x), s(y)) -> ge(x, y)
313.29/291.48	   -(x, 0) -> x
313.29/291.48	   -(s(x), s(y)) -> -(x, y)
313.29/291.48	   fact(x) -> iffact(x, ge(x, s(s(0))))
313.29/291.48	   iffact(x, true) -> *(x, fact(-(x, s(0))))
313.29/291.48	   iffact(x, false) -> s(0)
313.29/291.48	
313.29/291.48	S is empty.
313.29/291.48	Rewrite Strategy: FULL
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(1) RenamingProof (BOTH BOUNDS(ID, ID))
313.29/291.48	Renamed function symbols to avoid clashes with predefined symbol.
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(2)
313.29/291.48	Obligation:
313.29/291.48	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
313.29/291.48	
313.29/291.48	
313.29/291.48	The TRS R consists of the following rules:
313.29/291.48	
313.29/291.48	   +'(x, 0') -> x
313.29/291.48	   +'(x, s(y)) -> s(+'(x, y))
313.29/291.48	   *'(x, 0') -> 0'
313.29/291.48	   *'(x, s(y)) -> +'(*'(x, y), x)
313.29/291.48	   ge(x, 0') -> true
313.29/291.48	   ge(0', s(y)) -> false
313.29/291.48	   ge(s(x), s(y)) -> ge(x, y)
313.29/291.48	   -(x, 0') -> x
313.29/291.48	   -(s(x), s(y)) -> -(x, y)
313.29/291.48	   fact(x) -> iffact(x, ge(x, s(s(0'))))
313.29/291.48	   iffact(x, true) -> *'(x, fact(-(x, s(0'))))
313.29/291.48	   iffact(x, false) -> s(0')
313.29/291.48	
313.29/291.48	S is empty.
313.29/291.48	Rewrite Strategy: FULL
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
313.29/291.48	Infered types.
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(4)
313.29/291.48	Obligation:
313.29/291.48	TRS:
313.29/291.48	Rules:
313.29/291.48	+'(x, 0') -> x
313.29/291.48	+'(x, s(y)) -> s(+'(x, y))
313.29/291.48	*'(x, 0') -> 0'
313.29/291.48	*'(x, s(y)) -> +'(*'(x, y), x)
313.29/291.48	ge(x, 0') -> true
313.29/291.48	ge(0', s(y)) -> false
313.29/291.48	ge(s(x), s(y)) -> ge(x, y)
313.29/291.48	-(x, 0') -> x
313.29/291.48	-(s(x), s(y)) -> -(x, y)
313.29/291.48	fact(x) -> iffact(x, ge(x, s(s(0'))))
313.29/291.48	iffact(x, true) -> *'(x, fact(-(x, s(0'))))
313.29/291.48	iffact(x, false) -> s(0')
313.29/291.48	
313.29/291.48	Types:
313.29/291.48	+' :: 0':s -> 0':s -> 0':s
313.29/291.48	0' :: 0':s
313.29/291.48	s :: 0':s -> 0':s
313.29/291.48	*' :: 0':s -> 0':s -> 0':s
313.29/291.48	ge :: 0':s -> 0':s -> true:false
313.29/291.48	true :: true:false
313.29/291.48	false :: true:false
313.29/291.48	- :: 0':s -> 0':s -> 0':s
313.29/291.48	fact :: 0':s -> 0':s
313.29/291.48	iffact :: 0':s -> true:false -> 0':s
313.29/291.48	hole_0':s1_0 :: 0':s
313.29/291.48	hole_true:false2_0 :: true:false
313.29/291.48	gen_0':s3_0 :: Nat -> 0':s
313.29/291.48	
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(5) OrderProof (LOWER BOUND(ID))
313.29/291.48	Heuristically decided to analyse the following defined symbols:
313.29/291.48	+', *', ge, -, fact
313.29/291.48	
313.29/291.48	They will be analysed ascendingly in the following order:
313.29/291.48	+' < *'
313.29/291.48	*' < fact
313.29/291.48	ge < fact
313.29/291.48	- < fact
313.29/291.48	
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(6)
313.29/291.48	Obligation:
313.29/291.48	TRS:
313.29/291.48	Rules:
313.29/291.48	+'(x, 0') -> x
313.29/291.48	+'(x, s(y)) -> s(+'(x, y))
313.29/291.48	*'(x, 0') -> 0'
313.29/291.48	*'(x, s(y)) -> +'(*'(x, y), x)
313.29/291.48	ge(x, 0') -> true
313.29/291.48	ge(0', s(y)) -> false
313.29/291.48	ge(s(x), s(y)) -> ge(x, y)
313.29/291.48	-(x, 0') -> x
313.29/291.48	-(s(x), s(y)) -> -(x, y)
313.29/291.48	fact(x) -> iffact(x, ge(x, s(s(0'))))
313.29/291.48	iffact(x, true) -> *'(x, fact(-(x, s(0'))))
313.29/291.48	iffact(x, false) -> s(0')
313.29/291.48	
313.29/291.48	Types:
313.29/291.48	+' :: 0':s -> 0':s -> 0':s
313.29/291.48	0' :: 0':s
313.29/291.48	s :: 0':s -> 0':s
313.29/291.48	*' :: 0':s -> 0':s -> 0':s
313.29/291.48	ge :: 0':s -> 0':s -> true:false
313.29/291.48	true :: true:false
313.29/291.48	false :: true:false
313.29/291.48	- :: 0':s -> 0':s -> 0':s
313.29/291.48	fact :: 0':s -> 0':s
313.29/291.48	iffact :: 0':s -> true:false -> 0':s
313.29/291.48	hole_0':s1_0 :: 0':s
313.29/291.48	hole_true:false2_0 :: true:false
313.29/291.48	gen_0':s3_0 :: Nat -> 0':s
313.29/291.48	
313.29/291.48	
313.29/291.48	Generator Equations:
313.29/291.48	gen_0':s3_0(0) <=> 0'
313.29/291.48	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
313.29/291.48	
313.29/291.48	
313.29/291.48	The following defined symbols remain to be analysed:
313.29/291.48	+', *', ge, -, fact
313.29/291.48	
313.29/291.48	They will be analysed ascendingly in the following order:
313.29/291.48	+' < *'
313.29/291.48	*' < fact
313.29/291.48	ge < fact
313.29/291.48	- < fact
313.29/291.48	
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(7) RewriteLemmaProof (LOWER BOUND(ID))
313.29/291.48	Proved the following rewrite lemma:
313.29/291.48	+'(gen_0':s3_0(a), gen_0':s3_0(n5_0)) -> gen_0':s3_0(+(n5_0, a)), rt in Omega(1 + n5_0)
313.29/291.48	
313.29/291.48	Induction Base:
313.29/291.48	+'(gen_0':s3_0(a), gen_0':s3_0(0)) ->_R^Omega(1)
313.29/291.48	gen_0':s3_0(a)
313.29/291.48	
313.29/291.48	Induction Step:
313.29/291.48	+'(gen_0':s3_0(a), gen_0':s3_0(+(n5_0, 1))) ->_R^Omega(1)
313.29/291.48	s(+'(gen_0':s3_0(a), gen_0':s3_0(n5_0))) ->_IH
313.29/291.48	s(gen_0':s3_0(+(a, c6_0)))
313.29/291.48	
313.29/291.48	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(8)
313.29/291.48	Complex Obligation (BEST)
313.29/291.48	
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(9)
313.29/291.48	Obligation:
313.29/291.48	Proved the lower bound n^1 for the following obligation:
313.29/291.48	
313.29/291.48	TRS:
313.29/291.48	Rules:
313.29/291.48	+'(x, 0') -> x
313.29/291.48	+'(x, s(y)) -> s(+'(x, y))
313.29/291.48	*'(x, 0') -> 0'
313.29/291.48	*'(x, s(y)) -> +'(*'(x, y), x)
313.29/291.48	ge(x, 0') -> true
313.29/291.48	ge(0', s(y)) -> false
313.29/291.48	ge(s(x), s(y)) -> ge(x, y)
313.29/291.48	-(x, 0') -> x
313.29/291.48	-(s(x), s(y)) -> -(x, y)
313.29/291.48	fact(x) -> iffact(x, ge(x, s(s(0'))))
313.29/291.48	iffact(x, true) -> *'(x, fact(-(x, s(0'))))
313.29/291.48	iffact(x, false) -> s(0')
313.29/291.48	
313.29/291.48	Types:
313.29/291.48	+' :: 0':s -> 0':s -> 0':s
313.29/291.48	0' :: 0':s
313.29/291.48	s :: 0':s -> 0':s
313.29/291.48	*' :: 0':s -> 0':s -> 0':s
313.29/291.48	ge :: 0':s -> 0':s -> true:false
313.29/291.48	true :: true:false
313.29/291.48	false :: true:false
313.29/291.48	- :: 0':s -> 0':s -> 0':s
313.29/291.48	fact :: 0':s -> 0':s
313.29/291.48	iffact :: 0':s -> true:false -> 0':s
313.29/291.48	hole_0':s1_0 :: 0':s
313.29/291.48	hole_true:false2_0 :: true:false
313.29/291.48	gen_0':s3_0 :: Nat -> 0':s
313.29/291.48	
313.29/291.48	
313.29/291.48	Generator Equations:
313.29/291.48	gen_0':s3_0(0) <=> 0'
313.29/291.48	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
313.29/291.48	
313.29/291.48	
313.29/291.48	The following defined symbols remain to be analysed:
313.29/291.48	+', *', ge, -, fact
313.29/291.48	
313.29/291.48	They will be analysed ascendingly in the following order:
313.29/291.48	+' < *'
313.29/291.48	*' < fact
313.29/291.48	ge < fact
313.29/291.48	- < fact
313.29/291.48	
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(10) LowerBoundPropagationProof (FINISHED)
313.29/291.48	Propagated lower bound.
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(11)
313.29/291.48	BOUNDS(n^1, INF)
313.29/291.48	
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(12)
313.29/291.48	Obligation:
313.29/291.48	TRS:
313.29/291.48	Rules:
313.29/291.48	+'(x, 0') -> x
313.29/291.48	+'(x, s(y)) -> s(+'(x, y))
313.29/291.48	*'(x, 0') -> 0'
313.29/291.48	*'(x, s(y)) -> +'(*'(x, y), x)
313.29/291.48	ge(x, 0') -> true
313.29/291.48	ge(0', s(y)) -> false
313.29/291.48	ge(s(x), s(y)) -> ge(x, y)
313.29/291.48	-(x, 0') -> x
313.29/291.48	-(s(x), s(y)) -> -(x, y)
313.29/291.48	fact(x) -> iffact(x, ge(x, s(s(0'))))
313.29/291.48	iffact(x, true) -> *'(x, fact(-(x, s(0'))))
313.29/291.48	iffact(x, false) -> s(0')
313.29/291.48	
313.29/291.48	Types:
313.29/291.48	+' :: 0':s -> 0':s -> 0':s
313.29/291.48	0' :: 0':s
313.29/291.48	s :: 0':s -> 0':s
313.29/291.48	*' :: 0':s -> 0':s -> 0':s
313.29/291.48	ge :: 0':s -> 0':s -> true:false
313.29/291.48	true :: true:false
313.29/291.48	false :: true:false
313.29/291.48	- :: 0':s -> 0':s -> 0':s
313.29/291.48	fact :: 0':s -> 0':s
313.29/291.48	iffact :: 0':s -> true:false -> 0':s
313.29/291.48	hole_0':s1_0 :: 0':s
313.29/291.48	hole_true:false2_0 :: true:false
313.29/291.48	gen_0':s3_0 :: Nat -> 0':s
313.29/291.48	
313.29/291.48	
313.29/291.48	Lemmas:
313.29/291.48	+'(gen_0':s3_0(a), gen_0':s3_0(n5_0)) -> gen_0':s3_0(+(n5_0, a)), rt in Omega(1 + n5_0)
313.29/291.48	
313.29/291.48	
313.29/291.48	Generator Equations:
313.29/291.48	gen_0':s3_0(0) <=> 0'
313.29/291.48	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
313.29/291.48	
313.29/291.48	
313.29/291.48	The following defined symbols remain to be analysed:
313.29/291.48	*', ge, -, fact
313.29/291.48	
313.29/291.48	They will be analysed ascendingly in the following order:
313.29/291.48	*' < fact
313.29/291.48	ge < fact
313.29/291.48	- < fact
313.29/291.48	
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(13) RewriteLemmaProof (LOWER BOUND(ID))
313.29/291.48	Proved the following rewrite lemma:
313.29/291.48	*'(gen_0':s3_0(a), gen_0':s3_0(n548_0)) -> gen_0':s3_0(*(n548_0, a)), rt in Omega(1 + a*n548_0 + n548_0)
313.29/291.48	
313.29/291.48	Induction Base:
313.29/291.48	*'(gen_0':s3_0(a), gen_0':s3_0(0)) ->_R^Omega(1)
313.29/291.48	0'
313.29/291.48	
313.29/291.48	Induction Step:
313.29/291.48	*'(gen_0':s3_0(a), gen_0':s3_0(+(n548_0, 1))) ->_R^Omega(1)
313.29/291.48	+'(*'(gen_0':s3_0(a), gen_0':s3_0(n548_0)), gen_0':s3_0(a)) ->_IH
313.29/291.48	+'(gen_0':s3_0(*(c549_0, a)), gen_0':s3_0(a)) ->_L^Omega(1 + a)
313.29/291.48	gen_0':s3_0(+(a, *(n548_0, a)))
313.29/291.48	
313.29/291.48	We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2).
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(14)
313.29/291.48	Complex Obligation (BEST)
313.29/291.48	
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(15)
313.29/291.48	Obligation:
313.29/291.48	Proved the lower bound n^2 for the following obligation:
313.29/291.48	
313.29/291.48	TRS:
313.29/291.48	Rules:
313.29/291.48	+'(x, 0') -> x
313.29/291.48	+'(x, s(y)) -> s(+'(x, y))
313.29/291.48	*'(x, 0') -> 0'
313.29/291.48	*'(x, s(y)) -> +'(*'(x, y), x)
313.29/291.48	ge(x, 0') -> true
313.29/291.48	ge(0', s(y)) -> false
313.29/291.48	ge(s(x), s(y)) -> ge(x, y)
313.29/291.48	-(x, 0') -> x
313.29/291.48	-(s(x), s(y)) -> -(x, y)
313.29/291.48	fact(x) -> iffact(x, ge(x, s(s(0'))))
313.29/291.48	iffact(x, true) -> *'(x, fact(-(x, s(0'))))
313.29/291.48	iffact(x, false) -> s(0')
313.29/291.48	
313.29/291.48	Types:
313.29/291.48	+' :: 0':s -> 0':s -> 0':s
313.29/291.48	0' :: 0':s
313.29/291.48	s :: 0':s -> 0':s
313.29/291.48	*' :: 0':s -> 0':s -> 0':s
313.29/291.48	ge :: 0':s -> 0':s -> true:false
313.29/291.48	true :: true:false
313.29/291.48	false :: true:false
313.29/291.48	- :: 0':s -> 0':s -> 0':s
313.29/291.48	fact :: 0':s -> 0':s
313.29/291.48	iffact :: 0':s -> true:false -> 0':s
313.29/291.48	hole_0':s1_0 :: 0':s
313.29/291.48	hole_true:false2_0 :: true:false
313.29/291.48	gen_0':s3_0 :: Nat -> 0':s
313.29/291.48	
313.29/291.48	
313.29/291.48	Lemmas:
313.29/291.48	+'(gen_0':s3_0(a), gen_0':s3_0(n5_0)) -> gen_0':s3_0(+(n5_0, a)), rt in Omega(1 + n5_0)
313.29/291.48	
313.29/291.48	
313.29/291.48	Generator Equations:
313.29/291.48	gen_0':s3_0(0) <=> 0'
313.29/291.48	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
313.29/291.48	
313.29/291.48	
313.29/291.48	The following defined symbols remain to be analysed:
313.29/291.48	*', ge, -, fact
313.29/291.48	
313.29/291.48	They will be analysed ascendingly in the following order:
313.29/291.48	*' < fact
313.29/291.48	ge < fact
313.29/291.48	- < fact
313.29/291.48	
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(16) LowerBoundPropagationProof (FINISHED)
313.29/291.48	Propagated lower bound.
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(17)
313.29/291.48	BOUNDS(n^2, INF)
313.29/291.48	
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(18)
313.29/291.48	Obligation:
313.29/291.48	TRS:
313.29/291.48	Rules:
313.29/291.48	+'(x, 0') -> x
313.29/291.48	+'(x, s(y)) -> s(+'(x, y))
313.29/291.48	*'(x, 0') -> 0'
313.29/291.48	*'(x, s(y)) -> +'(*'(x, y), x)
313.29/291.48	ge(x, 0') -> true
313.29/291.48	ge(0', s(y)) -> false
313.29/291.48	ge(s(x), s(y)) -> ge(x, y)
313.29/291.48	-(x, 0') -> x
313.29/291.48	-(s(x), s(y)) -> -(x, y)
313.29/291.48	fact(x) -> iffact(x, ge(x, s(s(0'))))
313.29/291.48	iffact(x, true) -> *'(x, fact(-(x, s(0'))))
313.29/291.48	iffact(x, false) -> s(0')
313.29/291.48	
313.29/291.48	Types:
313.29/291.48	+' :: 0':s -> 0':s -> 0':s
313.29/291.48	0' :: 0':s
313.29/291.48	s :: 0':s -> 0':s
313.29/291.48	*' :: 0':s -> 0':s -> 0':s
313.29/291.48	ge :: 0':s -> 0':s -> true:false
313.29/291.48	true :: true:false
313.29/291.48	false :: true:false
313.29/291.48	- :: 0':s -> 0':s -> 0':s
313.29/291.48	fact :: 0':s -> 0':s
313.29/291.48	iffact :: 0':s -> true:false -> 0':s
313.29/291.48	hole_0':s1_0 :: 0':s
313.29/291.48	hole_true:false2_0 :: true:false
313.29/291.48	gen_0':s3_0 :: Nat -> 0':s
313.29/291.48	
313.29/291.48	
313.29/291.48	Lemmas:
313.29/291.48	+'(gen_0':s3_0(a), gen_0':s3_0(n5_0)) -> gen_0':s3_0(+(n5_0, a)), rt in Omega(1 + n5_0)
313.29/291.48	*'(gen_0':s3_0(a), gen_0':s3_0(n548_0)) -> gen_0':s3_0(*(n548_0, a)), rt in Omega(1 + a*n548_0 + n548_0)
313.29/291.48	
313.29/291.48	
313.29/291.48	Generator Equations:
313.29/291.48	gen_0':s3_0(0) <=> 0'
313.29/291.48	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
313.29/291.48	
313.29/291.48	
313.29/291.48	The following defined symbols remain to be analysed:
313.29/291.48	ge, -, fact
313.29/291.48	
313.29/291.48	They will be analysed ascendingly in the following order:
313.29/291.48	ge < fact
313.29/291.48	- < fact
313.29/291.48	
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(19) RewriteLemmaProof (LOWER BOUND(ID))
313.29/291.48	Proved the following rewrite lemma:
313.29/291.48	ge(gen_0':s3_0(n1208_0), gen_0':s3_0(n1208_0)) -> true, rt in Omega(1 + n1208_0)
313.29/291.48	
313.29/291.48	Induction Base:
313.29/291.48	ge(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1)
313.29/291.48	true
313.29/291.48	
313.29/291.48	Induction Step:
313.29/291.48	ge(gen_0':s3_0(+(n1208_0, 1)), gen_0':s3_0(+(n1208_0, 1))) ->_R^Omega(1)
313.29/291.48	ge(gen_0':s3_0(n1208_0), gen_0':s3_0(n1208_0)) ->_IH
313.29/291.48	true
313.29/291.48	
313.29/291.48	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(20)
313.29/291.48	Obligation:
313.29/291.48	TRS:
313.29/291.48	Rules:
313.29/291.48	+'(x, 0') -> x
313.29/291.48	+'(x, s(y)) -> s(+'(x, y))
313.29/291.48	*'(x, 0') -> 0'
313.29/291.48	*'(x, s(y)) -> +'(*'(x, y), x)
313.29/291.48	ge(x, 0') -> true
313.29/291.48	ge(0', s(y)) -> false
313.29/291.48	ge(s(x), s(y)) -> ge(x, y)
313.29/291.48	-(x, 0') -> x
313.29/291.48	-(s(x), s(y)) -> -(x, y)
313.29/291.48	fact(x) -> iffact(x, ge(x, s(s(0'))))
313.29/291.48	iffact(x, true) -> *'(x, fact(-(x, s(0'))))
313.29/291.48	iffact(x, false) -> s(0')
313.29/291.48	
313.29/291.48	Types:
313.29/291.48	+' :: 0':s -> 0':s -> 0':s
313.29/291.48	0' :: 0':s
313.29/291.48	s :: 0':s -> 0':s
313.29/291.48	*' :: 0':s -> 0':s -> 0':s
313.29/291.48	ge :: 0':s -> 0':s -> true:false
313.29/291.48	true :: true:false
313.29/291.48	false :: true:false
313.29/291.48	- :: 0':s -> 0':s -> 0':s
313.29/291.48	fact :: 0':s -> 0':s
313.29/291.48	iffact :: 0':s -> true:false -> 0':s
313.29/291.48	hole_0':s1_0 :: 0':s
313.29/291.48	hole_true:false2_0 :: true:false
313.29/291.48	gen_0':s3_0 :: Nat -> 0':s
313.29/291.48	
313.29/291.48	
313.29/291.48	Lemmas:
313.29/291.48	+'(gen_0':s3_0(a), gen_0':s3_0(n5_0)) -> gen_0':s3_0(+(n5_0, a)), rt in Omega(1 + n5_0)
313.29/291.48	*'(gen_0':s3_0(a), gen_0':s3_0(n548_0)) -> gen_0':s3_0(*(n548_0, a)), rt in Omega(1 + a*n548_0 + n548_0)
313.29/291.48	ge(gen_0':s3_0(n1208_0), gen_0':s3_0(n1208_0)) -> true, rt in Omega(1 + n1208_0)
313.29/291.48	
313.29/291.48	
313.29/291.48	Generator Equations:
313.29/291.48	gen_0':s3_0(0) <=> 0'
313.29/291.48	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
313.29/291.48	
313.29/291.48	
313.29/291.48	The following defined symbols remain to be analysed:
313.29/291.48	-, fact
313.29/291.48	
313.29/291.48	They will be analysed ascendingly in the following order:
313.29/291.48	- < fact
313.29/291.48	
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(21) RewriteLemmaProof (LOWER BOUND(ID))
313.29/291.48	Proved the following rewrite lemma:
313.29/291.48	-(gen_0':s3_0(n1478_0), gen_0':s3_0(n1478_0)) -> gen_0':s3_0(0), rt in Omega(1 + n1478_0)
313.29/291.48	
313.29/291.48	Induction Base:
313.29/291.48	-(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1)
313.29/291.48	gen_0':s3_0(0)
313.29/291.48	
313.29/291.48	Induction Step:
313.29/291.48	-(gen_0':s3_0(+(n1478_0, 1)), gen_0':s3_0(+(n1478_0, 1))) ->_R^Omega(1)
313.29/291.48	-(gen_0':s3_0(n1478_0), gen_0':s3_0(n1478_0)) ->_IH
313.29/291.48	gen_0':s3_0(0)
313.29/291.48	
313.29/291.48	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
313.29/291.48	----------------------------------------
313.29/291.48	
313.29/291.48	(22)
313.29/291.48	Obligation:
313.29/291.48	TRS:
313.29/291.48	Rules:
313.29/291.48	+'(x, 0') -> x
313.29/291.48	+'(x, s(y)) -> s(+'(x, y))
313.29/291.48	*'(x, 0') -> 0'
313.29/291.48	*'(x, s(y)) -> +'(*'(x, y), x)
313.29/291.48	ge(x, 0') -> true
313.29/291.48	ge(0', s(y)) -> false
313.29/291.48	ge(s(x), s(y)) -> ge(x, y)
313.29/291.48	-(x, 0') -> x
313.29/291.48	-(s(x), s(y)) -> -(x, y)
313.29/291.48	fact(x) -> iffact(x, ge(x, s(s(0'))))
313.29/291.48	iffact(x, true) -> *'(x, fact(-(x, s(0'))))
313.29/291.48	iffact(x, false) -> s(0')
313.29/291.48	
313.29/291.48	Types:
313.29/291.48	+' :: 0':s -> 0':s -> 0':s
313.29/291.48	0' :: 0':s
313.29/291.48	s :: 0':s -> 0':s
313.29/291.48	*' :: 0':s -> 0':s -> 0':s
313.29/291.48	ge :: 0':s -> 0':s -> true:false
313.29/291.48	true :: true:false
313.29/291.48	false :: true:false
313.29/291.48	- :: 0':s -> 0':s -> 0':s
313.29/291.48	fact :: 0':s -> 0':s
313.29/291.48	iffact :: 0':s -> true:false -> 0':s
313.29/291.48	hole_0':s1_0 :: 0':s
313.29/291.48	hole_true:false2_0 :: true:false
313.29/291.48	gen_0':s3_0 :: Nat -> 0':s
313.29/291.48	
313.29/291.48	
313.29/291.48	Lemmas:
313.29/291.48	+'(gen_0':s3_0(a), gen_0':s3_0(n5_0)) -> gen_0':s3_0(+(n5_0, a)), rt in Omega(1 + n5_0)
313.29/291.48	*'(gen_0':s3_0(a), gen_0':s3_0(n548_0)) -> gen_0':s3_0(*(n548_0, a)), rt in Omega(1 + a*n548_0 + n548_0)
313.29/291.48	ge(gen_0':s3_0(n1208_0), gen_0':s3_0(n1208_0)) -> true, rt in Omega(1 + n1208_0)
313.29/291.48	-(gen_0':s3_0(n1478_0), gen_0':s3_0(n1478_0)) -> gen_0':s3_0(0), rt in Omega(1 + n1478_0)
313.29/291.48	
313.29/291.48	
313.29/291.48	Generator Equations:
313.29/291.48	gen_0':s3_0(0) <=> 0'
313.29/291.48	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
313.29/291.48	
313.29/291.48	
313.29/291.48	The following defined symbols remain to be analysed:
313.29/291.48	fact
313.29/291.50	EOF