13.22/4.25	WORST_CASE(Omega(n^1), O(n^1))
13.22/4.26	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
13.22/4.26	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
13.22/4.26	
13.22/4.26	
13.22/4.26	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
13.22/4.26	
13.22/4.26	(0) CpxTRS
13.22/4.26	(1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
13.22/4.26	(2) CdtProblem
13.22/4.26	    (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
13.22/4.26	    (4) CdtProblem
13.22/4.26	    (5) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
13.22/4.26	    (6) CdtProblem
13.22/4.26	    (7) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
13.22/4.26	    (8) CdtProblem
13.22/4.26	    (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 17 ms]
13.22/4.26	    (10) CdtProblem
13.22/4.26	    (11) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
13.22/4.26	    (12) BOUNDS(1, 1)
13.22/4.26	(13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
13.22/4.26	(14) TRS for Loop Detection
13.22/4.26	    (15) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
13.22/4.26	    (16) BEST
13.22/4.26	        (17) proven lower bound
13.22/4.26	            (18) LowerBoundPropagationProof [FINISHED, 0 ms]
13.22/4.26	            (19) BOUNDS(n^1, INF)
13.22/4.26	        (20) TRS for Loop Detection
13.22/4.26	
13.22/4.26	
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(0)
13.22/4.26	Obligation:
13.22/4.26	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
13.22/4.26	
13.22/4.26	
13.22/4.26	The TRS R consists of the following rules:
13.22/4.26	
13.22/4.26	   a__f(b, X, c) -> a__f(X, a__c, X)
13.22/4.26	   a__c -> b
13.22/4.26	   mark(f(X1, X2, X3)) -> a__f(X1, mark(X2), X3)
13.22/4.26	   mark(c) -> a__c
13.22/4.26	   mark(b) -> b
13.22/4.26	   a__f(X1, X2, X3) -> f(X1, X2, X3)
13.22/4.26	   a__c -> c
13.22/4.26	
13.22/4.26	S is empty.
13.22/4.26	Rewrite Strategy: INNERMOST
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(1) CpxTrsToCdtProof (UPPER BOUND(ID))
13.22/4.26	Converted Cpx (relative) TRS to CDT
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(2)
13.22/4.26	Obligation:
13.22/4.26	Complexity Dependency Tuples Problem
13.22/4.26	
13.22/4.26	Rules:
13.22/4.26	   a__f(b, z0, c) -> a__f(z0, a__c, z0)
13.22/4.26	   a__f(z0, z1, z2) -> f(z0, z1, z2)
13.22/4.26	   a__c -> b
13.22/4.26	   a__c -> c
13.22/4.26	   mark(f(z0, z1, z2)) -> a__f(z0, mark(z1), z2)
13.22/4.26	   mark(c) -> a__c
13.22/4.26	   mark(b) -> b
13.22/4.26	Tuples:
13.22/4.26	   A__F(b, z0, c) -> c1(A__F(z0, a__c, z0), A__C)
13.22/4.26	   A__F(z0, z1, z2) -> c2
13.22/4.26	   A__C -> c3
13.22/4.26	   A__C -> c4
13.22/4.26	   MARK(f(z0, z1, z2)) -> c5(A__F(z0, mark(z1), z2), MARK(z1))
13.22/4.26	   MARK(c) -> c6(A__C)
13.22/4.26	   MARK(b) -> c7
13.22/4.26	S tuples:
13.22/4.26	   A__F(b, z0, c) -> c1(A__F(z0, a__c, z0), A__C)
13.22/4.26	   A__F(z0, z1, z2) -> c2
13.22/4.26	   A__C -> c3
13.22/4.26	   A__C -> c4
13.22/4.26	   MARK(f(z0, z1, z2)) -> c5(A__F(z0, mark(z1), z2), MARK(z1))
13.22/4.26	   MARK(c) -> c6(A__C)
13.22/4.26	   MARK(b) -> c7
13.22/4.26	K tuples:none
13.22/4.26	Defined Rule Symbols:   a__f_3, a__c, mark_1
13.22/4.26	
13.22/4.26	Defined Pair Symbols:   A__F_3, A__C, MARK_1
13.22/4.26	
13.22/4.26	Compound Symbols:   c1_2, c2, c3, c4, c5_2, c6_1, c7
13.22/4.26	
13.22/4.26	
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
13.22/4.26	Removed 6 trailing nodes:
13.22/4.26	   MARK(b) -> c7
13.22/4.26	   A__C -> c4
13.22/4.26	   MARK(c) -> c6(A__C)
13.22/4.26	   A__F(z0, z1, z2) -> c2
13.22/4.26	   A__C -> c3
13.22/4.26	   A__F(b, z0, c) -> c1(A__F(z0, a__c, z0), A__C)
13.22/4.26	
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(4)
13.22/4.26	Obligation:
13.22/4.26	Complexity Dependency Tuples Problem
13.22/4.26	
13.22/4.26	Rules:
13.22/4.26	   a__f(b, z0, c) -> a__f(z0, a__c, z0)
13.22/4.26	   a__f(z0, z1, z2) -> f(z0, z1, z2)
13.22/4.26	   a__c -> b
13.22/4.26	   a__c -> c
13.22/4.26	   mark(f(z0, z1, z2)) -> a__f(z0, mark(z1), z2)
13.22/4.26	   mark(c) -> a__c
13.22/4.26	   mark(b) -> b
13.22/4.26	Tuples:
13.22/4.26	   MARK(f(z0, z1, z2)) -> c5(A__F(z0, mark(z1), z2), MARK(z1))
13.22/4.26	S tuples:
13.22/4.26	   MARK(f(z0, z1, z2)) -> c5(A__F(z0, mark(z1), z2), MARK(z1))
13.22/4.26	K tuples:none
13.22/4.26	Defined Rule Symbols:   a__f_3, a__c, mark_1
13.22/4.26	
13.22/4.26	Defined Pair Symbols:   MARK_1
13.22/4.26	
13.22/4.26	Compound Symbols:   c5_2
13.22/4.26	
13.22/4.26	
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))
13.22/4.26	Removed 1 trailing tuple parts
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(6)
13.22/4.26	Obligation:
13.22/4.26	Complexity Dependency Tuples Problem
13.22/4.26	
13.22/4.26	Rules:
13.22/4.26	   a__f(b, z0, c) -> a__f(z0, a__c, z0)
13.22/4.26	   a__f(z0, z1, z2) -> f(z0, z1, z2)
13.22/4.26	   a__c -> b
13.22/4.26	   a__c -> c
13.22/4.26	   mark(f(z0, z1, z2)) -> a__f(z0, mark(z1), z2)
13.22/4.26	   mark(c) -> a__c
13.22/4.26	   mark(b) -> b
13.22/4.26	Tuples:
13.22/4.26	   MARK(f(z0, z1, z2)) -> c5(MARK(z1))
13.22/4.26	S tuples:
13.22/4.26	   MARK(f(z0, z1, z2)) -> c5(MARK(z1))
13.22/4.26	K tuples:none
13.22/4.26	Defined Rule Symbols:   a__f_3, a__c, mark_1
13.22/4.26	
13.22/4.26	Defined Pair Symbols:   MARK_1
13.22/4.26	
13.22/4.26	Compound Symbols:   c5_1
13.22/4.26	
13.22/4.26	
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(7) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
13.22/4.26	The following rules are not usable and were removed:
13.22/4.26	   a__f(b, z0, c) -> a__f(z0, a__c, z0)
13.22/4.26	   a__f(z0, z1, z2) -> f(z0, z1, z2)
13.22/4.26	   a__c -> b
13.22/4.26	   a__c -> c
13.22/4.26	   mark(f(z0, z1, z2)) -> a__f(z0, mark(z1), z2)
13.22/4.26	   mark(c) -> a__c
13.22/4.26	   mark(b) -> b
13.22/4.26	
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(8)
13.22/4.26	Obligation:
13.22/4.26	Complexity Dependency Tuples Problem
13.22/4.26	
13.22/4.26	Rules:none
13.22/4.26	Tuples:
13.22/4.26	   MARK(f(z0, z1, z2)) -> c5(MARK(z1))
13.22/4.26	S tuples:
13.22/4.26	   MARK(f(z0, z1, z2)) -> c5(MARK(z1))
13.22/4.26	K tuples:none
13.22/4.26	Defined Rule Symbols:none
13.22/4.26	
13.22/4.26	Defined Pair Symbols:   MARK_1
13.22/4.26	
13.22/4.26	Compound Symbols:   c5_1
13.22/4.26	
13.22/4.26	
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
13.22/4.26	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
13.22/4.26	   MARK(f(z0, z1, z2)) -> c5(MARK(z1))
13.22/4.26	We considered the (Usable) Rules:none
13.22/4.26	And the Tuples:
13.22/4.26	   MARK(f(z0, z1, z2)) -> c5(MARK(z1))
13.22/4.26	The order we found is given by the following interpretation:
13.22/4.26	
13.22/4.26	Polynomial interpretation :
13.22/4.26	
13.22/4.26	   POL(MARK(x_1)) = x_1
13.22/4.26	   POL(c5(x_1)) = x_1
13.22/4.26	   POL(f(x_1, x_2, x_3)) = [1] + x_2
13.22/4.26	
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(10)
13.22/4.26	Obligation:
13.22/4.26	Complexity Dependency Tuples Problem
13.22/4.26	
13.22/4.26	Rules:none
13.22/4.26	Tuples:
13.22/4.26	   MARK(f(z0, z1, z2)) -> c5(MARK(z1))
13.22/4.26	S tuples:none
13.22/4.26	K tuples:
13.22/4.26	   MARK(f(z0, z1, z2)) -> c5(MARK(z1))
13.22/4.26	Defined Rule Symbols:none
13.22/4.26	
13.22/4.26	Defined Pair Symbols:   MARK_1
13.22/4.26	
13.22/4.26	Compound Symbols:   c5_1
13.22/4.26	
13.22/4.26	
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(11) SIsEmptyProof (BOTH BOUNDS(ID, ID))
13.22/4.26	The set S is empty
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(12)
13.22/4.26	BOUNDS(1, 1)
13.22/4.26	
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(13) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
13.22/4.26	Transformed a relative TRS into a decreasing-loop problem.
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(14)
13.22/4.26	Obligation:
13.22/4.26	Analyzing the following TRS for decreasing loops:
13.22/4.26	
13.22/4.26	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
13.22/4.26	
13.22/4.26	
13.22/4.26	The TRS R consists of the following rules:
13.22/4.26	
13.22/4.26	   a__f(b, X, c) -> a__f(X, a__c, X)
13.22/4.26	   a__c -> b
13.22/4.26	   mark(f(X1, X2, X3)) -> a__f(X1, mark(X2), X3)
13.22/4.26	   mark(c) -> a__c
13.22/4.26	   mark(b) -> b
13.22/4.26	   a__f(X1, X2, X3) -> f(X1, X2, X3)
13.22/4.26	   a__c -> c
13.22/4.26	
13.22/4.26	S is empty.
13.22/4.26	Rewrite Strategy: INNERMOST
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(15) DecreasingLoopProof (LOWER BOUND(ID))
13.22/4.26	The following loop(s) give(s) rise to the lower bound Omega(n^1):
13.22/4.26	
13.22/4.26	The rewrite sequence
13.22/4.26	
13.22/4.26	mark(f(X1, X2, X3)) ->^+ a__f(X1, mark(X2), X3)
13.22/4.26	
13.22/4.26	gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
13.22/4.26	
13.22/4.26	The pumping substitution is [X2 / f(X1, X2, X3)].
13.22/4.26	
13.22/4.26	The result substitution is [ ].
13.22/4.26	
13.22/4.26	
13.22/4.26	
13.22/4.26	
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(16)
13.22/4.26	Complex Obligation (BEST)
13.22/4.26	
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(17)
13.22/4.26	Obligation:
13.22/4.26	Proved the lower bound n^1 for the following obligation:
13.22/4.26	
13.22/4.26	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
13.22/4.26	
13.22/4.26	
13.22/4.26	The TRS R consists of the following rules:
13.22/4.26	
13.22/4.26	   a__f(b, X, c) -> a__f(X, a__c, X)
13.22/4.26	   a__c -> b
13.22/4.26	   mark(f(X1, X2, X3)) -> a__f(X1, mark(X2), X3)
13.22/4.26	   mark(c) -> a__c
13.22/4.26	   mark(b) -> b
13.22/4.26	   a__f(X1, X2, X3) -> f(X1, X2, X3)
13.22/4.26	   a__c -> c
13.22/4.26	
13.22/4.26	S is empty.
13.22/4.26	Rewrite Strategy: INNERMOST
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(18) LowerBoundPropagationProof (FINISHED)
13.22/4.26	Propagated lower bound.
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(19)
13.22/4.26	BOUNDS(n^1, INF)
13.22/4.26	
13.22/4.26	----------------------------------------
13.22/4.26	
13.22/4.26	(20)
13.22/4.26	Obligation:
13.22/4.26	Analyzing the following TRS for decreasing loops:
13.22/4.26	
13.22/4.26	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
13.22/4.26	
13.22/4.26	
13.22/4.26	The TRS R consists of the following rules:
13.22/4.26	
13.22/4.26	   a__f(b, X, c) -> a__f(X, a__c, X)
13.22/4.26	   a__c -> b
13.22/4.26	   mark(f(X1, X2, X3)) -> a__f(X1, mark(X2), X3)
13.22/4.26	   mark(c) -> a__c
13.22/4.26	   mark(b) -> b
13.22/4.26	   a__f(X1, X2, X3) -> f(X1, X2, X3)
13.22/4.26	   a__c -> c
13.22/4.26	
13.22/4.26	S is empty.
13.22/4.26	Rewrite Strategy: INNERMOST
13.22/4.30	EOF