9.15/3.25	WORST_CASE(NON_POLY, ?)
9.15/3.26	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
9.15/3.26	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
9.15/3.26	
9.15/3.26	
9.15/3.26	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF).
9.15/3.26	
9.15/3.26	(0) CpxTRS
9.15/3.26	(1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
9.15/3.26	(2) TRS for Loop Detection
9.15/3.26	(3) DecreasingLoopProof [LOWER BOUND(ID), 38 ms]
9.15/3.26	(4) BEST
9.15/3.26	    (5) proven lower bound
9.15/3.26	        (6) LowerBoundPropagationProof [FINISHED, 0 ms]
9.15/3.26	        (7) BOUNDS(n^1, INF)
9.15/3.26	    (8) TRS for Loop Detection
9.15/3.26	        (9) InfiniteLowerBoundProof [FINISHED, 1296 ms]
9.15/3.26	        (10) BOUNDS(INF, INF)
9.15/3.26	
9.15/3.26	
9.15/3.26	----------------------------------------
9.15/3.26	
9.15/3.26	(0)
9.15/3.26	Obligation:
9.15/3.26	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF).
9.15/3.26	
9.15/3.26	
9.15/3.26	The TRS R consists of the following rules:
9.15/3.26	
9.15/3.26	   and(tt, T) -> T
9.15/3.26	   isNatIList(IL) -> isNatList(activate(IL))
9.15/3.26	   isNat(n__0) -> tt
9.15/3.26	   isNat(n__s(N)) -> isNat(activate(N))
9.15/3.26	   isNat(n__length(L)) -> isNatList(activate(L))
9.15/3.26	   isNatIList(n__zeros) -> tt
9.15/3.26	   isNatIList(n__cons(N, IL)) -> and(isNat(activate(N)), isNatIList(activate(IL)))
9.15/3.26	   isNatList(n__nil) -> tt
9.15/3.26	   isNatList(n__cons(N, L)) -> and(isNat(activate(N)), isNatList(activate(L)))
9.15/3.26	   isNatList(n__take(N, IL)) -> and(isNat(activate(N)), isNatIList(activate(IL)))
9.15/3.26	   zeros -> cons(0, n__zeros)
9.15/3.26	   take(0, IL) -> uTake1(isNatIList(IL))
9.15/3.26	   uTake1(tt) -> nil
9.15/3.26	   take(s(M), cons(N, IL)) -> uTake2(and(isNat(M), and(isNat(N), isNatIList(activate(IL)))), M, N, activate(IL))
9.15/3.26	   uTake2(tt, M, N, IL) -> cons(activate(N), n__take(activate(M), activate(IL)))
9.15/3.26	   length(cons(N, L)) -> uLength(and(isNat(N), isNatList(activate(L))), activate(L))
9.15/3.26	   uLength(tt, L) -> s(length(activate(L)))
9.15/3.26	   0 -> n__0
9.15/3.26	   s(X) -> n__s(X)
9.15/3.26	   length(X) -> n__length(X)
9.15/3.26	   zeros -> n__zeros
9.15/3.26	   cons(X1, X2) -> n__cons(X1, X2)
9.15/3.26	   nil -> n__nil
9.15/3.26	   take(X1, X2) -> n__take(X1, X2)
9.15/3.26	   activate(n__0) -> 0
9.15/3.26	   activate(n__s(X)) -> s(X)
9.15/3.26	   activate(n__length(X)) -> length(X)
9.15/3.26	   activate(n__zeros) -> zeros
9.15/3.26	   activate(n__cons(X1, X2)) -> cons(X1, X2)
9.15/3.26	   activate(n__nil) -> nil
9.15/3.26	   activate(n__take(X1, X2)) -> take(X1, X2)
9.15/3.26	   activate(X) -> X
9.15/3.26	
9.15/3.26	S is empty.
9.15/3.26	Rewrite Strategy: FULL
9.15/3.26	----------------------------------------
9.15/3.26	
9.15/3.26	(1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
9.15/3.26	Transformed a relative TRS into a decreasing-loop problem.
9.15/3.26	----------------------------------------
9.15/3.26	
9.15/3.26	(2)
9.15/3.26	Obligation:
9.15/3.26	Analyzing the following TRS for decreasing loops:
9.15/3.26	
9.15/3.26	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF).
9.15/3.26	
9.15/3.26	
9.15/3.26	The TRS R consists of the following rules:
9.15/3.26	
9.15/3.26	   and(tt, T) -> T
9.15/3.26	   isNatIList(IL) -> isNatList(activate(IL))
9.15/3.26	   isNat(n__0) -> tt
9.15/3.26	   isNat(n__s(N)) -> isNat(activate(N))
9.15/3.26	   isNat(n__length(L)) -> isNatList(activate(L))
9.15/3.26	   isNatIList(n__zeros) -> tt
9.15/3.26	   isNatIList(n__cons(N, IL)) -> and(isNat(activate(N)), isNatIList(activate(IL)))
9.15/3.26	   isNatList(n__nil) -> tt
9.15/3.26	   isNatList(n__cons(N, L)) -> and(isNat(activate(N)), isNatList(activate(L)))
9.15/3.26	   isNatList(n__take(N, IL)) -> and(isNat(activate(N)), isNatIList(activate(IL)))
9.15/3.26	   zeros -> cons(0, n__zeros)
9.15/3.26	   take(0, IL) -> uTake1(isNatIList(IL))
9.15/3.26	   uTake1(tt) -> nil
9.15/3.26	   take(s(M), cons(N, IL)) -> uTake2(and(isNat(M), and(isNat(N), isNatIList(activate(IL)))), M, N, activate(IL))
9.15/3.26	   uTake2(tt, M, N, IL) -> cons(activate(N), n__take(activate(M), activate(IL)))
9.15/3.26	   length(cons(N, L)) -> uLength(and(isNat(N), isNatList(activate(L))), activate(L))
9.15/3.26	   uLength(tt, L) -> s(length(activate(L)))
9.15/3.26	   0 -> n__0
9.15/3.26	   s(X) -> n__s(X)
9.15/3.26	   length(X) -> n__length(X)
9.15/3.26	   zeros -> n__zeros
9.15/3.26	   cons(X1, X2) -> n__cons(X1, X2)
9.15/3.26	   nil -> n__nil
9.15/3.26	   take(X1, X2) -> n__take(X1, X2)
9.15/3.26	   activate(n__0) -> 0
9.15/3.26	   activate(n__s(X)) -> s(X)
9.15/3.26	   activate(n__length(X)) -> length(X)
9.15/3.26	   activate(n__zeros) -> zeros
9.15/3.26	   activate(n__cons(X1, X2)) -> cons(X1, X2)
9.15/3.26	   activate(n__nil) -> nil
9.15/3.26	   activate(n__take(X1, X2)) -> take(X1, X2)
9.15/3.26	   activate(X) -> X
9.15/3.26	
9.15/3.26	S is empty.
9.15/3.26	Rewrite Strategy: FULL
9.15/3.26	----------------------------------------
9.15/3.26	
9.15/3.26	(3) DecreasingLoopProof (LOWER BOUND(ID))
9.15/3.26	The following loop(s) give(s) rise to the lower bound Omega(n^1):
9.15/3.26	
9.15/3.26	The rewrite sequence
9.15/3.26	
9.15/3.26	isNatIList(n__cons(N, IL)) ->^+ and(isNat(activate(N)), isNatIList(IL))
9.15/3.26	
9.15/3.26	gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
9.15/3.26	
9.15/3.26	The pumping substitution is [IL / n__cons(N, IL)].
9.15/3.26	
9.15/3.26	The result substitution is [ ].
9.15/3.26	
9.15/3.26	
9.15/3.26	
9.15/3.26	
9.15/3.26	----------------------------------------
9.15/3.26	
9.15/3.26	(4)
9.15/3.26	Complex Obligation (BEST)
9.15/3.26	
9.15/3.26	----------------------------------------
9.15/3.26	
9.15/3.26	(5)
9.15/3.26	Obligation:
9.15/3.26	Proved the lower bound n^1 for the following obligation:
9.15/3.26	
9.15/3.26	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF).
9.15/3.26	
9.15/3.26	
9.15/3.26	The TRS R consists of the following rules:
9.15/3.26	
9.15/3.26	   and(tt, T) -> T
9.15/3.26	   isNatIList(IL) -> isNatList(activate(IL))
9.15/3.26	   isNat(n__0) -> tt
9.15/3.26	   isNat(n__s(N)) -> isNat(activate(N))
9.15/3.26	   isNat(n__length(L)) -> isNatList(activate(L))
9.15/3.26	   isNatIList(n__zeros) -> tt
9.15/3.26	   isNatIList(n__cons(N, IL)) -> and(isNat(activate(N)), isNatIList(activate(IL)))
9.15/3.26	   isNatList(n__nil) -> tt
9.15/3.26	   isNatList(n__cons(N, L)) -> and(isNat(activate(N)), isNatList(activate(L)))
9.15/3.26	   isNatList(n__take(N, IL)) -> and(isNat(activate(N)), isNatIList(activate(IL)))
9.15/3.26	   zeros -> cons(0, n__zeros)
9.15/3.26	   take(0, IL) -> uTake1(isNatIList(IL))
9.15/3.26	   uTake1(tt) -> nil
9.15/3.26	   take(s(M), cons(N, IL)) -> uTake2(and(isNat(M), and(isNat(N), isNatIList(activate(IL)))), M, N, activate(IL))
9.15/3.26	   uTake2(tt, M, N, IL) -> cons(activate(N), n__take(activate(M), activate(IL)))
9.15/3.26	   length(cons(N, L)) -> uLength(and(isNat(N), isNatList(activate(L))), activate(L))
9.15/3.26	   uLength(tt, L) -> s(length(activate(L)))
9.15/3.26	   0 -> n__0
9.15/3.26	   s(X) -> n__s(X)
9.15/3.26	   length(X) -> n__length(X)
9.15/3.26	   zeros -> n__zeros
9.15/3.26	   cons(X1, X2) -> n__cons(X1, X2)
9.15/3.26	   nil -> n__nil
9.15/3.26	   take(X1, X2) -> n__take(X1, X2)
9.15/3.26	   activate(n__0) -> 0
9.15/3.26	   activate(n__s(X)) -> s(X)
9.15/3.26	   activate(n__length(X)) -> length(X)
9.15/3.26	   activate(n__zeros) -> zeros
9.15/3.26	   activate(n__cons(X1, X2)) -> cons(X1, X2)
9.15/3.26	   activate(n__nil) -> nil
9.15/3.26	   activate(n__take(X1, X2)) -> take(X1, X2)
9.15/3.26	   activate(X) -> X
9.15/3.26	
9.15/3.26	S is empty.
9.15/3.26	Rewrite Strategy: FULL
9.15/3.26	----------------------------------------
9.15/3.26	
9.15/3.26	(6) LowerBoundPropagationProof (FINISHED)
9.15/3.26	Propagated lower bound.
9.15/3.26	----------------------------------------
9.15/3.26	
9.15/3.26	(7)
9.15/3.26	BOUNDS(n^1, INF)
9.15/3.26	
9.15/3.26	----------------------------------------
9.15/3.26	
9.15/3.26	(8)
9.15/3.26	Obligation:
9.15/3.26	Analyzing the following TRS for decreasing loops:
9.15/3.26	
9.15/3.26	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF).
9.15/3.26	
9.15/3.26	
9.15/3.26	The TRS R consists of the following rules:
9.15/3.26	
9.15/3.26	   and(tt, T) -> T
9.15/3.26	   isNatIList(IL) -> isNatList(activate(IL))
9.15/3.26	   isNat(n__0) -> tt
9.15/3.26	   isNat(n__s(N)) -> isNat(activate(N))
9.15/3.26	   isNat(n__length(L)) -> isNatList(activate(L))
9.15/3.26	   isNatIList(n__zeros) -> tt
9.15/3.26	   isNatIList(n__cons(N, IL)) -> and(isNat(activate(N)), isNatIList(activate(IL)))
9.15/3.26	   isNatList(n__nil) -> tt
9.15/3.26	   isNatList(n__cons(N, L)) -> and(isNat(activate(N)), isNatList(activate(L)))
9.15/3.26	   isNatList(n__take(N, IL)) -> and(isNat(activate(N)), isNatIList(activate(IL)))
9.15/3.26	   zeros -> cons(0, n__zeros)
9.15/3.26	   take(0, IL) -> uTake1(isNatIList(IL))
9.15/3.26	   uTake1(tt) -> nil
9.15/3.26	   take(s(M), cons(N, IL)) -> uTake2(and(isNat(M), and(isNat(N), isNatIList(activate(IL)))), M, N, activate(IL))
9.15/3.26	   uTake2(tt, M, N, IL) -> cons(activate(N), n__take(activate(M), activate(IL)))
9.15/3.26	   length(cons(N, L)) -> uLength(and(isNat(N), isNatList(activate(L))), activate(L))
9.15/3.26	   uLength(tt, L) -> s(length(activate(L)))
9.15/3.26	   0 -> n__0
9.15/3.26	   s(X) -> n__s(X)
9.15/3.26	   length(X) -> n__length(X)
9.15/3.26	   zeros -> n__zeros
9.15/3.26	   cons(X1, X2) -> n__cons(X1, X2)
9.15/3.26	   nil -> n__nil
9.15/3.26	   take(X1, X2) -> n__take(X1, X2)
9.15/3.26	   activate(n__0) -> 0
9.15/3.26	   activate(n__s(X)) -> s(X)
9.15/3.26	   activate(n__length(X)) -> length(X)
9.15/3.26	   activate(n__zeros) -> zeros
9.15/3.26	   activate(n__cons(X1, X2)) -> cons(X1, X2)
9.15/3.26	   activate(n__nil) -> nil
9.15/3.26	   activate(n__take(X1, X2)) -> take(X1, X2)
9.15/3.26	   activate(X) -> X
9.15/3.26	
9.15/3.26	S is empty.
9.15/3.26	Rewrite Strategy: FULL
9.15/3.26	----------------------------------------
9.15/3.26	
9.15/3.26	(9) InfiniteLowerBoundProof (FINISHED)
9.15/3.26	The following loop proves infinite runtime complexity:
9.15/3.26	
9.15/3.26	The rewrite sequence
9.15/3.26	
9.15/3.26	isNatIList(n__cons(N, n__zeros)) ->^+ and(isNat(activate(N)), isNatIList(n__cons(0, n__zeros)))
9.15/3.26	
9.15/3.26	gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
9.15/3.26	
9.15/3.26	The pumping substitution is [ ].
9.15/3.26	
9.15/3.26	The result substitution is [N / 0].
9.15/3.26	
9.15/3.26	
9.15/3.26	
9.15/3.26	
9.15/3.26	----------------------------------------
9.15/3.26	
9.15/3.26	(10)
9.15/3.26	BOUNDS(INF, INF)
9.29/3.31	EOF