946.53/291.42	WORST_CASE(Omega(n^3), ?)
946.53/291.44	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
946.53/291.44	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
946.53/291.44	
946.53/291.44	
946.53/291.44	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF).
946.53/291.44	
946.53/291.44	(0) CpxTRS
946.53/291.44	(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
946.53/291.44	(2) CpxTRS
946.53/291.44	(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
946.53/291.44	(4) typed CpxTrs
946.53/291.44	(5) OrderProof [LOWER BOUND(ID), 0 ms]
946.53/291.44	(6) typed CpxTrs
946.53/291.44	(7) RewriteLemmaProof [LOWER BOUND(ID), 303 ms]
946.53/291.44	(8) BEST
946.53/291.44	    (9) proven lower bound
946.53/291.44	        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
946.53/291.44	        (11) BOUNDS(n^1, INF)
946.53/291.44	    (12) typed CpxTrs
946.53/291.44	        (13) RewriteLemmaProof [LOWER BOUND(ID), 67 ms]
946.53/291.44	        (14) BEST
946.53/291.44	            (15) proven lower bound
946.53/291.44	                (16) LowerBoundPropagationProof [FINISHED, 0 ms]
946.53/291.44	                (17) BOUNDS(n^2, INF)
946.53/291.44	            (18) typed CpxTrs
946.53/291.44	                (19) RewriteLemmaProof [LOWER BOUND(ID), 908 ms]
946.53/291.44	                (20) typed CpxTrs
946.53/291.44	                (21) RewriteLemmaProof [LOWER BOUND(ID), 5937 ms]
946.53/291.44	                (22) proven lower bound
946.53/291.44	                (23) LowerBoundPropagationProof [FINISHED, 0 ms]
946.53/291.44	                (24) BOUNDS(n^3, INF)
946.53/291.44	
946.53/291.44	
946.53/291.44	----------------------------------------
946.53/291.44	
946.53/291.44	(0)
946.53/291.44	Obligation:
946.53/291.44	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF).
946.53/291.44	
946.53/291.44	
946.53/291.44	The TRS R consists of the following rules:
946.53/291.44	
946.53/291.44	   fac(0) -> 1
946.53/291.44	   fac(s(x)) -> *(s(x), fac(x))
946.53/291.44	   floop(0, y) -> y
946.53/291.44	   floop(s(x), y) -> floop(x, *(s(x), y))
946.53/291.44	   *(x, 0) -> 0
946.53/291.44	   *(x, s(y)) -> +(*(x, y), x)
946.53/291.44	   +(x, 0) -> x
946.53/291.44	   +(x, s(y)) -> s(+(x, y))
946.53/291.44	   1 -> s(0)
946.53/291.44	   fac(0) -> s(0)
946.53/291.44	
946.53/291.44	S is empty.
946.53/291.44	Rewrite Strategy: INNERMOST
946.53/291.44	----------------------------------------
946.53/291.44	
946.53/291.44	(1) RenamingProof (BOTH BOUNDS(ID, ID))
946.53/291.44	Renamed function symbols to avoid clashes with predefined symbol.
946.53/291.44	----------------------------------------
946.53/291.44	
946.53/291.44	(2)
946.53/291.44	Obligation:
946.53/291.44	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF).
946.53/291.44	
946.53/291.44	
946.53/291.44	The TRS R consists of the following rules:
946.53/291.44	
946.53/291.44	   fac(0') -> 1'
946.53/291.44	   fac(s(x)) -> *'(s(x), fac(x))
946.53/291.44	   floop(0', y) -> y
946.53/291.44	   floop(s(x), y) -> floop(x, *'(s(x), y))
946.53/291.44	   *'(x, 0') -> 0'
946.53/291.44	   *'(x, s(y)) -> +'(*'(x, y), x)
946.53/291.44	   +'(x, 0') -> x
946.53/291.44	   +'(x, s(y)) -> s(+'(x, y))
946.53/291.44	   1' -> s(0')
946.53/291.44	   fac(0') -> s(0')
946.53/291.44	
946.53/291.44	S is empty.
946.53/291.44	Rewrite Strategy: INNERMOST
946.53/291.44	----------------------------------------
946.53/291.44	
946.53/291.44	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
946.53/291.44	Infered types.
946.53/291.44	----------------------------------------
946.53/291.44	
946.53/291.44	(4)
946.53/291.44	Obligation:
946.53/291.44	Innermost TRS:
946.53/291.44	Rules:
946.53/291.44	fac(0') -> 1'
946.53/291.44	fac(s(x)) -> *'(s(x), fac(x))
946.53/291.44	floop(0', y) -> y
946.53/291.44	floop(s(x), y) -> floop(x, *'(s(x), y))
946.53/291.44	*'(x, 0') -> 0'
946.53/291.44	*'(x, s(y)) -> +'(*'(x, y), x)
946.53/291.44	+'(x, 0') -> x
946.53/291.44	+'(x, s(y)) -> s(+'(x, y))
946.53/291.44	1' -> s(0')
946.53/291.44	fac(0') -> s(0')
946.53/291.44	
946.53/291.44	Types:
946.53/291.44	fac :: 0':s -> 0':s
946.53/291.44	0' :: 0':s
946.53/291.44	1' :: 0':s
946.53/291.44	s :: 0':s -> 0':s
946.53/291.44	*' :: 0':s -> 0':s -> 0':s
946.53/291.44	floop :: 0':s -> 0':s -> 0':s
946.53/291.44	+' :: 0':s -> 0':s -> 0':s
946.53/291.44	hole_0':s1_0 :: 0':s
946.53/291.44	gen_0':s2_0 :: Nat -> 0':s
946.53/291.44	
946.53/291.44	----------------------------------------
946.53/291.44	
946.53/291.44	(5) OrderProof (LOWER BOUND(ID))
946.53/291.44	Heuristically decided to analyse the following defined symbols:
946.53/291.44	fac, *', floop, +'
946.53/291.44	
946.53/291.44	They will be analysed ascendingly in the following order:
946.53/291.44	*' < fac
946.53/291.44	*' < floop
946.53/291.44	+' < *'
946.53/291.44	
946.53/291.44	----------------------------------------
946.53/291.44	
946.53/291.44	(6)
946.53/291.44	Obligation:
946.53/291.44	Innermost TRS:
946.53/291.44	Rules:
946.53/291.44	fac(0') -> 1'
946.53/291.44	fac(s(x)) -> *'(s(x), fac(x))
946.53/291.44	floop(0', y) -> y
946.53/291.44	floop(s(x), y) -> floop(x, *'(s(x), y))
946.53/291.44	*'(x, 0') -> 0'
946.53/291.44	*'(x, s(y)) -> +'(*'(x, y), x)
946.53/291.44	+'(x, 0') -> x
946.53/291.44	+'(x, s(y)) -> s(+'(x, y))
946.53/291.44	1' -> s(0')
946.53/291.44	fac(0') -> s(0')
946.53/291.44	
946.53/291.44	Types:
946.53/291.44	fac :: 0':s -> 0':s
946.53/291.44	0' :: 0':s
946.53/291.44	1' :: 0':s
946.53/291.44	s :: 0':s -> 0':s
946.53/291.44	*' :: 0':s -> 0':s -> 0':s
946.53/291.44	floop :: 0':s -> 0':s -> 0':s
946.53/291.44	+' :: 0':s -> 0':s -> 0':s
946.53/291.44	hole_0':s1_0 :: 0':s
946.53/291.44	gen_0':s2_0 :: Nat -> 0':s
946.53/291.44	
946.53/291.44	
946.53/291.44	Generator Equations:
946.53/291.44	gen_0':s2_0(0) <=> 0'
946.53/291.44	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
946.53/291.44	
946.53/291.44	
946.53/291.44	The following defined symbols remain to be analysed:
946.53/291.44	+', fac, *', floop
946.53/291.44	
946.53/291.44	They will be analysed ascendingly in the following order:
946.53/291.44	*' < fac
946.53/291.44	*' < floop
946.53/291.44	+' < *'
946.53/291.44	
946.53/291.44	----------------------------------------
946.53/291.44	
946.53/291.44	(7) RewriteLemmaProof (LOWER BOUND(ID))
946.53/291.44	Proved the following rewrite lemma:
946.53/291.44	+'(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0)
946.87/291.44	
946.87/291.44	Induction Base:
946.87/291.44	+'(gen_0':s2_0(a), gen_0':s2_0(0)) ->_R^Omega(1)
946.87/291.44	gen_0':s2_0(a)
946.87/291.44	
946.87/291.44	Induction Step:
946.87/291.44	+'(gen_0':s2_0(a), gen_0':s2_0(+(n4_0, 1))) ->_R^Omega(1)
946.87/291.44	s(+'(gen_0':s2_0(a), gen_0':s2_0(n4_0))) ->_IH
946.87/291.44	s(gen_0':s2_0(+(a, c5_0)))
946.87/291.44	
946.87/291.44	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(8)
946.87/291.44	Complex Obligation (BEST)
946.87/291.44	
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(9)
946.87/291.44	Obligation:
946.87/291.44	Proved the lower bound n^1 for the following obligation:
946.87/291.44	
946.87/291.44	Innermost TRS:
946.87/291.44	Rules:
946.87/291.44	fac(0') -> 1'
946.87/291.44	fac(s(x)) -> *'(s(x), fac(x))
946.87/291.44	floop(0', y) -> y
946.87/291.44	floop(s(x), y) -> floop(x, *'(s(x), y))
946.87/291.44	*'(x, 0') -> 0'
946.87/291.44	*'(x, s(y)) -> +'(*'(x, y), x)
946.87/291.44	+'(x, 0') -> x
946.87/291.44	+'(x, s(y)) -> s(+'(x, y))
946.87/291.44	1' -> s(0')
946.87/291.44	fac(0') -> s(0')
946.87/291.44	
946.87/291.44	Types:
946.87/291.44	fac :: 0':s -> 0':s
946.87/291.44	0' :: 0':s
946.87/291.44	1' :: 0':s
946.87/291.44	s :: 0':s -> 0':s
946.87/291.44	*' :: 0':s -> 0':s -> 0':s
946.87/291.44	floop :: 0':s -> 0':s -> 0':s
946.87/291.44	+' :: 0':s -> 0':s -> 0':s
946.87/291.44	hole_0':s1_0 :: 0':s
946.87/291.44	gen_0':s2_0 :: Nat -> 0':s
946.87/291.44	
946.87/291.44	
946.87/291.44	Generator Equations:
946.87/291.44	gen_0':s2_0(0) <=> 0'
946.87/291.44	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
946.87/291.44	
946.87/291.44	
946.87/291.44	The following defined symbols remain to be analysed:
946.87/291.44	+', fac, *', floop
946.87/291.44	
946.87/291.44	They will be analysed ascendingly in the following order:
946.87/291.44	*' < fac
946.87/291.44	*' < floop
946.87/291.44	+' < *'
946.87/291.44	
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(10) LowerBoundPropagationProof (FINISHED)
946.87/291.44	Propagated lower bound.
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(11)
946.87/291.44	BOUNDS(n^1, INF)
946.87/291.44	
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(12)
946.87/291.44	Obligation:
946.87/291.44	Innermost TRS:
946.87/291.44	Rules:
946.87/291.44	fac(0') -> 1'
946.87/291.44	fac(s(x)) -> *'(s(x), fac(x))
946.87/291.44	floop(0', y) -> y
946.87/291.44	floop(s(x), y) -> floop(x, *'(s(x), y))
946.87/291.44	*'(x, 0') -> 0'
946.87/291.44	*'(x, s(y)) -> +'(*'(x, y), x)
946.87/291.44	+'(x, 0') -> x
946.87/291.44	+'(x, s(y)) -> s(+'(x, y))
946.87/291.44	1' -> s(0')
946.87/291.44	fac(0') -> s(0')
946.87/291.44	
946.87/291.44	Types:
946.87/291.44	fac :: 0':s -> 0':s
946.87/291.44	0' :: 0':s
946.87/291.44	1' :: 0':s
946.87/291.44	s :: 0':s -> 0':s
946.87/291.44	*' :: 0':s -> 0':s -> 0':s
946.87/291.44	floop :: 0':s -> 0':s -> 0':s
946.87/291.44	+' :: 0':s -> 0':s -> 0':s
946.87/291.44	hole_0':s1_0 :: 0':s
946.87/291.44	gen_0':s2_0 :: Nat -> 0':s
946.87/291.44	
946.87/291.44	
946.87/291.44	Lemmas:
946.87/291.44	+'(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0)
946.87/291.44	
946.87/291.44	
946.87/291.44	Generator Equations:
946.87/291.44	gen_0':s2_0(0) <=> 0'
946.87/291.44	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
946.87/291.44	
946.87/291.44	
946.87/291.44	The following defined symbols remain to be analysed:
946.87/291.44	*', fac, floop
946.87/291.44	
946.87/291.44	They will be analysed ascendingly in the following order:
946.87/291.44	*' < fac
946.87/291.44	*' < floop
946.87/291.44	
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(13) RewriteLemmaProof (LOWER BOUND(ID))
946.87/291.44	Proved the following rewrite lemma:
946.87/291.44	*'(gen_0':s2_0(a), gen_0':s2_0(n591_0)) -> gen_0':s2_0(*(n591_0, a)), rt in Omega(1 + a*n591_0 + n591_0)
946.87/291.44	
946.87/291.44	Induction Base:
946.87/291.44	*'(gen_0':s2_0(a), gen_0':s2_0(0)) ->_R^Omega(1)
946.87/291.44	0'
946.87/291.44	
946.87/291.44	Induction Step:
946.87/291.44	*'(gen_0':s2_0(a), gen_0':s2_0(+(n591_0, 1))) ->_R^Omega(1)
946.87/291.44	+'(*'(gen_0':s2_0(a), gen_0':s2_0(n591_0)), gen_0':s2_0(a)) ->_IH
946.87/291.44	+'(gen_0':s2_0(*(c592_0, a)), gen_0':s2_0(a)) ->_L^Omega(1 + a)
946.87/291.44	gen_0':s2_0(+(a, *(n591_0, a)))
946.87/291.44	
946.87/291.44	We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2).
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(14)
946.87/291.44	Complex Obligation (BEST)
946.87/291.44	
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(15)
946.87/291.44	Obligation:
946.87/291.44	Proved the lower bound n^2 for the following obligation:
946.87/291.44	
946.87/291.44	Innermost TRS:
946.87/291.44	Rules:
946.87/291.44	fac(0') -> 1'
946.87/291.44	fac(s(x)) -> *'(s(x), fac(x))
946.87/291.44	floop(0', y) -> y
946.87/291.44	floop(s(x), y) -> floop(x, *'(s(x), y))
946.87/291.44	*'(x, 0') -> 0'
946.87/291.44	*'(x, s(y)) -> +'(*'(x, y), x)
946.87/291.44	+'(x, 0') -> x
946.87/291.44	+'(x, s(y)) -> s(+'(x, y))
946.87/291.44	1' -> s(0')
946.87/291.44	fac(0') -> s(0')
946.87/291.44	
946.87/291.44	Types:
946.87/291.44	fac :: 0':s -> 0':s
946.87/291.44	0' :: 0':s
946.87/291.44	1' :: 0':s
946.87/291.44	s :: 0':s -> 0':s
946.87/291.44	*' :: 0':s -> 0':s -> 0':s
946.87/291.44	floop :: 0':s -> 0':s -> 0':s
946.87/291.44	+' :: 0':s -> 0':s -> 0':s
946.87/291.44	hole_0':s1_0 :: 0':s
946.87/291.44	gen_0':s2_0 :: Nat -> 0':s
946.87/291.44	
946.87/291.44	
946.87/291.44	Lemmas:
946.87/291.44	+'(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0)
946.87/291.44	
946.87/291.44	
946.87/291.44	Generator Equations:
946.87/291.44	gen_0':s2_0(0) <=> 0'
946.87/291.44	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
946.87/291.44	
946.87/291.44	
946.87/291.44	The following defined symbols remain to be analysed:
946.87/291.44	*', fac, floop
946.87/291.44	
946.87/291.44	They will be analysed ascendingly in the following order:
946.87/291.44	*' < fac
946.87/291.44	*' < floop
946.87/291.44	
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(16) LowerBoundPropagationProof (FINISHED)
946.87/291.44	Propagated lower bound.
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(17)
946.87/291.44	BOUNDS(n^2, INF)
946.87/291.44	
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(18)
946.87/291.44	Obligation:
946.87/291.44	Innermost TRS:
946.87/291.44	Rules:
946.87/291.44	fac(0') -> 1'
946.87/291.44	fac(s(x)) -> *'(s(x), fac(x))
946.87/291.44	floop(0', y) -> y
946.87/291.44	floop(s(x), y) -> floop(x, *'(s(x), y))
946.87/291.44	*'(x, 0') -> 0'
946.87/291.44	*'(x, s(y)) -> +'(*'(x, y), x)
946.87/291.44	+'(x, 0') -> x
946.87/291.44	+'(x, s(y)) -> s(+'(x, y))
946.87/291.44	1' -> s(0')
946.87/291.44	fac(0') -> s(0')
946.87/291.44	
946.87/291.44	Types:
946.87/291.44	fac :: 0':s -> 0':s
946.87/291.44	0' :: 0':s
946.87/291.44	1' :: 0':s
946.87/291.44	s :: 0':s -> 0':s
946.87/291.44	*' :: 0':s -> 0':s -> 0':s
946.87/291.44	floop :: 0':s -> 0':s -> 0':s
946.87/291.44	+' :: 0':s -> 0':s -> 0':s
946.87/291.44	hole_0':s1_0 :: 0':s
946.87/291.44	gen_0':s2_0 :: Nat -> 0':s
946.87/291.44	
946.87/291.44	
946.87/291.44	Lemmas:
946.87/291.44	+'(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0)
946.87/291.44	*'(gen_0':s2_0(a), gen_0':s2_0(n591_0)) -> gen_0':s2_0(*(n591_0, a)), rt in Omega(1 + a*n591_0 + n591_0)
946.87/291.44	
946.87/291.44	
946.87/291.44	Generator Equations:
946.87/291.44	gen_0':s2_0(0) <=> 0'
946.87/291.44	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
946.87/291.44	
946.87/291.44	
946.87/291.44	The following defined symbols remain to be analysed:
946.87/291.44	fac, floop
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(19) RewriteLemmaProof (LOWER BOUND(ID))
946.87/291.44	Proved the following rewrite lemma:
946.87/291.44	fac(gen_0':s2_0(+(1, n1297_0))) -> *3_0, rt in Omega(n1297_0)
946.87/291.44	
946.87/291.44	Induction Base:
946.87/291.44	fac(gen_0':s2_0(+(1, 0)))
946.87/291.44	
946.87/291.44	Induction Step:
946.87/291.44	fac(gen_0':s2_0(+(1, +(n1297_0, 1)))) ->_R^Omega(1)
946.87/291.44	*'(s(gen_0':s2_0(+(1, n1297_0))), fac(gen_0':s2_0(+(1, n1297_0)))) ->_IH
946.87/291.44	*'(s(gen_0':s2_0(+(1, n1297_0))), *3_0)
946.87/291.44	
946.87/291.44	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(20)
946.87/291.44	Obligation:
946.87/291.44	Innermost TRS:
946.87/291.44	Rules:
946.87/291.44	fac(0') -> 1'
946.87/291.44	fac(s(x)) -> *'(s(x), fac(x))
946.87/291.44	floop(0', y) -> y
946.87/291.44	floop(s(x), y) -> floop(x, *'(s(x), y))
946.87/291.44	*'(x, 0') -> 0'
946.87/291.44	*'(x, s(y)) -> +'(*'(x, y), x)
946.87/291.44	+'(x, 0') -> x
946.87/291.44	+'(x, s(y)) -> s(+'(x, y))
946.87/291.44	1' -> s(0')
946.87/291.44	fac(0') -> s(0')
946.87/291.44	
946.87/291.44	Types:
946.87/291.44	fac :: 0':s -> 0':s
946.87/291.44	0' :: 0':s
946.87/291.44	1' :: 0':s
946.87/291.44	s :: 0':s -> 0':s
946.87/291.44	*' :: 0':s -> 0':s -> 0':s
946.87/291.44	floop :: 0':s -> 0':s -> 0':s
946.87/291.44	+' :: 0':s -> 0':s -> 0':s
946.87/291.44	hole_0':s1_0 :: 0':s
946.87/291.44	gen_0':s2_0 :: Nat -> 0':s
946.87/291.44	
946.87/291.44	
946.87/291.44	Lemmas:
946.87/291.44	+'(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0)
946.87/291.44	*'(gen_0':s2_0(a), gen_0':s2_0(n591_0)) -> gen_0':s2_0(*(n591_0, a)), rt in Omega(1 + a*n591_0 + n591_0)
946.87/291.44	fac(gen_0':s2_0(+(1, n1297_0))) -> *3_0, rt in Omega(n1297_0)
946.87/291.44	
946.87/291.44	
946.87/291.44	Generator Equations:
946.87/291.44	gen_0':s2_0(0) <=> 0'
946.87/291.44	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
946.87/291.44	
946.87/291.44	
946.87/291.44	The following defined symbols remain to be analysed:
946.87/291.44	floop
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(21) RewriteLemmaProof (LOWER BOUND(ID))
946.87/291.44	Proved the following rewrite lemma:
946.87/291.44	floop(gen_0':s2_0(n2437_0), gen_0':s2_0(b)) -> *3_0, rt in Omega(b*n2437_0 + b*n2437_0^2 + n2437_0)
946.87/291.44	
946.87/291.44	Induction Base:
946.87/291.44	floop(gen_0':s2_0(0), gen_0':s2_0(b))
946.87/291.44	
946.87/291.44	Induction Step:
946.87/291.44	floop(gen_0':s2_0(+(n2437_0, 1)), gen_0':s2_0(b)) ->_R^Omega(1)
946.87/291.44	floop(gen_0':s2_0(n2437_0), *'(s(gen_0':s2_0(n2437_0)), gen_0':s2_0(b))) ->_L^Omega(1 + 2*b + b*n2437_0)
946.87/291.44	floop(gen_0':s2_0(n2437_0), gen_0':s2_0(*(b, +(n2437_0, 1)))) ->_IH
946.87/291.44	*3_0
946.87/291.44	
946.87/291.44	We have rt in Omega(n^3) and sz in O(n). Thus, we have irc_R in Omega(n^3).
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(22)
946.87/291.44	Obligation:
946.87/291.44	Proved the lower bound n^3 for the following obligation:
946.87/291.44	
946.87/291.44	Innermost TRS:
946.87/291.44	Rules:
946.87/291.44	fac(0') -> 1'
946.87/291.44	fac(s(x)) -> *'(s(x), fac(x))
946.87/291.44	floop(0', y) -> y
946.87/291.44	floop(s(x), y) -> floop(x, *'(s(x), y))
946.87/291.44	*'(x, 0') -> 0'
946.87/291.44	*'(x, s(y)) -> +'(*'(x, y), x)
946.87/291.44	+'(x, 0') -> x
946.87/291.44	+'(x, s(y)) -> s(+'(x, y))
946.87/291.44	1' -> s(0')
946.87/291.44	fac(0') -> s(0')
946.87/291.44	
946.87/291.44	Types:
946.87/291.44	fac :: 0':s -> 0':s
946.87/291.44	0' :: 0':s
946.87/291.44	1' :: 0':s
946.87/291.44	s :: 0':s -> 0':s
946.87/291.44	*' :: 0':s -> 0':s -> 0':s
946.87/291.44	floop :: 0':s -> 0':s -> 0':s
946.87/291.44	+' :: 0':s -> 0':s -> 0':s
946.87/291.44	hole_0':s1_0 :: 0':s
946.87/291.44	gen_0':s2_0 :: Nat -> 0':s
946.87/291.44	
946.87/291.44	
946.87/291.44	Lemmas:
946.87/291.44	+'(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0)
946.87/291.44	*'(gen_0':s2_0(a), gen_0':s2_0(n591_0)) -> gen_0':s2_0(*(n591_0, a)), rt in Omega(1 + a*n591_0 + n591_0)
946.87/291.44	fac(gen_0':s2_0(+(1, n1297_0))) -> *3_0, rt in Omega(n1297_0)
946.87/291.44	
946.87/291.44	
946.87/291.44	Generator Equations:
946.87/291.44	gen_0':s2_0(0) <=> 0'
946.87/291.44	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
946.87/291.44	
946.87/291.44	
946.87/291.44	The following defined symbols remain to be analysed:
946.87/291.44	floop
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(23) LowerBoundPropagationProof (FINISHED)
946.87/291.44	Propagated lower bound.
946.87/291.44	----------------------------------------
946.87/291.44	
946.87/291.44	(24)
946.87/291.44	BOUNDS(n^3, INF)
946.87/291.48	EOF