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