39.89/11.60	WORST_CASE(Omega(n^1), O(n^1))
39.89/11.61	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
39.89/11.61	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
39.89/11.61	
39.89/11.61	
39.89/11.61	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
39.89/11.61	
39.89/11.61	(0) CpxTRS
39.89/11.61	(1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
39.89/11.61	(2) CpxTRS
39.89/11.61	    (3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
39.89/11.61	    (4) CdtProblem
39.89/11.61	    (5) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
39.89/11.61	    (6) CdtProblem
39.89/11.61	    (7) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
39.89/11.61	    (8) CdtProblem
39.89/11.61	    (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
39.89/11.61	    (10) CdtProblem
39.89/11.61	    (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 49 ms]
39.89/11.61	    (12) CdtProblem
39.89/11.61	    (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 6 ms]
39.89/11.61	    (14) CdtProblem
39.89/11.61	    (15) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
39.89/11.61	    (16) BOUNDS(1, 1)
39.89/11.61	(17) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
39.89/11.61	(18) TRS for Loop Detection
39.89/11.61	    (19) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
39.89/11.61	    (20) BEST
39.89/11.61	        (21) proven lower bound
39.89/11.61	            (22) LowerBoundPropagationProof [FINISHED, 1 ms]
39.89/11.61	            (23) BOUNDS(n^1, INF)
39.89/11.61	        (24) TRS for Loop Detection
39.89/11.61	
39.89/11.61	
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(0)
39.89/11.61	Obligation:
39.89/11.61	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
39.89/11.61	
39.89/11.61	
39.89/11.61	The TRS R consists of the following rules:
39.89/11.61	
39.89/11.61	   perfectp(0) -> false
39.89/11.61	   perfectp(s(x)) -> f(x, s(0), s(x), s(x))
39.89/11.61	   f(0, y, 0, u) -> true
39.89/11.61	   f(0, y, s(z), u) -> false
39.89/11.61	   f(s(x), 0, z, u) -> f(x, u, minus(z, s(x)), u)
39.89/11.61	   f(s(x), s(y), z, u) -> if(le(x, y), f(s(x), minus(y, x), z, u), f(x, u, z, u))
39.89/11.61	
39.89/11.61	S is empty.
39.89/11.61	Rewrite Strategy: FULL
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(1) RcToIrcProof (BOTH BOUNDS(ID, ID))
39.89/11.61	Converted rc-obligation to irc-obligation.
39.89/11.61	
39.89/11.61	As the TRS does not nest defined symbols, we have rc = irc.
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(2)
39.89/11.61	Obligation:
39.89/11.61	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
39.89/11.61	
39.89/11.61	
39.89/11.61	The TRS R consists of the following rules:
39.89/11.61	
39.89/11.61	   perfectp(0) -> false
39.89/11.61	   perfectp(s(x)) -> f(x, s(0), s(x), s(x))
39.89/11.61	   f(0, y, 0, u) -> true
39.89/11.61	   f(0, y, s(z), u) -> false
39.89/11.61	   f(s(x), 0, z, u) -> f(x, u, minus(z, s(x)), u)
39.89/11.61	   f(s(x), s(y), z, u) -> if(le(x, y), f(s(x), minus(y, x), z, u), f(x, u, z, u))
39.89/11.61	
39.89/11.61	S is empty.
39.89/11.61	Rewrite Strategy: INNERMOST
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(3) CpxTrsToCdtProof (UPPER BOUND(ID))
39.89/11.61	Converted Cpx (relative) TRS to CDT
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(4)
39.89/11.61	Obligation:
39.89/11.61	Complexity Dependency Tuples Problem
39.89/11.61	
39.89/11.61	Rules:
39.89/11.61	   perfectp(0) -> false
39.89/11.61	   perfectp(s(z0)) -> f(z0, s(0), s(z0), s(z0))
39.89/11.61	   f(0, z0, 0, z1) -> true
39.89/11.61	   f(0, z0, s(z1), z2) -> false
39.89/11.61	   f(s(z0), 0, z1, z2) -> f(z0, z2, minus(z1, s(z0)), z2)
39.89/11.61	   f(s(z0), s(z1), z2, z3) -> if(le(z0, z1), f(s(z0), minus(z1, z0), z2, z3), f(z0, z3, z2, z3))
39.89/11.61	Tuples:
39.89/11.61	   PERFECTP(0) -> c
39.89/11.61	   PERFECTP(s(z0)) -> c1(F(z0, s(0), s(z0), s(z0)))
39.89/11.61	   F(0, z0, 0, z1) -> c2
39.89/11.61	   F(0, z0, s(z1), z2) -> c3
39.89/11.61	   F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2))
39.89/11.61	   F(s(z0), s(z1), z2, z3) -> c5(F(s(z0), minus(z1, z0), z2, z3), F(z0, z3, z2, z3))
39.89/11.61	S tuples:
39.89/11.61	   PERFECTP(0) -> c
39.89/11.61	   PERFECTP(s(z0)) -> c1(F(z0, s(0), s(z0), s(z0)))
39.89/11.61	   F(0, z0, 0, z1) -> c2
39.89/11.61	   F(0, z0, s(z1), z2) -> c3
39.89/11.61	   F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2))
39.89/11.61	   F(s(z0), s(z1), z2, z3) -> c5(F(s(z0), minus(z1, z0), z2, z3), F(z0, z3, z2, z3))
39.89/11.61	K tuples:none
39.89/11.61	Defined Rule Symbols:   perfectp_1, f_4
39.89/11.61	
39.89/11.61	Defined Pair Symbols:   PERFECTP_1, F_4
39.89/11.61	
39.89/11.61	Compound Symbols:   c, c1_1, c2, c3, c4_1, c5_2
39.89/11.61	
39.89/11.61	
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(5) CdtLeafRemovalProof (ComplexityIfPolyImplication)
39.89/11.61	Removed 1 leading nodes:
39.89/11.61	   PERFECTP(s(z0)) -> c1(F(z0, s(0), s(z0), s(z0)))
39.89/11.61	Removed 3 trailing nodes:
39.89/11.61	   F(0, z0, 0, z1) -> c2
39.89/11.61	   PERFECTP(0) -> c
39.89/11.61	   F(0, z0, s(z1), z2) -> c3
39.89/11.61	
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(6)
39.89/11.61	Obligation:
39.89/11.61	Complexity Dependency Tuples Problem
39.89/11.61	
39.89/11.61	Rules:
39.89/11.61	   perfectp(0) -> false
39.89/11.61	   perfectp(s(z0)) -> f(z0, s(0), s(z0), s(z0))
39.89/11.61	   f(0, z0, 0, z1) -> true
39.89/11.61	   f(0, z0, s(z1), z2) -> false
39.89/11.61	   f(s(z0), 0, z1, z2) -> f(z0, z2, minus(z1, s(z0)), z2)
39.89/11.61	   f(s(z0), s(z1), z2, z3) -> if(le(z0, z1), f(s(z0), minus(z1, z0), z2, z3), f(z0, z3, z2, z3))
39.89/11.61	Tuples:
39.89/11.61	   F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2))
39.89/11.61	   F(s(z0), s(z1), z2, z3) -> c5(F(s(z0), minus(z1, z0), z2, z3), F(z0, z3, z2, z3))
39.89/11.61	S tuples:
39.89/11.61	   F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2))
39.89/11.61	   F(s(z0), s(z1), z2, z3) -> c5(F(s(z0), minus(z1, z0), z2, z3), F(z0, z3, z2, z3))
39.89/11.61	K tuples:none
39.89/11.61	Defined Rule Symbols:   perfectp_1, f_4
39.89/11.61	
39.89/11.61	Defined Pair Symbols:   F_4
39.89/11.61	
39.89/11.61	Compound Symbols:   c4_1, c5_2
39.89/11.61	
39.89/11.61	
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))
39.89/11.61	Removed 1 trailing tuple parts
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(8)
39.89/11.61	Obligation:
39.89/11.61	Complexity Dependency Tuples Problem
39.89/11.61	
39.89/11.61	Rules:
39.89/11.61	   perfectp(0) -> false
39.89/11.61	   perfectp(s(z0)) -> f(z0, s(0), s(z0), s(z0))
39.89/11.61	   f(0, z0, 0, z1) -> true
39.89/11.61	   f(0, z0, s(z1), z2) -> false
39.89/11.61	   f(s(z0), 0, z1, z2) -> f(z0, z2, minus(z1, s(z0)), z2)
39.89/11.61	   f(s(z0), s(z1), z2, z3) -> if(le(z0, z1), f(s(z0), minus(z1, z0), z2, z3), f(z0, z3, z2, z3))
39.89/11.61	Tuples:
39.89/11.61	   F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2))
39.89/11.61	   F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3))
39.89/11.61	S tuples:
39.89/11.61	   F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2))
39.89/11.61	   F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3))
39.89/11.61	K tuples:none
39.89/11.61	Defined Rule Symbols:   perfectp_1, f_4
39.89/11.61	
39.89/11.61	Defined Pair Symbols:   F_4
39.89/11.61	
39.89/11.61	Compound Symbols:   c4_1, c5_1
39.89/11.61	
39.89/11.61	
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
39.89/11.61	The following rules are not usable and were removed:
39.89/11.61	   perfectp(0) -> false
39.89/11.61	   perfectp(s(z0)) -> f(z0, s(0), s(z0), s(z0))
39.89/11.61	   f(0, z0, 0, z1) -> true
39.89/11.61	   f(0, z0, s(z1), z2) -> false
39.89/11.61	   f(s(z0), 0, z1, z2) -> f(z0, z2, minus(z1, s(z0)), z2)
39.89/11.61	   f(s(z0), s(z1), z2, z3) -> if(le(z0, z1), f(s(z0), minus(z1, z0), z2, z3), f(z0, z3, z2, z3))
39.89/11.61	
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(10)
39.89/11.61	Obligation:
39.89/11.61	Complexity Dependency Tuples Problem
39.89/11.61	
39.89/11.61	Rules:none
39.89/11.61	Tuples:
39.89/11.61	   F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2))
39.89/11.61	   F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3))
39.89/11.61	S tuples:
39.89/11.61	   F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2))
39.89/11.61	   F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3))
39.89/11.61	K tuples:none
39.89/11.61	Defined Rule Symbols:none
39.89/11.61	
39.89/11.61	Defined Pair Symbols:   F_4
39.89/11.61	
39.89/11.61	Compound Symbols:   c4_1, c5_1
39.89/11.61	
39.89/11.61	
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
39.89/11.61	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
39.89/11.61	   F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3))
39.89/11.61	We considered the (Usable) Rules:none
39.89/11.61	And the Tuples:
39.89/11.61	   F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2))
39.89/11.61	   F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3))
39.89/11.61	The order we found is given by the following interpretation:
39.89/11.61	
39.89/11.61	Polynomial interpretation :
39.89/11.61	
39.89/11.61	   POL(0) = 0
39.89/11.61	   POL(F(x_1, x_2, x_3, x_4)) = x_1 + x_3
39.89/11.61	   POL(c4(x_1)) = x_1
39.89/11.61	   POL(c5(x_1)) = x_1
39.89/11.61	   POL(minus(x_1, x_2)) = [1]
39.89/11.61	   POL(s(x_1)) = [1] + x_1
39.89/11.61	
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(12)
39.89/11.61	Obligation:
39.89/11.61	Complexity Dependency Tuples Problem
39.89/11.61	
39.89/11.61	Rules:none
39.89/11.61	Tuples:
39.89/11.61	   F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2))
39.89/11.61	   F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3))
39.89/11.61	S tuples:
39.89/11.61	   F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2))
39.89/11.61	K tuples:
39.89/11.61	   F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3))
39.89/11.61	Defined Rule Symbols:none
39.89/11.61	
39.89/11.61	Defined Pair Symbols:   F_4
39.89/11.61	
39.89/11.61	Compound Symbols:   c4_1, c5_1
39.89/11.61	
39.89/11.61	
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
39.89/11.61	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
39.89/11.61	   F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2))
39.89/11.61	We considered the (Usable) Rules:none
39.89/11.61	And the Tuples:
39.89/11.61	   F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2))
39.89/11.61	   F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3))
39.89/11.61	The order we found is given by the following interpretation:
39.89/11.61	
39.89/11.61	Polynomial interpretation :
39.89/11.61	
39.89/11.61	   POL(0) = 0
39.89/11.61	   POL(F(x_1, x_2, x_3, x_4)) = x_1 + x_3
39.89/11.61	   POL(c4(x_1)) = x_1
39.89/11.61	   POL(c5(x_1)) = x_1
39.89/11.61	   POL(minus(x_1, x_2)) = x_1
39.89/11.61	   POL(s(x_1)) = [1] + x_1
39.89/11.61	
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(14)
39.89/11.61	Obligation:
39.89/11.61	Complexity Dependency Tuples Problem
39.89/11.61	
39.89/11.61	Rules:none
39.89/11.61	Tuples:
39.89/11.61	   F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2))
39.89/11.61	   F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3))
39.89/11.61	S tuples:none
39.89/11.61	K tuples:
39.89/11.61	   F(s(z0), s(z1), z2, z3) -> c5(F(z0, z3, z2, z3))
39.89/11.61	   F(s(z0), 0, z1, z2) -> c4(F(z0, z2, minus(z1, s(z0)), z2))
39.89/11.61	Defined Rule Symbols:none
39.89/11.61	
39.89/11.61	Defined Pair Symbols:   F_4
39.89/11.61	
39.89/11.61	Compound Symbols:   c4_1, c5_1
39.89/11.61	
39.89/11.61	
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(15) SIsEmptyProof (BOTH BOUNDS(ID, ID))
39.89/11.61	The set S is empty
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(16)
39.89/11.61	BOUNDS(1, 1)
39.89/11.61	
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(17) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
39.89/11.61	Transformed a relative TRS into a decreasing-loop problem.
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(18)
39.89/11.61	Obligation:
39.89/11.61	Analyzing the following TRS for decreasing loops:
39.89/11.61	
39.89/11.61	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
39.89/11.61	
39.89/11.61	
39.89/11.61	The TRS R consists of the following rules:
39.89/11.61	
39.89/11.61	   perfectp(0) -> false
39.89/11.61	   perfectp(s(x)) -> f(x, s(0), s(x), s(x))
39.89/11.61	   f(0, y, 0, u) -> true
39.89/11.61	   f(0, y, s(z), u) -> false
39.89/11.61	   f(s(x), 0, z, u) -> f(x, u, minus(z, s(x)), u)
39.89/11.61	   f(s(x), s(y), z, u) -> if(le(x, y), f(s(x), minus(y, x), z, u), f(x, u, z, u))
39.89/11.61	
39.89/11.61	S is empty.
39.89/11.61	Rewrite Strategy: FULL
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(19) DecreasingLoopProof (LOWER BOUND(ID))
39.89/11.61	The following loop(s) give(s) rise to the lower bound Omega(n^1):
39.89/11.61	
39.89/11.61	The rewrite sequence
39.89/11.61	
39.89/11.61	f(s(s(x1_0)), s(y), z, s(y2_0)) ->^+ if(le(s(x1_0), y), f(s(s(x1_0)), minus(y, s(x1_0)), z, s(y2_0)), if(le(x1_0, y2_0), f(s(x1_0), minus(y2_0, x1_0), z, s(y2_0)), f(x1_0, s(y2_0), z, s(y2_0))))
39.89/11.61	
39.89/11.61	gives rise to a decreasing loop by considering the right hand sides subterm at position [2,2].
39.89/11.61	
39.89/11.61	The pumping substitution is [x1_0 / s(s(x1_0))].
39.89/11.61	
39.89/11.61	The result substitution is [y / y2_0].
39.89/11.61	
39.89/11.61	
39.89/11.61	
39.89/11.61	
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(20)
39.89/11.61	Complex Obligation (BEST)
39.89/11.61	
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(21)
39.89/11.61	Obligation:
39.89/11.61	Proved the lower bound n^1 for the following obligation:
39.89/11.61	
39.89/11.61	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
39.89/11.61	
39.89/11.61	
39.89/11.61	The TRS R consists of the following rules:
39.89/11.61	
39.89/11.61	   perfectp(0) -> false
39.89/11.61	   perfectp(s(x)) -> f(x, s(0), s(x), s(x))
39.89/11.61	   f(0, y, 0, u) -> true
39.89/11.61	   f(0, y, s(z), u) -> false
39.89/11.61	   f(s(x), 0, z, u) -> f(x, u, minus(z, s(x)), u)
39.89/11.61	   f(s(x), s(y), z, u) -> if(le(x, y), f(s(x), minus(y, x), z, u), f(x, u, z, u))
39.89/11.61	
39.89/11.61	S is empty.
39.89/11.61	Rewrite Strategy: FULL
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(22) LowerBoundPropagationProof (FINISHED)
39.89/11.61	Propagated lower bound.
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(23)
39.89/11.61	BOUNDS(n^1, INF)
39.89/11.61	
39.89/11.61	----------------------------------------
39.89/11.61	
39.89/11.61	(24)
39.89/11.61	Obligation:
39.89/11.61	Analyzing the following TRS for decreasing loops:
39.89/11.61	
39.89/11.61	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
39.89/11.61	
39.89/11.61	
39.89/11.61	The TRS R consists of the following rules:
39.89/11.61	
39.89/11.61	   perfectp(0) -> false
39.89/11.61	   perfectp(s(x)) -> f(x, s(0), s(x), s(x))
39.89/11.61	   f(0, y, 0, u) -> true
39.89/11.61	   f(0, y, s(z), u) -> false
39.89/11.61	   f(s(x), 0, z, u) -> f(x, u, minus(z, s(x)), u)
39.89/11.61	   f(s(x), s(y), z, u) -> if(le(x, y), f(s(x), minus(y, x), z, u), f(x, u, z, u))
39.89/11.61	
39.89/11.61	S is empty.
39.89/11.61	Rewrite Strategy: FULL
40.11/11.65	EOF