20.21/6.56	WORST_CASE(Omega(n^1), O(n^1))
20.53/9.95	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
20.53/9.95	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
20.53/9.95	
20.53/9.95	
20.53/9.95	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
20.53/9.95	
20.53/9.95	(0) CpxTRS
20.53/9.95	(1) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
20.53/9.95	(2) CpxTRS
20.53/9.95	    (3) CpxTrsMatchBoundsProof [FINISHED, 0 ms]
20.53/9.95	    (4) BOUNDS(1, n^1)
20.53/9.95	(5) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
20.53/9.95	(6) TRS for Loop Detection
20.53/9.95	    (7) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
20.53/9.95	    (8) BEST
20.53/9.95	        (9) proven lower bound
20.53/9.95	            (10) LowerBoundPropagationProof [FINISHED, 0 ms]
20.53/9.95	            (11) BOUNDS(n^1, INF)
20.53/9.95	        (12) TRS for Loop Detection
20.53/9.95	
20.53/9.95	
20.53/9.95	----------------------------------------
20.53/9.95	
20.53/9.95	(0)
20.53/9.95	Obligation:
20.53/9.95	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
20.53/9.95	
20.53/9.95	
20.53/9.95	The TRS R consists of the following rules:
20.53/9.95	
20.53/9.95	   odd(S(x)) -> even(x)
20.53/9.95	   even(S(x)) -> odd(x)
20.53/9.95	   odd(0) -> 0
20.53/9.95	   even(0) -> S(0)
20.53/9.95	
20.53/9.95	S is empty.
20.53/9.95	Rewrite Strategy: INNERMOST
20.55/10.03	----------------------------------------
20.55/10.03	
20.55/10.03	(1) RelTrsToTrsProof (UPPER BOUND(ID))
20.55/10.03	transformed relative TRS to TRS
20.55/10.03	----------------------------------------
20.55/10.03	
20.55/10.03	(2)
20.55/10.03	Obligation:
20.55/10.03	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
20.55/10.03	
20.55/10.03	
20.55/10.03	The TRS R consists of the following rules:
20.55/10.03	
20.55/10.03	   odd(S(x)) -> even(x)
20.55/10.03	   even(S(x)) -> odd(x)
20.55/10.03	   odd(0) -> 0
20.55/10.03	   even(0) -> S(0)
20.55/10.03	
20.55/10.03	S is empty.
20.55/10.03	Rewrite Strategy: INNERMOST
20.55/10.03	----------------------------------------
20.55/10.03	
20.55/10.03	(3) CpxTrsMatchBoundsProof (FINISHED)
20.55/10.03	A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1. 
20.55/10.03	The certificate found is represented by the following graph.
20.55/10.03	
20.55/10.03	"[1, 2, 3]
20.55/10.03	{(1,2,[odd_1|0, even_1|0, even_1|1, 0|1, odd_1|1]), (1,3,[S_1|1]), (2,2,[S_1|0, 0|0]), (3,2,[0|1])}"
20.55/10.03	----------------------------------------
20.55/10.03	
20.55/10.03	(4)
20.55/10.03	BOUNDS(1, n^1)
20.55/10.03	
20.55/10.03	----------------------------------------
20.55/10.03	
20.55/10.03	(5) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
20.55/10.03	Transformed a relative TRS into a decreasing-loop problem.
20.55/10.03	----------------------------------------
20.55/10.03	
20.55/10.03	(6)
20.55/10.03	Obligation:
20.55/10.03	Analyzing the following TRS for decreasing loops:
20.55/10.03	
20.55/10.03	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
20.55/10.03	
20.55/10.03	
20.55/10.03	The TRS R consists of the following rules:
20.55/10.03	
20.55/10.03	   odd(S(x)) -> even(x)
20.55/10.03	   even(S(x)) -> odd(x)
20.55/10.03	   odd(0) -> 0
20.55/10.03	   even(0) -> S(0)
20.55/10.03	
20.55/10.03	S is empty.
20.55/10.03	Rewrite Strategy: INNERMOST
20.55/10.03	----------------------------------------
20.55/10.03	
20.55/10.03	(7) DecreasingLoopProof (LOWER BOUND(ID))
20.55/10.03	The following loop(s) give(s) rise to the lower bound Omega(n^1):
20.55/10.03	
20.55/10.03	The rewrite sequence
20.55/10.03	
20.55/10.03	even(S(S(x1_0))) ->^+ even(x1_0)
20.55/10.03	
20.55/10.03	gives rise to a decreasing loop by considering the right hand sides subterm at position [].
20.55/10.03	
20.55/10.03	The pumping substitution is [x1_0 / S(S(x1_0))].
20.55/10.03	
20.55/10.03	The result substitution is [ ].
20.55/10.03	
20.55/10.03	
20.55/10.03	
20.55/10.03	
20.55/10.03	----------------------------------------
20.55/10.03	
20.55/10.03	(8)
20.55/10.03	Complex Obligation (BEST)
20.55/10.03	
20.55/10.03	----------------------------------------
20.55/10.03	
20.55/10.03	(9)
20.55/10.03	Obligation:
20.55/10.03	Proved the lower bound n^1 for the following obligation:
20.55/10.03	
20.55/10.03	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
20.55/10.03	
20.55/10.03	
20.55/10.03	The TRS R consists of the following rules:
20.55/10.03	
20.55/10.03	   odd(S(x)) -> even(x)
20.55/10.03	   even(S(x)) -> odd(x)
20.55/10.03	   odd(0) -> 0
20.55/10.03	   even(0) -> S(0)
20.55/10.03	
20.55/10.03	S is empty.
20.55/10.03	Rewrite Strategy: INNERMOST
20.55/10.03	----------------------------------------
20.55/10.03	
20.55/10.03	(10) LowerBoundPropagationProof (FINISHED)
20.55/10.03	Propagated lower bound.
20.55/10.03	----------------------------------------
20.55/10.03	
20.55/10.03	(11)
20.55/10.03	BOUNDS(n^1, INF)
20.55/10.03	
20.55/10.03	----------------------------------------
20.55/10.03	
20.55/10.03	(12)
20.55/10.03	Obligation:
20.55/10.03	Analyzing the following TRS for decreasing loops:
20.55/10.03	
20.55/10.03	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
20.55/10.03	
20.55/10.03	
20.55/10.03	The TRS R consists of the following rules:
20.55/10.03	
20.55/10.03	   odd(S(x)) -> even(x)
20.55/10.03	   even(S(x)) -> odd(x)
20.55/10.03	   odd(0) -> 0
20.55/10.03	   even(0) -> S(0)
20.55/10.03	
20.55/10.03	S is empty.
20.55/10.03	Rewrite Strategy: INNERMOST
20.58/10.13	EOF