12.76/4.33	WORST_CASE(Omega(n^1), O(n^1))
12.76/4.33	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
12.76/4.33	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
12.76/4.33	
12.76/4.33	
12.76/4.33	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
12.76/4.33	
12.76/4.33	(0) CpxTRS
12.76/4.33	(1) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
12.76/4.33	(2) CpxTRS
12.76/4.33	    (3) CpxTrsMatchBoundsTAProof [FINISHED, 0 ms]
12.76/4.33	    (4) BOUNDS(1, n^1)
12.76/4.33	(5) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
12.76/4.33	(6) TRS for Loop Detection
12.76/4.33	    (7) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
12.76/4.33	    (8) BEST
12.76/4.33	        (9) proven lower bound
12.76/4.33	            (10) LowerBoundPropagationProof [FINISHED, 0 ms]
12.76/4.33	            (11) BOUNDS(n^1, INF)
12.76/4.33	        (12) TRS for Loop Detection
12.76/4.33	
12.76/4.33	
12.76/4.33	----------------------------------------
12.76/4.33	
12.76/4.33	(0)
12.76/4.33	Obligation:
12.76/4.33	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
12.76/4.33	
12.76/4.33	
12.76/4.33	The TRS R consists of the following rules:
12.76/4.33	
12.76/4.33	   f(c(s(x), y)) -> f(c(x, s(y)))
12.76/4.33	   g(c(x, s(y))) -> g(c(s(x), y))
12.76/4.33	
12.76/4.33	S is empty.
12.76/4.33	Rewrite Strategy: INNERMOST
12.76/4.33	----------------------------------------
12.76/4.33	
12.76/4.33	(1) RelTrsToTrsProof (UPPER BOUND(ID))
12.76/4.33	transformed relative TRS to TRS
12.76/4.33	----------------------------------------
12.76/4.33	
12.76/4.33	(2)
12.76/4.33	Obligation:
12.76/4.33	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
12.76/4.33	
12.76/4.33	
12.76/4.33	The TRS R consists of the following rules:
12.76/4.33	
12.76/4.33	   f(c(s(x), y)) -> f(c(x, s(y)))
12.76/4.33	   g(c(x, s(y))) -> g(c(s(x), y))
12.76/4.33	
12.76/4.33	S is empty.
12.76/4.33	Rewrite Strategy: INNERMOST
12.76/4.33	----------------------------------------
12.76/4.33	
12.76/4.33	(3) CpxTrsMatchBoundsTAProof (FINISHED)
12.76/4.33	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 1. 
12.76/4.33	
12.76/4.33	The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 
12.76/4.33	final states : [1, 2]
12.76/4.33	transitions: 
12.76/4.33	c0(0, 0) -> 0
12.76/4.33	s0(0) -> 0
12.76/4.33	f0(0) -> 1
12.76/4.33	g0(0) -> 2
12.76/4.33	s1(0) -> 4
12.76/4.33	c1(0, 4) -> 3
12.76/4.33	f1(3) -> 1
12.76/4.33	s1(0) -> 6
12.76/4.33	c1(6, 0) -> 5
12.76/4.33	g1(5) -> 2
12.76/4.33	s1(4) -> 4
12.76/4.33	s1(6) -> 6
12.76/4.33	
12.76/4.33	----------------------------------------
12.76/4.33	
12.76/4.33	(4)
12.76/4.33	BOUNDS(1, n^1)
12.76/4.33	
12.76/4.33	----------------------------------------
12.76/4.33	
12.76/4.33	(5) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
12.76/4.33	Transformed a relative TRS into a decreasing-loop problem.
12.76/4.33	----------------------------------------
12.76/4.33	
12.76/4.33	(6)
12.76/4.33	Obligation:
12.76/4.33	Analyzing the following TRS for decreasing loops:
12.76/4.33	
12.76/4.33	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
12.76/4.33	
12.76/4.33	
12.76/4.33	The TRS R consists of the following rules:
12.76/4.33	
12.76/4.33	   f(c(s(x), y)) -> f(c(x, s(y)))
12.76/4.33	   g(c(x, s(y))) -> g(c(s(x), y))
12.76/4.33	
12.76/4.33	S is empty.
12.76/4.33	Rewrite Strategy: INNERMOST
12.76/4.33	----------------------------------------
12.76/4.33	
12.76/4.33	(7) DecreasingLoopProof (LOWER BOUND(ID))
12.76/4.33	The following loop(s) give(s) rise to the lower bound Omega(n^1):
12.76/4.33	
12.76/4.33	The rewrite sequence
12.76/4.33	
12.76/4.33	g(c(x, s(y))) ->^+ g(c(s(x), y))
12.76/4.33	
12.76/4.33	gives rise to a decreasing loop by considering the right hand sides subterm at position [].
12.76/4.33	
12.76/4.33	The pumping substitution is [y / s(y)].
12.76/4.33	
12.76/4.33	The result substitution is [x / s(x)].
12.76/4.33	
12.76/4.33	
12.76/4.33	
12.76/4.33	
12.76/4.33	----------------------------------------
12.76/4.33	
12.76/4.33	(8)
12.76/4.33	Complex Obligation (BEST)
12.76/4.33	
12.76/4.33	----------------------------------------
12.76/4.33	
12.76/4.33	(9)
12.76/4.33	Obligation:
12.76/4.33	Proved the lower bound n^1 for the following obligation:
12.76/4.33	
12.76/4.33	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
12.76/4.33	
12.76/4.33	
12.76/4.33	The TRS R consists of the following rules:
12.76/4.33	
12.76/4.33	   f(c(s(x), y)) -> f(c(x, s(y)))
12.76/4.33	   g(c(x, s(y))) -> g(c(s(x), y))
12.76/4.33	
12.76/4.33	S is empty.
12.76/4.33	Rewrite Strategy: INNERMOST
12.76/4.33	----------------------------------------
12.76/4.33	
12.76/4.33	(10) LowerBoundPropagationProof (FINISHED)
12.76/4.33	Propagated lower bound.
12.76/4.33	----------------------------------------
12.76/4.33	
12.76/4.33	(11)
12.76/4.33	BOUNDS(n^1, INF)
12.76/4.33	
12.76/4.33	----------------------------------------
12.76/4.33	
12.76/4.33	(12)
12.76/4.33	Obligation:
12.76/4.33	Analyzing the following TRS for decreasing loops:
12.76/4.33	
12.76/4.33	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
12.76/4.33	
12.76/4.33	
12.76/4.33	The TRS R consists of the following rules:
12.76/4.33	
12.76/4.33	   f(c(s(x), y)) -> f(c(x, s(y)))
12.76/4.33	   g(c(x, s(y))) -> g(c(s(x), y))
12.76/4.33	
12.76/4.33	S is empty.
12.76/4.33	Rewrite Strategy: INNERMOST
13.08/4.38	EOF