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