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