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