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