318.97/291.92	WORST_CASE(Omega(n^1), ?)
318.97/291.93	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
318.97/291.93	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
318.97/291.93	
318.97/291.93	
318.97/291.93	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
318.97/291.93	
318.97/291.93	(0) CpxTRS
318.97/291.93	(1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
318.97/291.93	(2) TRS for Loop Detection
318.97/291.93	(3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
318.97/291.93	(4) BEST
318.97/291.93	    (5) proven lower bound
318.97/291.93	        (6) LowerBoundPropagationProof [FINISHED, 0 ms]
318.97/291.93	        (7) BOUNDS(n^1, INF)
318.97/291.93	    (8) TRS for Loop Detection
318.97/291.93	
318.97/291.93	
318.97/291.93	----------------------------------------
318.97/291.93	
318.97/291.93	(0)
318.97/291.93	Obligation:
318.97/291.93	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
318.97/291.93	
318.97/291.93	
318.97/291.93	The TRS R consists of the following rules:
318.97/291.93	
318.97/291.93	   p(s(N)) -> N
318.97/291.93	   +(N, 0) -> N
318.97/291.93	   +(s(N), s(M)) -> s(s(+(N, M)))
318.97/291.93	   *(N, 0) -> 0
318.97/291.93	   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
318.97/291.93	   gt(0, M) -> False
318.97/291.93	   gt(NzN, 0) -> u_4(is_NzNat(NzN))
318.97/291.93	   u_4(True) -> True
318.97/291.93	   is_NzNat(0) -> False
318.97/291.93	   is_NzNat(s(N)) -> True
318.97/291.93	   gt(s(N), s(M)) -> gt(N, M)
318.97/291.93	   lt(N, M) -> gt(M, N)
318.97/291.93	   d(0, N) -> N
318.97/291.93	   d(s(N), s(M)) -> d(N, M)
318.97/291.93	   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
318.97/291.93	   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
318.97/291.93	   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
318.97/291.93	   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
318.97/291.93	   u_01(True) -> s(0)
318.97/291.93	   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
318.97/291.93	   u_21(True, NzM, N) -> u_2(gt(NzM, N))
318.97/291.93	   u_2(True) -> 0
318.97/291.93	   gcd(0, N) -> 0
318.97/291.93	   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
318.97/291.93	   u_02(True, NzM) -> NzM
318.97/291.93	   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
318.97/291.93	   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
318.97/291.93	   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)
318.97/291.93	
318.97/291.93	S is empty.
318.97/291.93	Rewrite Strategy: FULL
318.97/291.93	----------------------------------------
318.97/291.93	
318.97/291.93	(1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
318.97/291.93	Transformed a relative TRS into a decreasing-loop problem.
318.97/291.93	----------------------------------------
318.97/291.93	
318.97/291.93	(2)
318.97/291.93	Obligation:
318.97/291.93	Analyzing the following TRS for decreasing loops:
318.97/291.93	
318.97/291.93	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
318.97/291.93	
318.97/291.93	
318.97/291.93	The TRS R consists of the following rules:
318.97/291.93	
318.97/291.93	   p(s(N)) -> N
318.97/291.93	   +(N, 0) -> N
318.97/291.93	   +(s(N), s(M)) -> s(s(+(N, M)))
318.97/291.93	   *(N, 0) -> 0
318.97/291.93	   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
318.97/291.93	   gt(0, M) -> False
318.97/291.93	   gt(NzN, 0) -> u_4(is_NzNat(NzN))
318.97/291.93	   u_4(True) -> True
318.97/291.93	   is_NzNat(0) -> False
318.97/291.93	   is_NzNat(s(N)) -> True
318.97/291.93	   gt(s(N), s(M)) -> gt(N, M)
318.97/291.93	   lt(N, M) -> gt(M, N)
318.97/291.93	   d(0, N) -> N
318.97/291.93	   d(s(N), s(M)) -> d(N, M)
318.97/291.93	   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
318.97/291.93	   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
318.97/291.93	   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
318.97/291.93	   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
318.97/291.93	   u_01(True) -> s(0)
318.97/291.93	   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
318.97/291.93	   u_21(True, NzM, N) -> u_2(gt(NzM, N))
318.97/291.93	   u_2(True) -> 0
318.97/291.93	   gcd(0, N) -> 0
318.97/291.93	   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
318.97/291.93	   u_02(True, NzM) -> NzM
318.97/291.93	   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
318.97/291.93	   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
318.97/291.93	   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)
318.97/291.93	
318.97/291.93	S is empty.
318.97/291.93	Rewrite Strategy: FULL
318.97/291.93	----------------------------------------
318.97/291.93	
318.97/291.93	(3) DecreasingLoopProof (LOWER BOUND(ID))
318.97/291.93	The following loop(s) give(s) rise to the lower bound Omega(n^1):
318.97/291.93	
318.97/291.93	The rewrite sequence
318.97/291.93	
318.97/291.93	gt(s(N), s(M)) ->^+ gt(N, M)
318.97/291.93	
318.97/291.93	gives rise to a decreasing loop by considering the right hand sides subterm at position [].
318.97/291.93	
318.97/291.93	The pumping substitution is [N / s(N), M / s(M)].
318.97/291.93	
318.97/291.93	The result substitution is [ ].
318.97/291.93	
318.97/291.93	
318.97/291.93	
318.97/291.93	
318.97/291.93	----------------------------------------
318.97/291.93	
318.97/291.93	(4)
318.97/291.93	Complex Obligation (BEST)
318.97/291.93	
318.97/291.93	----------------------------------------
318.97/291.93	
318.97/291.93	(5)
318.97/291.93	Obligation:
318.97/291.93	Proved the lower bound n^1 for the following obligation:
318.97/291.93	
318.97/291.93	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
318.97/291.93	
318.97/291.93	
318.97/291.93	The TRS R consists of the following rules:
318.97/291.93	
318.97/291.93	   p(s(N)) -> N
318.97/291.93	   +(N, 0) -> N
318.97/291.93	   +(s(N), s(M)) -> s(s(+(N, M)))
318.97/291.93	   *(N, 0) -> 0
318.97/291.93	   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
318.97/291.93	   gt(0, M) -> False
318.97/291.93	   gt(NzN, 0) -> u_4(is_NzNat(NzN))
318.97/291.93	   u_4(True) -> True
318.97/291.93	   is_NzNat(0) -> False
318.97/291.93	   is_NzNat(s(N)) -> True
318.97/291.93	   gt(s(N), s(M)) -> gt(N, M)
318.97/291.93	   lt(N, M) -> gt(M, N)
318.97/291.93	   d(0, N) -> N
318.97/291.93	   d(s(N), s(M)) -> d(N, M)
318.97/291.93	   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
318.97/291.93	   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
318.97/291.93	   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
318.97/291.93	   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
318.97/291.93	   u_01(True) -> s(0)
318.97/291.93	   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
318.97/291.93	   u_21(True, NzM, N) -> u_2(gt(NzM, N))
318.97/291.93	   u_2(True) -> 0
318.97/291.93	   gcd(0, N) -> 0
318.97/291.93	   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
318.97/291.93	   u_02(True, NzM) -> NzM
318.97/291.93	   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
318.97/291.93	   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
318.97/291.93	   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)
318.97/291.93	
318.97/291.93	S is empty.
318.97/291.93	Rewrite Strategy: FULL
318.97/291.93	----------------------------------------
318.97/291.93	
318.97/291.93	(6) LowerBoundPropagationProof (FINISHED)
318.97/291.93	Propagated lower bound.
318.97/291.93	----------------------------------------
318.97/291.93	
318.97/291.93	(7)
318.97/291.93	BOUNDS(n^1, INF)
318.97/291.93	
318.97/291.93	----------------------------------------
318.97/291.93	
318.97/291.93	(8)
318.97/291.93	Obligation:
318.97/291.93	Analyzing the following TRS for decreasing loops:
318.97/291.93	
318.97/291.93	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
318.97/291.93	
318.97/291.93	
318.97/291.93	The TRS R consists of the following rules:
318.97/291.93	
318.97/291.93	   p(s(N)) -> N
318.97/291.93	   +(N, 0) -> N
318.97/291.93	   +(s(N), s(M)) -> s(s(+(N, M)))
318.97/291.93	   *(N, 0) -> 0
318.97/291.93	   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
318.97/291.93	   gt(0, M) -> False
318.97/291.93	   gt(NzN, 0) -> u_4(is_NzNat(NzN))
318.97/291.93	   u_4(True) -> True
318.97/291.93	   is_NzNat(0) -> False
318.97/291.93	   is_NzNat(s(N)) -> True
318.97/291.93	   gt(s(N), s(M)) -> gt(N, M)
318.97/291.93	   lt(N, M) -> gt(M, N)
318.97/291.93	   d(0, N) -> N
318.97/291.93	   d(s(N), s(M)) -> d(N, M)
318.97/291.93	   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
318.97/291.93	   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
318.97/291.93	   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
318.97/291.93	   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
318.97/291.93	   u_01(True) -> s(0)
318.97/291.93	   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
318.97/291.93	   u_21(True, NzM, N) -> u_2(gt(NzM, N))
318.97/291.93	   u_2(True) -> 0
318.97/291.93	   gcd(0, N) -> 0
318.97/291.93	   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
318.97/291.93	   u_02(True, NzM) -> NzM
318.97/291.93	   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
318.97/291.93	   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
318.97/291.93	   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)
318.97/291.93	
318.97/291.93	S is empty.
318.97/291.93	Rewrite Strategy: FULL
319.07/291.95	EOF