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