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