1097.91/291.54	WORST_CASE(Omega(n^1), ?)
1097.91/291.55	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
1097.91/291.55	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
1097.91/291.55	
1097.91/291.55	
1097.91/291.55	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1097.91/291.55	
1097.91/291.55	(0) CpxTRS
1097.91/291.55	(1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
1097.91/291.55	(2) TRS for Loop Detection
1097.91/291.55	(3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
1097.91/291.55	(4) BEST
1097.91/291.55	    (5) proven lower bound
1097.91/291.55	        (6) LowerBoundPropagationProof [FINISHED, 0 ms]
1097.91/291.55	        (7) BOUNDS(n^1, INF)
1097.91/291.55	    (8) TRS for Loop Detection
1097.91/291.55	
1097.91/291.55	
1097.91/291.55	----------------------------------------
1097.91/291.55	
1097.91/291.55	(0)
1097.91/291.55	Obligation:
1097.91/291.55	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1097.91/291.55	
1097.91/291.55	
1097.91/291.55	The TRS R consists of the following rules:
1097.91/291.55	
1097.91/291.55	   le(s(x), 0) -> false
1097.91/291.55	   le(0, y) -> true
1097.91/291.55	   le(s(x), s(y)) -> le(x, y)
1097.91/291.55	   double(0) -> 0
1097.91/291.55	   double(s(x)) -> s(s(double(x)))
1097.91/291.55	   log(0) -> logError
1097.91/291.55	   log(s(x)) -> loop(s(x), s(0), 0)
1097.91/291.55	   loop(x, s(y), z) -> if(le(x, s(y)), x, s(y), z)
1097.91/291.55	   if(true, x, y, z) -> z
1097.91/291.55	   if(false, x, y, z) -> loop(x, double(y), s(z))
1097.91/291.55	
1097.91/291.55	S is empty.
1097.91/291.55	Rewrite Strategy: INNERMOST
1097.91/291.55	----------------------------------------
1097.91/291.55	
1097.91/291.55	(1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
1097.91/291.55	Transformed a relative TRS into a decreasing-loop problem.
1097.91/291.55	----------------------------------------
1097.91/291.55	
1097.91/291.55	(2)
1097.91/291.55	Obligation:
1097.91/291.55	Analyzing the following TRS for decreasing loops:
1097.91/291.55	
1097.91/291.55	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1097.91/291.55	
1097.91/291.55	
1097.91/291.55	The TRS R consists of the following rules:
1097.91/291.55	
1097.91/291.55	   le(s(x), 0) -> false
1097.91/291.55	   le(0, y) -> true
1097.91/291.55	   le(s(x), s(y)) -> le(x, y)
1097.91/291.55	   double(0) -> 0
1097.91/291.55	   double(s(x)) -> s(s(double(x)))
1097.91/291.55	   log(0) -> logError
1097.91/291.55	   log(s(x)) -> loop(s(x), s(0), 0)
1097.91/291.55	   loop(x, s(y), z) -> if(le(x, s(y)), x, s(y), z)
1097.91/291.55	   if(true, x, y, z) -> z
1097.91/291.55	   if(false, x, y, z) -> loop(x, double(y), s(z))
1097.91/291.55	
1097.91/291.55	S is empty.
1097.91/291.55	Rewrite Strategy: INNERMOST
1097.91/291.55	----------------------------------------
1097.91/291.55	
1097.91/291.55	(3) DecreasingLoopProof (LOWER BOUND(ID))
1097.91/291.55	The following loop(s) give(s) rise to the lower bound Omega(n^1):
1097.91/291.55	
1097.91/291.55	The rewrite sequence
1097.91/291.55	
1097.91/291.55	double(s(x)) ->^+ s(s(double(x)))
1097.91/291.55	
1097.91/291.55	gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0].
1097.91/291.55	
1097.91/291.55	The pumping substitution is [x / s(x)].
1097.91/291.55	
1097.91/291.55	The result substitution is [ ].
1097.91/291.55	
1097.91/291.55	
1097.91/291.55	
1097.91/291.55	
1097.91/291.55	----------------------------------------
1097.91/291.55	
1097.91/291.55	(4)
1097.91/291.55	Complex Obligation (BEST)
1097.91/291.55	
1097.91/291.55	----------------------------------------
1097.91/291.55	
1097.91/291.55	(5)
1097.91/291.55	Obligation:
1097.91/291.55	Proved the lower bound n^1 for the following obligation:
1097.91/291.55	
1097.91/291.55	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1097.91/291.55	
1097.91/291.55	
1097.91/291.55	The TRS R consists of the following rules:
1097.91/291.55	
1097.91/291.55	   le(s(x), 0) -> false
1097.91/291.55	   le(0, y) -> true
1097.91/291.55	   le(s(x), s(y)) -> le(x, y)
1097.91/291.55	   double(0) -> 0
1097.91/291.55	   double(s(x)) -> s(s(double(x)))
1097.91/291.55	   log(0) -> logError
1097.91/291.55	   log(s(x)) -> loop(s(x), s(0), 0)
1097.91/291.55	   loop(x, s(y), z) -> if(le(x, s(y)), x, s(y), z)
1097.91/291.55	   if(true, x, y, z) -> z
1097.91/291.55	   if(false, x, y, z) -> loop(x, double(y), s(z))
1097.91/291.55	
1097.91/291.55	S is empty.
1097.91/291.55	Rewrite Strategy: INNERMOST
1097.91/291.55	----------------------------------------
1097.91/291.55	
1097.91/291.55	(6) LowerBoundPropagationProof (FINISHED)
1097.91/291.55	Propagated lower bound.
1097.91/291.55	----------------------------------------
1097.91/291.55	
1097.91/291.55	(7)
1097.91/291.55	BOUNDS(n^1, INF)
1097.91/291.55	
1097.91/291.55	----------------------------------------
1097.91/291.55	
1097.91/291.55	(8)
1097.91/291.55	Obligation:
1097.91/291.55	Analyzing the following TRS for decreasing loops:
1097.91/291.55	
1097.91/291.55	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1097.91/291.55	
1097.91/291.55	
1097.91/291.55	The TRS R consists of the following rules:
1097.91/291.55	
1097.91/291.55	   le(s(x), 0) -> false
1097.91/291.55	   le(0, y) -> true
1097.91/291.55	   le(s(x), s(y)) -> le(x, y)
1097.91/291.55	   double(0) -> 0
1097.91/291.55	   double(s(x)) -> s(s(double(x)))
1097.91/291.55	   log(0) -> logError
1097.91/291.55	   log(s(x)) -> loop(s(x), s(0), 0)
1097.91/291.55	   loop(x, s(y), z) -> if(le(x, s(y)), x, s(y), z)
1097.91/291.55	   if(true, x, y, z) -> z
1097.91/291.55	   if(false, x, y, z) -> loop(x, double(y), s(z))
1097.91/291.55	
1097.91/291.55	S is empty.
1097.91/291.55	Rewrite Strategy: INNERMOST
1098.11/291.62	EOF