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