1152.57/298.99	WORST_CASE(Omega(n^1), ?)
1152.57/299.06	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
1152.57/299.06	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
1152.57/299.06	
1152.57/299.06	
1152.57/299.06	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1152.57/299.06	
1152.57/299.06	(0) CpxTRS
1152.57/299.06	(1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
1152.57/299.06	(2) TRS for Loop Detection
1152.57/299.06	(3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
1152.57/299.06	(4) BEST
1152.57/299.06	    (5) proven lower bound
1152.57/299.06	        (6) LowerBoundPropagationProof [FINISHED, 0 ms]
1152.57/299.06	        (7) BOUNDS(n^1, INF)
1152.57/299.06	    (8) TRS for Loop Detection
1152.57/299.06	
1152.57/299.06	
1152.57/299.06	----------------------------------------
1152.57/299.06	
1152.57/299.06	(0)
1152.57/299.06	Obligation:
1152.57/299.06	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1152.57/299.06	
1152.57/299.06	
1152.57/299.06	The TRS R consists of the following rules:
1152.57/299.06	
1152.57/299.06	   a__and(tt, T) -> mark(T)
1152.57/299.06	   a__isNatIList(IL) -> a__isNatList(IL)
1152.57/299.06	   a__isNat(0) -> tt
1152.57/299.06	   a__isNat(s(N)) -> a__isNat(N)
1152.57/299.06	   a__isNat(length(L)) -> a__isNatList(L)
1152.57/299.06	   a__isNatIList(zeros) -> tt
1152.57/299.06	   a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL))
1152.57/299.06	   a__isNatList(nil) -> tt
1152.57/299.06	   a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L))
1152.57/299.06	   a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL))
1152.57/299.06	   a__zeros -> cons(0, zeros)
1152.57/299.06	   a__take(0, IL) -> a__uTake1(a__isNatIList(IL))
1152.57/299.06	   a__uTake1(tt) -> nil
1152.57/299.06	   a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL)
1152.57/299.06	   a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL))
1152.57/299.06	   a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L)
1152.57/299.06	   a__uLength(tt, L) -> s(a__length(mark(L)))
1152.57/299.06	   mark(and(X1, X2)) -> a__and(mark(X1), mark(X2))
1152.57/299.06	   mark(isNatIList(X)) -> a__isNatIList(X)
1152.57/299.06	   mark(isNatList(X)) -> a__isNatList(X)
1152.57/299.06	   mark(isNat(X)) -> a__isNat(X)
1152.57/299.06	   mark(length(X)) -> a__length(mark(X))
1152.57/299.06	   mark(zeros) -> a__zeros
1152.57/299.06	   mark(take(X1, X2)) -> a__take(mark(X1), mark(X2))
1152.57/299.06	   mark(uTake1(X)) -> a__uTake1(mark(X))
1152.57/299.06	   mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4)
1152.57/299.06	   mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2)
1152.57/299.06	   mark(tt) -> tt
1152.57/299.06	   mark(0) -> 0
1152.57/299.06	   mark(s(X)) -> s(mark(X))
1152.57/299.06	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
1152.57/299.06	   mark(nil) -> nil
1152.57/299.06	   a__and(X1, X2) -> and(X1, X2)
1152.57/299.06	   a__isNatIList(X) -> isNatIList(X)
1152.57/299.06	   a__isNatList(X) -> isNatList(X)
1152.57/299.06	   a__isNat(X) -> isNat(X)
1152.57/299.06	   a__length(X) -> length(X)
1152.57/299.06	   a__zeros -> zeros
1152.57/299.06	   a__take(X1, X2) -> take(X1, X2)
1152.57/299.06	   a__uTake1(X) -> uTake1(X)
1152.57/299.06	   a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4)
1152.57/299.06	   a__uLength(X1, X2) -> uLength(X1, X2)
1152.57/299.06	
1152.57/299.06	S is empty.
1152.57/299.06	Rewrite Strategy: INNERMOST
1152.57/299.06	----------------------------------------
1152.57/299.06	
1152.57/299.06	(1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
1152.57/299.06	Transformed a relative TRS into a decreasing-loop problem.
1152.57/299.06	----------------------------------------
1152.57/299.06	
1152.57/299.06	(2)
1152.57/299.06	Obligation:
1152.57/299.06	Analyzing the following TRS for decreasing loops:
1152.57/299.06	
1152.57/299.06	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1152.57/299.06	
1152.57/299.06	
1152.57/299.06	The TRS R consists of the following rules:
1152.57/299.06	
1152.57/299.06	   a__and(tt, T) -> mark(T)
1152.57/299.06	   a__isNatIList(IL) -> a__isNatList(IL)
1152.57/299.06	   a__isNat(0) -> tt
1152.57/299.06	   a__isNat(s(N)) -> a__isNat(N)
1152.57/299.06	   a__isNat(length(L)) -> a__isNatList(L)
1152.57/299.06	   a__isNatIList(zeros) -> tt
1152.57/299.06	   a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL))
1152.57/299.06	   a__isNatList(nil) -> tt
1152.57/299.06	   a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L))
1152.57/299.06	   a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL))
1152.57/299.06	   a__zeros -> cons(0, zeros)
1152.57/299.06	   a__take(0, IL) -> a__uTake1(a__isNatIList(IL))
1152.57/299.06	   a__uTake1(tt) -> nil
1152.57/299.06	   a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL)
1152.57/299.06	   a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL))
1152.57/299.06	   a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L)
1152.57/299.06	   a__uLength(tt, L) -> s(a__length(mark(L)))
1152.57/299.06	   mark(and(X1, X2)) -> a__and(mark(X1), mark(X2))
1152.57/299.06	   mark(isNatIList(X)) -> a__isNatIList(X)
1152.57/299.06	   mark(isNatList(X)) -> a__isNatList(X)
1152.57/299.06	   mark(isNat(X)) -> a__isNat(X)
1152.57/299.06	   mark(length(X)) -> a__length(mark(X))
1152.57/299.06	   mark(zeros) -> a__zeros
1152.57/299.06	   mark(take(X1, X2)) -> a__take(mark(X1), mark(X2))
1152.57/299.06	   mark(uTake1(X)) -> a__uTake1(mark(X))
1152.57/299.06	   mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4)
1152.57/299.06	   mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2)
1152.57/299.06	   mark(tt) -> tt
1152.57/299.06	   mark(0) -> 0
1152.57/299.06	   mark(s(X)) -> s(mark(X))
1152.57/299.06	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
1152.57/299.06	   mark(nil) -> nil
1152.57/299.06	   a__and(X1, X2) -> and(X1, X2)
1152.57/299.06	   a__isNatIList(X) -> isNatIList(X)
1152.57/299.06	   a__isNatList(X) -> isNatList(X)
1152.57/299.06	   a__isNat(X) -> isNat(X)
1152.57/299.06	   a__length(X) -> length(X)
1152.57/299.06	   a__zeros -> zeros
1152.57/299.06	   a__take(X1, X2) -> take(X1, X2)
1152.57/299.06	   a__uTake1(X) -> uTake1(X)
1152.57/299.06	   a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4)
1152.57/299.06	   a__uLength(X1, X2) -> uLength(X1, X2)
1152.57/299.06	
1152.57/299.06	S is empty.
1152.57/299.06	Rewrite Strategy: INNERMOST
1152.57/299.06	----------------------------------------
1152.57/299.06	
1152.57/299.06	(3) DecreasingLoopProof (LOWER BOUND(ID))
1152.57/299.06	The following loop(s) give(s) rise to the lower bound Omega(n^1):
1152.57/299.06	
1152.57/299.06	The rewrite sequence
1152.57/299.06	
1152.57/299.06	a__isNat(s(N)) ->^+ a__isNat(N)
1152.57/299.06	
1152.57/299.06	gives rise to a decreasing loop by considering the right hand sides subterm at position [].
1152.57/299.06	
1152.57/299.06	The pumping substitution is [N / s(N)].
1152.57/299.06	
1152.57/299.06	The result substitution is [ ].
1152.57/299.06	
1152.57/299.06	
1152.57/299.06	
1152.57/299.06	
1152.57/299.06	----------------------------------------
1152.57/299.06	
1152.57/299.06	(4)
1152.57/299.06	Complex Obligation (BEST)
1152.57/299.06	
1152.57/299.06	----------------------------------------
1152.57/299.06	
1152.57/299.06	(5)
1152.57/299.06	Obligation:
1152.57/299.06	Proved the lower bound n^1 for the following obligation:
1152.57/299.06	
1152.57/299.06	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1152.57/299.06	
1152.57/299.06	
1152.57/299.06	The TRS R consists of the following rules:
1152.57/299.06	
1152.57/299.06	   a__and(tt, T) -> mark(T)
1152.57/299.06	   a__isNatIList(IL) -> a__isNatList(IL)
1152.57/299.06	   a__isNat(0) -> tt
1152.57/299.06	   a__isNat(s(N)) -> a__isNat(N)
1152.57/299.06	   a__isNat(length(L)) -> a__isNatList(L)
1152.57/299.06	   a__isNatIList(zeros) -> tt
1152.57/299.06	   a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL))
1152.57/299.06	   a__isNatList(nil) -> tt
1152.57/299.06	   a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L))
1152.57/299.06	   a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL))
1152.57/299.06	   a__zeros -> cons(0, zeros)
1152.57/299.06	   a__take(0, IL) -> a__uTake1(a__isNatIList(IL))
1152.57/299.06	   a__uTake1(tt) -> nil
1152.57/299.06	   a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL)
1152.57/299.06	   a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL))
1152.57/299.06	   a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L)
1152.57/299.06	   a__uLength(tt, L) -> s(a__length(mark(L)))
1152.57/299.06	   mark(and(X1, X2)) -> a__and(mark(X1), mark(X2))
1152.57/299.06	   mark(isNatIList(X)) -> a__isNatIList(X)
1152.57/299.06	   mark(isNatList(X)) -> a__isNatList(X)
1152.57/299.06	   mark(isNat(X)) -> a__isNat(X)
1152.57/299.06	   mark(length(X)) -> a__length(mark(X))
1152.57/299.06	   mark(zeros) -> a__zeros
1152.57/299.06	   mark(take(X1, X2)) -> a__take(mark(X1), mark(X2))
1152.57/299.06	   mark(uTake1(X)) -> a__uTake1(mark(X))
1152.57/299.06	   mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4)
1152.57/299.06	   mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2)
1152.57/299.06	   mark(tt) -> tt
1152.57/299.06	   mark(0) -> 0
1152.57/299.06	   mark(s(X)) -> s(mark(X))
1152.57/299.06	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
1152.57/299.06	   mark(nil) -> nil
1152.57/299.06	   a__and(X1, X2) -> and(X1, X2)
1152.57/299.06	   a__isNatIList(X) -> isNatIList(X)
1152.57/299.06	   a__isNatList(X) -> isNatList(X)
1152.57/299.06	   a__isNat(X) -> isNat(X)
1152.57/299.06	   a__length(X) -> length(X)
1152.57/299.06	   a__zeros -> zeros
1152.57/299.06	   a__take(X1, X2) -> take(X1, X2)
1152.57/299.06	   a__uTake1(X) -> uTake1(X)
1152.57/299.06	   a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4)
1152.57/299.06	   a__uLength(X1, X2) -> uLength(X1, X2)
1152.57/299.06	
1152.57/299.06	S is empty.
1152.57/299.06	Rewrite Strategy: INNERMOST
1152.57/299.06	----------------------------------------
1152.57/299.06	
1152.57/299.06	(6) LowerBoundPropagationProof (FINISHED)
1152.57/299.06	Propagated lower bound.
1152.57/299.06	----------------------------------------
1152.57/299.06	
1152.57/299.06	(7)
1152.57/299.06	BOUNDS(n^1, INF)
1152.57/299.06	
1152.57/299.06	----------------------------------------
1152.57/299.06	
1152.57/299.06	(8)
1152.57/299.06	Obligation:
1152.57/299.06	Analyzing the following TRS for decreasing loops:
1152.57/299.06	
1152.57/299.06	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1152.57/299.06	
1152.57/299.06	
1152.57/299.06	The TRS R consists of the following rules:
1152.57/299.06	
1152.57/299.06	   a__and(tt, T) -> mark(T)
1152.57/299.06	   a__isNatIList(IL) -> a__isNatList(IL)
1152.57/299.06	   a__isNat(0) -> tt
1152.57/299.06	   a__isNat(s(N)) -> a__isNat(N)
1152.57/299.06	   a__isNat(length(L)) -> a__isNatList(L)
1152.57/299.06	   a__isNatIList(zeros) -> tt
1152.57/299.06	   a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL))
1152.57/299.06	   a__isNatList(nil) -> tt
1152.57/299.06	   a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L))
1152.57/299.06	   a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL))
1152.57/299.06	   a__zeros -> cons(0, zeros)
1152.57/299.06	   a__take(0, IL) -> a__uTake1(a__isNatIList(IL))
1152.57/299.06	   a__uTake1(tt) -> nil
1152.57/299.06	   a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL)
1152.57/299.06	   a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL))
1152.57/299.06	   a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L)
1152.57/299.06	   a__uLength(tt, L) -> s(a__length(mark(L)))
1152.57/299.06	   mark(and(X1, X2)) -> a__and(mark(X1), mark(X2))
1152.57/299.06	   mark(isNatIList(X)) -> a__isNatIList(X)
1152.57/299.06	   mark(isNatList(X)) -> a__isNatList(X)
1152.57/299.06	   mark(isNat(X)) -> a__isNat(X)
1152.57/299.06	   mark(length(X)) -> a__length(mark(X))
1152.57/299.06	   mark(zeros) -> a__zeros
1152.57/299.06	   mark(take(X1, X2)) -> a__take(mark(X1), mark(X2))
1152.57/299.06	   mark(uTake1(X)) -> a__uTake1(mark(X))
1152.57/299.06	   mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4)
1152.57/299.06	   mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2)
1152.57/299.06	   mark(tt) -> tt
1152.57/299.06	   mark(0) -> 0
1152.57/299.06	   mark(s(X)) -> s(mark(X))
1152.57/299.06	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
1152.57/299.06	   mark(nil) -> nil
1152.57/299.06	   a__and(X1, X2) -> and(X1, X2)
1152.57/299.06	   a__isNatIList(X) -> isNatIList(X)
1152.57/299.06	   a__isNatList(X) -> isNatList(X)
1152.57/299.06	   a__isNat(X) -> isNat(X)
1152.57/299.06	   a__length(X) -> length(X)
1152.57/299.06	   a__zeros -> zeros
1152.57/299.06	   a__take(X1, X2) -> take(X1, X2)
1152.57/299.06	   a__uTake1(X) -> uTake1(X)
1152.57/299.06	   a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4)
1152.57/299.06	   a__uLength(X1, X2) -> uLength(X1, X2)
1152.57/299.06	
1152.57/299.06	S is empty.
1152.57/299.06	Rewrite Strategy: INNERMOST
1152.99/299.15	EOF