796.15/291.49	WORST_CASE(Omega(n^2), ?)
796.15/291.50	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
796.15/291.50	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
796.15/291.50	
796.15/291.50	
796.15/291.50	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
796.15/291.50	
796.15/291.50	(0) CpxTRS
796.15/291.50	(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
796.15/291.50	(2) CpxTRS
796.15/291.50	(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
796.15/291.50	(4) typed CpxTrs
796.15/291.50	(5) OrderProof [LOWER BOUND(ID), 0 ms]
796.15/291.50	(6) typed CpxTrs
796.15/291.50	(7) RewriteLemmaProof [LOWER BOUND(ID), 317 ms]
796.15/291.50	(8) BEST
796.15/291.50	    (9) proven lower bound
796.15/291.50	        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
796.15/291.50	        (11) BOUNDS(n^1, INF)
796.15/291.50	    (12) typed CpxTrs
796.15/291.50	        (13) RewriteLemmaProof [LOWER BOUND(ID), 12 ms]
796.15/291.50	        (14) typed CpxTrs
796.15/291.50	        (15) RewriteLemmaProof [LOWER BOUND(ID), 73 ms]
796.15/291.50	        (16) BEST
796.15/291.50	            (17) proven lower bound
796.15/291.50	                (18) LowerBoundPropagationProof [FINISHED, 0 ms]
796.15/291.50	                (19) BOUNDS(n^2, INF)
796.15/291.50	            (20) typed CpxTrs
796.15/291.50	                (21) RewriteLemmaProof [LOWER BOUND(ID), 39 ms]
796.15/291.50	                (22) typed CpxTrs
796.15/291.50	                (23) RewriteLemmaProof [LOWER BOUND(ID), 3772 ms]
796.15/291.50	                (24) BOUNDS(1, INF)
796.15/291.50	
796.15/291.50	
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(0)
796.15/291.50	Obligation:
796.15/291.50	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
796.15/291.50	
796.15/291.50	
796.15/291.50	The TRS R consists of the following rules:
796.15/291.50	
796.15/291.50	   sum#1(Nil) -> 0
796.15/291.50	   sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
796.15/291.50	   map#2(Nil) -> Nil
796.15/291.50	   map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
796.15/291.50	   unfoldr#2(0) -> Nil
796.15/291.50	   unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
796.15/291.50	   mult#2(0, x2) -> 0
796.15/291.50	   mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
796.15/291.50	   plus#2(0, x8) -> x8
796.15/291.50	   plus#2(S(x4), x2) -> S(plus#2(x4, x2))
796.15/291.50	   main(0) -> 0
796.15/291.50	   main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))
796.15/291.50	
796.15/291.50	S is empty.
796.15/291.50	Rewrite Strategy: INNERMOST
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(1) RenamingProof (BOTH BOUNDS(ID, ID))
796.15/291.50	Renamed function symbols to avoid clashes with predefined symbol.
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(2)
796.15/291.50	Obligation:
796.15/291.50	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
796.15/291.50	
796.15/291.50	
796.15/291.50	The TRS R consists of the following rules:
796.15/291.50	
796.15/291.50	   sum#1(Nil) -> 0'
796.15/291.50	   sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
796.15/291.50	   map#2(Nil) -> Nil
796.15/291.50	   map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
796.15/291.50	   unfoldr#2(0') -> Nil
796.15/291.50	   unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
796.15/291.50	   mult#2(0', x2) -> 0'
796.15/291.50	   mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
796.15/291.50	   plus#2(0', x8) -> x8
796.15/291.50	   plus#2(S(x4), x2) -> S(plus#2(x4, x2))
796.15/291.50	   main(0') -> 0'
796.15/291.50	   main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))
796.15/291.50	
796.15/291.50	S is empty.
796.15/291.50	Rewrite Strategy: INNERMOST
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
796.15/291.50	Infered types.
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(4)
796.15/291.50	Obligation:
796.15/291.50	Innermost TRS:
796.15/291.50	Rules:
796.15/291.50	sum#1(Nil) -> 0'
796.15/291.50	sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
796.15/291.50	map#2(Nil) -> Nil
796.15/291.50	map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
796.15/291.50	unfoldr#2(0') -> Nil
796.15/291.50	unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
796.15/291.50	mult#2(0', x2) -> 0'
796.15/291.50	mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
796.15/291.50	plus#2(0', x8) -> x8
796.15/291.50	plus#2(S(x4), x2) -> S(plus#2(x4, x2))
796.15/291.50	main(0') -> 0'
796.15/291.50	main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))
796.15/291.50	
796.15/291.50	Types:
796.15/291.50	sum#1 :: Nil:Cons -> 0':S
796.15/291.50	Nil :: Nil:Cons
796.15/291.50	0' :: 0':S
796.15/291.50	Cons :: 0':S -> Nil:Cons -> Nil:Cons
796.15/291.50	plus#2 :: 0':S -> 0':S -> 0':S
796.15/291.50	map#2 :: Nil:Cons -> Nil:Cons
796.15/291.50	mult#2 :: 0':S -> 0':S -> 0':S
796.15/291.50	unfoldr#2 :: 0':S -> Nil:Cons
796.15/291.50	S :: 0':S -> 0':S
796.15/291.50	main :: 0':S -> 0':S
796.15/291.50	hole_0':S1_0 :: 0':S
796.15/291.50	hole_Nil:Cons2_0 :: Nil:Cons
796.15/291.50	gen_0':S3_0 :: Nat -> 0':S
796.15/291.50	gen_Nil:Cons4_0 :: Nat -> Nil:Cons
796.15/291.50	
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(5) OrderProof (LOWER BOUND(ID))
796.15/291.50	Heuristically decided to analyse the following defined symbols:
796.15/291.50	sum#1, plus#2, map#2, mult#2, unfoldr#2
796.15/291.50	
796.15/291.50	They will be analysed ascendingly in the following order:
796.15/291.50	plus#2 < sum#1
796.15/291.50	plus#2 < mult#2
796.15/291.50	mult#2 < map#2
796.15/291.50	
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(6)
796.15/291.50	Obligation:
796.15/291.50	Innermost TRS:
796.15/291.50	Rules:
796.15/291.50	sum#1(Nil) -> 0'
796.15/291.50	sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
796.15/291.50	map#2(Nil) -> Nil
796.15/291.50	map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
796.15/291.50	unfoldr#2(0') -> Nil
796.15/291.50	unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
796.15/291.50	mult#2(0', x2) -> 0'
796.15/291.50	mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
796.15/291.50	plus#2(0', x8) -> x8
796.15/291.50	plus#2(S(x4), x2) -> S(plus#2(x4, x2))
796.15/291.50	main(0') -> 0'
796.15/291.50	main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))
796.15/291.50	
796.15/291.50	Types:
796.15/291.50	sum#1 :: Nil:Cons -> 0':S
796.15/291.50	Nil :: Nil:Cons
796.15/291.50	0' :: 0':S
796.15/291.50	Cons :: 0':S -> Nil:Cons -> Nil:Cons
796.15/291.50	plus#2 :: 0':S -> 0':S -> 0':S
796.15/291.50	map#2 :: Nil:Cons -> Nil:Cons
796.15/291.50	mult#2 :: 0':S -> 0':S -> 0':S
796.15/291.50	unfoldr#2 :: 0':S -> Nil:Cons
796.15/291.50	S :: 0':S -> 0':S
796.15/291.50	main :: 0':S -> 0':S
796.15/291.50	hole_0':S1_0 :: 0':S
796.15/291.50	hole_Nil:Cons2_0 :: Nil:Cons
796.15/291.50	gen_0':S3_0 :: Nat -> 0':S
796.15/291.50	gen_Nil:Cons4_0 :: Nat -> Nil:Cons
796.15/291.50	
796.15/291.50	
796.15/291.50	Generator Equations:
796.15/291.50	gen_0':S3_0(0) <=> 0'
796.15/291.50	gen_0':S3_0(+(x, 1)) <=> S(gen_0':S3_0(x))
796.15/291.50	gen_Nil:Cons4_0(0) <=> Nil
796.15/291.50	gen_Nil:Cons4_0(+(x, 1)) <=> Cons(0', gen_Nil:Cons4_0(x))
796.15/291.50	
796.15/291.50	
796.15/291.50	The following defined symbols remain to be analysed:
796.15/291.50	plus#2, sum#1, map#2, mult#2, unfoldr#2
796.15/291.50	
796.15/291.50	They will be analysed ascendingly in the following order:
796.15/291.50	plus#2 < sum#1
796.15/291.50	plus#2 < mult#2
796.15/291.50	mult#2 < map#2
796.15/291.50	
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(7) RewriteLemmaProof (LOWER BOUND(ID))
796.15/291.50	Proved the following rewrite lemma:
796.15/291.50	plus#2(gen_0':S3_0(n6_0), gen_0':S3_0(b)) -> gen_0':S3_0(+(n6_0, b)), rt in Omega(1 + n6_0)
796.15/291.50	
796.15/291.50	Induction Base:
796.15/291.50	plus#2(gen_0':S3_0(0), gen_0':S3_0(b)) ->_R^Omega(1)
796.15/291.50	gen_0':S3_0(b)
796.15/291.50	
796.15/291.50	Induction Step:
796.15/291.50	plus#2(gen_0':S3_0(+(n6_0, 1)), gen_0':S3_0(b)) ->_R^Omega(1)
796.15/291.50	S(plus#2(gen_0':S3_0(n6_0), gen_0':S3_0(b))) ->_IH
796.15/291.50	S(gen_0':S3_0(+(b, c7_0)))
796.15/291.50	
796.15/291.50	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(8)
796.15/291.50	Complex Obligation (BEST)
796.15/291.50	
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(9)
796.15/291.50	Obligation:
796.15/291.50	Proved the lower bound n^1 for the following obligation:
796.15/291.50	
796.15/291.50	Innermost TRS:
796.15/291.50	Rules:
796.15/291.50	sum#1(Nil) -> 0'
796.15/291.50	sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
796.15/291.50	map#2(Nil) -> Nil
796.15/291.50	map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
796.15/291.50	unfoldr#2(0') -> Nil
796.15/291.50	unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
796.15/291.50	mult#2(0', x2) -> 0'
796.15/291.50	mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
796.15/291.50	plus#2(0', x8) -> x8
796.15/291.50	plus#2(S(x4), x2) -> S(plus#2(x4, x2))
796.15/291.50	main(0') -> 0'
796.15/291.50	main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))
796.15/291.50	
796.15/291.50	Types:
796.15/291.50	sum#1 :: Nil:Cons -> 0':S
796.15/291.50	Nil :: Nil:Cons
796.15/291.50	0' :: 0':S
796.15/291.50	Cons :: 0':S -> Nil:Cons -> Nil:Cons
796.15/291.50	plus#2 :: 0':S -> 0':S -> 0':S
796.15/291.50	map#2 :: Nil:Cons -> Nil:Cons
796.15/291.50	mult#2 :: 0':S -> 0':S -> 0':S
796.15/291.50	unfoldr#2 :: 0':S -> Nil:Cons
796.15/291.50	S :: 0':S -> 0':S
796.15/291.50	main :: 0':S -> 0':S
796.15/291.50	hole_0':S1_0 :: 0':S
796.15/291.50	hole_Nil:Cons2_0 :: Nil:Cons
796.15/291.50	gen_0':S3_0 :: Nat -> 0':S
796.15/291.50	gen_Nil:Cons4_0 :: Nat -> Nil:Cons
796.15/291.50	
796.15/291.50	
796.15/291.50	Generator Equations:
796.15/291.50	gen_0':S3_0(0) <=> 0'
796.15/291.50	gen_0':S3_0(+(x, 1)) <=> S(gen_0':S3_0(x))
796.15/291.50	gen_Nil:Cons4_0(0) <=> Nil
796.15/291.50	gen_Nil:Cons4_0(+(x, 1)) <=> Cons(0', gen_Nil:Cons4_0(x))
796.15/291.50	
796.15/291.50	
796.15/291.50	The following defined symbols remain to be analysed:
796.15/291.50	plus#2, sum#1, map#2, mult#2, unfoldr#2
796.15/291.50	
796.15/291.50	They will be analysed ascendingly in the following order:
796.15/291.50	plus#2 < sum#1
796.15/291.50	plus#2 < mult#2
796.15/291.50	mult#2 < map#2
796.15/291.50	
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(10) LowerBoundPropagationProof (FINISHED)
796.15/291.50	Propagated lower bound.
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(11)
796.15/291.50	BOUNDS(n^1, INF)
796.15/291.50	
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(12)
796.15/291.50	Obligation:
796.15/291.50	Innermost TRS:
796.15/291.50	Rules:
796.15/291.50	sum#1(Nil) -> 0'
796.15/291.50	sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
796.15/291.50	map#2(Nil) -> Nil
796.15/291.50	map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
796.15/291.50	unfoldr#2(0') -> Nil
796.15/291.50	unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
796.15/291.50	mult#2(0', x2) -> 0'
796.15/291.50	mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
796.15/291.50	plus#2(0', x8) -> x8
796.15/291.50	plus#2(S(x4), x2) -> S(plus#2(x4, x2))
796.15/291.50	main(0') -> 0'
796.15/291.50	main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))
796.15/291.50	
796.15/291.50	Types:
796.15/291.50	sum#1 :: Nil:Cons -> 0':S
796.15/291.50	Nil :: Nil:Cons
796.15/291.50	0' :: 0':S
796.15/291.50	Cons :: 0':S -> Nil:Cons -> Nil:Cons
796.15/291.50	plus#2 :: 0':S -> 0':S -> 0':S
796.15/291.50	map#2 :: Nil:Cons -> Nil:Cons
796.15/291.50	mult#2 :: 0':S -> 0':S -> 0':S
796.15/291.50	unfoldr#2 :: 0':S -> Nil:Cons
796.15/291.50	S :: 0':S -> 0':S
796.15/291.50	main :: 0':S -> 0':S
796.15/291.50	hole_0':S1_0 :: 0':S
796.15/291.50	hole_Nil:Cons2_0 :: Nil:Cons
796.15/291.50	gen_0':S3_0 :: Nat -> 0':S
796.15/291.50	gen_Nil:Cons4_0 :: Nat -> Nil:Cons
796.15/291.50	
796.15/291.50	
796.15/291.50	Lemmas:
796.15/291.50	plus#2(gen_0':S3_0(n6_0), gen_0':S3_0(b)) -> gen_0':S3_0(+(n6_0, b)), rt in Omega(1 + n6_0)
796.15/291.50	
796.15/291.50	
796.15/291.50	Generator Equations:
796.15/291.50	gen_0':S3_0(0) <=> 0'
796.15/291.50	gen_0':S3_0(+(x, 1)) <=> S(gen_0':S3_0(x))
796.15/291.50	gen_Nil:Cons4_0(0) <=> Nil
796.15/291.50	gen_Nil:Cons4_0(+(x, 1)) <=> Cons(0', gen_Nil:Cons4_0(x))
796.15/291.50	
796.15/291.50	
796.15/291.50	The following defined symbols remain to be analysed:
796.15/291.50	sum#1, map#2, mult#2, unfoldr#2
796.15/291.50	
796.15/291.50	They will be analysed ascendingly in the following order:
796.15/291.50	mult#2 < map#2
796.15/291.50	
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(13) RewriteLemmaProof (LOWER BOUND(ID))
796.15/291.50	Proved the following rewrite lemma:
796.15/291.50	sum#1(gen_Nil:Cons4_0(n715_0)) -> gen_0':S3_0(0), rt in Omega(1 + n715_0)
796.15/291.50	
796.15/291.50	Induction Base:
796.15/291.50	sum#1(gen_Nil:Cons4_0(0)) ->_R^Omega(1)
796.15/291.50	0'
796.15/291.50	
796.15/291.50	Induction Step:
796.15/291.50	sum#1(gen_Nil:Cons4_0(+(n715_0, 1))) ->_R^Omega(1)
796.15/291.50	plus#2(0', sum#1(gen_Nil:Cons4_0(n715_0))) ->_IH
796.15/291.50	plus#2(0', gen_0':S3_0(0)) ->_L^Omega(1)
796.15/291.50	gen_0':S3_0(+(0, 0))
796.15/291.50	
796.15/291.50	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(14)
796.15/291.50	Obligation:
796.15/291.50	Innermost TRS:
796.15/291.50	Rules:
796.15/291.50	sum#1(Nil) -> 0'
796.15/291.50	sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
796.15/291.50	map#2(Nil) -> Nil
796.15/291.50	map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
796.15/291.50	unfoldr#2(0') -> Nil
796.15/291.50	unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
796.15/291.50	mult#2(0', x2) -> 0'
796.15/291.50	mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
796.15/291.50	plus#2(0', x8) -> x8
796.15/291.50	plus#2(S(x4), x2) -> S(plus#2(x4, x2))
796.15/291.50	main(0') -> 0'
796.15/291.50	main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))
796.15/291.50	
796.15/291.50	Types:
796.15/291.50	sum#1 :: Nil:Cons -> 0':S
796.15/291.50	Nil :: Nil:Cons
796.15/291.50	0' :: 0':S
796.15/291.50	Cons :: 0':S -> Nil:Cons -> Nil:Cons
796.15/291.50	plus#2 :: 0':S -> 0':S -> 0':S
796.15/291.50	map#2 :: Nil:Cons -> Nil:Cons
796.15/291.50	mult#2 :: 0':S -> 0':S -> 0':S
796.15/291.50	unfoldr#2 :: 0':S -> Nil:Cons
796.15/291.50	S :: 0':S -> 0':S
796.15/291.50	main :: 0':S -> 0':S
796.15/291.50	hole_0':S1_0 :: 0':S
796.15/291.50	hole_Nil:Cons2_0 :: Nil:Cons
796.15/291.50	gen_0':S3_0 :: Nat -> 0':S
796.15/291.50	gen_Nil:Cons4_0 :: Nat -> Nil:Cons
796.15/291.50	
796.15/291.50	
796.15/291.50	Lemmas:
796.15/291.50	plus#2(gen_0':S3_0(n6_0), gen_0':S3_0(b)) -> gen_0':S3_0(+(n6_0, b)), rt in Omega(1 + n6_0)
796.15/291.50	sum#1(gen_Nil:Cons4_0(n715_0)) -> gen_0':S3_0(0), rt in Omega(1 + n715_0)
796.15/291.50	
796.15/291.50	
796.15/291.50	Generator Equations:
796.15/291.50	gen_0':S3_0(0) <=> 0'
796.15/291.50	gen_0':S3_0(+(x, 1)) <=> S(gen_0':S3_0(x))
796.15/291.50	gen_Nil:Cons4_0(0) <=> Nil
796.15/291.50	gen_Nil:Cons4_0(+(x, 1)) <=> Cons(0', gen_Nil:Cons4_0(x))
796.15/291.50	
796.15/291.50	
796.15/291.50	The following defined symbols remain to be analysed:
796.15/291.50	mult#2, map#2, unfoldr#2
796.15/291.50	
796.15/291.50	They will be analysed ascendingly in the following order:
796.15/291.50	mult#2 < map#2
796.15/291.50	
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(15) RewriteLemmaProof (LOWER BOUND(ID))
796.15/291.50	Proved the following rewrite lemma:
796.15/291.50	mult#2(gen_0':S3_0(n1039_0), gen_0':S3_0(b)) -> gen_0':S3_0(*(n1039_0, b)), rt in Omega(1 + b*n1039_0 + n1039_0)
796.15/291.50	
796.15/291.50	Induction Base:
796.15/291.50	mult#2(gen_0':S3_0(0), gen_0':S3_0(b)) ->_R^Omega(1)
796.15/291.50	0'
796.15/291.50	
796.15/291.50	Induction Step:
796.15/291.50	mult#2(gen_0':S3_0(+(n1039_0, 1)), gen_0':S3_0(b)) ->_R^Omega(1)
796.15/291.50	plus#2(gen_0':S3_0(b), mult#2(gen_0':S3_0(n1039_0), gen_0':S3_0(b))) ->_IH
796.15/291.50	plus#2(gen_0':S3_0(b), gen_0':S3_0(*(c1040_0, b))) ->_L^Omega(1 + b)
796.15/291.50	gen_0':S3_0(+(b, *(n1039_0, b)))
796.15/291.50	
796.15/291.50	We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2).
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(16)
796.15/291.50	Complex Obligation (BEST)
796.15/291.50	
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(17)
796.15/291.50	Obligation:
796.15/291.50	Proved the lower bound n^2 for the following obligation:
796.15/291.50	
796.15/291.50	Innermost TRS:
796.15/291.50	Rules:
796.15/291.50	sum#1(Nil) -> 0'
796.15/291.50	sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
796.15/291.50	map#2(Nil) -> Nil
796.15/291.50	map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
796.15/291.50	unfoldr#2(0') -> Nil
796.15/291.50	unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
796.15/291.50	mult#2(0', x2) -> 0'
796.15/291.50	mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
796.15/291.50	plus#2(0', x8) -> x8
796.15/291.50	plus#2(S(x4), x2) -> S(plus#2(x4, x2))
796.15/291.50	main(0') -> 0'
796.15/291.50	main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))
796.15/291.50	
796.15/291.50	Types:
796.15/291.50	sum#1 :: Nil:Cons -> 0':S
796.15/291.50	Nil :: Nil:Cons
796.15/291.50	0' :: 0':S
796.15/291.50	Cons :: 0':S -> Nil:Cons -> Nil:Cons
796.15/291.50	plus#2 :: 0':S -> 0':S -> 0':S
796.15/291.50	map#2 :: Nil:Cons -> Nil:Cons
796.15/291.50	mult#2 :: 0':S -> 0':S -> 0':S
796.15/291.50	unfoldr#2 :: 0':S -> Nil:Cons
796.15/291.50	S :: 0':S -> 0':S
796.15/291.50	main :: 0':S -> 0':S
796.15/291.50	hole_0':S1_0 :: 0':S
796.15/291.50	hole_Nil:Cons2_0 :: Nil:Cons
796.15/291.50	gen_0':S3_0 :: Nat -> 0':S
796.15/291.50	gen_Nil:Cons4_0 :: Nat -> Nil:Cons
796.15/291.50	
796.15/291.50	
796.15/291.50	Lemmas:
796.15/291.50	plus#2(gen_0':S3_0(n6_0), gen_0':S3_0(b)) -> gen_0':S3_0(+(n6_0, b)), rt in Omega(1 + n6_0)
796.15/291.50	sum#1(gen_Nil:Cons4_0(n715_0)) -> gen_0':S3_0(0), rt in Omega(1 + n715_0)
796.15/291.50	
796.15/291.50	
796.15/291.50	Generator Equations:
796.15/291.50	gen_0':S3_0(0) <=> 0'
796.15/291.50	gen_0':S3_0(+(x, 1)) <=> S(gen_0':S3_0(x))
796.15/291.50	gen_Nil:Cons4_0(0) <=> Nil
796.15/291.50	gen_Nil:Cons4_0(+(x, 1)) <=> Cons(0', gen_Nil:Cons4_0(x))
796.15/291.50	
796.15/291.50	
796.15/291.50	The following defined symbols remain to be analysed:
796.15/291.50	mult#2, map#2, unfoldr#2
796.15/291.50	
796.15/291.50	They will be analysed ascendingly in the following order:
796.15/291.50	mult#2 < map#2
796.15/291.50	
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(18) LowerBoundPropagationProof (FINISHED)
796.15/291.50	Propagated lower bound.
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(19)
796.15/291.50	BOUNDS(n^2, INF)
796.15/291.50	
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(20)
796.15/291.50	Obligation:
796.15/291.50	Innermost TRS:
796.15/291.50	Rules:
796.15/291.50	sum#1(Nil) -> 0'
796.15/291.50	sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
796.15/291.50	map#2(Nil) -> Nil
796.15/291.50	map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
796.15/291.50	unfoldr#2(0') -> Nil
796.15/291.50	unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
796.15/291.50	mult#2(0', x2) -> 0'
796.15/291.50	mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
796.15/291.50	plus#2(0', x8) -> x8
796.15/291.50	plus#2(S(x4), x2) -> S(plus#2(x4, x2))
796.15/291.50	main(0') -> 0'
796.15/291.50	main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))
796.15/291.50	
796.15/291.50	Types:
796.15/291.50	sum#1 :: Nil:Cons -> 0':S
796.15/291.50	Nil :: Nil:Cons
796.15/291.50	0' :: 0':S
796.15/291.50	Cons :: 0':S -> Nil:Cons -> Nil:Cons
796.15/291.50	plus#2 :: 0':S -> 0':S -> 0':S
796.15/291.50	map#2 :: Nil:Cons -> Nil:Cons
796.15/291.50	mult#2 :: 0':S -> 0':S -> 0':S
796.15/291.50	unfoldr#2 :: 0':S -> Nil:Cons
796.15/291.50	S :: 0':S -> 0':S
796.15/291.50	main :: 0':S -> 0':S
796.15/291.50	hole_0':S1_0 :: 0':S
796.15/291.50	hole_Nil:Cons2_0 :: Nil:Cons
796.15/291.50	gen_0':S3_0 :: Nat -> 0':S
796.15/291.50	gen_Nil:Cons4_0 :: Nat -> Nil:Cons
796.15/291.50	
796.15/291.50	
796.15/291.50	Lemmas:
796.15/291.50	plus#2(gen_0':S3_0(n6_0), gen_0':S3_0(b)) -> gen_0':S3_0(+(n6_0, b)), rt in Omega(1 + n6_0)
796.15/291.50	sum#1(gen_Nil:Cons4_0(n715_0)) -> gen_0':S3_0(0), rt in Omega(1 + n715_0)
796.15/291.50	mult#2(gen_0':S3_0(n1039_0), gen_0':S3_0(b)) -> gen_0':S3_0(*(n1039_0, b)), rt in Omega(1 + b*n1039_0 + n1039_0)
796.15/291.50	
796.15/291.50	
796.15/291.50	Generator Equations:
796.15/291.50	gen_0':S3_0(0) <=> 0'
796.15/291.50	gen_0':S3_0(+(x, 1)) <=> S(gen_0':S3_0(x))
796.15/291.50	gen_Nil:Cons4_0(0) <=> Nil
796.15/291.50	gen_Nil:Cons4_0(+(x, 1)) <=> Cons(0', gen_Nil:Cons4_0(x))
796.15/291.50	
796.15/291.50	
796.15/291.50	The following defined symbols remain to be analysed:
796.15/291.50	map#2, unfoldr#2
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(21) RewriteLemmaProof (LOWER BOUND(ID))
796.15/291.50	Proved the following rewrite lemma:
796.15/291.50	map#2(gen_Nil:Cons4_0(n1983_0)) -> gen_Nil:Cons4_0(n1983_0), rt in Omega(1 + n1983_0)
796.15/291.50	
796.15/291.50	Induction Base:
796.15/291.50	map#2(gen_Nil:Cons4_0(0)) ->_R^Omega(1)
796.15/291.50	Nil
796.15/291.50	
796.15/291.50	Induction Step:
796.15/291.50	map#2(gen_Nil:Cons4_0(+(n1983_0, 1))) ->_R^Omega(1)
796.15/291.50	Cons(mult#2(0', 0'), map#2(gen_Nil:Cons4_0(n1983_0))) ->_L^Omega(1)
796.15/291.50	Cons(gen_0':S3_0(*(0, 0)), map#2(gen_Nil:Cons4_0(n1983_0))) ->_IH
796.15/291.50	Cons(gen_0':S3_0(0), gen_Nil:Cons4_0(c1984_0))
796.15/291.50	
796.15/291.50	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(22)
796.15/291.50	Obligation:
796.15/291.50	Innermost TRS:
796.15/291.50	Rules:
796.15/291.50	sum#1(Nil) -> 0'
796.15/291.50	sum#1(Cons(x2, x1)) -> plus#2(x2, sum#1(x1))
796.15/291.50	map#2(Nil) -> Nil
796.15/291.50	map#2(Cons(x2, x5)) -> Cons(mult#2(x2, x2), map#2(x5))
796.15/291.50	unfoldr#2(0') -> Nil
796.15/291.50	unfoldr#2(S(x2)) -> Cons(x2, unfoldr#2(x2))
796.15/291.50	mult#2(0', x2) -> 0'
796.15/291.50	mult#2(S(x4), x2) -> plus#2(x2, mult#2(x4, x2))
796.15/291.50	plus#2(0', x8) -> x8
796.15/291.50	plus#2(S(x4), x2) -> S(plus#2(x4, x2))
796.15/291.50	main(0') -> 0'
796.15/291.50	main(S(x1)) -> sum#1(map#2(Cons(S(x1), unfoldr#2(S(x1)))))
796.15/291.50	
796.15/291.50	Types:
796.15/291.50	sum#1 :: Nil:Cons -> 0':S
796.15/291.50	Nil :: Nil:Cons
796.15/291.50	0' :: 0':S
796.15/291.50	Cons :: 0':S -> Nil:Cons -> Nil:Cons
796.15/291.50	plus#2 :: 0':S -> 0':S -> 0':S
796.15/291.50	map#2 :: Nil:Cons -> Nil:Cons
796.15/291.50	mult#2 :: 0':S -> 0':S -> 0':S
796.15/291.50	unfoldr#2 :: 0':S -> Nil:Cons
796.15/291.50	S :: 0':S -> 0':S
796.15/291.50	main :: 0':S -> 0':S
796.15/291.50	hole_0':S1_0 :: 0':S
796.15/291.50	hole_Nil:Cons2_0 :: Nil:Cons
796.15/291.50	gen_0':S3_0 :: Nat -> 0':S
796.15/291.50	gen_Nil:Cons4_0 :: Nat -> Nil:Cons
796.15/291.50	
796.15/291.50	
796.15/291.50	Lemmas:
796.15/291.50	plus#2(gen_0':S3_0(n6_0), gen_0':S3_0(b)) -> gen_0':S3_0(+(n6_0, b)), rt in Omega(1 + n6_0)
796.15/291.50	sum#1(gen_Nil:Cons4_0(n715_0)) -> gen_0':S3_0(0), rt in Omega(1 + n715_0)
796.15/291.50	mult#2(gen_0':S3_0(n1039_0), gen_0':S3_0(b)) -> gen_0':S3_0(*(n1039_0, b)), rt in Omega(1 + b*n1039_0 + n1039_0)
796.15/291.50	map#2(gen_Nil:Cons4_0(n1983_0)) -> gen_Nil:Cons4_0(n1983_0), rt in Omega(1 + n1983_0)
796.15/291.50	
796.15/291.50	
796.15/291.50	Generator Equations:
796.15/291.50	gen_0':S3_0(0) <=> 0'
796.15/291.50	gen_0':S3_0(+(x, 1)) <=> S(gen_0':S3_0(x))
796.15/291.50	gen_Nil:Cons4_0(0) <=> Nil
796.15/291.50	gen_Nil:Cons4_0(+(x, 1)) <=> Cons(0', gen_Nil:Cons4_0(x))
796.15/291.50	
796.15/291.50	
796.15/291.50	The following defined symbols remain to be analysed:
796.15/291.50	unfoldr#2
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(23) RewriteLemmaProof (LOWER BOUND(ID))
796.15/291.50	Proved the following rewrite lemma:
796.15/291.50	unfoldr#2(gen_0':S3_0(+(1, n2324_0))) -> *5_0, rt in Omega(n2324_0)
796.15/291.50	
796.15/291.50	Induction Base:
796.15/291.50	unfoldr#2(gen_0':S3_0(+(1, 0)))
796.15/291.50	
796.15/291.50	Induction Step:
796.15/291.50	unfoldr#2(gen_0':S3_0(+(1, +(n2324_0, 1)))) ->_R^Omega(1)
796.15/291.50	Cons(gen_0':S3_0(+(1, n2324_0)), unfoldr#2(gen_0':S3_0(+(1, n2324_0)))) ->_IH
796.15/291.50	Cons(gen_0':S3_0(+(1, n2324_0)), *5_0)
796.15/291.50	
796.15/291.50	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
796.15/291.50	----------------------------------------
796.15/291.50	
796.15/291.50	(24)
796.15/291.50	BOUNDS(1, INF)
796.34/291.56	EOF