36.57/10.26	WORST_CASE(NON_POLY, ?)
36.57/10.26	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
36.57/10.26	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
36.57/10.26	
36.57/10.26	
36.57/10.26	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(INF, INF).
36.57/10.26	
36.57/10.26	(0) CpxTRS
36.57/10.26	(1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
36.57/10.26	(2) TRS for Loop Detection
36.57/10.26	(3) DecreasingLoopProof [LOWER BOUND(ID), 20 ms]
36.57/10.26	(4) BEST
36.57/10.26	    (5) proven lower bound
36.57/10.26	        (6) LowerBoundPropagationProof [FINISHED, 0 ms]
36.57/10.26	        (7) BOUNDS(n^1, INF)
36.57/10.26	    (8) TRS for Loop Detection
36.57/10.26	        (9) InfiniteLowerBoundProof [FINISHED, 5539 ms]
36.57/10.26	        (10) BOUNDS(INF, INF)
36.57/10.26	
36.57/10.26	
36.57/10.26	----------------------------------------
36.57/10.26	
36.57/10.26	(0)
36.57/10.26	Obligation:
36.57/10.26	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(INF, INF).
36.57/10.26	
36.57/10.26	
36.57/10.26	The TRS R consists of the following rules:
36.57/10.26	
36.57/10.26	   zeros -> cons(0, n__zeros)
36.57/10.26	   U11(tt, L) -> U12(tt, activate(L))
36.57/10.26	   U12(tt, L) -> s(length(activate(L)))
36.57/10.26	   U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N))
36.57/10.26	   U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N))
36.57/10.26	   U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL)))
36.57/10.26	   length(nil) -> 0
36.57/10.26	   length(cons(N, L)) -> U11(tt, activate(L))
36.57/10.26	   take(0, IL) -> nil
36.57/10.26	   take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N)
36.57/10.26	   zeros -> n__zeros
36.57/10.26	   take(X1, X2) -> n__take(X1, X2)
36.57/10.26	   activate(n__zeros) -> zeros
36.57/10.26	   activate(n__take(X1, X2)) -> take(X1, X2)
36.57/10.26	   activate(X) -> X
36.57/10.26	
36.57/10.26	S is empty.
36.57/10.26	Rewrite Strategy: INNERMOST
36.57/10.26	----------------------------------------
36.57/10.26	
36.57/10.26	(1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
36.57/10.26	Transformed a relative TRS into a decreasing-loop problem.
36.57/10.26	----------------------------------------
36.57/10.26	
36.57/10.26	(2)
36.57/10.26	Obligation:
36.57/10.26	Analyzing the following TRS for decreasing loops:
36.57/10.26	
36.57/10.26	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(INF, INF).
36.57/10.26	
36.57/10.26	
36.57/10.26	The TRS R consists of the following rules:
36.57/10.26	
36.57/10.26	   zeros -> cons(0, n__zeros)
36.57/10.26	   U11(tt, L) -> U12(tt, activate(L))
36.57/10.26	   U12(tt, L) -> s(length(activate(L)))
36.57/10.26	   U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N))
36.57/10.26	   U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N))
36.57/10.26	   U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL)))
36.57/10.26	   length(nil) -> 0
36.57/10.26	   length(cons(N, L)) -> U11(tt, activate(L))
36.57/10.26	   take(0, IL) -> nil
36.57/10.26	   take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N)
36.57/10.26	   zeros -> n__zeros
36.57/10.26	   take(X1, X2) -> n__take(X1, X2)
36.57/10.26	   activate(n__zeros) -> zeros
36.57/10.26	   activate(n__take(X1, X2)) -> take(X1, X2)
36.57/10.26	   activate(X) -> X
36.57/10.26	
36.57/10.26	S is empty.
36.57/10.26	Rewrite Strategy: INNERMOST
36.57/10.26	----------------------------------------
36.57/10.26	
36.57/10.26	(3) DecreasingLoopProof (LOWER BOUND(ID))
36.57/10.26	The following loop(s) give(s) rise to the lower bound Omega(n^1):
36.57/10.26	
36.57/10.26	The rewrite sequence
36.57/10.26	
36.57/10.26	activate(n__take(s(M1_0), cons(N2_0, IL3_0))) ->^+ U21(tt, activate(IL3_0), M1_0, N2_0)
36.57/10.26	
36.57/10.26	gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
36.57/10.26	
36.57/10.26	The pumping substitution is [IL3_0 / n__take(s(M1_0), cons(N2_0, IL3_0))].
36.57/10.26	
36.57/10.26	The result substitution is [ ].
36.57/10.26	
36.57/10.26	
36.57/10.26	
36.57/10.26	
36.57/10.26	----------------------------------------
36.57/10.26	
36.57/10.26	(4)
36.57/10.26	Complex Obligation (BEST)
36.57/10.26	
36.57/10.26	----------------------------------------
36.57/10.26	
36.57/10.26	(5)
36.57/10.26	Obligation:
36.57/10.26	Proved the lower bound n^1 for the following obligation:
36.57/10.26	
36.57/10.26	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(INF, INF).
36.57/10.26	
36.57/10.26	
36.57/10.26	The TRS R consists of the following rules:
36.57/10.26	
36.57/10.26	   zeros -> cons(0, n__zeros)
36.57/10.26	   U11(tt, L) -> U12(tt, activate(L))
36.57/10.26	   U12(tt, L) -> s(length(activate(L)))
36.57/10.26	   U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N))
36.57/10.26	   U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N))
36.57/10.26	   U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL)))
36.57/10.26	   length(nil) -> 0
36.57/10.26	   length(cons(N, L)) -> U11(tt, activate(L))
36.57/10.26	   take(0, IL) -> nil
36.57/10.26	   take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N)
36.57/10.26	   zeros -> n__zeros
36.57/10.26	   take(X1, X2) -> n__take(X1, X2)
36.57/10.26	   activate(n__zeros) -> zeros
36.57/10.26	   activate(n__take(X1, X2)) -> take(X1, X2)
36.57/10.26	   activate(X) -> X
36.57/10.26	
36.57/10.26	S is empty.
36.57/10.26	Rewrite Strategy: INNERMOST
36.57/10.26	----------------------------------------
36.57/10.26	
36.57/10.26	(6) LowerBoundPropagationProof (FINISHED)
36.57/10.26	Propagated lower bound.
36.57/10.26	----------------------------------------
36.57/10.26	
36.57/10.26	(7)
36.57/10.26	BOUNDS(n^1, INF)
36.57/10.26	
36.57/10.26	----------------------------------------
36.57/10.26	
36.57/10.26	(8)
36.57/10.26	Obligation:
36.57/10.26	Analyzing the following TRS for decreasing loops:
36.57/10.26	
36.57/10.26	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(INF, INF).
36.57/10.26	
36.57/10.26	
36.57/10.26	The TRS R consists of the following rules:
36.57/10.26	
36.57/10.26	   zeros -> cons(0, n__zeros)
36.57/10.26	   U11(tt, L) -> U12(tt, activate(L))
36.57/10.26	   U12(tt, L) -> s(length(activate(L)))
36.57/10.26	   U21(tt, IL, M, N) -> U22(tt, activate(IL), activate(M), activate(N))
36.57/10.26	   U22(tt, IL, M, N) -> U23(tt, activate(IL), activate(M), activate(N))
36.57/10.26	   U23(tt, IL, M, N) -> cons(activate(N), n__take(activate(M), activate(IL)))
36.57/10.26	   length(nil) -> 0
36.57/10.26	   length(cons(N, L)) -> U11(tt, activate(L))
36.57/10.26	   take(0, IL) -> nil
36.57/10.26	   take(s(M), cons(N, IL)) -> U21(tt, activate(IL), M, N)
36.57/10.26	   zeros -> n__zeros
36.57/10.26	   take(X1, X2) -> n__take(X1, X2)
36.57/10.26	   activate(n__zeros) -> zeros
36.57/10.26	   activate(n__take(X1, X2)) -> take(X1, X2)
36.57/10.26	   activate(X) -> X
36.57/10.26	
36.57/10.26	S is empty.
36.57/10.26	Rewrite Strategy: INNERMOST
36.57/10.26	----------------------------------------
36.57/10.26	
36.57/10.26	(9) InfiniteLowerBoundProof (FINISHED)
36.57/10.26	The following loop proves infinite runtime complexity:
36.57/10.26	
36.57/10.26	The rewrite sequence
36.57/10.26	
36.57/10.26	length(cons(N, n__zeros)) ->^+ s(length(cons(0, n__zeros)))
36.57/10.26	
36.57/10.26	gives rise to a decreasing loop by considering the right hand sides subterm at position [0].
36.57/10.26	
36.57/10.26	The pumping substitution is [ ].
36.57/10.26	
36.57/10.26	The result substitution is [N / 0].
36.57/10.26	
36.57/10.26	
36.57/10.26	
36.57/10.26	
36.57/10.26	----------------------------------------
36.57/10.26	
36.57/10.26	(10)
36.57/10.26	BOUNDS(INF, INF)
36.82/10.30	EOF