325.86/291.53	WORST_CASE(Omega(n^2), ?)
325.86/291.54	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
325.86/291.54	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
325.86/291.54	
325.86/291.54	
325.86/291.54	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
325.86/291.54	
325.86/291.54	(0) CpxTRS
325.86/291.54	(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
325.86/291.54	(2) CpxTRS
325.86/291.54	(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
325.86/291.54	(4) typed CpxTrs
325.86/291.54	(5) OrderProof [LOWER BOUND(ID), 0 ms]
325.86/291.54	(6) typed CpxTrs
325.86/291.54	(7) RewriteLemmaProof [LOWER BOUND(ID), 375 ms]
325.86/291.54	(8) BEST
325.86/291.54	    (9) proven lower bound
325.86/291.54	        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
325.86/291.54	        (11) BOUNDS(n^1, INF)
325.86/291.54	    (12) typed CpxTrs
325.86/291.54	        (13) RewriteLemmaProof [LOWER BOUND(ID), 4065 ms]
325.86/291.54	        (14) BEST
325.86/291.54	            (15) proven lower bound
325.86/291.54	                (16) LowerBoundPropagationProof [FINISHED, 0 ms]
325.86/291.54	                (17) BOUNDS(n^2, INF)
325.86/291.54	            (18) typed CpxTrs
325.86/291.54	                (19) RewriteLemmaProof [LOWER BOUND(ID), 11 ms]
325.86/291.54	                (20) typed CpxTrs
325.86/291.54	                (21) RewriteLemmaProof [LOWER BOUND(ID), 345 ms]
325.86/291.54	                (22) BOUNDS(1, INF)
325.86/291.54	
325.86/291.54	
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(0)
325.86/291.54	Obligation:
325.86/291.54	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
325.86/291.54	
325.86/291.54	
325.86/291.54	The TRS R consists of the following rules:
325.86/291.54	
325.86/291.54	   +(x, 0) -> x
325.86/291.54	   +(0, x) -> x
325.86/291.54	   +(s(x), s(y)) -> s(s(+(x, y)))
325.86/291.54	   *(x, 0) -> 0
325.86/291.54	   *(0, x) -> 0
325.86/291.54	   *(s(x), s(y)) -> s(+(*(x, y), +(x, y)))
325.86/291.54	   sum(nil) -> 0
325.86/291.54	   sum(cons(x, l)) -> +(x, sum(l))
325.86/291.54	   prod(nil) -> s(0)
325.86/291.54	   prod(cons(x, l)) -> *(x, prod(l))
325.86/291.54	
325.86/291.54	S is empty.
325.86/291.54	Rewrite Strategy: FULL
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(1) RenamingProof (BOTH BOUNDS(ID, ID))
325.86/291.54	Renamed function symbols to avoid clashes with predefined symbol.
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(2)
325.86/291.54	Obligation:
325.86/291.54	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
325.86/291.54	
325.86/291.54	
325.86/291.54	The TRS R consists of the following rules:
325.86/291.54	
325.86/291.54	   +'(x, 0') -> x
325.86/291.54	   +'(0', x) -> x
325.86/291.54	   +'(s(x), s(y)) -> s(s(+'(x, y)))
325.86/291.54	   *'(x, 0') -> 0'
325.86/291.54	   *'(0', x) -> 0'
325.86/291.54	   *'(s(x), s(y)) -> s(+'(*'(x, y), +'(x, y)))
325.86/291.54	   sum(nil) -> 0'
325.86/291.54	   sum(cons(x, l)) -> +'(x, sum(l))
325.86/291.54	   prod(nil) -> s(0')
325.86/291.54	   prod(cons(x, l)) -> *'(x, prod(l))
325.86/291.54	
325.86/291.54	S is empty.
325.86/291.54	Rewrite Strategy: FULL
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
325.86/291.54	Infered types.
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(4)
325.86/291.54	Obligation:
325.86/291.54	TRS:
325.86/291.54	Rules:
325.86/291.54	+'(x, 0') -> x
325.86/291.54	+'(0', x) -> x
325.86/291.54	+'(s(x), s(y)) -> s(s(+'(x, y)))
325.86/291.54	*'(x, 0') -> 0'
325.86/291.54	*'(0', x) -> 0'
325.86/291.54	*'(s(x), s(y)) -> s(+'(*'(x, y), +'(x, y)))
325.86/291.54	sum(nil) -> 0'
325.86/291.54	sum(cons(x, l)) -> +'(x, sum(l))
325.86/291.54	prod(nil) -> s(0')
325.86/291.54	prod(cons(x, l)) -> *'(x, prod(l))
325.86/291.54	
325.86/291.54	Types:
325.86/291.54	+' :: 0':s -> 0':s -> 0':s
325.86/291.54	0' :: 0':s
325.86/291.54	s :: 0':s -> 0':s
325.86/291.54	*' :: 0':s -> 0':s -> 0':s
325.86/291.54	sum :: nil:cons -> 0':s
325.86/291.54	nil :: nil:cons
325.86/291.54	cons :: 0':s -> nil:cons -> nil:cons
325.86/291.54	prod :: nil:cons -> 0':s
325.86/291.54	hole_0':s1_0 :: 0':s
325.86/291.54	hole_nil:cons2_0 :: nil:cons
325.86/291.54	gen_0':s3_0 :: Nat -> 0':s
325.86/291.54	gen_nil:cons4_0 :: Nat -> nil:cons
325.86/291.54	
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(5) OrderProof (LOWER BOUND(ID))
325.86/291.54	Heuristically decided to analyse the following defined symbols:
325.86/291.54	+', *', sum, prod
325.86/291.54	
325.86/291.54	They will be analysed ascendingly in the following order:
325.86/291.54	+' < *'
325.86/291.54	+' < sum
325.86/291.54	*' < prod
325.86/291.54	
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(6)
325.86/291.54	Obligation:
325.86/291.54	TRS:
325.86/291.54	Rules:
325.86/291.54	+'(x, 0') -> x
325.86/291.54	+'(0', x) -> x
325.86/291.54	+'(s(x), s(y)) -> s(s(+'(x, y)))
325.86/291.54	*'(x, 0') -> 0'
325.86/291.54	*'(0', x) -> 0'
325.86/291.54	*'(s(x), s(y)) -> s(+'(*'(x, y), +'(x, y)))
325.86/291.54	sum(nil) -> 0'
325.86/291.54	sum(cons(x, l)) -> +'(x, sum(l))
325.86/291.54	prod(nil) -> s(0')
325.86/291.54	prod(cons(x, l)) -> *'(x, prod(l))
325.86/291.54	
325.86/291.54	Types:
325.86/291.54	+' :: 0':s -> 0':s -> 0':s
325.86/291.54	0' :: 0':s
325.86/291.54	s :: 0':s -> 0':s
325.86/291.54	*' :: 0':s -> 0':s -> 0':s
325.86/291.54	sum :: nil:cons -> 0':s
325.86/291.54	nil :: nil:cons
325.86/291.54	cons :: 0':s -> nil:cons -> nil:cons
325.86/291.54	prod :: nil:cons -> 0':s
325.86/291.54	hole_0':s1_0 :: 0':s
325.86/291.54	hole_nil:cons2_0 :: nil:cons
325.86/291.54	gen_0':s3_0 :: Nat -> 0':s
325.86/291.54	gen_nil:cons4_0 :: Nat -> nil:cons
325.86/291.54	
325.86/291.54	
325.86/291.54	Generator Equations:
325.86/291.54	gen_0':s3_0(0) <=> 0'
325.86/291.54	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
325.86/291.54	gen_nil:cons4_0(0) <=> nil
325.86/291.54	gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x))
325.86/291.54	
325.86/291.54	
325.86/291.54	The following defined symbols remain to be analysed:
325.86/291.54	+', *', sum, prod
325.86/291.54	
325.86/291.54	They will be analysed ascendingly in the following order:
325.86/291.54	+' < *'
325.86/291.54	+' < sum
325.86/291.54	*' < prod
325.86/291.54	
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(7) RewriteLemmaProof (LOWER BOUND(ID))
325.86/291.54	Proved the following rewrite lemma:
325.86/291.54	+'(gen_0':s3_0(n6_0), gen_0':s3_0(n6_0)) -> gen_0':s3_0(*(2, n6_0)), rt in Omega(1 + n6_0)
325.86/291.54	
325.86/291.54	Induction Base:
325.86/291.54	+'(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1)
325.86/291.54	gen_0':s3_0(0)
325.86/291.54	
325.86/291.54	Induction Step:
325.86/291.54	+'(gen_0':s3_0(+(n6_0, 1)), gen_0':s3_0(+(n6_0, 1))) ->_R^Omega(1)
325.86/291.54	s(s(+'(gen_0':s3_0(n6_0), gen_0':s3_0(n6_0)))) ->_IH
325.86/291.54	s(s(gen_0':s3_0(*(2, c7_0))))
325.86/291.54	
325.86/291.54	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(8)
325.86/291.54	Complex Obligation (BEST)
325.86/291.54	
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(9)
325.86/291.54	Obligation:
325.86/291.54	Proved the lower bound n^1 for the following obligation:
325.86/291.54	
325.86/291.54	TRS:
325.86/291.54	Rules:
325.86/291.54	+'(x, 0') -> x
325.86/291.54	+'(0', x) -> x
325.86/291.54	+'(s(x), s(y)) -> s(s(+'(x, y)))
325.86/291.54	*'(x, 0') -> 0'
325.86/291.54	*'(0', x) -> 0'
325.86/291.54	*'(s(x), s(y)) -> s(+'(*'(x, y), +'(x, y)))
325.86/291.54	sum(nil) -> 0'
325.86/291.54	sum(cons(x, l)) -> +'(x, sum(l))
325.86/291.54	prod(nil) -> s(0')
325.86/291.54	prod(cons(x, l)) -> *'(x, prod(l))
325.86/291.54	
325.86/291.54	Types:
325.86/291.54	+' :: 0':s -> 0':s -> 0':s
325.86/291.54	0' :: 0':s
325.86/291.54	s :: 0':s -> 0':s
325.86/291.54	*' :: 0':s -> 0':s -> 0':s
325.86/291.54	sum :: nil:cons -> 0':s
325.86/291.54	nil :: nil:cons
325.86/291.54	cons :: 0':s -> nil:cons -> nil:cons
325.86/291.54	prod :: nil:cons -> 0':s
325.86/291.54	hole_0':s1_0 :: 0':s
325.86/291.54	hole_nil:cons2_0 :: nil:cons
325.86/291.54	gen_0':s3_0 :: Nat -> 0':s
325.86/291.54	gen_nil:cons4_0 :: Nat -> nil:cons
325.86/291.54	
325.86/291.54	
325.86/291.54	Generator Equations:
325.86/291.54	gen_0':s3_0(0) <=> 0'
325.86/291.54	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
325.86/291.54	gen_nil:cons4_0(0) <=> nil
325.86/291.54	gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x))
325.86/291.54	
325.86/291.54	
325.86/291.54	The following defined symbols remain to be analysed:
325.86/291.54	+', *', sum, prod
325.86/291.54	
325.86/291.54	They will be analysed ascendingly in the following order:
325.86/291.54	+' < *'
325.86/291.54	+' < sum
325.86/291.54	*' < prod
325.86/291.54	
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(10) LowerBoundPropagationProof (FINISHED)
325.86/291.54	Propagated lower bound.
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(11)
325.86/291.54	BOUNDS(n^1, INF)
325.86/291.54	
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(12)
325.86/291.54	Obligation:
325.86/291.54	TRS:
325.86/291.54	Rules:
325.86/291.54	+'(x, 0') -> x
325.86/291.54	+'(0', x) -> x
325.86/291.54	+'(s(x), s(y)) -> s(s(+'(x, y)))
325.86/291.54	*'(x, 0') -> 0'
325.86/291.54	*'(0', x) -> 0'
325.86/291.54	*'(s(x), s(y)) -> s(+'(*'(x, y), +'(x, y)))
325.86/291.54	sum(nil) -> 0'
325.86/291.54	sum(cons(x, l)) -> +'(x, sum(l))
325.86/291.54	prod(nil) -> s(0')
325.86/291.54	prod(cons(x, l)) -> *'(x, prod(l))
325.86/291.54	
325.86/291.54	Types:
325.86/291.54	+' :: 0':s -> 0':s -> 0':s
325.86/291.54	0' :: 0':s
325.86/291.54	s :: 0':s -> 0':s
325.86/291.54	*' :: 0':s -> 0':s -> 0':s
325.86/291.54	sum :: nil:cons -> 0':s
325.86/291.54	nil :: nil:cons
325.86/291.54	cons :: 0':s -> nil:cons -> nil:cons
325.86/291.54	prod :: nil:cons -> 0':s
325.86/291.54	hole_0':s1_0 :: 0':s
325.86/291.54	hole_nil:cons2_0 :: nil:cons
325.86/291.54	gen_0':s3_0 :: Nat -> 0':s
325.86/291.54	gen_nil:cons4_0 :: Nat -> nil:cons
325.86/291.54	
325.86/291.54	
325.86/291.54	Lemmas:
325.86/291.54	+'(gen_0':s3_0(n6_0), gen_0':s3_0(n6_0)) -> gen_0':s3_0(*(2, n6_0)), rt in Omega(1 + n6_0)
325.86/291.54	
325.86/291.54	
325.86/291.54	Generator Equations:
325.86/291.54	gen_0':s3_0(0) <=> 0'
325.86/291.54	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
325.86/291.54	gen_nil:cons4_0(0) <=> nil
325.86/291.54	gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x))
325.86/291.54	
325.86/291.54	
325.86/291.54	The following defined symbols remain to be analysed:
325.86/291.54	*', sum, prod
325.86/291.54	
325.86/291.54	They will be analysed ascendingly in the following order:
325.86/291.54	*' < prod
325.86/291.54	
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(13) RewriteLemmaProof (LOWER BOUND(ID))
325.86/291.54	Proved the following rewrite lemma:
325.86/291.54	*'(gen_0':s3_0(n464_0), gen_0':s3_0(n464_0)) -> *5_0, rt in Omega(n464_0 + n464_0^2)
325.86/291.54	
325.86/291.54	Induction Base:
325.86/291.54	*'(gen_0':s3_0(0), gen_0':s3_0(0))
325.86/291.54	
325.86/291.54	Induction Step:
325.86/291.54	*'(gen_0':s3_0(+(n464_0, 1)), gen_0':s3_0(+(n464_0, 1))) ->_R^Omega(1)
325.86/291.54	s(+'(*'(gen_0':s3_0(n464_0), gen_0':s3_0(n464_0)), +'(gen_0':s3_0(n464_0), gen_0':s3_0(n464_0)))) ->_IH
325.86/291.54	s(+'(*5_0, +'(gen_0':s3_0(n464_0), gen_0':s3_0(n464_0)))) ->_L^Omega(1 + n464_0)
325.86/291.54	s(+'(*5_0, gen_0':s3_0(*(2, n464_0))))
325.86/291.54	
325.86/291.54	We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2).
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(14)
325.86/291.54	Complex Obligation (BEST)
325.86/291.54	
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(15)
325.86/291.54	Obligation:
325.86/291.54	Proved the lower bound n^2 for the following obligation:
325.86/291.54	
325.86/291.54	TRS:
325.86/291.54	Rules:
325.86/291.54	+'(x, 0') -> x
325.86/291.54	+'(0', x) -> x
325.86/291.54	+'(s(x), s(y)) -> s(s(+'(x, y)))
325.86/291.54	*'(x, 0') -> 0'
325.86/291.54	*'(0', x) -> 0'
325.86/291.54	*'(s(x), s(y)) -> s(+'(*'(x, y), +'(x, y)))
325.86/291.54	sum(nil) -> 0'
325.86/291.54	sum(cons(x, l)) -> +'(x, sum(l))
325.86/291.54	prod(nil) -> s(0')
325.86/291.54	prod(cons(x, l)) -> *'(x, prod(l))
325.86/291.54	
325.86/291.54	Types:
325.86/291.54	+' :: 0':s -> 0':s -> 0':s
325.86/291.54	0' :: 0':s
325.86/291.54	s :: 0':s -> 0':s
325.86/291.54	*' :: 0':s -> 0':s -> 0':s
325.86/291.54	sum :: nil:cons -> 0':s
325.86/291.54	nil :: nil:cons
325.86/291.54	cons :: 0':s -> nil:cons -> nil:cons
325.86/291.54	prod :: nil:cons -> 0':s
325.86/291.54	hole_0':s1_0 :: 0':s
325.86/291.54	hole_nil:cons2_0 :: nil:cons
325.86/291.54	gen_0':s3_0 :: Nat -> 0':s
325.86/291.54	gen_nil:cons4_0 :: Nat -> nil:cons
325.86/291.54	
325.86/291.54	
325.86/291.54	Lemmas:
325.86/291.54	+'(gen_0':s3_0(n6_0), gen_0':s3_0(n6_0)) -> gen_0':s3_0(*(2, n6_0)), rt in Omega(1 + n6_0)
325.86/291.54	
325.86/291.54	
325.86/291.54	Generator Equations:
325.86/291.54	gen_0':s3_0(0) <=> 0'
325.86/291.54	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
325.86/291.54	gen_nil:cons4_0(0) <=> nil
325.86/291.54	gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x))
325.86/291.54	
325.86/291.54	
325.86/291.54	The following defined symbols remain to be analysed:
325.86/291.54	*', sum, prod
325.86/291.54	
325.86/291.54	They will be analysed ascendingly in the following order:
325.86/291.54	*' < prod
325.86/291.54	
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(16) LowerBoundPropagationProof (FINISHED)
325.86/291.54	Propagated lower bound.
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(17)
325.86/291.54	BOUNDS(n^2, INF)
325.86/291.54	
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(18)
325.86/291.54	Obligation:
325.86/291.54	TRS:
325.86/291.54	Rules:
325.86/291.54	+'(x, 0') -> x
325.86/291.54	+'(0', x) -> x
325.86/291.54	+'(s(x), s(y)) -> s(s(+'(x, y)))
325.86/291.54	*'(x, 0') -> 0'
325.86/291.54	*'(0', x) -> 0'
325.86/291.54	*'(s(x), s(y)) -> s(+'(*'(x, y), +'(x, y)))
325.86/291.54	sum(nil) -> 0'
325.86/291.54	sum(cons(x, l)) -> +'(x, sum(l))
325.86/291.54	prod(nil) -> s(0')
325.86/291.54	prod(cons(x, l)) -> *'(x, prod(l))
325.86/291.54	
325.86/291.54	Types:
325.86/291.54	+' :: 0':s -> 0':s -> 0':s
325.86/291.54	0' :: 0':s
325.86/291.54	s :: 0':s -> 0':s
325.86/291.54	*' :: 0':s -> 0':s -> 0':s
325.86/291.54	sum :: nil:cons -> 0':s
325.86/291.54	nil :: nil:cons
325.86/291.54	cons :: 0':s -> nil:cons -> nil:cons
325.86/291.54	prod :: nil:cons -> 0':s
325.86/291.54	hole_0':s1_0 :: 0':s
325.86/291.54	hole_nil:cons2_0 :: nil:cons
325.86/291.54	gen_0':s3_0 :: Nat -> 0':s
325.86/291.54	gen_nil:cons4_0 :: Nat -> nil:cons
325.86/291.54	
325.86/291.54	
325.86/291.54	Lemmas:
325.86/291.54	+'(gen_0':s3_0(n6_0), gen_0':s3_0(n6_0)) -> gen_0':s3_0(*(2, n6_0)), rt in Omega(1 + n6_0)
325.86/291.54	*'(gen_0':s3_0(n464_0), gen_0':s3_0(n464_0)) -> *5_0, rt in Omega(n464_0 + n464_0^2)
325.86/291.54	
325.86/291.54	
325.86/291.54	Generator Equations:
325.86/291.54	gen_0':s3_0(0) <=> 0'
325.86/291.54	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
325.86/291.54	gen_nil:cons4_0(0) <=> nil
325.86/291.54	gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x))
325.86/291.54	
325.86/291.54	
325.86/291.54	The following defined symbols remain to be analysed:
325.86/291.54	sum, prod
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(19) RewriteLemmaProof (LOWER BOUND(ID))
325.86/291.54	Proved the following rewrite lemma:
325.86/291.54	sum(gen_nil:cons4_0(n9896_0)) -> gen_0':s3_0(0), rt in Omega(1 + n9896_0)
325.86/291.54	
325.86/291.54	Induction Base:
325.86/291.54	sum(gen_nil:cons4_0(0)) ->_R^Omega(1)
325.86/291.54	0'
325.86/291.54	
325.86/291.54	Induction Step:
325.86/291.54	sum(gen_nil:cons4_0(+(n9896_0, 1))) ->_R^Omega(1)
325.86/291.54	+'(0', sum(gen_nil:cons4_0(n9896_0))) ->_IH
325.86/291.54	+'(0', gen_0':s3_0(0)) ->_L^Omega(1)
325.86/291.54	gen_0':s3_0(*(2, 0))
325.86/291.54	
325.86/291.54	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(20)
325.86/291.54	Obligation:
325.86/291.54	TRS:
325.86/291.54	Rules:
325.86/291.54	+'(x, 0') -> x
325.86/291.54	+'(0', x) -> x
325.86/291.54	+'(s(x), s(y)) -> s(s(+'(x, y)))
325.86/291.54	*'(x, 0') -> 0'
325.86/291.54	*'(0', x) -> 0'
325.86/291.54	*'(s(x), s(y)) -> s(+'(*'(x, y), +'(x, y)))
325.86/291.54	sum(nil) -> 0'
325.86/291.54	sum(cons(x, l)) -> +'(x, sum(l))
325.86/291.54	prod(nil) -> s(0')
325.86/291.54	prod(cons(x, l)) -> *'(x, prod(l))
325.86/291.54	
325.86/291.54	Types:
325.86/291.54	+' :: 0':s -> 0':s -> 0':s
325.86/291.54	0' :: 0':s
325.86/291.54	s :: 0':s -> 0':s
325.86/291.54	*' :: 0':s -> 0':s -> 0':s
325.86/291.54	sum :: nil:cons -> 0':s
325.86/291.54	nil :: nil:cons
325.86/291.54	cons :: 0':s -> nil:cons -> nil:cons
325.86/291.54	prod :: nil:cons -> 0':s
325.86/291.54	hole_0':s1_0 :: 0':s
325.86/291.54	hole_nil:cons2_0 :: nil:cons
325.86/291.54	gen_0':s3_0 :: Nat -> 0':s
325.86/291.54	gen_nil:cons4_0 :: Nat -> nil:cons
325.86/291.54	
325.86/291.54	
325.86/291.54	Lemmas:
325.86/291.54	+'(gen_0':s3_0(n6_0), gen_0':s3_0(n6_0)) -> gen_0':s3_0(*(2, n6_0)), rt in Omega(1 + n6_0)
325.86/291.54	*'(gen_0':s3_0(n464_0), gen_0':s3_0(n464_0)) -> *5_0, rt in Omega(n464_0 + n464_0^2)
325.86/291.54	sum(gen_nil:cons4_0(n9896_0)) -> gen_0':s3_0(0), rt in Omega(1 + n9896_0)
325.86/291.54	
325.86/291.54	
325.86/291.54	Generator Equations:
325.86/291.54	gen_0':s3_0(0) <=> 0'
325.86/291.54	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
325.86/291.54	gen_nil:cons4_0(0) <=> nil
325.86/291.54	gen_nil:cons4_0(+(x, 1)) <=> cons(0', gen_nil:cons4_0(x))
325.86/291.54	
325.86/291.54	
325.86/291.54	The following defined symbols remain to be analysed:
325.86/291.54	prod
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(21) RewriteLemmaProof (LOWER BOUND(ID))
325.86/291.54	Proved the following rewrite lemma:
325.86/291.54	prod(gen_nil:cons4_0(n10329_0)) -> *5_0, rt in Omega(n10329_0)
325.86/291.54	
325.86/291.54	Induction Base:
325.86/291.54	prod(gen_nil:cons4_0(0))
325.86/291.54	
325.86/291.54	Induction Step:
325.86/291.54	prod(gen_nil:cons4_0(+(n10329_0, 1))) ->_R^Omega(1)
325.86/291.54	*'(0', prod(gen_nil:cons4_0(n10329_0))) ->_IH
325.86/291.54	*'(0', *5_0)
325.86/291.54	
325.86/291.54	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
325.86/291.54	----------------------------------------
325.86/291.54	
325.86/291.54	(22)
325.86/291.54	BOUNDS(1, INF)
325.86/291.57	EOF