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