7.69/3.09	YES
7.79/3.11	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
7.79/3.11	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
7.79/3.11	
7.79/3.11	
7.79/3.11	Termination w.r.t. Q of the given QTRS could be proven:
7.79/3.11	
7.79/3.11	(0) QTRS
7.79/3.11	(1) DependencyPairsProof [EQUIVALENT, 0 ms]
7.79/3.11	(2) QDP
7.79/3.11	(3) QDPOrderProof [EQUIVALENT, 69 ms]
7.79/3.11	(4) QDP
7.79/3.11	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
7.79/3.11	(6) QDP
7.79/3.11	(7) QDPOrderProof [EQUIVALENT, 17 ms]
7.79/3.11	(8) QDP
7.79/3.11	(9) QDPOrderProof [EQUIVALENT, 35 ms]
7.79/3.11	(10) QDP
7.79/3.11	(11) UsableRulesProof [EQUIVALENT, 0 ms]
7.79/3.11	(12) QDP
7.79/3.11	(13) QReductionProof [EQUIVALENT, 0 ms]
7.79/3.11	(14) QDP
7.79/3.11	(15) QDPSizeChangeProof [EQUIVALENT, 0 ms]
7.79/3.11	(16) YES
7.79/3.11	
7.79/3.11	
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(0)
7.79/3.11	Obligation:
7.79/3.11	Q restricted rewrite system:
7.79/3.11	The TRS R consists of the following rules:
7.79/3.11	
7.79/3.11	   a__2nd(cons(X, cons(Y, Z))) -> mark(Y)
7.79/3.11	   a__from(X) -> cons(mark(X), from(s(X)))
7.79/3.11	   mark(2nd(X)) -> a__2nd(mark(X))
7.79/3.11	   mark(from(X)) -> a__from(mark(X))
7.79/3.11	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
7.79/3.11	   mark(s(X)) -> s(mark(X))
7.79/3.11	   a__2nd(X) -> 2nd(X)
7.79/3.11	   a__from(X) -> from(X)
7.79/3.11	
7.79/3.11	The set Q consists of the following terms:
7.79/3.11	
7.79/3.11	   a__from(x0)
7.79/3.11	   mark(2nd(x0))
7.79/3.11	   mark(from(x0))
7.79/3.11	   mark(cons(x0, x1))
7.79/3.11	   mark(s(x0))
7.79/3.11	   a__2nd(x0)
7.79/3.11	
7.79/3.11	
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(1) DependencyPairsProof (EQUIVALENT)
7.79/3.11	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(2)
7.79/3.11	Obligation:
7.79/3.11	Q DP problem:
7.79/3.11	The TRS P consists of the following rules:
7.79/3.11	
7.79/3.11	   A__2ND(cons(X, cons(Y, Z))) -> MARK(Y)
7.79/3.11	   A__FROM(X) -> MARK(X)
7.79/3.11	   MARK(2nd(X)) -> A__2ND(mark(X))
7.79/3.11	   MARK(2nd(X)) -> MARK(X)
7.79/3.11	   MARK(from(X)) -> A__FROM(mark(X))
7.79/3.11	   MARK(from(X)) -> MARK(X)
7.79/3.11	   MARK(cons(X1, X2)) -> MARK(X1)
7.79/3.11	   MARK(s(X)) -> MARK(X)
7.79/3.11	
7.79/3.11	The TRS R consists of the following rules:
7.79/3.11	
7.79/3.11	   a__2nd(cons(X, cons(Y, Z))) -> mark(Y)
7.79/3.11	   a__from(X) -> cons(mark(X), from(s(X)))
7.79/3.11	   mark(2nd(X)) -> a__2nd(mark(X))
7.79/3.11	   mark(from(X)) -> a__from(mark(X))
7.79/3.11	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
7.79/3.11	   mark(s(X)) -> s(mark(X))
7.79/3.11	   a__2nd(X) -> 2nd(X)
7.79/3.11	   a__from(X) -> from(X)
7.79/3.11	
7.79/3.11	The set Q consists of the following terms:
7.79/3.11	
7.79/3.11	   a__from(x0)
7.79/3.11	   mark(2nd(x0))
7.79/3.11	   mark(from(x0))
7.79/3.11	   mark(cons(x0, x1))
7.79/3.11	   mark(s(x0))
7.79/3.11	   a__2nd(x0)
7.79/3.11	
7.79/3.11	We have to consider all minimal (P,Q,R)-chains.
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(3) QDPOrderProof (EQUIVALENT)
7.79/3.11	We use the reduction pair processor [LPAR04,JAR06].
7.79/3.11	
7.79/3.11	
7.79/3.11	The following pairs can be oriented strictly and are deleted.
7.79/3.11	
7.79/3.11	   MARK(2nd(X)) -> A__2ND(mark(X))
7.79/3.11	   MARK(2nd(X)) -> MARK(X)
7.79/3.11	The remaining pairs can at least be oriented weakly.
7.79/3.11	Used ordering:  Polynomial interpretation [POLO,RATPOLO]:
7.79/3.11	
7.79/3.11	   POL(2nd(x_1)) = [2] + [2]x_1
7.79/3.11	   POL(A__2ND(x_1)) = [4] + [4]x_1
7.79/3.11	   POL(A__FROM(x_1)) = [4] + [4]x_1
7.79/3.11	   POL(MARK(x_1)) = [4] + [2]x_1
7.79/3.11	   POL(a__2nd(x_1)) = [2] + [2]x_1
7.79/3.11	   POL(a__from(x_1)) = [4]x_1
7.79/3.11	   POL(cons(x_1, x_2)) = [2]x_1 + [1/4]x_2
7.79/3.11	   POL(from(x_1)) = [4]x_1
7.79/3.11	   POL(mark(x_1)) = x_1
7.79/3.11	   POL(s(x_1)) = x_1
7.79/3.11	The value of delta used in the strict ordering is 4.
7.79/3.11	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
7.79/3.11	
7.79/3.11	   mark(2nd(X)) -> a__2nd(mark(X))
7.79/3.11	   a__2nd(cons(X, cons(Y, Z))) -> mark(Y)
7.79/3.11	   mark(from(X)) -> a__from(mark(X))
7.79/3.11	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
7.79/3.11	   mark(s(X)) -> s(mark(X))
7.79/3.11	   a__2nd(X) -> 2nd(X)
7.79/3.11	   a__from(X) -> from(X)
7.79/3.11	   a__from(X) -> cons(mark(X), from(s(X)))
7.79/3.11	
7.79/3.11	
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(4)
7.79/3.11	Obligation:
7.79/3.11	Q DP problem:
7.79/3.11	The TRS P consists of the following rules:
7.79/3.11	
7.79/3.11	   A__2ND(cons(X, cons(Y, Z))) -> MARK(Y)
7.79/3.11	   A__FROM(X) -> MARK(X)
7.79/3.11	   MARK(from(X)) -> A__FROM(mark(X))
7.79/3.11	   MARK(from(X)) -> MARK(X)
7.79/3.11	   MARK(cons(X1, X2)) -> MARK(X1)
7.79/3.11	   MARK(s(X)) -> MARK(X)
7.79/3.11	
7.79/3.11	The TRS R consists of the following rules:
7.79/3.11	
7.79/3.11	   a__2nd(cons(X, cons(Y, Z))) -> mark(Y)
7.79/3.11	   a__from(X) -> cons(mark(X), from(s(X)))
7.79/3.11	   mark(2nd(X)) -> a__2nd(mark(X))
7.79/3.11	   mark(from(X)) -> a__from(mark(X))
7.79/3.11	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
7.79/3.11	   mark(s(X)) -> s(mark(X))
7.79/3.11	   a__2nd(X) -> 2nd(X)
7.79/3.11	   a__from(X) -> from(X)
7.79/3.11	
7.79/3.11	The set Q consists of the following terms:
7.79/3.11	
7.79/3.11	   a__from(x0)
7.79/3.11	   mark(2nd(x0))
7.79/3.11	   mark(from(x0))
7.79/3.11	   mark(cons(x0, x1))
7.79/3.11	   mark(s(x0))
7.79/3.11	   a__2nd(x0)
7.79/3.11	
7.79/3.11	We have to consider all minimal (P,Q,R)-chains.
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(5) DependencyGraphProof (EQUIVALENT)
7.79/3.11	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(6)
7.79/3.11	Obligation:
7.79/3.11	Q DP problem:
7.79/3.11	The TRS P consists of the following rules:
7.79/3.11	
7.79/3.11	   MARK(from(X)) -> A__FROM(mark(X))
7.79/3.11	   A__FROM(X) -> MARK(X)
7.79/3.11	   MARK(from(X)) -> MARK(X)
7.79/3.11	   MARK(cons(X1, X2)) -> MARK(X1)
7.79/3.11	   MARK(s(X)) -> MARK(X)
7.79/3.11	
7.79/3.11	The TRS R consists of the following rules:
7.79/3.11	
7.79/3.11	   a__2nd(cons(X, cons(Y, Z))) -> mark(Y)
7.79/3.11	   a__from(X) -> cons(mark(X), from(s(X)))
7.79/3.11	   mark(2nd(X)) -> a__2nd(mark(X))
7.79/3.11	   mark(from(X)) -> a__from(mark(X))
7.79/3.11	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
7.79/3.11	   mark(s(X)) -> s(mark(X))
7.79/3.11	   a__2nd(X) -> 2nd(X)
7.79/3.11	   a__from(X) -> from(X)
7.79/3.11	
7.79/3.11	The set Q consists of the following terms:
7.79/3.11	
7.79/3.11	   a__from(x0)
7.79/3.11	   mark(2nd(x0))
7.79/3.11	   mark(from(x0))
7.79/3.11	   mark(cons(x0, x1))
7.79/3.11	   mark(s(x0))
7.79/3.11	   a__2nd(x0)
7.79/3.11	
7.79/3.11	We have to consider all minimal (P,Q,R)-chains.
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(7) QDPOrderProof (EQUIVALENT)
7.79/3.11	We use the reduction pair processor [LPAR04,JAR06].
7.79/3.11	
7.79/3.11	
7.79/3.11	The following pairs can be oriented strictly and are deleted.
7.79/3.11	
7.79/3.11	   MARK(from(X)) -> MARK(X)
7.79/3.11	The remaining pairs can at least be oriented weakly.
7.79/3.11	Used ordering:  Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]:
7.79/3.11	
7.79/3.11	   <<<
7.79/3.11	 POL(MARK(x_1)) =  	[[0A]] 	 +  	[[0A]] 	* 	x_1
7.79/3.11	>>>
7.79/3.11	
7.79/3.11	   <<<
7.79/3.11	 POL(from(x_1)) =  	[[1A]] 	 +  	[[1A]] 	* 	x_1
7.79/3.11	>>>
7.79/3.11	
7.79/3.11	   <<<
7.79/3.11	 POL(A__FROM(x_1)) =  	[[0A]] 	 +  	[[1A]] 	* 	x_1
7.79/3.11	>>>
7.79/3.11	
7.79/3.11	   <<<
7.79/3.11	 POL(mark(x_1)) =  	[[0A]] 	 +  	[[0A]] 	* 	x_1
7.79/3.11	>>>
7.79/3.11	
7.79/3.11	   <<<
7.79/3.11	 POL(cons(x_1, x_2)) =  	[[-I]] 	 +  	[[0A]] 	* 	x_1 	 +  	[[0A]] 	* 	x_2
7.79/3.11	>>>
7.79/3.11	
7.79/3.11	   <<<
7.79/3.11	 POL(s(x_1)) =  	[[-I]] 	 +  	[[0A]] 	* 	x_1
7.79/3.11	>>>
7.79/3.11	
7.79/3.11	   <<<
7.79/3.11	 POL(2nd(x_1)) =  	[[1A]] 	 +  	[[1A]] 	* 	x_1
7.79/3.11	>>>
7.79/3.11	
7.79/3.11	   <<<
7.79/3.11	 POL(a__2nd(x_1)) =  	[[1A]] 	 +  	[[1A]] 	* 	x_1
7.79/3.11	>>>
7.79/3.11	
7.79/3.11	   <<<
7.79/3.11	 POL(a__from(x_1)) =  	[[1A]] 	 +  	[[1A]] 	* 	x_1
7.79/3.11	>>>
7.79/3.11	
7.79/3.11	
7.79/3.11	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
7.79/3.11	
7.79/3.11	   mark(2nd(X)) -> a__2nd(mark(X))
7.79/3.11	   a__2nd(cons(X, cons(Y, Z))) -> mark(Y)
7.79/3.11	   mark(from(X)) -> a__from(mark(X))
7.79/3.11	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
7.79/3.11	   mark(s(X)) -> s(mark(X))
7.79/3.11	   a__2nd(X) -> 2nd(X)
7.79/3.11	   a__from(X) -> from(X)
7.79/3.11	   a__from(X) -> cons(mark(X), from(s(X)))
7.79/3.11	
7.79/3.11	
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(8)
7.79/3.11	Obligation:
7.79/3.11	Q DP problem:
7.79/3.11	The TRS P consists of the following rules:
7.79/3.11	
7.79/3.11	   MARK(from(X)) -> A__FROM(mark(X))
7.79/3.11	   A__FROM(X) -> MARK(X)
7.79/3.11	   MARK(cons(X1, X2)) -> MARK(X1)
7.79/3.11	   MARK(s(X)) -> MARK(X)
7.79/3.11	
7.79/3.11	The TRS R consists of the following rules:
7.79/3.11	
7.79/3.11	   a__2nd(cons(X, cons(Y, Z))) -> mark(Y)
7.79/3.11	   a__from(X) -> cons(mark(X), from(s(X)))
7.79/3.11	   mark(2nd(X)) -> a__2nd(mark(X))
7.79/3.11	   mark(from(X)) -> a__from(mark(X))
7.79/3.11	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
7.79/3.11	   mark(s(X)) -> s(mark(X))
7.79/3.11	   a__2nd(X) -> 2nd(X)
7.79/3.11	   a__from(X) -> from(X)
7.79/3.11	
7.79/3.11	The set Q consists of the following terms:
7.79/3.11	
7.79/3.11	   a__from(x0)
7.79/3.11	   mark(2nd(x0))
7.79/3.11	   mark(from(x0))
7.79/3.11	   mark(cons(x0, x1))
7.79/3.11	   mark(s(x0))
7.79/3.11	   a__2nd(x0)
7.79/3.11	
7.79/3.11	We have to consider all minimal (P,Q,R)-chains.
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(9) QDPOrderProof (EQUIVALENT)
7.79/3.11	We use the reduction pair processor [LPAR04,JAR06].
7.79/3.11	
7.79/3.11	
7.79/3.11	The following pairs can be oriented strictly and are deleted.
7.79/3.11	
7.79/3.11	   MARK(from(X)) -> A__FROM(mark(X))
7.79/3.11	   A__FROM(X) -> MARK(X)
7.79/3.11	   MARK(cons(X1, X2)) -> MARK(X1)
7.79/3.11	The remaining pairs can at least be oriented weakly.
7.79/3.11	Used ordering:  Polynomial interpretation [POLO,RATPOLO]:
7.79/3.11	
7.79/3.11	   POL(2nd(x_1)) = [1] + [4]x_1
7.79/3.11	   POL(A__FROM(x_1)) = [1] + x_1
7.79/3.11	   POL(MARK(x_1)) = [1/2] + [1/2]x_1
7.79/3.11	   POL(a__2nd(x_1)) = [1] + [4]x_1
7.79/3.11	   POL(a__from(x_1)) = [2] + [2]x_1
7.79/3.11	   POL(cons(x_1, x_2)) = [1/4] + x_1 + [1/4]x_2
7.79/3.11	   POL(from(x_1)) = [2] + [2]x_1
7.79/3.11	   POL(mark(x_1)) = x_1
7.79/3.11	   POL(s(x_1)) = x_1
7.79/3.11	The value of delta used in the strict ordering is 1/8.
7.79/3.11	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
7.79/3.11	
7.79/3.11	   mark(2nd(X)) -> a__2nd(mark(X))
7.79/3.11	   a__2nd(cons(X, cons(Y, Z))) -> mark(Y)
7.79/3.11	   mark(from(X)) -> a__from(mark(X))
7.79/3.11	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
7.79/3.11	   mark(s(X)) -> s(mark(X))
7.79/3.11	   a__2nd(X) -> 2nd(X)
7.79/3.11	   a__from(X) -> from(X)
7.79/3.11	   a__from(X) -> cons(mark(X), from(s(X)))
7.79/3.11	
7.79/3.11	
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(10)
7.79/3.11	Obligation:
7.79/3.11	Q DP problem:
7.79/3.11	The TRS P consists of the following rules:
7.79/3.11	
7.79/3.11	   MARK(s(X)) -> MARK(X)
7.79/3.11	
7.79/3.11	The TRS R consists of the following rules:
7.79/3.11	
7.79/3.11	   a__2nd(cons(X, cons(Y, Z))) -> mark(Y)
7.79/3.11	   a__from(X) -> cons(mark(X), from(s(X)))
7.79/3.11	   mark(2nd(X)) -> a__2nd(mark(X))
7.79/3.11	   mark(from(X)) -> a__from(mark(X))
7.79/3.11	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
7.79/3.11	   mark(s(X)) -> s(mark(X))
7.79/3.11	   a__2nd(X) -> 2nd(X)
7.79/3.11	   a__from(X) -> from(X)
7.79/3.11	
7.79/3.11	The set Q consists of the following terms:
7.79/3.11	
7.79/3.11	   a__from(x0)
7.79/3.11	   mark(2nd(x0))
7.79/3.11	   mark(from(x0))
7.79/3.11	   mark(cons(x0, x1))
7.79/3.11	   mark(s(x0))
7.79/3.11	   a__2nd(x0)
7.79/3.11	
7.79/3.11	We have to consider all minimal (P,Q,R)-chains.
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(11) UsableRulesProof (EQUIVALENT)
7.79/3.11	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.
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(12)
7.79/3.11	Obligation:
7.79/3.11	Q DP problem:
7.79/3.11	The TRS P consists of the following rules:
7.79/3.11	
7.79/3.11	   MARK(s(X)) -> MARK(X)
7.79/3.11	
7.79/3.11	R is empty.
7.79/3.11	The set Q consists of the following terms:
7.79/3.11	
7.79/3.11	   a__from(x0)
7.79/3.11	   mark(2nd(x0))
7.79/3.11	   mark(from(x0))
7.79/3.11	   mark(cons(x0, x1))
7.79/3.11	   mark(s(x0))
7.79/3.11	   a__2nd(x0)
7.79/3.11	
7.79/3.11	We have to consider all minimal (P,Q,R)-chains.
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(13) QReductionProof (EQUIVALENT)
7.79/3.11	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
7.79/3.11	
7.79/3.11	   a__from(x0)
7.79/3.11	   mark(2nd(x0))
7.79/3.11	   mark(from(x0))
7.79/3.11	   mark(cons(x0, x1))
7.79/3.11	   mark(s(x0))
7.79/3.11	   a__2nd(x0)
7.79/3.11	
7.79/3.11	
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(14)
7.79/3.11	Obligation:
7.79/3.11	Q DP problem:
7.79/3.11	The TRS P consists of the following rules:
7.79/3.11	
7.79/3.11	   MARK(s(X)) -> MARK(X)
7.79/3.11	
7.79/3.11	R is empty.
7.79/3.11	Q is empty.
7.79/3.11	We have to consider all minimal (P,Q,R)-chains.
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(15) QDPSizeChangeProof (EQUIVALENT)
7.79/3.11	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. 
7.79/3.11	
7.79/3.11	From the DPs we obtained the following set of size-change graphs:
7.79/3.11	*MARK(s(X)) -> MARK(X)
7.79/3.11	The graph contains the following edges 1 > 1
7.79/3.11	
7.79/3.11	
7.79/3.11	----------------------------------------
7.79/3.11	
7.79/3.11	(16)
7.79/3.11	YES
7.82/3.14	EOF