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