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