4.25/1.94	YES
4.25/1.95	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
4.25/1.95	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.25/1.95	
4.25/1.95	
4.25/1.95	Quasi decreasingness of the given CTRS could be proven:
4.25/1.95	
4.25/1.95	(0) CTRS
4.25/1.95	(1) CTRSToQTRSProof [SOUND, 0 ms]
4.25/1.95	(2) QTRS
4.25/1.95	(3) DependencyPairsProof [EQUIVALENT, 0 ms]
4.25/1.95	(4) QDP
4.25/1.95	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
4.25/1.95	(6) AND
4.25/1.95	    (7) QDP
4.25/1.95	        (8) UsableRulesProof [EQUIVALENT, 0 ms]
4.25/1.95	        (9) QDP
4.25/1.95	        (10) QDPSizeChangeProof [EQUIVALENT, 0 ms]
4.25/1.95	        (11) YES
4.25/1.95	    (12) QDP
4.25/1.95	        (13) UsableRulesProof [EQUIVALENT, 0 ms]
4.25/1.95	        (14) QDP
4.25/1.95	        (15) QDPSizeChangeProof [EQUIVALENT, 0 ms]
4.25/1.95	        (16) YES
4.25/1.95	    (17) QDP
4.25/1.95	        (18) QDPOrderProof [EQUIVALENT, 36 ms]
4.25/1.95	        (19) QDP
4.25/1.95	        (20) DependencyGraphProof [EQUIVALENT, 0 ms]
4.25/1.95	        (21) TRUE
4.25/1.95	
4.25/1.95	
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(0)
4.25/1.95	Obligation:
4.25/1.95	Conditional term rewrite system:
4.25/1.95	The TRS R consists of the following rules:
4.25/1.95	
4.25/1.95	   less(x, 0) -> false
4.25/1.95	   less(0, s(x)) -> true
4.25/1.95	   less(s(x), s(y)) -> less(x, y)
4.25/1.95	   minus(0, s(y)) -> 0
4.25/1.95	   minus(x, 0) -> x
4.25/1.95	   minus(s(x), s(y)) -> minus(x, y)
4.25/1.95	   gcd(x, x) -> x
4.25/1.95	   gcd(s(x), 0) -> s(x)
4.25/1.95	   gcd(0, s(y)) -> s(y)
4.25/1.95	
4.25/1.95	The conditional TRS C consists of the following conditional rules:
4.25/1.95	
4.25/1.95	   gcd(s(x), s(y)) -> gcd(minus(x, y), s(y)) <= less(y, x) -> true
4.25/1.95	   gcd(s(x), s(y)) -> gcd(s(x), minus(y, x)) <= less(x, y) -> true
4.25/1.95	
4.25/1.95	
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(1) CTRSToQTRSProof (SOUND)
4.25/1.95	The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC].
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(2)
4.25/1.95	Obligation:
4.25/1.95	Q restricted rewrite system:
4.25/1.95	The TRS R consists of the following rules:
4.25/1.95	
4.25/1.95	   gcd(s(x), s(y)) -> U1(less(y, x), x, y)
4.25/1.95	   U1(true, x, y) -> gcd(minus(x, y), s(y))
4.25/1.95	   gcd(s(x), s(y)) -> U2(less(x, y), x, y)
4.25/1.95	   U2(true, x, y) -> gcd(s(x), minus(y, x))
4.25/1.95	   less(x, 0) -> false
4.25/1.95	   less(0, s(x)) -> true
4.25/1.95	   less(s(x), s(y)) -> less(x, y)
4.25/1.95	   minus(0, s(y)) -> 0
4.25/1.95	   minus(x, 0) -> x
4.25/1.95	   minus(s(x), s(y)) -> minus(x, y)
4.25/1.95	   gcd(x, x) -> x
4.25/1.95	   gcd(s(x), 0) -> s(x)
4.25/1.95	   gcd(0, s(y)) -> s(y)
4.25/1.95	
4.25/1.95	Q is empty.
4.25/1.95	
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(3) DependencyPairsProof (EQUIVALENT)
4.25/1.95	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(4)
4.25/1.95	Obligation:
4.25/1.95	Q DP problem:
4.25/1.95	The TRS P consists of the following rules:
4.25/1.95	
4.25/1.95	   GCD(s(x), s(y)) -> U1^1(less(y, x), x, y)
4.25/1.95	   GCD(s(x), s(y)) -> LESS(y, x)
4.25/1.95	   U1^1(true, x, y) -> GCD(minus(x, y), s(y))
4.25/1.95	   U1^1(true, x, y) -> MINUS(x, y)
4.25/1.95	   GCD(s(x), s(y)) -> U2^1(less(x, y), x, y)
4.25/1.95	   GCD(s(x), s(y)) -> LESS(x, y)
4.25/1.95	   U2^1(true, x, y) -> GCD(s(x), minus(y, x))
4.25/1.95	   U2^1(true, x, y) -> MINUS(y, x)
4.25/1.95	   LESS(s(x), s(y)) -> LESS(x, y)
4.25/1.95	   MINUS(s(x), s(y)) -> MINUS(x, y)
4.25/1.95	
4.25/1.95	The TRS R consists of the following rules:
4.25/1.95	
4.25/1.95	   gcd(s(x), s(y)) -> U1(less(y, x), x, y)
4.25/1.95	   U1(true, x, y) -> gcd(minus(x, y), s(y))
4.25/1.95	   gcd(s(x), s(y)) -> U2(less(x, y), x, y)
4.25/1.95	   U2(true, x, y) -> gcd(s(x), minus(y, x))
4.25/1.95	   less(x, 0) -> false
4.25/1.95	   less(0, s(x)) -> true
4.25/1.95	   less(s(x), s(y)) -> less(x, y)
4.25/1.95	   minus(0, s(y)) -> 0
4.25/1.95	   minus(x, 0) -> x
4.25/1.95	   minus(s(x), s(y)) -> minus(x, y)
4.25/1.95	   gcd(x, x) -> x
4.25/1.95	   gcd(s(x), 0) -> s(x)
4.25/1.95	   gcd(0, s(y)) -> s(y)
4.25/1.95	
4.25/1.95	Q is empty.
4.25/1.95	We have to consider all minimal (P,Q,R)-chains.
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(5) DependencyGraphProof (EQUIVALENT)
4.25/1.95	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 4 less nodes.
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(6)
4.25/1.95	Complex Obligation (AND)
4.25/1.95	
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(7)
4.25/1.95	Obligation:
4.25/1.95	Q DP problem:
4.25/1.95	The TRS P consists of the following rules:
4.25/1.95	
4.25/1.95	   MINUS(s(x), s(y)) -> MINUS(x, y)
4.25/1.95	
4.25/1.95	The TRS R consists of the following rules:
4.25/1.95	
4.25/1.95	   gcd(s(x), s(y)) -> U1(less(y, x), x, y)
4.25/1.95	   U1(true, x, y) -> gcd(minus(x, y), s(y))
4.25/1.95	   gcd(s(x), s(y)) -> U2(less(x, y), x, y)
4.25/1.95	   U2(true, x, y) -> gcd(s(x), minus(y, x))
4.25/1.95	   less(x, 0) -> false
4.25/1.95	   less(0, s(x)) -> true
4.25/1.95	   less(s(x), s(y)) -> less(x, y)
4.25/1.95	   minus(0, s(y)) -> 0
4.25/1.95	   minus(x, 0) -> x
4.25/1.95	   minus(s(x), s(y)) -> minus(x, y)
4.25/1.95	   gcd(x, x) -> x
4.25/1.95	   gcd(s(x), 0) -> s(x)
4.25/1.95	   gcd(0, s(y)) -> s(y)
4.25/1.95	
4.25/1.95	Q is empty.
4.25/1.95	We have to consider all minimal (P,Q,R)-chains.
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(8) UsableRulesProof (EQUIVALENT)
4.25/1.95	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.
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(9)
4.25/1.95	Obligation:
4.25/1.95	Q DP problem:
4.25/1.95	The TRS P consists of the following rules:
4.25/1.95	
4.25/1.95	   MINUS(s(x), s(y)) -> MINUS(x, y)
4.25/1.95	
4.25/1.95	R is empty.
4.25/1.95	Q is empty.
4.25/1.95	We have to consider all minimal (P,Q,R)-chains.
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(10) QDPSizeChangeProof (EQUIVALENT)
4.25/1.95	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. 
4.25/1.95	
4.25/1.95	From the DPs we obtained the following set of size-change graphs:
4.25/1.95	*MINUS(s(x), s(y)) -> MINUS(x, y)
4.25/1.95	The graph contains the following edges 1 > 1, 2 > 2
4.25/1.95	
4.25/1.95	
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(11)
4.25/1.95	YES
4.25/1.95	
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(12)
4.25/1.95	Obligation:
4.25/1.95	Q DP problem:
4.25/1.95	The TRS P consists of the following rules:
4.25/1.95	
4.25/1.95	   LESS(s(x), s(y)) -> LESS(x, y)
4.25/1.95	
4.25/1.95	The TRS R consists of the following rules:
4.25/1.95	
4.25/1.95	   gcd(s(x), s(y)) -> U1(less(y, x), x, y)
4.25/1.95	   U1(true, x, y) -> gcd(minus(x, y), s(y))
4.25/1.95	   gcd(s(x), s(y)) -> U2(less(x, y), x, y)
4.25/1.95	   U2(true, x, y) -> gcd(s(x), minus(y, x))
4.25/1.95	   less(x, 0) -> false
4.25/1.95	   less(0, s(x)) -> true
4.25/1.95	   less(s(x), s(y)) -> less(x, y)
4.25/1.95	   minus(0, s(y)) -> 0
4.25/1.95	   minus(x, 0) -> x
4.25/1.95	   minus(s(x), s(y)) -> minus(x, y)
4.25/1.95	   gcd(x, x) -> x
4.25/1.95	   gcd(s(x), 0) -> s(x)
4.25/1.95	   gcd(0, s(y)) -> s(y)
4.25/1.95	
4.25/1.95	Q is empty.
4.25/1.95	We have to consider all minimal (P,Q,R)-chains.
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(13) UsableRulesProof (EQUIVALENT)
4.25/1.95	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.
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(14)
4.25/1.95	Obligation:
4.25/1.95	Q DP problem:
4.25/1.95	The TRS P consists of the following rules:
4.25/1.95	
4.25/1.95	   LESS(s(x), s(y)) -> LESS(x, y)
4.25/1.95	
4.25/1.95	R is empty.
4.25/1.95	Q is empty.
4.25/1.95	We have to consider all minimal (P,Q,R)-chains.
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(15) QDPSizeChangeProof (EQUIVALENT)
4.25/1.95	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. 
4.25/1.95	
4.25/1.95	From the DPs we obtained the following set of size-change graphs:
4.25/1.95	*LESS(s(x), s(y)) -> LESS(x, y)
4.25/1.95	The graph contains the following edges 1 > 1, 2 > 2
4.25/1.95	
4.25/1.95	
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(16)
4.25/1.95	YES
4.25/1.95	
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(17)
4.25/1.95	Obligation:
4.25/1.95	Q DP problem:
4.25/1.95	The TRS P consists of the following rules:
4.25/1.95	
4.25/1.95	   U1^1(true, x, y) -> GCD(minus(x, y), s(y))
4.25/1.95	   GCD(s(x), s(y)) -> U1^1(less(y, x), x, y)
4.25/1.95	   GCD(s(x), s(y)) -> U2^1(less(x, y), x, y)
4.25/1.95	   U2^1(true, x, y) -> GCD(s(x), minus(y, x))
4.25/1.95	
4.25/1.95	The TRS R consists of the following rules:
4.25/1.95	
4.25/1.95	   gcd(s(x), s(y)) -> U1(less(y, x), x, y)
4.25/1.95	   U1(true, x, y) -> gcd(minus(x, y), s(y))
4.25/1.95	   gcd(s(x), s(y)) -> U2(less(x, y), x, y)
4.25/1.95	   U2(true, x, y) -> gcd(s(x), minus(y, x))
4.25/1.95	   less(x, 0) -> false
4.25/1.95	   less(0, s(x)) -> true
4.25/1.95	   less(s(x), s(y)) -> less(x, y)
4.25/1.95	   minus(0, s(y)) -> 0
4.25/1.95	   minus(x, 0) -> x
4.25/1.95	   minus(s(x), s(y)) -> minus(x, y)
4.25/1.95	   gcd(x, x) -> x
4.25/1.95	   gcd(s(x), 0) -> s(x)
4.25/1.95	   gcd(0, s(y)) -> s(y)
4.25/1.95	
4.25/1.95	Q is empty.
4.25/1.95	We have to consider all minimal (P,Q,R)-chains.
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(18) QDPOrderProof (EQUIVALENT)
4.25/1.95	We use the reduction pair processor [LPAR04,JAR06].
4.25/1.95	
4.25/1.95	
4.25/1.95	The following pairs can be oriented strictly and are deleted.
4.25/1.95	
4.25/1.95	   GCD(s(x), s(y)) -> U1^1(less(y, x), x, y)
4.25/1.95	   U2^1(true, x, y) -> GCD(s(x), minus(y, x))
4.25/1.95	The remaining pairs can at least be oriented weakly.
4.25/1.95	Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:
4.25/1.95	
4.25/1.95	POL( GCD_2(x_1, x_2) ) = max{0, 2x_1 + 2x_2 - 2}
4.25/1.95	POL( minus_2(x_1, x_2) ) = x_1
4.25/1.95	POL( 0 ) = 0
4.25/1.95	POL( s_1(x_1) ) = x_1 + 2
4.25/1.95	POL( U1^1_3(x_1, ..., x_3) ) = x_1 + 2x_2 + 2x_3
4.25/1.95	POL( U2^1_3(x_1, ..., x_3) ) = 2x_1 + 2x_2 + 2x_3 + 2
4.25/1.95	POL( less_2(x_1, x_2) ) = 2
4.25/1.95	POL( false ) = 2
4.25/1.95	POL( true ) = 2
4.25/1.95	
4.25/1.95	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
4.25/1.95	
4.25/1.95	   minus(0, s(y)) -> 0
4.25/1.95	   minus(x, 0) -> x
4.25/1.95	   minus(s(x), s(y)) -> minus(x, y)
4.25/1.95	   less(x, 0) -> false
4.25/1.95	   less(0, s(x)) -> true
4.25/1.95	   less(s(x), s(y)) -> less(x, y)
4.25/1.95	
4.25/1.95	
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(19)
4.25/1.95	Obligation:
4.25/1.95	Q DP problem:
4.25/1.95	The TRS P consists of the following rules:
4.25/1.95	
4.25/1.95	   U1^1(true, x, y) -> GCD(minus(x, y), s(y))
4.25/1.95	   GCD(s(x), s(y)) -> U2^1(less(x, y), x, y)
4.25/1.95	
4.25/1.95	The TRS R consists of the following rules:
4.25/1.95	
4.25/1.95	   gcd(s(x), s(y)) -> U1(less(y, x), x, y)
4.25/1.95	   U1(true, x, y) -> gcd(minus(x, y), s(y))
4.25/1.95	   gcd(s(x), s(y)) -> U2(less(x, y), x, y)
4.25/1.95	   U2(true, x, y) -> gcd(s(x), minus(y, x))
4.25/1.95	   less(x, 0) -> false
4.25/1.95	   less(0, s(x)) -> true
4.25/1.95	   less(s(x), s(y)) -> less(x, y)
4.25/1.95	   minus(0, s(y)) -> 0
4.25/1.95	   minus(x, 0) -> x
4.25/1.95	   minus(s(x), s(y)) -> minus(x, y)
4.25/1.95	   gcd(x, x) -> x
4.25/1.95	   gcd(s(x), 0) -> s(x)
4.25/1.95	   gcd(0, s(y)) -> s(y)
4.25/1.95	
4.25/1.95	Q is empty.
4.25/1.95	We have to consider all minimal (P,Q,R)-chains.
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(20) DependencyGraphProof (EQUIVALENT)
4.25/1.95	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes.
4.25/1.95	----------------------------------------
4.25/1.95	
4.25/1.95	(21)
4.25/1.95	TRUE
4.60/2.05	EOF