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