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