13.78/5.17	WORST_CASE(Omega(n^1), O(n^1))
13.78/5.19	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
13.78/5.19	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
13.78/5.19	
13.78/5.19	
13.78/5.19	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
13.78/5.19	
13.78/5.19	(0) CpxTRS
13.78/5.19	(1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
13.78/5.19	(2) CdtProblem
13.78/5.19	    (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
13.78/5.19	    (4) CdtProblem
13.78/5.19	    (5) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 39 ms]
13.78/5.19	    (6) CdtProblem
13.78/5.19	    (7) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
13.78/5.19	    (8) BOUNDS(1, 1)
13.78/5.19	(9) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
13.78/5.19	(10) TRS for Loop Detection
13.78/5.19	    (11) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
13.78/5.19	    (12) BEST
13.78/5.19	        (13) proven lower bound
13.78/5.19	            (14) LowerBoundPropagationProof [FINISHED, 0 ms]
13.78/5.19	            (15) BOUNDS(n^1, INF)
13.78/5.19	        (16) TRS for Loop Detection
13.78/5.19	
13.78/5.19	
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(0)
13.78/5.19	Obligation:
13.78/5.19	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
13.78/5.19	
13.78/5.19	
13.78/5.19	The TRS R consists of the following rules:
13.78/5.19	
13.78/5.19	   f(0, y) -> 0
13.78/5.19	   f(s(x), y) -> f(f(x, y), y)
13.78/5.19	
13.78/5.19	S is empty.
13.78/5.19	Rewrite Strategy: INNERMOST
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(1) CpxTrsToCdtProof (UPPER BOUND(ID))
13.78/5.19	Converted Cpx (relative) TRS to CDT
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(2)
13.78/5.19	Obligation:
13.78/5.19	Complexity Dependency Tuples Problem
13.78/5.19	
13.78/5.19	Rules:
13.78/5.19	   f(0, z0) -> 0
13.78/5.19	   f(s(z0), z1) -> f(f(z0, z1), z1)
13.78/5.19	Tuples:
13.78/5.19	   F(0, z0) -> c
13.78/5.19	   F(s(z0), z1) -> c1(F(f(z0, z1), z1), F(z0, z1))
13.78/5.19	S tuples:
13.78/5.19	   F(0, z0) -> c
13.78/5.19	   F(s(z0), z1) -> c1(F(f(z0, z1), z1), F(z0, z1))
13.78/5.19	K tuples:none
13.78/5.19	Defined Rule Symbols:   f_2
13.78/5.19	
13.78/5.19	Defined Pair Symbols:   F_2
13.78/5.19	
13.78/5.19	Compound Symbols:   c, c1_2
13.78/5.19	
13.78/5.19	
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
13.78/5.19	Removed 1 trailing nodes:
13.78/5.19	   F(0, z0) -> c
13.78/5.19	
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(4)
13.78/5.19	Obligation:
13.78/5.19	Complexity Dependency Tuples Problem
13.78/5.19	
13.78/5.19	Rules:
13.78/5.19	   f(0, z0) -> 0
13.78/5.19	   f(s(z0), z1) -> f(f(z0, z1), z1)
13.78/5.19	Tuples:
13.78/5.19	   F(s(z0), z1) -> c1(F(f(z0, z1), z1), F(z0, z1))
13.78/5.19	S tuples:
13.78/5.19	   F(s(z0), z1) -> c1(F(f(z0, z1), z1), F(z0, z1))
13.78/5.19	K tuples:none
13.78/5.19	Defined Rule Symbols:   f_2
13.78/5.19	
13.78/5.19	Defined Pair Symbols:   F_2
13.78/5.19	
13.78/5.19	Compound Symbols:   c1_2
13.78/5.19	
13.78/5.19	
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(5) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
13.78/5.19	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
13.78/5.19	   F(s(z0), z1) -> c1(F(f(z0, z1), z1), F(z0, z1))
13.78/5.19	We considered the (Usable) Rules:
13.78/5.19	   f(0, z0) -> 0
13.78/5.19	   f(s(z0), z1) -> f(f(z0, z1), z1)
13.78/5.19	And the Tuples:
13.78/5.19	   F(s(z0), z1) -> c1(F(f(z0, z1), z1), F(z0, z1))
13.78/5.19	The order we found is given by the following interpretation:
13.78/5.19	
13.78/5.19	Polynomial interpretation :
13.78/5.19	
13.78/5.19	   POL(0) = 0
13.78/5.19	   POL(F(x_1, x_2)) = x_1
13.78/5.19	   POL(c1(x_1, x_2)) = x_1 + x_2
13.78/5.19	   POL(f(x_1, x_2)) = 0
13.78/5.19	   POL(s(x_1)) = [1] + x_1
13.78/5.19	
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(6)
13.78/5.19	Obligation:
13.78/5.19	Complexity Dependency Tuples Problem
13.78/5.19	
13.78/5.19	Rules:
13.78/5.19	   f(0, z0) -> 0
13.78/5.19	   f(s(z0), z1) -> f(f(z0, z1), z1)
13.78/5.19	Tuples:
13.78/5.19	   F(s(z0), z1) -> c1(F(f(z0, z1), z1), F(z0, z1))
13.78/5.19	S tuples:none
13.78/5.19	K tuples:
13.78/5.19	   F(s(z0), z1) -> c1(F(f(z0, z1), z1), F(z0, z1))
13.78/5.19	Defined Rule Symbols:   f_2
13.78/5.19	
13.78/5.19	Defined Pair Symbols:   F_2
13.78/5.19	
13.78/5.19	Compound Symbols:   c1_2
13.78/5.19	
13.78/5.19	
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(7) SIsEmptyProof (BOTH BOUNDS(ID, ID))
13.78/5.19	The set S is empty
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(8)
13.78/5.19	BOUNDS(1, 1)
13.78/5.19	
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(9) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
13.78/5.19	Transformed a relative TRS into a decreasing-loop problem.
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(10)
13.78/5.19	Obligation:
13.78/5.19	Analyzing the following TRS for decreasing loops:
13.78/5.19	
13.78/5.19	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
13.78/5.19	
13.78/5.19	
13.78/5.19	The TRS R consists of the following rules:
13.78/5.19	
13.78/5.19	   f(0, y) -> 0
13.78/5.19	   f(s(x), y) -> f(f(x, y), y)
13.78/5.19	
13.78/5.19	S is empty.
13.78/5.19	Rewrite Strategy: INNERMOST
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(11) DecreasingLoopProof (LOWER BOUND(ID))
13.78/5.19	The following loop(s) give(s) rise to the lower bound Omega(n^1):
13.78/5.19	
13.78/5.19	The rewrite sequence
13.78/5.19	
13.78/5.19	f(s(x), y) ->^+ f(f(x, y), y)
13.78/5.19	
13.78/5.19	gives rise to a decreasing loop by considering the right hand sides subterm at position [0].
13.78/5.19	
13.78/5.19	The pumping substitution is [x / s(x)].
13.78/5.19	
13.78/5.19	The result substitution is [ ].
13.78/5.19	
13.78/5.19	
13.78/5.19	
13.78/5.19	
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(12)
13.78/5.19	Complex Obligation (BEST)
13.78/5.19	
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(13)
13.78/5.19	Obligation:
13.78/5.19	Proved the lower bound n^1 for the following obligation:
13.78/5.19	
13.78/5.19	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
13.78/5.19	
13.78/5.19	
13.78/5.19	The TRS R consists of the following rules:
13.78/5.19	
13.78/5.19	   f(0, y) -> 0
13.78/5.19	   f(s(x), y) -> f(f(x, y), y)
13.78/5.19	
13.78/5.19	S is empty.
13.78/5.19	Rewrite Strategy: INNERMOST
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(14) LowerBoundPropagationProof (FINISHED)
13.78/5.19	Propagated lower bound.
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(15)
13.78/5.19	BOUNDS(n^1, INF)
13.78/5.19	
13.78/5.19	----------------------------------------
13.78/5.19	
13.78/5.19	(16)
13.78/5.19	Obligation:
13.78/5.19	Analyzing the following TRS for decreasing loops:
13.78/5.19	
13.78/5.19	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
13.78/5.19	
13.78/5.19	
13.78/5.19	The TRS R consists of the following rules:
13.78/5.19	
13.78/5.19	   f(0, y) -> 0
13.78/5.19	   f(s(x), y) -> f(f(x, y), y)
13.78/5.19	
13.78/5.19	S is empty.
13.78/5.19	Rewrite Strategy: INNERMOST
14.36/5.47	EOF