1166.12/295.76	WORST_CASE(Omega(n^1), ?)
1166.12/295.78	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
1166.12/295.78	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
1166.12/295.78	
1166.12/295.78	
1166.12/295.78	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1166.12/295.78	
1166.12/295.78	(0) CpxTRS
1166.12/295.78	(1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
1166.12/295.78	(2) TRS for Loop Detection
1166.12/295.78	(3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
1166.12/295.78	(4) BEST
1166.12/295.78	    (5) proven lower bound
1166.12/295.78	        (6) LowerBoundPropagationProof [FINISHED, 0 ms]
1166.12/295.78	        (7) BOUNDS(n^1, INF)
1166.12/295.78	    (8) TRS for Loop Detection
1166.12/295.78	
1166.12/295.78	
1166.12/295.78	----------------------------------------
1166.12/295.78	
1166.12/295.78	(0)
1166.12/295.78	Obligation:
1166.12/295.78	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1166.12/295.78	
1166.12/295.78	
1166.12/295.78	The TRS R consists of the following rules:
1166.12/295.78	
1166.12/295.78	   f(s(x1), x2, x3, x4, x5, x6, x7, x8, x9, x10) -> f(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, s(x2), x3, x4, x5, x6, x7, x8, x9, x10) -> f(x2, x2, x3, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, s(x3), x4, x5, x6, x7, x8, x9, x10) -> f(x3, x3, x3, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, s(x4), x5, x6, x7, x8, x9, x10) -> f(x4, x4, x4, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, s(x5), x6, x7, x8, x9, x10) -> f(x5, x5, x5, x5, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, s(x6), x7, x8, x9, x10) -> f(x6, x6, x6, x6, x6, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, s(x7), x8, x9, x10) -> f(x7, x7, x7, x7, x7, x7, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, 0, s(x8), x9, x10) -> f(x8, x8, x8, x8, x8, x8, x8, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, 0, 0, s(x9), x10) -> f(x9, x9, x9, x9, x9, x9, x9, x9, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, 0, 0, 0, s(x10)) -> f(x10, x10, x10, x10, x10, x10, x10, x10, x10, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) -> 0
1166.12/295.78	
1166.12/295.78	S is empty.
1166.12/295.78	Rewrite Strategy: INNERMOST
1166.12/295.78	----------------------------------------
1166.12/295.78	
1166.12/295.78	(1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
1166.12/295.78	Transformed a relative TRS into a decreasing-loop problem.
1166.12/295.78	----------------------------------------
1166.12/295.78	
1166.12/295.78	(2)
1166.12/295.78	Obligation:
1166.12/295.78	Analyzing the following TRS for decreasing loops:
1166.12/295.78	
1166.12/295.78	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1166.12/295.78	
1166.12/295.78	
1166.12/295.78	The TRS R consists of the following rules:
1166.12/295.78	
1166.12/295.78	   f(s(x1), x2, x3, x4, x5, x6, x7, x8, x9, x10) -> f(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, s(x2), x3, x4, x5, x6, x7, x8, x9, x10) -> f(x2, x2, x3, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, s(x3), x4, x5, x6, x7, x8, x9, x10) -> f(x3, x3, x3, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, s(x4), x5, x6, x7, x8, x9, x10) -> f(x4, x4, x4, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, s(x5), x6, x7, x8, x9, x10) -> f(x5, x5, x5, x5, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, s(x6), x7, x8, x9, x10) -> f(x6, x6, x6, x6, x6, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, s(x7), x8, x9, x10) -> f(x7, x7, x7, x7, x7, x7, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, 0, s(x8), x9, x10) -> f(x8, x8, x8, x8, x8, x8, x8, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, 0, 0, s(x9), x10) -> f(x9, x9, x9, x9, x9, x9, x9, x9, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, 0, 0, 0, s(x10)) -> f(x10, x10, x10, x10, x10, x10, x10, x10, x10, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) -> 0
1166.12/295.78	
1166.12/295.78	S is empty.
1166.12/295.78	Rewrite Strategy: INNERMOST
1166.12/295.78	----------------------------------------
1166.12/295.78	
1166.12/295.78	(3) DecreasingLoopProof (LOWER BOUND(ID))
1166.12/295.78	The following loop(s) give(s) rise to the lower bound Omega(n^1):
1166.12/295.78	
1166.12/295.78	The rewrite sequence
1166.12/295.78	
1166.12/295.78	f(s(x1), x2, x3, x4, x5, x6, x7, x8, x9, x10) ->^+ f(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	
1166.12/295.78	gives rise to a decreasing loop by considering the right hand sides subterm at position [].
1166.12/295.78	
1166.12/295.78	The pumping substitution is [x1 / s(x1)].
1166.12/295.78	
1166.12/295.78	The result substitution is [ ].
1166.12/295.78	
1166.12/295.78	
1166.12/295.78	
1166.12/295.78	
1166.12/295.78	----------------------------------------
1166.12/295.78	
1166.12/295.78	(4)
1166.12/295.78	Complex Obligation (BEST)
1166.12/295.78	
1166.12/295.78	----------------------------------------
1166.12/295.78	
1166.12/295.78	(5)
1166.12/295.78	Obligation:
1166.12/295.78	Proved the lower bound n^1 for the following obligation:
1166.12/295.78	
1166.12/295.78	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1166.12/295.78	
1166.12/295.78	
1166.12/295.78	The TRS R consists of the following rules:
1166.12/295.78	
1166.12/295.78	   f(s(x1), x2, x3, x4, x5, x6, x7, x8, x9, x10) -> f(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, s(x2), x3, x4, x5, x6, x7, x8, x9, x10) -> f(x2, x2, x3, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, s(x3), x4, x5, x6, x7, x8, x9, x10) -> f(x3, x3, x3, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, s(x4), x5, x6, x7, x8, x9, x10) -> f(x4, x4, x4, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, s(x5), x6, x7, x8, x9, x10) -> f(x5, x5, x5, x5, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, s(x6), x7, x8, x9, x10) -> f(x6, x6, x6, x6, x6, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, s(x7), x8, x9, x10) -> f(x7, x7, x7, x7, x7, x7, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, 0, s(x8), x9, x10) -> f(x8, x8, x8, x8, x8, x8, x8, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, 0, 0, s(x9), x10) -> f(x9, x9, x9, x9, x9, x9, x9, x9, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, 0, 0, 0, s(x10)) -> f(x10, x10, x10, x10, x10, x10, x10, x10, x10, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) -> 0
1166.12/295.78	
1166.12/295.78	S is empty.
1166.12/295.78	Rewrite Strategy: INNERMOST
1166.12/295.78	----------------------------------------
1166.12/295.78	
1166.12/295.78	(6) LowerBoundPropagationProof (FINISHED)
1166.12/295.78	Propagated lower bound.
1166.12/295.78	----------------------------------------
1166.12/295.78	
1166.12/295.78	(7)
1166.12/295.78	BOUNDS(n^1, INF)
1166.12/295.78	
1166.12/295.78	----------------------------------------
1166.12/295.78	
1166.12/295.78	(8)
1166.12/295.78	Obligation:
1166.12/295.78	Analyzing the following TRS for decreasing loops:
1166.12/295.78	
1166.12/295.78	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1166.12/295.78	
1166.12/295.78	
1166.12/295.78	The TRS R consists of the following rules:
1166.12/295.78	
1166.12/295.78	   f(s(x1), x2, x3, x4, x5, x6, x7, x8, x9, x10) -> f(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, s(x2), x3, x4, x5, x6, x7, x8, x9, x10) -> f(x2, x2, x3, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, s(x3), x4, x5, x6, x7, x8, x9, x10) -> f(x3, x3, x3, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, s(x4), x5, x6, x7, x8, x9, x10) -> f(x4, x4, x4, x4, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, s(x5), x6, x7, x8, x9, x10) -> f(x5, x5, x5, x5, x5, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, s(x6), x7, x8, x9, x10) -> f(x6, x6, x6, x6, x6, x6, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, s(x7), x8, x9, x10) -> f(x7, x7, x7, x7, x7, x7, x7, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, 0, s(x8), x9, x10) -> f(x8, x8, x8, x8, x8, x8, x8, x8, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, 0, 0, s(x9), x10) -> f(x9, x9, x9, x9, x9, x9, x9, x9, x9, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, 0, 0, 0, s(x10)) -> f(x10, x10, x10, x10, x10, x10, x10, x10, x10, x10)
1166.12/295.78	   f(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) -> 0
1166.12/295.78	
1166.12/295.78	S is empty.
1166.12/295.78	Rewrite Strategy: INNERMOST
1166.40/295.88	EOF