1113.40/291.49	WORST_CASE(Omega(n^1), ?)
1113.40/291.53	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
1113.40/291.53	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
1113.40/291.53	
1113.40/291.53	
1113.40/291.53	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1113.40/291.53	
1113.40/291.53	(0) CpxTRS
1113.40/291.53	(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
1113.40/291.53	(2) CpxTRS
1113.40/291.53	(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
1113.40/291.53	(4) typed CpxTrs
1113.40/291.53	(5) OrderProof [LOWER BOUND(ID), 0 ms]
1113.40/291.53	(6) typed CpxTrs
1113.40/291.53	(7) RewriteLemmaProof [LOWER BOUND(ID), 211 ms]
1113.40/291.53	(8) BEST
1113.40/291.53	    (9) proven lower bound
1113.40/291.53	        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
1113.40/291.53	        (11) BOUNDS(n^1, INF)
1113.40/291.53	    (12) typed CpxTrs
1113.40/291.53	        (13) RewriteLemmaProof [LOWER BOUND(ID), 54 ms]
1113.40/291.53	        (14) typed CpxTrs
1113.40/291.53	
1113.40/291.53	
1113.40/291.53	----------------------------------------
1113.40/291.53	
1113.40/291.53	(0)
1113.40/291.53	Obligation:
1113.40/291.53	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1113.40/291.53	
1113.40/291.53	
1113.40/291.53	The TRS R consists of the following rules:
1113.40/291.53	
1113.40/291.53	   times(x, y) -> sum(generate(x, y))
1113.40/291.53	   generate(x, y) -> gen(x, y, 0)
1113.40/291.53	   gen(x, y, z) -> if(ge(z, x), x, y, z)
1113.40/291.53	   if(true, x, y, z) -> nil
1113.40/291.53	   if(false, x, y, z) -> cons(y, gen(x, y, s(z)))
1113.40/291.53	   sum(nil) -> 0
1113.40/291.53	   sum(cons(0, xs)) -> sum(xs)
1113.40/291.53	   sum(cons(s(x), xs)) -> s(sum(cons(x, xs)))
1113.40/291.53	   ge(x, 0) -> true
1113.40/291.53	   ge(0, s(y)) -> false
1113.40/291.53	   ge(s(x), s(y)) -> ge(x, y)
1113.40/291.53	
1113.40/291.53	S is empty.
1113.40/291.53	Rewrite Strategy: INNERMOST
1113.40/291.53	----------------------------------------
1113.40/291.53	
1113.40/291.53	(1) RenamingProof (BOTH BOUNDS(ID, ID))
1113.40/291.53	Renamed function symbols to avoid clashes with predefined symbol.
1113.40/291.53	----------------------------------------
1113.40/291.53	
1113.40/291.53	(2)
1113.40/291.53	Obligation:
1113.40/291.53	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1113.40/291.53	
1113.40/291.53	
1113.40/291.53	The TRS R consists of the following rules:
1113.40/291.53	
1113.40/291.53	   times(x, y) -> sum(generate(x, y))
1113.40/291.53	   generate(x, y) -> gen(x, y, 0')
1113.40/291.53	   gen(x, y, z) -> if(ge(z, x), x, y, z)
1113.40/291.53	   if(true, x, y, z) -> nil
1113.40/291.53	   if(false, x, y, z) -> cons(y, gen(x, y, s(z)))
1113.40/291.53	   sum(nil) -> 0'
1113.40/291.53	   sum(cons(0', xs)) -> sum(xs)
1113.40/291.53	   sum(cons(s(x), xs)) -> s(sum(cons(x, xs)))
1113.40/291.53	   ge(x, 0') -> true
1113.40/291.53	   ge(0', s(y)) -> false
1113.40/291.53	   ge(s(x), s(y)) -> ge(x, y)
1113.40/291.53	
1113.40/291.53	S is empty.
1113.40/291.53	Rewrite Strategy: INNERMOST
1113.40/291.53	----------------------------------------
1113.40/291.53	
1113.40/291.53	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
1113.40/291.53	Infered types.
1113.40/291.53	----------------------------------------
1113.40/291.53	
1113.40/291.53	(4)
1113.40/291.53	Obligation:
1113.40/291.53	Innermost TRS:
1113.40/291.53	Rules:
1113.40/291.53	times(x, y) -> sum(generate(x, y))
1113.40/291.53	generate(x, y) -> gen(x, y, 0')
1113.40/291.53	gen(x, y, z) -> if(ge(z, x), x, y, z)
1113.40/291.53	if(true, x, y, z) -> nil
1113.40/291.53	if(false, x, y, z) -> cons(y, gen(x, y, s(z)))
1113.40/291.53	sum(nil) -> 0'
1113.40/291.53	sum(cons(0', xs)) -> sum(xs)
1113.40/291.53	sum(cons(s(x), xs)) -> s(sum(cons(x, xs)))
1113.40/291.53	ge(x, 0') -> true
1113.40/291.53	ge(0', s(y)) -> false
1113.40/291.53	ge(s(x), s(y)) -> ge(x, y)
1113.40/291.53	
1113.40/291.53	Types:
1113.40/291.53	times :: 0':s -> 0':s -> 0':s
1113.40/291.53	sum :: nil:cons -> 0':s
1113.40/291.53	generate :: 0':s -> 0':s -> nil:cons
1113.40/291.53	gen :: 0':s -> 0':s -> 0':s -> nil:cons
1113.40/291.53	0' :: 0':s
1113.40/291.53	if :: true:false -> 0':s -> 0':s -> 0':s -> nil:cons
1113.40/291.53	ge :: 0':s -> 0':s -> true:false
1113.40/291.53	true :: true:false
1113.40/291.53	nil :: nil:cons
1113.40/291.53	false :: true:false
1113.40/291.53	cons :: 0':s -> nil:cons -> nil:cons
1113.40/291.53	s :: 0':s -> 0':s
1113.40/291.53	hole_0':s1_0 :: 0':s
1113.40/291.53	hole_nil:cons2_0 :: nil:cons
1113.40/291.53	hole_true:false3_0 :: true:false
1113.40/291.53	gen_0':s4_0 :: Nat -> 0':s
1113.40/291.53	gen_nil:cons5_0 :: Nat -> nil:cons
1113.40/291.53	
1113.40/291.53	----------------------------------------
1113.40/291.53	
1113.40/291.53	(5) OrderProof (LOWER BOUND(ID))
1113.40/291.53	Heuristically decided to analyse the following defined symbols:
1113.40/291.53	sum, gen, ge
1113.40/291.53	
1113.40/291.53	They will be analysed ascendingly in the following order:
1113.40/291.53	ge < gen
1113.40/291.53	
1113.40/291.53	----------------------------------------
1113.40/291.53	
1113.40/291.53	(6)
1113.40/291.53	Obligation:
1113.40/291.53	Innermost TRS:
1113.40/291.53	Rules:
1113.40/291.53	times(x, y) -> sum(generate(x, y))
1113.40/291.53	generate(x, y) -> gen(x, y, 0')
1113.40/291.53	gen(x, y, z) -> if(ge(z, x), x, y, z)
1113.40/291.53	if(true, x, y, z) -> nil
1113.40/291.53	if(false, x, y, z) -> cons(y, gen(x, y, s(z)))
1113.40/291.53	sum(nil) -> 0'
1113.40/291.53	sum(cons(0', xs)) -> sum(xs)
1113.40/291.53	sum(cons(s(x), xs)) -> s(sum(cons(x, xs)))
1113.40/291.53	ge(x, 0') -> true
1113.40/291.53	ge(0', s(y)) -> false
1113.40/291.53	ge(s(x), s(y)) -> ge(x, y)
1113.40/291.53	
1113.40/291.53	Types:
1113.40/291.53	times :: 0':s -> 0':s -> 0':s
1113.40/291.53	sum :: nil:cons -> 0':s
1113.40/291.53	generate :: 0':s -> 0':s -> nil:cons
1113.40/291.53	gen :: 0':s -> 0':s -> 0':s -> nil:cons
1113.40/291.53	0' :: 0':s
1113.40/291.53	if :: true:false -> 0':s -> 0':s -> 0':s -> nil:cons
1113.40/291.53	ge :: 0':s -> 0':s -> true:false
1113.40/291.53	true :: true:false
1113.40/291.53	nil :: nil:cons
1113.40/291.53	false :: true:false
1113.40/291.53	cons :: 0':s -> nil:cons -> nil:cons
1113.40/291.53	s :: 0':s -> 0':s
1113.40/291.53	hole_0':s1_0 :: 0':s
1113.40/291.53	hole_nil:cons2_0 :: nil:cons
1113.40/291.53	hole_true:false3_0 :: true:false
1113.40/291.53	gen_0':s4_0 :: Nat -> 0':s
1113.40/291.53	gen_nil:cons5_0 :: Nat -> nil:cons
1113.40/291.53	
1113.40/291.53	
1113.40/291.53	Generator Equations:
1113.40/291.53	gen_0':s4_0(0) <=> 0'
1113.40/291.53	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
1113.40/291.53	gen_nil:cons5_0(0) <=> nil
1113.40/291.53	gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x))
1113.40/291.53	
1113.40/291.53	
1113.40/291.53	The following defined symbols remain to be analysed:
1113.40/291.53	sum, gen, ge
1113.40/291.53	
1113.40/291.53	They will be analysed ascendingly in the following order:
1113.40/291.53	ge < gen
1113.40/291.53	
1113.40/291.53	----------------------------------------
1113.40/291.53	
1113.40/291.53	(7) RewriteLemmaProof (LOWER BOUND(ID))
1113.40/291.53	Proved the following rewrite lemma:
1113.40/291.53	sum(gen_nil:cons5_0(n7_0)) -> gen_0':s4_0(0), rt in Omega(1 + n7_0)
1113.40/291.53	
1113.40/291.53	Induction Base:
1113.40/291.53	sum(gen_nil:cons5_0(0)) ->_R^Omega(1)
1113.40/291.53	0'
1113.40/291.53	
1113.40/291.53	Induction Step:
1113.40/291.53	sum(gen_nil:cons5_0(+(n7_0, 1))) ->_R^Omega(1)
1113.40/291.53	sum(gen_nil:cons5_0(n7_0)) ->_IH
1113.40/291.53	gen_0':s4_0(0)
1113.40/291.53	
1113.40/291.53	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
1113.40/291.53	----------------------------------------
1113.40/291.53	
1113.40/291.53	(8)
1113.40/291.53	Complex Obligation (BEST)
1113.40/291.53	
1113.40/291.53	----------------------------------------
1113.40/291.53	
1113.40/291.53	(9)
1113.40/291.53	Obligation:
1113.40/291.53	Proved the lower bound n^1 for the following obligation:
1113.40/291.53	
1113.40/291.53	Innermost TRS:
1113.40/291.53	Rules:
1113.40/291.53	times(x, y) -> sum(generate(x, y))
1113.40/291.53	generate(x, y) -> gen(x, y, 0')
1113.40/291.53	gen(x, y, z) -> if(ge(z, x), x, y, z)
1113.40/291.53	if(true, x, y, z) -> nil
1113.40/291.53	if(false, x, y, z) -> cons(y, gen(x, y, s(z)))
1113.40/291.53	sum(nil) -> 0'
1113.40/291.53	sum(cons(0', xs)) -> sum(xs)
1113.40/291.53	sum(cons(s(x), xs)) -> s(sum(cons(x, xs)))
1113.40/291.53	ge(x, 0') -> true
1113.40/291.53	ge(0', s(y)) -> false
1113.40/291.53	ge(s(x), s(y)) -> ge(x, y)
1113.40/291.53	
1113.40/291.53	Types:
1113.40/291.53	times :: 0':s -> 0':s -> 0':s
1113.40/291.53	sum :: nil:cons -> 0':s
1113.40/291.53	generate :: 0':s -> 0':s -> nil:cons
1113.40/291.53	gen :: 0':s -> 0':s -> 0':s -> nil:cons
1113.40/291.53	0' :: 0':s
1113.40/291.53	if :: true:false -> 0':s -> 0':s -> 0':s -> nil:cons
1113.40/291.53	ge :: 0':s -> 0':s -> true:false
1113.40/291.53	true :: true:false
1113.40/291.53	nil :: nil:cons
1113.40/291.53	false :: true:false
1113.40/291.53	cons :: 0':s -> nil:cons -> nil:cons
1113.40/291.53	s :: 0':s -> 0':s
1113.40/291.53	hole_0':s1_0 :: 0':s
1113.40/291.53	hole_nil:cons2_0 :: nil:cons
1113.40/291.53	hole_true:false3_0 :: true:false
1113.40/291.53	gen_0':s4_0 :: Nat -> 0':s
1113.40/291.53	gen_nil:cons5_0 :: Nat -> nil:cons
1113.40/291.53	
1113.40/291.53	
1113.40/291.53	Generator Equations:
1113.40/291.53	gen_0':s4_0(0) <=> 0'
1113.40/291.53	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
1113.40/291.53	gen_nil:cons5_0(0) <=> nil
1113.40/291.53	gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x))
1113.40/291.53	
1113.40/291.53	
1113.40/291.53	The following defined symbols remain to be analysed:
1113.40/291.53	sum, gen, ge
1113.40/291.53	
1113.40/291.53	They will be analysed ascendingly in the following order:
1113.40/291.53	ge < gen
1113.40/291.53	
1113.40/291.53	----------------------------------------
1113.40/291.53	
1113.40/291.53	(10) LowerBoundPropagationProof (FINISHED)
1113.40/291.53	Propagated lower bound.
1113.40/291.53	----------------------------------------
1113.40/291.53	
1113.40/291.53	(11)
1113.40/291.53	BOUNDS(n^1, INF)
1113.40/291.53	
1113.40/291.53	----------------------------------------
1113.40/291.53	
1113.40/291.53	(12)
1113.40/291.53	Obligation:
1113.40/291.53	Innermost TRS:
1113.40/291.53	Rules:
1113.40/291.53	times(x, y) -> sum(generate(x, y))
1113.40/291.53	generate(x, y) -> gen(x, y, 0')
1113.40/291.53	gen(x, y, z) -> if(ge(z, x), x, y, z)
1113.40/291.53	if(true, x, y, z) -> nil
1113.40/291.53	if(false, x, y, z) -> cons(y, gen(x, y, s(z)))
1113.40/291.53	sum(nil) -> 0'
1113.40/291.53	sum(cons(0', xs)) -> sum(xs)
1113.40/291.53	sum(cons(s(x), xs)) -> s(sum(cons(x, xs)))
1113.40/291.53	ge(x, 0') -> true
1113.40/291.53	ge(0', s(y)) -> false
1113.40/291.53	ge(s(x), s(y)) -> ge(x, y)
1113.40/291.53	
1113.40/291.53	Types:
1113.40/291.53	times :: 0':s -> 0':s -> 0':s
1113.40/291.53	sum :: nil:cons -> 0':s
1113.40/291.53	generate :: 0':s -> 0':s -> nil:cons
1113.40/291.53	gen :: 0':s -> 0':s -> 0':s -> nil:cons
1113.40/291.53	0' :: 0':s
1113.40/291.53	if :: true:false -> 0':s -> 0':s -> 0':s -> nil:cons
1113.40/291.53	ge :: 0':s -> 0':s -> true:false
1113.40/291.53	true :: true:false
1113.40/291.53	nil :: nil:cons
1113.40/291.53	false :: true:false
1113.40/291.53	cons :: 0':s -> nil:cons -> nil:cons
1113.40/291.53	s :: 0':s -> 0':s
1113.40/291.53	hole_0':s1_0 :: 0':s
1113.40/291.53	hole_nil:cons2_0 :: nil:cons
1113.40/291.53	hole_true:false3_0 :: true:false
1113.40/291.53	gen_0':s4_0 :: Nat -> 0':s
1113.40/291.53	gen_nil:cons5_0 :: Nat -> nil:cons
1113.40/291.53	
1113.40/291.53	
1113.40/291.53	Lemmas:
1113.40/291.53	sum(gen_nil:cons5_0(n7_0)) -> gen_0':s4_0(0), rt in Omega(1 + n7_0)
1113.40/291.53	
1113.40/291.53	
1113.40/291.53	Generator Equations:
1113.40/291.53	gen_0':s4_0(0) <=> 0'
1113.40/291.53	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
1113.40/291.53	gen_nil:cons5_0(0) <=> nil
1113.40/291.53	gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x))
1113.40/291.53	
1113.40/291.53	
1113.40/291.53	The following defined symbols remain to be analysed:
1113.40/291.53	ge, gen
1113.40/291.53	
1113.40/291.53	They will be analysed ascendingly in the following order:
1113.40/291.53	ge < gen
1113.40/291.53	
1113.40/291.53	----------------------------------------
1113.40/291.53	
1113.40/291.53	(13) RewriteLemmaProof (LOWER BOUND(ID))
1113.40/291.53	Proved the following rewrite lemma:
1113.40/291.53	ge(gen_0':s4_0(n300_0), gen_0':s4_0(n300_0)) -> true, rt in Omega(1 + n300_0)
1113.40/291.53	
1113.40/291.53	Induction Base:
1113.40/291.53	ge(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1)
1113.40/291.53	true
1113.40/291.53	
1113.40/291.53	Induction Step:
1113.40/291.53	ge(gen_0':s4_0(+(n300_0, 1)), gen_0':s4_0(+(n300_0, 1))) ->_R^Omega(1)
1113.40/291.53	ge(gen_0':s4_0(n300_0), gen_0':s4_0(n300_0)) ->_IH
1113.40/291.53	true
1113.40/291.53	
1113.40/291.53	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
1113.40/291.53	----------------------------------------
1113.40/291.53	
1113.40/291.53	(14)
1113.40/291.53	Obligation:
1113.40/291.53	Innermost TRS:
1113.40/291.53	Rules:
1113.40/291.53	times(x, y) -> sum(generate(x, y))
1113.40/291.53	generate(x, y) -> gen(x, y, 0')
1113.40/291.53	gen(x, y, z) -> if(ge(z, x), x, y, z)
1113.40/291.53	if(true, x, y, z) -> nil
1113.40/291.53	if(false, x, y, z) -> cons(y, gen(x, y, s(z)))
1113.40/291.53	sum(nil) -> 0'
1113.40/291.53	sum(cons(0', xs)) -> sum(xs)
1113.40/291.53	sum(cons(s(x), xs)) -> s(sum(cons(x, xs)))
1113.40/291.53	ge(x, 0') -> true
1113.40/291.53	ge(0', s(y)) -> false
1113.40/291.53	ge(s(x), s(y)) -> ge(x, y)
1113.40/291.53	
1113.40/291.53	Types:
1113.40/291.53	times :: 0':s -> 0':s -> 0':s
1113.40/291.53	sum :: nil:cons -> 0':s
1113.40/291.53	generate :: 0':s -> 0':s -> nil:cons
1113.40/291.53	gen :: 0':s -> 0':s -> 0':s -> nil:cons
1113.40/291.53	0' :: 0':s
1113.40/291.53	if :: true:false -> 0':s -> 0':s -> 0':s -> nil:cons
1113.40/291.53	ge :: 0':s -> 0':s -> true:false
1113.40/291.53	true :: true:false
1113.40/291.53	nil :: nil:cons
1113.40/291.53	false :: true:false
1113.40/291.53	cons :: 0':s -> nil:cons -> nil:cons
1113.40/291.53	s :: 0':s -> 0':s
1113.40/291.53	hole_0':s1_0 :: 0':s
1113.40/291.53	hole_nil:cons2_0 :: nil:cons
1113.40/291.53	hole_true:false3_0 :: true:false
1113.40/291.53	gen_0':s4_0 :: Nat -> 0':s
1113.40/291.53	gen_nil:cons5_0 :: Nat -> nil:cons
1113.40/291.53	
1113.40/291.53	
1113.40/291.53	Lemmas:
1113.40/291.53	sum(gen_nil:cons5_0(n7_0)) -> gen_0':s4_0(0), rt in Omega(1 + n7_0)
1113.40/291.53	ge(gen_0':s4_0(n300_0), gen_0':s4_0(n300_0)) -> true, rt in Omega(1 + n300_0)
1113.40/291.53	
1113.40/291.53	
1113.40/291.53	Generator Equations:
1113.40/291.53	gen_0':s4_0(0) <=> 0'
1113.40/291.53	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
1113.40/291.53	gen_nil:cons5_0(0) <=> nil
1113.40/291.53	gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x))
1113.40/291.53	
1113.40/291.53	
1113.40/291.53	The following defined symbols remain to be analysed:
1113.40/291.53	gen
1113.81/291.61	EOF