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