16.78/5.24	WORST_CASE(Omega(n^1), O(n^1))
16.78/5.25	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
16.78/5.25	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
16.78/5.25	
16.78/5.25	
16.78/5.25	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
16.78/5.25	
16.78/5.25	(0) CpxTRS
16.78/5.25	(1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
16.78/5.25	(2) CpxTRS
16.78/5.25	    (3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
16.78/5.25	    (4) CdtProblem
16.78/5.25	    (5) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
16.78/5.25	    (6) CdtProblem
16.78/5.25	    (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 32 ms]
16.78/5.25	    (8) CdtProblem
16.78/5.25	    (9) CdtKnowledgeProof [FINISHED, 0 ms]
16.78/5.25	    (10) BOUNDS(1, 1)
16.78/5.25	(11) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
16.78/5.25	(12) TRS for Loop Detection
16.78/5.25	    (13) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
16.78/5.25	    (14) BEST
16.78/5.25	        (15) proven lower bound
16.78/5.25	            (16) LowerBoundPropagationProof [FINISHED, 0 ms]
16.78/5.25	            (17) BOUNDS(n^1, INF)
16.78/5.25	        (18) TRS for Loop Detection
16.78/5.25	
16.78/5.25	
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(0)
16.78/5.25	Obligation:
16.78/5.25	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
16.78/5.25	
16.78/5.25	
16.78/5.25	The TRS R consists of the following rules:
16.78/5.25	
16.78/5.25	   f(0, 1, x) -> f(s(x), x, x)
16.78/5.25	   f(x, y, s(z)) -> s(f(0, 1, z))
16.78/5.25	
16.78/5.25	S is empty.
16.78/5.25	Rewrite Strategy: FULL
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(1) RcToIrcProof (BOTH BOUNDS(ID, ID))
16.78/5.25	Converted rc-obligation to irc-obligation.
16.78/5.25	
16.78/5.25	As the TRS does not nest defined symbols, we have rc = irc.
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(2)
16.78/5.25	Obligation:
16.78/5.25	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
16.78/5.25	
16.78/5.25	
16.78/5.25	The TRS R consists of the following rules:
16.78/5.25	
16.78/5.25	   f(0, 1, x) -> f(s(x), x, x)
16.78/5.25	   f(x, y, s(z)) -> s(f(0, 1, z))
16.78/5.25	
16.78/5.25	S is empty.
16.78/5.25	Rewrite Strategy: INNERMOST
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(3) CpxTrsToCdtProof (UPPER BOUND(ID))
16.78/5.25	Converted Cpx (relative) TRS to CDT
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(4)
16.78/5.25	Obligation:
16.78/5.25	Complexity Dependency Tuples Problem
16.78/5.25	
16.78/5.25	Rules:
16.78/5.25	   f(0, 1, z0) -> f(s(z0), z0, z0)
16.78/5.25	   f(z0, z1, s(z2)) -> s(f(0, 1, z2))
16.78/5.25	Tuples:
16.78/5.25	   F(0, 1, z0) -> c(F(s(z0), z0, z0))
16.78/5.25	   F(z0, z1, s(z2)) -> c1(F(0, 1, z2))
16.78/5.25	S tuples:
16.78/5.25	   F(0, 1, z0) -> c(F(s(z0), z0, z0))
16.78/5.25	   F(z0, z1, s(z2)) -> c1(F(0, 1, z2))
16.78/5.25	K tuples:none
16.78/5.25	Defined Rule Symbols:   f_3
16.78/5.25	
16.78/5.25	Defined Pair Symbols:   F_3
16.78/5.25	
16.78/5.25	Compound Symbols:   c_1, c1_1
16.78/5.25	
16.78/5.25	
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(5) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
16.78/5.25	The following rules are not usable and were removed:
16.78/5.25	   f(0, 1, z0) -> f(s(z0), z0, z0)
16.78/5.25	   f(z0, z1, s(z2)) -> s(f(0, 1, z2))
16.78/5.25	
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(6)
16.78/5.25	Obligation:
16.78/5.25	Complexity Dependency Tuples Problem
16.78/5.25	
16.78/5.25	Rules:none
16.78/5.25	Tuples:
16.78/5.25	   F(0, 1, z0) -> c(F(s(z0), z0, z0))
16.78/5.25	   F(z0, z1, s(z2)) -> c1(F(0, 1, z2))
16.78/5.25	S tuples:
16.78/5.25	   F(0, 1, z0) -> c(F(s(z0), z0, z0))
16.78/5.25	   F(z0, z1, s(z2)) -> c1(F(0, 1, z2))
16.78/5.25	K tuples:none
16.78/5.25	Defined Rule Symbols:none
16.78/5.25	
16.78/5.25	Defined Pair Symbols:   F_3
16.78/5.25	
16.78/5.25	Compound Symbols:   c_1, c1_1
16.78/5.25	
16.78/5.25	
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
16.78/5.25	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
16.78/5.25	   F(z0, z1, s(z2)) -> c1(F(0, 1, z2))
16.78/5.25	We considered the (Usable) Rules:none
16.78/5.25	And the Tuples:
16.78/5.25	   F(0, 1, z0) -> c(F(s(z0), z0, z0))
16.78/5.25	   F(z0, z1, s(z2)) -> c1(F(0, 1, z2))
16.78/5.25	The order we found is given by the following interpretation:
16.78/5.25	
16.78/5.25	Polynomial interpretation :
16.78/5.25	
16.78/5.25	   POL(0) = [1]
16.78/5.25	   POL(1) = 0
16.78/5.25	   POL(F(x_1, x_2, x_3)) = x_3
16.78/5.25	   POL(c(x_1)) = x_1
16.78/5.25	   POL(c1(x_1)) = x_1
16.78/5.25	   POL(s(x_1)) = [1] + x_1
16.78/5.25	
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(8)
16.78/5.25	Obligation:
16.78/5.25	Complexity Dependency Tuples Problem
16.78/5.25	
16.78/5.25	Rules:none
16.78/5.25	Tuples:
16.78/5.25	   F(0, 1, z0) -> c(F(s(z0), z0, z0))
16.78/5.25	   F(z0, z1, s(z2)) -> c1(F(0, 1, z2))
16.78/5.25	S tuples:
16.78/5.25	   F(0, 1, z0) -> c(F(s(z0), z0, z0))
16.78/5.25	K tuples:
16.78/5.25	   F(z0, z1, s(z2)) -> c1(F(0, 1, z2))
16.78/5.25	Defined Rule Symbols:none
16.78/5.25	
16.78/5.25	Defined Pair Symbols:   F_3
16.78/5.25	
16.78/5.25	Compound Symbols:   c_1, c1_1
16.78/5.25	
16.78/5.25	
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(9) CdtKnowledgeProof (FINISHED)
16.78/5.25	The following tuples could be moved from S to K by knowledge propagation:
16.78/5.25	   F(0, 1, z0) -> c(F(s(z0), z0, z0))
16.78/5.25	   F(z0, z1, s(z2)) -> c1(F(0, 1, z2))
16.78/5.25	Now S is empty
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(10)
16.78/5.25	BOUNDS(1, 1)
16.78/5.25	
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(11) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
16.78/5.25	Transformed a relative TRS into a decreasing-loop problem.
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(12)
16.78/5.25	Obligation:
16.78/5.25	Analyzing the following TRS for decreasing loops:
16.78/5.25	
16.78/5.25	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
16.78/5.25	
16.78/5.25	
16.78/5.25	The TRS R consists of the following rules:
16.78/5.25	
16.78/5.25	   f(0, 1, x) -> f(s(x), x, x)
16.78/5.25	   f(x, y, s(z)) -> s(f(0, 1, z))
16.78/5.25	
16.78/5.25	S is empty.
16.78/5.25	Rewrite Strategy: FULL
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(13) DecreasingLoopProof (LOWER BOUND(ID))
16.78/5.25	The following loop(s) give(s) rise to the lower bound Omega(n^1):
16.78/5.25	
16.78/5.25	The rewrite sequence
16.78/5.25	
16.78/5.25	f(x, y, s(z)) ->^+ s(f(0, 1, z))
16.78/5.25	
16.78/5.25	gives rise to a decreasing loop by considering the right hand sides subterm at position [0].
16.78/5.25	
16.78/5.25	The pumping substitution is [z / s(z)].
16.78/5.25	
16.78/5.25	The result substitution is [x / 0, y / 1].
16.78/5.25	
16.78/5.25	
16.78/5.25	
16.78/5.25	
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(14)
16.78/5.25	Complex Obligation (BEST)
16.78/5.25	
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(15)
16.78/5.25	Obligation:
16.78/5.25	Proved the lower bound n^1 for the following obligation:
16.78/5.25	
16.78/5.25	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
16.78/5.25	
16.78/5.25	
16.78/5.25	The TRS R consists of the following rules:
16.78/5.25	
16.78/5.25	   f(0, 1, x) -> f(s(x), x, x)
16.78/5.25	   f(x, y, s(z)) -> s(f(0, 1, z))
16.78/5.25	
16.78/5.25	S is empty.
16.78/5.25	Rewrite Strategy: FULL
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(16) LowerBoundPropagationProof (FINISHED)
16.78/5.25	Propagated lower bound.
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(17)
16.78/5.25	BOUNDS(n^1, INF)
16.78/5.25	
16.78/5.25	----------------------------------------
16.78/5.25	
16.78/5.25	(18)
16.78/5.25	Obligation:
16.78/5.25	Analyzing the following TRS for decreasing loops:
16.78/5.25	
16.78/5.25	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
16.78/5.25	
16.78/5.25	
16.78/5.25	The TRS R consists of the following rules:
16.78/5.25	
16.78/5.25	   f(0, 1, x) -> f(s(x), x, x)
16.78/5.25	   f(x, y, s(z)) -> s(f(0, 1, z))
16.78/5.25	
16.78/5.25	S is empty.
16.78/5.25	Rewrite Strategy: FULL
16.93/5.41	EOF