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