3.58/1.78	YES
3.58/1.78	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.58/1.78	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.58/1.78	
3.58/1.78	
3.58/1.78	Quasi decreasingness of the given CTRS could be proven:
3.58/1.78	
3.58/1.78	(0) CTRS
3.58/1.78	(1) CTRSToQTRSProof [SOUND, 0 ms]
3.58/1.78	(2) QTRS
3.58/1.78	(3) DependencyPairsProof [EQUIVALENT, 0 ms]
3.58/1.78	(4) QDP
3.58/1.78	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
3.58/1.78	(6) AND
3.58/1.78	    (7) QDP
3.58/1.78	        (8) UsableRulesProof [EQUIVALENT, 0 ms]
3.58/1.78	        (9) QDP
3.58/1.78	        (10) QDPSizeChangeProof [EQUIVALENT, 0 ms]
3.58/1.78	        (11) YES
3.58/1.78	    (12) QDP
3.58/1.78	        (13) UsableRulesProof [EQUIVALENT, 0 ms]
3.58/1.78	        (14) QDP
3.58/1.78	        (15) QDPSizeChangeProof [EQUIVALENT, 0 ms]
3.58/1.78	        (16) YES
3.58/1.78	
3.58/1.78	
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(0)
3.58/1.78	Obligation:
3.58/1.78	Conditional term rewrite system:
3.58/1.78	The TRS R consists of the following rules:
3.58/1.78	
3.58/1.78	   gcd(add(x, y), y) -> gcd(x, y)
3.58/1.78	   gcd(y, add(x, y)) -> gcd(x, y)
3.58/1.78	   gcd(x, 0) -> x
3.58/1.78	   gcd(0, x) -> x
3.58/1.78	   add(0, y) -> y
3.58/1.78	   add(s(x), y) -> s(add(x, y))
3.58/1.78	
3.58/1.78	The conditional TRS C consists of the following conditional rules:
3.58/1.78	
3.58/1.78	   gcd(x, y) -> gcd(y, x) <= leq(y, x) -> false
3.58/1.78	
3.58/1.78	
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(1) CTRSToQTRSProof (SOUND)
3.58/1.78	The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC].
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(2)
3.58/1.78	Obligation:
3.58/1.78	Q restricted rewrite system:
3.58/1.78	The TRS R consists of the following rules:
3.58/1.78	
3.58/1.78	   gcd(x, y) -> U1(leq(y, x), x, y)
3.58/1.78	   U1(false, x, y) -> gcd(y, x)
3.58/1.78	   gcd(add(x, y), y) -> gcd(x, y)
3.58/1.78	   gcd(y, add(x, y)) -> gcd(x, y)
3.58/1.78	   gcd(x, 0) -> x
3.58/1.78	   gcd(0, x) -> x
3.58/1.78	   add(0, y) -> y
3.58/1.78	   add(s(x), y) -> s(add(x, y))
3.58/1.78	
3.58/1.78	Q is empty.
3.58/1.78	
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(3) DependencyPairsProof (EQUIVALENT)
3.58/1.78	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(4)
3.58/1.78	Obligation:
3.58/1.78	Q DP problem:
3.58/1.78	The TRS P consists of the following rules:
3.58/1.78	
3.58/1.78	   GCD(x, y) -> U1^1(leq(y, x), x, y)
3.58/1.78	   U1^1(false, x, y) -> GCD(y, x)
3.58/1.78	   GCD(add(x, y), y) -> GCD(x, y)
3.58/1.78	   GCD(y, add(x, y)) -> GCD(x, y)
3.58/1.78	   ADD(s(x), y) -> ADD(x, y)
3.58/1.78	
3.58/1.78	The TRS R consists of the following rules:
3.58/1.78	
3.58/1.78	   gcd(x, y) -> U1(leq(y, x), x, y)
3.58/1.78	   U1(false, x, y) -> gcd(y, x)
3.58/1.78	   gcd(add(x, y), y) -> gcd(x, y)
3.58/1.78	   gcd(y, add(x, y)) -> gcd(x, y)
3.58/1.78	   gcd(x, 0) -> x
3.58/1.78	   gcd(0, x) -> x
3.58/1.78	   add(0, y) -> y
3.58/1.78	   add(s(x), y) -> s(add(x, y))
3.58/1.78	
3.58/1.78	Q is empty.
3.58/1.78	We have to consider all minimal (P,Q,R)-chains.
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(5) DependencyGraphProof (EQUIVALENT)
3.58/1.78	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 2 less nodes.
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(6)
3.58/1.78	Complex Obligation (AND)
3.58/1.78	
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(7)
3.58/1.78	Obligation:
3.58/1.78	Q DP problem:
3.58/1.78	The TRS P consists of the following rules:
3.58/1.78	
3.58/1.78	   ADD(s(x), y) -> ADD(x, y)
3.58/1.78	
3.58/1.78	The TRS R consists of the following rules:
3.58/1.78	
3.58/1.78	   gcd(x, y) -> U1(leq(y, x), x, y)
3.58/1.78	   U1(false, x, y) -> gcd(y, x)
3.58/1.78	   gcd(add(x, y), y) -> gcd(x, y)
3.58/1.78	   gcd(y, add(x, y)) -> gcd(x, y)
3.58/1.78	   gcd(x, 0) -> x
3.58/1.78	   gcd(0, x) -> x
3.58/1.78	   add(0, y) -> y
3.58/1.78	   add(s(x), y) -> s(add(x, y))
3.58/1.78	
3.58/1.78	Q is empty.
3.58/1.78	We have to consider all minimal (P,Q,R)-chains.
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(8) UsableRulesProof (EQUIVALENT)
3.58/1.78	We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(9)
3.58/1.78	Obligation:
3.58/1.78	Q DP problem:
3.58/1.78	The TRS P consists of the following rules:
3.58/1.78	
3.58/1.78	   ADD(s(x), y) -> ADD(x, y)
3.58/1.78	
3.58/1.78	R is empty.
3.58/1.78	Q is empty.
3.58/1.78	We have to consider all minimal (P,Q,R)-chains.
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(10) QDPSizeChangeProof (EQUIVALENT)
3.58/1.78	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.58/1.78	
3.58/1.78	From the DPs we obtained the following set of size-change graphs:
3.58/1.78	*ADD(s(x), y) -> ADD(x, y)
3.58/1.78	The graph contains the following edges 1 > 1, 2 >= 2
3.58/1.78	
3.58/1.78	
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(11)
3.58/1.78	YES
3.58/1.78	
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(12)
3.58/1.78	Obligation:
3.58/1.78	Q DP problem:
3.58/1.78	The TRS P consists of the following rules:
3.58/1.78	
3.58/1.78	   GCD(y, add(x, y)) -> GCD(x, y)
3.58/1.78	   GCD(add(x, y), y) -> GCD(x, y)
3.58/1.78	
3.58/1.78	The TRS R consists of the following rules:
3.58/1.78	
3.58/1.78	   gcd(x, y) -> U1(leq(y, x), x, y)
3.58/1.78	   U1(false, x, y) -> gcd(y, x)
3.58/1.78	   gcd(add(x, y), y) -> gcd(x, y)
3.58/1.78	   gcd(y, add(x, y)) -> gcd(x, y)
3.58/1.78	   gcd(x, 0) -> x
3.58/1.78	   gcd(0, x) -> x
3.58/1.78	   add(0, y) -> y
3.58/1.78	   add(s(x), y) -> s(add(x, y))
3.58/1.78	
3.58/1.78	Q is empty.
3.58/1.78	We have to consider all minimal (P,Q,R)-chains.
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(13) UsableRulesProof (EQUIVALENT)
3.58/1.78	We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(14)
3.58/1.78	Obligation:
3.58/1.78	Q DP problem:
3.58/1.78	The TRS P consists of the following rules:
3.58/1.78	
3.58/1.78	   GCD(y, add(x, y)) -> GCD(x, y)
3.58/1.78	   GCD(add(x, y), y) -> GCD(x, y)
3.58/1.78	
3.58/1.78	R is empty.
3.58/1.78	Q is empty.
3.58/1.78	We have to consider all minimal (P,Q,R)-chains.
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(15) QDPSizeChangeProof (EQUIVALENT)
3.58/1.78	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.58/1.78	
3.58/1.78	From the DPs we obtained the following set of size-change graphs:
3.58/1.78	*GCD(y, add(x, y)) -> GCD(x, y)
3.58/1.78	The graph contains the following edges 2 > 1, 1 >= 2, 2 > 2
3.58/1.78	
3.58/1.78	
3.58/1.78	*GCD(add(x, y), y) -> GCD(x, y)
3.58/1.78	The graph contains the following edges 1 > 1, 1 > 2, 2 >= 2
3.58/1.78	
3.58/1.78	
3.58/1.78	----------------------------------------
3.58/1.78	
3.58/1.78	(16)
3.58/1.78	YES
3.72/1.81	EOF