3.73/1.67	WORST_CASE(Omega(n^1), O(n^1))
3.73/1.68	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.73/1.68	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.73/1.68	
3.73/1.68	
3.73/1.68	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
3.73/1.68	
3.73/1.68	(0) CpxTRS
3.73/1.68	(1) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
3.73/1.68	(2) CpxTRS
3.73/1.68	    (3) CpxTrsMatchBoundsTAProof [FINISHED, 67 ms]
3.73/1.68	    (4) BOUNDS(1, n^1)
3.73/1.68	(5) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
3.73/1.68	(6) TRS for Loop Detection
3.73/1.68	    (7) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
3.73/1.68	    (8) BEST
3.73/1.68	        (9) proven lower bound
3.73/1.68	            (10) LowerBoundPropagationProof [FINISHED, 0 ms]
3.73/1.68	            (11) BOUNDS(n^1, INF)
3.73/1.68	        (12) TRS for Loop Detection
3.73/1.68	
3.73/1.68	
3.73/1.68	----------------------------------------
3.73/1.68	
3.73/1.68	(0)
3.73/1.68	Obligation:
3.73/1.68	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
3.73/1.68	
3.73/1.68	
3.73/1.68	The TRS R consists of the following rules:
3.73/1.68	
3.73/1.68	   f(a, a) -> f(a, b)
3.73/1.68	   f(a, b) -> f(s(a), c)
3.73/1.68	   f(s(X), c) -> f(X, c)
3.73/1.68	   f(c, c) -> f(a, a)
3.73/1.68	
3.73/1.68	S is empty.
3.73/1.68	Rewrite Strategy: FULL
3.73/1.68	----------------------------------------
3.73/1.68	
3.73/1.68	(1) RelTrsToTrsProof (UPPER BOUND(ID))
3.73/1.68	transformed relative TRS to TRS
3.73/1.68	----------------------------------------
3.73/1.68	
3.73/1.68	(2)
3.73/1.68	Obligation:
3.73/1.68	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
3.73/1.68	
3.73/1.68	
3.73/1.68	The TRS R consists of the following rules:
3.73/1.68	
3.73/1.68	   f(a, a) -> f(a, b)
3.73/1.68	   f(a, b) -> f(s(a), c)
3.73/1.68	   f(s(X), c) -> f(X, c)
3.73/1.68	   f(c, c) -> f(a, a)
3.73/1.68	
3.73/1.68	S is empty.
3.73/1.68	Rewrite Strategy: FULL
3.73/1.68	----------------------------------------
3.73/1.68	
3.73/1.68	(3) CpxTrsMatchBoundsTAProof (FINISHED)
3.73/1.68	A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 4. 
3.73/1.68	
3.73/1.68	The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 
3.73/1.68	final states : [1]
3.73/1.68	transitions: 
3.73/1.68	a0() -> 0
3.73/1.68	b0() -> 0
3.73/1.68	s0(0) -> 0
3.73/1.68	c0() -> 0
3.73/1.68	f0(0, 0) -> 1
3.73/1.68	a1() -> 2
3.73/1.68	b1() -> 3
3.73/1.68	f1(2, 3) -> 1
3.73/1.68	a1() -> 5
3.73/1.68	s1(5) -> 4
3.73/1.68	c1() -> 6
3.73/1.68	f1(4, 6) -> 1
3.73/1.68	f1(0, 6) -> 1
3.73/1.68	a1() -> 7
3.73/1.68	f1(2, 7) -> 1
3.73/1.68	a2() -> 8
3.73/1.68	b2() -> 9
3.73/1.68	f2(8, 9) -> 1
3.73/1.68	a2() -> 11
3.73/1.68	s2(11) -> 10
3.73/1.68	c2() -> 12
3.73/1.68	f2(10, 12) -> 1
3.73/1.68	f2(5, 12) -> 1
3.73/1.68	a3() -> 14
3.73/1.68	s3(14) -> 13
3.73/1.68	c3() -> 15
3.73/1.68	f3(13, 15) -> 1
3.73/1.68	f3(11, 15) -> 1
3.73/1.68	c4() -> 16
3.73/1.68	f4(14, 16) -> 1
3.73/1.68	
3.73/1.68	----------------------------------------
3.73/1.68	
3.73/1.68	(4)
3.73/1.68	BOUNDS(1, n^1)
3.73/1.68	
3.73/1.68	----------------------------------------
3.73/1.68	
3.73/1.68	(5) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
3.73/1.68	Transformed a relative TRS into a decreasing-loop problem.
3.73/1.68	----------------------------------------
3.73/1.68	
3.73/1.68	(6)
3.73/1.68	Obligation:
3.73/1.68	Analyzing the following TRS for decreasing loops:
3.73/1.68	
3.73/1.68	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
3.73/1.68	
3.73/1.68	
3.73/1.68	The TRS R consists of the following rules:
3.73/1.68	
3.73/1.68	   f(a, a) -> f(a, b)
3.73/1.68	   f(a, b) -> f(s(a), c)
3.73/1.68	   f(s(X), c) -> f(X, c)
3.73/1.68	   f(c, c) -> f(a, a)
3.73/1.68	
3.73/1.68	S is empty.
3.73/1.68	Rewrite Strategy: FULL
3.73/1.68	----------------------------------------
3.73/1.68	
3.73/1.68	(7) DecreasingLoopProof (LOWER BOUND(ID))
3.73/1.68	The following loop(s) give(s) rise to the lower bound Omega(n^1):
3.73/1.68	
3.73/1.68	The rewrite sequence
3.73/1.68	
3.73/1.68	f(s(X), c) ->^+ f(X, c)
3.73/1.68	
3.73/1.68	gives rise to a decreasing loop by considering the right hand sides subterm at position [].
3.73/1.68	
3.73/1.68	The pumping substitution is [X / s(X)].
3.73/1.68	
3.73/1.68	The result substitution is [ ].
3.73/1.68	
3.73/1.68	
3.73/1.68	
3.73/1.68	
3.73/1.68	----------------------------------------
3.73/1.68	
3.73/1.68	(8)
3.73/1.68	Complex Obligation (BEST)
3.73/1.68	
3.73/1.68	----------------------------------------
3.73/1.68	
3.73/1.68	(9)
3.73/1.68	Obligation:
3.73/1.68	Proved the lower bound n^1 for the following obligation:
3.73/1.68	
3.73/1.68	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
3.73/1.68	
3.73/1.68	
3.73/1.68	The TRS R consists of the following rules:
3.73/1.68	
3.73/1.68	   f(a, a) -> f(a, b)
3.73/1.68	   f(a, b) -> f(s(a), c)
3.73/1.68	   f(s(X), c) -> f(X, c)
3.73/1.68	   f(c, c) -> f(a, a)
3.73/1.68	
3.73/1.68	S is empty.
3.73/1.68	Rewrite Strategy: FULL
3.73/1.68	----------------------------------------
3.73/1.68	
3.73/1.68	(10) LowerBoundPropagationProof (FINISHED)
3.73/1.68	Propagated lower bound.
3.73/1.68	----------------------------------------
3.73/1.68	
3.73/1.68	(11)
3.73/1.68	BOUNDS(n^1, INF)
3.73/1.68	
3.73/1.68	----------------------------------------
3.73/1.68	
3.73/1.68	(12)
3.73/1.68	Obligation:
3.73/1.68	Analyzing the following TRS for decreasing loops:
3.73/1.68	
3.73/1.68	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
3.73/1.68	
3.73/1.68	
3.73/1.68	The TRS R consists of the following rules:
3.73/1.68	
3.73/1.68	   f(a, a) -> f(a, b)
3.73/1.68	   f(a, b) -> f(s(a), c)
3.73/1.68	   f(s(X), c) -> f(X, c)
3.73/1.68	   f(c, c) -> f(a, a)
3.73/1.68	
3.73/1.68	S is empty.
3.73/1.68	Rewrite Strategy: FULL
3.97/1.72	EOF