3.82/2.74	YES
3.82/2.75	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.82/2.75	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.82/2.75	
3.82/2.75	
3.82/2.75	Termination w.r.t. Q of the given QTRS could be proven:
3.82/2.75	
3.82/2.75	(0) QTRS
3.82/2.75	(1) DependencyPairsProof [EQUIVALENT, 0 ms]
3.82/2.75	(2) QDP
3.82/2.75	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
3.82/2.75	(4) AND
3.82/2.75	    (5) QDP
3.82/2.75	        (6) UsableRulesProof [EQUIVALENT, 0 ms]
3.82/2.75	        (7) QDP
3.82/2.75	        (8) QReductionProof [EQUIVALENT, 0 ms]
3.82/2.75	        (9) QDP
3.82/2.75	        (10) QDPSizeChangeProof [EQUIVALENT, 0 ms]
3.82/2.75	        (11) YES
3.82/2.75	    (12) QDP
3.82/2.75	        (13) MRRProof [EQUIVALENT, 15 ms]
3.82/2.75	        (14) QDP
3.82/2.75	        (15) TransformationProof [EQUIVALENT, 0 ms]
3.82/2.75	        (16) QDP
3.82/2.75	        (17) UsableRulesProof [EQUIVALENT, 0 ms]
3.82/2.75	        (18) QDP
3.82/2.75	        (19) TransformationProof [EQUIVALENT, 0 ms]
3.82/2.75	        (20) QDP
3.82/2.75	        (21) UsableRulesProof [EQUIVALENT, 0 ms]
3.82/2.75	        (22) QDP
3.82/2.75	        (23) TransformationProof [EQUIVALENT, 0 ms]
3.82/2.75	        (24) QDP
3.82/2.75	        (25) DependencyGraphProof [EQUIVALENT, 0 ms]
3.82/2.75	        (26) TRUE
3.82/2.75	
3.82/2.75	
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(0)
3.82/2.75	Obligation:
3.82/2.75	Q restricted rewrite system:
3.82/2.75	The TRS R consists of the following rules:
3.82/2.75	
3.82/2.75	   active(f(X, X)) -> mark(f(a, b))
3.82/2.75	   active(b) -> mark(a)
3.82/2.75	   mark(f(X1, X2)) -> active(f(mark(X1), X2))
3.82/2.75	   mark(a) -> active(a)
3.82/2.75	   mark(b) -> active(b)
3.82/2.75	   f(mark(X1), X2) -> f(X1, X2)
3.82/2.75	   f(X1, mark(X2)) -> f(X1, X2)
3.82/2.75	   f(active(X1), X2) -> f(X1, X2)
3.82/2.75	   f(X1, active(X2)) -> f(X1, X2)
3.82/2.75	
3.82/2.75	The set Q consists of the following terms:
3.82/2.75	
3.82/2.75	   active(f(x0, x0))
3.82/2.75	   active(b)
3.82/2.75	   mark(f(x0, x1))
3.82/2.75	   mark(a)
3.82/2.75	   mark(b)
3.82/2.75	   f(mark(x0), x1)
3.82/2.75	   f(x0, mark(x1))
3.82/2.75	   f(active(x0), x1)
3.82/2.75	   f(x0, active(x1))
3.82/2.75	
3.82/2.75	
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(1) DependencyPairsProof (EQUIVALENT)
3.82/2.75	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(2)
3.82/2.75	Obligation:
3.82/2.75	Q DP problem:
3.82/2.75	The TRS P consists of the following rules:
3.82/2.75	
3.82/2.75	   ACTIVE(f(X, X)) -> MARK(f(a, b))
3.82/2.75	   ACTIVE(f(X, X)) -> F(a, b)
3.82/2.75	   ACTIVE(b) -> MARK(a)
3.82/2.75	   MARK(f(X1, X2)) -> ACTIVE(f(mark(X1), X2))
3.82/2.75	   MARK(f(X1, X2)) -> F(mark(X1), X2)
3.82/2.75	   MARK(f(X1, X2)) -> MARK(X1)
3.82/2.75	   MARK(a) -> ACTIVE(a)
3.82/2.75	   MARK(b) -> ACTIVE(b)
3.82/2.75	   F(mark(X1), X2) -> F(X1, X2)
3.82/2.75	   F(X1, mark(X2)) -> F(X1, X2)
3.82/2.75	   F(active(X1), X2) -> F(X1, X2)
3.82/2.75	   F(X1, active(X2)) -> F(X1, X2)
3.82/2.75	
3.82/2.75	The TRS R consists of the following rules:
3.82/2.75	
3.82/2.75	   active(f(X, X)) -> mark(f(a, b))
3.82/2.75	   active(b) -> mark(a)
3.82/2.75	   mark(f(X1, X2)) -> active(f(mark(X1), X2))
3.82/2.75	   mark(a) -> active(a)
3.82/2.75	   mark(b) -> active(b)
3.82/2.75	   f(mark(X1), X2) -> f(X1, X2)
3.82/2.75	   f(X1, mark(X2)) -> f(X1, X2)
3.82/2.75	   f(active(X1), X2) -> f(X1, X2)
3.82/2.75	   f(X1, active(X2)) -> f(X1, X2)
3.82/2.75	
3.82/2.75	The set Q consists of the following terms:
3.82/2.75	
3.82/2.75	   active(f(x0, x0))
3.82/2.75	   active(b)
3.82/2.75	   mark(f(x0, x1))
3.82/2.75	   mark(a)
3.82/2.75	   mark(b)
3.82/2.75	   f(mark(x0), x1)
3.82/2.75	   f(x0, mark(x1))
3.82/2.75	   f(active(x0), x1)
3.82/2.75	   f(x0, active(x1))
3.82/2.75	
3.82/2.75	We have to consider all minimal (P,Q,R)-chains.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(3) DependencyGraphProof (EQUIVALENT)
3.82/2.75	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 5 less nodes.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(4)
3.82/2.75	Complex Obligation (AND)
3.82/2.75	
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(5)
3.82/2.75	Obligation:
3.82/2.75	Q DP problem:
3.82/2.75	The TRS P consists of the following rules:
3.82/2.75	
3.82/2.75	   F(X1, mark(X2)) -> F(X1, X2)
3.82/2.75	   F(mark(X1), X2) -> F(X1, X2)
3.82/2.75	   F(active(X1), X2) -> F(X1, X2)
3.82/2.75	   F(X1, active(X2)) -> F(X1, X2)
3.82/2.75	
3.82/2.75	The TRS R consists of the following rules:
3.82/2.75	
3.82/2.75	   active(f(X, X)) -> mark(f(a, b))
3.82/2.75	   active(b) -> mark(a)
3.82/2.75	   mark(f(X1, X2)) -> active(f(mark(X1), X2))
3.82/2.75	   mark(a) -> active(a)
3.82/2.75	   mark(b) -> active(b)
3.82/2.75	   f(mark(X1), X2) -> f(X1, X2)
3.82/2.75	   f(X1, mark(X2)) -> f(X1, X2)
3.82/2.75	   f(active(X1), X2) -> f(X1, X2)
3.82/2.75	   f(X1, active(X2)) -> f(X1, X2)
3.82/2.75	
3.82/2.75	The set Q consists of the following terms:
3.82/2.75	
3.82/2.75	   active(f(x0, x0))
3.82/2.75	   active(b)
3.82/2.75	   mark(f(x0, x1))
3.82/2.75	   mark(a)
3.82/2.75	   mark(b)
3.82/2.75	   f(mark(x0), x1)
3.82/2.75	   f(x0, mark(x1))
3.82/2.75	   f(active(x0), x1)
3.82/2.75	   f(x0, active(x1))
3.82/2.75	
3.82/2.75	We have to consider all minimal (P,Q,R)-chains.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(6) UsableRulesProof (EQUIVALENT)
3.82/2.75	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(7)
3.82/2.75	Obligation:
3.82/2.75	Q DP problem:
3.82/2.75	The TRS P consists of the following rules:
3.82/2.75	
3.82/2.75	   F(X1, mark(X2)) -> F(X1, X2)
3.82/2.75	   F(mark(X1), X2) -> F(X1, X2)
3.82/2.75	   F(active(X1), X2) -> F(X1, X2)
3.82/2.75	   F(X1, active(X2)) -> F(X1, X2)
3.82/2.75	
3.82/2.75	R is empty.
3.82/2.75	The set Q consists of the following terms:
3.82/2.75	
3.82/2.75	   active(f(x0, x0))
3.82/2.75	   active(b)
3.82/2.75	   mark(f(x0, x1))
3.82/2.75	   mark(a)
3.82/2.75	   mark(b)
3.82/2.75	   f(mark(x0), x1)
3.82/2.75	   f(x0, mark(x1))
3.82/2.75	   f(active(x0), x1)
3.82/2.75	   f(x0, active(x1))
3.82/2.75	
3.82/2.75	We have to consider all minimal (P,Q,R)-chains.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(8) QReductionProof (EQUIVALENT)
3.82/2.75	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
3.82/2.75	
3.82/2.75	   f(mark(x0), x1)
3.82/2.75	   f(x0, mark(x1))
3.82/2.75	   f(active(x0), x1)
3.82/2.75	   f(x0, active(x1))
3.82/2.75	
3.82/2.75	
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(9)
3.82/2.75	Obligation:
3.82/2.75	Q DP problem:
3.82/2.75	The TRS P consists of the following rules:
3.82/2.75	
3.82/2.75	   F(X1, mark(X2)) -> F(X1, X2)
3.82/2.75	   F(mark(X1), X2) -> F(X1, X2)
3.82/2.75	   F(active(X1), X2) -> F(X1, X2)
3.82/2.75	   F(X1, active(X2)) -> F(X1, X2)
3.82/2.75	
3.82/2.75	R is empty.
3.82/2.75	The set Q consists of the following terms:
3.82/2.75	
3.82/2.75	   active(f(x0, x0))
3.82/2.75	   active(b)
3.82/2.75	   mark(f(x0, x1))
3.82/2.75	   mark(a)
3.82/2.75	   mark(b)
3.82/2.75	
3.82/2.75	We have to consider all minimal (P,Q,R)-chains.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(10) QDPSizeChangeProof (EQUIVALENT)
3.82/2.75	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
3.82/2.75	
3.82/2.75	From the DPs we obtained the following set of size-change graphs:
3.82/2.75	*F(X1, mark(X2)) -> F(X1, X2)
3.82/2.75	The graph contains the following edges 1 >= 1, 2 > 2
3.82/2.75	
3.82/2.75	
3.82/2.75	*F(mark(X1), X2) -> F(X1, X2)
3.82/2.75	The graph contains the following edges 1 > 1, 2 >= 2
3.82/2.75	
3.82/2.75	
3.82/2.75	*F(active(X1), X2) -> F(X1, X2)
3.82/2.75	The graph contains the following edges 1 > 1, 2 >= 2
3.82/2.75	
3.82/2.75	
3.82/2.75	*F(X1, active(X2)) -> F(X1, X2)
3.82/2.75	The graph contains the following edges 1 >= 1, 2 > 2
3.82/2.75	
3.82/2.75	
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(11)
3.82/2.75	YES
3.82/2.75	
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(12)
3.82/2.75	Obligation:
3.82/2.75	Q DP problem:
3.82/2.75	The TRS P consists of the following rules:
3.82/2.75	
3.82/2.75	   MARK(f(X1, X2)) -> ACTIVE(f(mark(X1), X2))
3.82/2.75	   ACTIVE(f(X, X)) -> MARK(f(a, b))
3.82/2.75	   MARK(f(X1, X2)) -> MARK(X1)
3.82/2.75	
3.82/2.75	The TRS R consists of the following rules:
3.82/2.75	
3.82/2.75	   active(f(X, X)) -> mark(f(a, b))
3.82/2.75	   active(b) -> mark(a)
3.82/2.75	   mark(f(X1, X2)) -> active(f(mark(X1), X2))
3.82/2.75	   mark(a) -> active(a)
3.82/2.75	   mark(b) -> active(b)
3.82/2.75	   f(mark(X1), X2) -> f(X1, X2)
3.82/2.75	   f(X1, mark(X2)) -> f(X1, X2)
3.82/2.75	   f(active(X1), X2) -> f(X1, X2)
3.82/2.75	   f(X1, active(X2)) -> f(X1, X2)
3.82/2.75	
3.82/2.75	The set Q consists of the following terms:
3.82/2.75	
3.82/2.75	   active(f(x0, x0))
3.82/2.75	   active(b)
3.82/2.75	   mark(f(x0, x1))
3.82/2.75	   mark(a)
3.82/2.75	   mark(b)
3.82/2.75	   f(mark(x0), x1)
3.82/2.75	   f(x0, mark(x1))
3.82/2.75	   f(active(x0), x1)
3.82/2.75	   f(x0, active(x1))
3.82/2.75	
3.82/2.75	We have to consider all minimal (P,Q,R)-chains.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(13) MRRProof (EQUIVALENT)
3.82/2.75	By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.
3.82/2.75	
3.82/2.75	Strictly oriented dependency pairs:
3.82/2.75	
3.82/2.75	   MARK(f(X1, X2)) -> MARK(X1)
3.82/2.75	
3.82/2.75	
3.82/2.75	Used ordering: Polynomial interpretation [POLO]:
3.82/2.75	
3.82/2.75	   POL(ACTIVE(x_1)) = 2 + 2*x_1
3.82/2.75	   POL(MARK(x_1)) = 2 + 2*x_1
3.82/2.75	   POL(a) = 0
3.82/2.75	   POL(active(x_1)) = x_1
3.82/2.75	   POL(b) = 0
3.82/2.75	   POL(f(x_1, x_2)) = 1 + 2*x_1 + 2*x_2
3.82/2.75	   POL(mark(x_1)) = x_1
3.82/2.75	
3.82/2.75	
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(14)
3.82/2.75	Obligation:
3.82/2.75	Q DP problem:
3.82/2.75	The TRS P consists of the following rules:
3.82/2.75	
3.82/2.75	   MARK(f(X1, X2)) -> ACTIVE(f(mark(X1), X2))
3.82/2.75	   ACTIVE(f(X, X)) -> MARK(f(a, b))
3.82/2.75	
3.82/2.75	The TRS R consists of the following rules:
3.82/2.75	
3.82/2.75	   active(f(X, X)) -> mark(f(a, b))
3.82/2.75	   active(b) -> mark(a)
3.82/2.75	   mark(f(X1, X2)) -> active(f(mark(X1), X2))
3.82/2.75	   mark(a) -> active(a)
3.82/2.75	   mark(b) -> active(b)
3.82/2.75	   f(mark(X1), X2) -> f(X1, X2)
3.82/2.75	   f(X1, mark(X2)) -> f(X1, X2)
3.82/2.75	   f(active(X1), X2) -> f(X1, X2)
3.82/2.75	   f(X1, active(X2)) -> f(X1, X2)
3.82/2.75	
3.82/2.75	The set Q consists of the following terms:
3.82/2.75	
3.82/2.75	   active(f(x0, x0))
3.82/2.75	   active(b)
3.82/2.75	   mark(f(x0, x1))
3.82/2.75	   mark(a)
3.82/2.75	   mark(b)
3.82/2.75	   f(mark(x0), x1)
3.82/2.75	   f(x0, mark(x1))
3.82/2.75	   f(active(x0), x1)
3.82/2.75	   f(x0, active(x1))
3.82/2.75	
3.82/2.75	We have to consider all minimal (P,Q,R)-chains.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(15) TransformationProof (EQUIVALENT)
3.82/2.75	By instantiating [LPAR04] the rule MARK(f(X1, X2)) -> ACTIVE(f(mark(X1), X2)) we obtained the following new rules [LPAR04]:
3.82/2.75	
3.82/2.75	   (MARK(f(a, b)) -> ACTIVE(f(mark(a), b)),MARK(f(a, b)) -> ACTIVE(f(mark(a), b)))
3.82/2.75	
3.82/2.75	
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(16)
3.82/2.75	Obligation:
3.82/2.75	Q DP problem:
3.82/2.75	The TRS P consists of the following rules:
3.82/2.75	
3.82/2.75	   ACTIVE(f(X, X)) -> MARK(f(a, b))
3.82/2.75	   MARK(f(a, b)) -> ACTIVE(f(mark(a), b))
3.82/2.75	
3.82/2.75	The TRS R consists of the following rules:
3.82/2.75	
3.82/2.75	   active(f(X, X)) -> mark(f(a, b))
3.82/2.75	   active(b) -> mark(a)
3.82/2.75	   mark(f(X1, X2)) -> active(f(mark(X1), X2))
3.82/2.75	   mark(a) -> active(a)
3.82/2.75	   mark(b) -> active(b)
3.82/2.75	   f(mark(X1), X2) -> f(X1, X2)
3.82/2.75	   f(X1, mark(X2)) -> f(X1, X2)
3.82/2.75	   f(active(X1), X2) -> f(X1, X2)
3.82/2.75	   f(X1, active(X2)) -> f(X1, X2)
3.82/2.75	
3.82/2.75	The set Q consists of the following terms:
3.82/2.75	
3.82/2.75	   active(f(x0, x0))
3.82/2.75	   active(b)
3.82/2.75	   mark(f(x0, x1))
3.82/2.75	   mark(a)
3.82/2.75	   mark(b)
3.82/2.75	   f(mark(x0), x1)
3.82/2.75	   f(x0, mark(x1))
3.82/2.75	   f(active(x0), x1)
3.82/2.75	   f(x0, active(x1))
3.82/2.75	
3.82/2.75	We have to consider all minimal (P,Q,R)-chains.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(17) UsableRulesProof (EQUIVALENT)
3.82/2.75	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(18)
3.82/2.75	Obligation:
3.82/2.75	Q DP problem:
3.82/2.75	The TRS P consists of the following rules:
3.82/2.75	
3.82/2.75	   ACTIVE(f(X, X)) -> MARK(f(a, b))
3.82/2.75	   MARK(f(a, b)) -> ACTIVE(f(mark(a), b))
3.82/2.75	
3.82/2.75	The TRS R consists of the following rules:
3.82/2.75	
3.82/2.75	   mark(a) -> active(a)
3.82/2.75	   f(X1, mark(X2)) -> f(X1, X2)
3.82/2.75	   f(mark(X1), X2) -> f(X1, X2)
3.82/2.75	   f(active(X1), X2) -> f(X1, X2)
3.82/2.75	   f(X1, active(X2)) -> f(X1, X2)
3.82/2.75	
3.82/2.75	The set Q consists of the following terms:
3.82/2.75	
3.82/2.75	   active(f(x0, x0))
3.82/2.75	   active(b)
3.82/2.75	   mark(f(x0, x1))
3.82/2.75	   mark(a)
3.82/2.75	   mark(b)
3.82/2.75	   f(mark(x0), x1)
3.82/2.75	   f(x0, mark(x1))
3.82/2.75	   f(active(x0), x1)
3.82/2.75	   f(x0, active(x1))
3.82/2.75	
3.82/2.75	We have to consider all minimal (P,Q,R)-chains.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(19) TransformationProof (EQUIVALENT)
3.82/2.75	By rewriting [LPAR04] the rule MARK(f(a, b)) -> ACTIVE(f(mark(a), b)) at position [0,0] we obtained the following new rules [LPAR04]:
3.82/2.75	
3.82/2.75	   (MARK(f(a, b)) -> ACTIVE(f(active(a), b)),MARK(f(a, b)) -> ACTIVE(f(active(a), b)))
3.82/2.75	
3.82/2.75	
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(20)
3.82/2.75	Obligation:
3.82/2.75	Q DP problem:
3.82/2.75	The TRS P consists of the following rules:
3.82/2.75	
3.82/2.75	   ACTIVE(f(X, X)) -> MARK(f(a, b))
3.82/2.75	   MARK(f(a, b)) -> ACTIVE(f(active(a), b))
3.82/2.75	
3.82/2.75	The TRS R consists of the following rules:
3.82/2.75	
3.82/2.75	   mark(a) -> active(a)
3.82/2.75	   f(X1, mark(X2)) -> f(X1, X2)
3.82/2.75	   f(mark(X1), X2) -> f(X1, X2)
3.82/2.75	   f(active(X1), X2) -> f(X1, X2)
3.82/2.75	   f(X1, active(X2)) -> f(X1, X2)
3.82/2.75	
3.82/2.75	The set Q consists of the following terms:
3.82/2.75	
3.82/2.75	   active(f(x0, x0))
3.82/2.75	   active(b)
3.82/2.75	   mark(f(x0, x1))
3.82/2.75	   mark(a)
3.82/2.75	   mark(b)
3.82/2.75	   f(mark(x0), x1)
3.82/2.75	   f(x0, mark(x1))
3.82/2.75	   f(active(x0), x1)
3.82/2.75	   f(x0, active(x1))
3.82/2.75	
3.82/2.75	We have to consider all minimal (P,Q,R)-chains.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(21) UsableRulesProof (EQUIVALENT)
3.82/2.75	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(22)
3.82/2.75	Obligation:
3.82/2.75	Q DP problem:
3.82/2.75	The TRS P consists of the following rules:
3.82/2.75	
3.82/2.75	   ACTIVE(f(X, X)) -> MARK(f(a, b))
3.82/2.75	   MARK(f(a, b)) -> ACTIVE(f(active(a), b))
3.82/2.75	
3.82/2.75	The TRS R consists of the following rules:
3.82/2.75	
3.82/2.75	   f(X1, mark(X2)) -> f(X1, X2)
3.82/2.75	   f(mark(X1), X2) -> f(X1, X2)
3.82/2.75	   f(active(X1), X2) -> f(X1, X2)
3.82/2.75	   f(X1, active(X2)) -> f(X1, X2)
3.82/2.75	
3.82/2.75	The set Q consists of the following terms:
3.82/2.75	
3.82/2.75	   active(f(x0, x0))
3.82/2.75	   active(b)
3.82/2.75	   mark(f(x0, x1))
3.82/2.75	   mark(a)
3.82/2.75	   mark(b)
3.82/2.75	   f(mark(x0), x1)
3.82/2.75	   f(x0, mark(x1))
3.82/2.75	   f(active(x0), x1)
3.82/2.75	   f(x0, active(x1))
3.82/2.75	
3.82/2.75	We have to consider all minimal (P,Q,R)-chains.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(23) TransformationProof (EQUIVALENT)
3.82/2.75	By narrowing [LPAR04] the rule MARK(f(a, b)) -> ACTIVE(f(active(a), b)) at position [0] we obtained the following new rules [LPAR04]:
3.82/2.75	
3.82/2.75	   (MARK(f(a, b)) -> ACTIVE(f(a, b)),MARK(f(a, b)) -> ACTIVE(f(a, b)))
3.82/2.75	
3.82/2.75	
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(24)
3.82/2.75	Obligation:
3.82/2.75	Q DP problem:
3.82/2.75	The TRS P consists of the following rules:
3.82/2.75	
3.82/2.75	   ACTIVE(f(X, X)) -> MARK(f(a, b))
3.82/2.75	   MARK(f(a, b)) -> ACTIVE(f(a, b))
3.82/2.75	
3.82/2.75	The TRS R consists of the following rules:
3.82/2.75	
3.82/2.75	   f(X1, mark(X2)) -> f(X1, X2)
3.82/2.75	   f(mark(X1), X2) -> f(X1, X2)
3.82/2.75	   f(active(X1), X2) -> f(X1, X2)
3.82/2.75	   f(X1, active(X2)) -> f(X1, X2)
3.82/2.75	
3.82/2.75	The set Q consists of the following terms:
3.82/2.75	
3.82/2.75	   active(f(x0, x0))
3.82/2.75	   active(b)
3.82/2.75	   mark(f(x0, x1))
3.82/2.75	   mark(a)
3.82/2.75	   mark(b)
3.82/2.75	   f(mark(x0), x1)
3.82/2.75	   f(x0, mark(x1))
3.82/2.75	   f(active(x0), x1)
3.82/2.75	   f(x0, active(x1))
3.82/2.75	
3.82/2.75	We have to consider all minimal (P,Q,R)-chains.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(25) DependencyGraphProof (EQUIVALENT)
3.82/2.75	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes.
3.82/2.75	----------------------------------------
3.82/2.75	
3.82/2.75	(26)
3.82/2.75	TRUE
4.01/2.78	EOF