4.32/2.09	YES
4.63/2.10	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
4.63/2.10	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.63/2.10	
4.63/2.10	
4.63/2.10	Termination of the given ETRS could be proven:
4.63/2.10	
4.63/2.10	(0) ETRS
4.63/2.10	(1) EquationalDependencyPairsProof [EQUIVALENT, 0 ms]
4.63/2.10	(2) EDP
4.63/2.10	(3) EDependencyGraphProof [EQUIVALENT, 0 ms]
4.63/2.10	(4) AND
4.63/2.10	    (5) EDP
4.63/2.10	        (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
4.63/2.10	        (7) EDP
4.63/2.10	        (8) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
4.63/2.10	        (9) EDP
4.63/2.10	        (10) PisEmptyProof [EQUIVALENT, 0 ms]
4.63/2.10	        (11) YES
4.63/2.10	    (12) EDP
4.63/2.10	        (13) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
4.63/2.10	        (14) EDP
4.63/2.10	        (15) EDPPoloProof [EQUIVALENT, 0 ms]
4.63/2.10	        (16) EDP
4.63/2.10	        (17) PisEmptyProof [EQUIVALENT, 0 ms]
4.63/2.10	        (18) YES
4.63/2.10	    (19) EDP
4.63/2.10	        (20) EDPPoloProof [EQUIVALENT, 27 ms]
4.63/2.10	        (21) EDP
4.63/2.10	        (22) EDependencyGraphProof [EQUIVALENT, 0 ms]
4.63/2.10	        (23) TRUE
4.63/2.10	
4.63/2.10	
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(0)
4.63/2.10	Obligation:
4.63/2.10	Equational rewrite system:
4.63/2.10	The TRS R consists of the following rules:
4.63/2.10	
4.63/2.10	   le(0, y) -> true
4.63/2.10	   le(s(x), 0) -> false
4.63/2.10	   le(s(x), s(y)) -> le(x, y)
4.63/2.10	   minus(0, y) -> 0
4.63/2.10	   minus(s(x), y) -> if_minus(le(s(x), y), s(x), y)
4.63/2.10	   if_minus(true, s(x), y) -> 0
4.63/2.10	   if_minus(false, s(x), y) -> s(minus(x, y))
4.63/2.10	   gcd(0, y) -> y
4.63/2.10	   gcd(s(x), 0) -> s(x)
4.63/2.10	   gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y))
4.63/2.10	   if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y))
4.63/2.10	   if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x))
4.63/2.10	
4.63/2.10	The set E consists of the following equations:
4.63/2.10	
4.63/2.10	   gcd(x, y) == gcd(y, x)
4.63/2.10	
4.63/2.10	
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(1) EquationalDependencyPairsProof (EQUIVALENT)
4.63/2.10	Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem:
4.63/2.10	The TRS P consists of the following rules:
4.63/2.10	
4.63/2.10	   LE(s(x), s(y)) -> LE(x, y)
4.63/2.10	   MINUS(s(x), y) -> IF_MINUS(le(s(x), y), s(x), y)
4.63/2.10	   MINUS(s(x), y) -> LE(s(x), y)
4.63/2.10	   IF_MINUS(false, s(x), y) -> MINUS(x, y)
4.63/2.10	   GCD(s(x), s(y)) -> IF_GCD(le(y, x), s(x), s(y))
4.63/2.10	   GCD(s(x), s(y)) -> LE(y, x)
4.63/2.10	   IF_GCD(true, s(x), s(y)) -> GCD(minus(x, y), s(y))
4.63/2.10	   IF_GCD(true, s(x), s(y)) -> MINUS(x, y)
4.63/2.10	   IF_GCD(false, s(x), s(y)) -> GCD(minus(y, x), s(x))
4.63/2.10	   IF_GCD(false, s(x), s(y)) -> MINUS(y, x)
4.63/2.10	
4.63/2.10	The TRS R consists of the following rules:
4.63/2.10	
4.63/2.10	   le(0, y) -> true
4.63/2.10	   le(s(x), 0) -> false
4.63/2.10	   le(s(x), s(y)) -> le(x, y)
4.63/2.10	   minus(0, y) -> 0
4.63/2.10	   minus(s(x), y) -> if_minus(le(s(x), y), s(x), y)
4.63/2.10	   if_minus(true, s(x), y) -> 0
4.63/2.10	   if_minus(false, s(x), y) -> s(minus(x, y))
4.63/2.10	   gcd(0, y) -> y
4.63/2.10	   gcd(s(x), 0) -> s(x)
4.63/2.10	   gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y))
4.63/2.10	   if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y))
4.63/2.10	   if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x))
4.63/2.10	
4.63/2.10	The set E consists of the following equations:
4.63/2.10	
4.63/2.10	   gcd(x, y) == gcd(y, x)
4.63/2.10	
4.63/2.10	The set E# consists of the following equations:
4.63/2.10	
4.63/2.10	   GCD(x, y) == GCD(y, x)
4.63/2.10	
4.63/2.10	We have to consider all minimal (P,E#,R,E)-chains
4.63/2.10	
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(2)
4.63/2.10	Obligation:
4.63/2.10	The TRS P consists of the following rules:
4.63/2.10	
4.63/2.10	   LE(s(x), s(y)) -> LE(x, y)
4.63/2.10	   MINUS(s(x), y) -> IF_MINUS(le(s(x), y), s(x), y)
4.63/2.10	   MINUS(s(x), y) -> LE(s(x), y)
4.63/2.10	   IF_MINUS(false, s(x), y) -> MINUS(x, y)
4.63/2.10	   GCD(s(x), s(y)) -> IF_GCD(le(y, x), s(x), s(y))
4.63/2.10	   GCD(s(x), s(y)) -> LE(y, x)
4.63/2.10	   IF_GCD(true, s(x), s(y)) -> GCD(minus(x, y), s(y))
4.63/2.10	   IF_GCD(true, s(x), s(y)) -> MINUS(x, y)
4.63/2.10	   IF_GCD(false, s(x), s(y)) -> GCD(minus(y, x), s(x))
4.63/2.10	   IF_GCD(false, s(x), s(y)) -> MINUS(y, x)
4.63/2.10	
4.63/2.10	The TRS R consists of the following rules:
4.63/2.10	
4.63/2.10	   le(0, y) -> true
4.63/2.10	   le(s(x), 0) -> false
4.63/2.10	   le(s(x), s(y)) -> le(x, y)
4.63/2.10	   minus(0, y) -> 0
4.63/2.10	   minus(s(x), y) -> if_minus(le(s(x), y), s(x), y)
4.63/2.10	   if_minus(true, s(x), y) -> 0
4.63/2.10	   if_minus(false, s(x), y) -> s(minus(x, y))
4.63/2.10	   gcd(0, y) -> y
4.63/2.10	   gcd(s(x), 0) -> s(x)
4.63/2.10	   gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y))
4.63/2.10	   if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y))
4.63/2.10	   if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x))
4.63/2.10	
4.63/2.10	The set E consists of the following equations:
4.63/2.10	
4.63/2.10	   gcd(x, y) == gcd(y, x)
4.63/2.10	
4.63/2.10	The set E# consists of the following equations:
4.63/2.10	
4.63/2.10	   GCD(x, y) == GCD(y, x)
4.63/2.10	
4.63/2.10	We have to consider all minimal (P,E#,R,E)-chains
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(3) EDependencyGraphProof (EQUIVALENT)
4.63/2.10	The approximation of the Equational Dependency Graph [DA_STEIN] contains 3 SCCs with 4 less nodes.
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(4)
4.63/2.10	Complex Obligation (AND)
4.63/2.10	
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(5)
4.63/2.10	Obligation:
4.63/2.10	The TRS P consists of the following rules:
4.63/2.10	
4.63/2.10	   LE(s(x), s(y)) -> LE(x, y)
4.63/2.10	
4.63/2.10	The TRS R consists of the following rules:
4.63/2.10	
4.63/2.10	   le(0, y) -> true
4.63/2.10	   le(s(x), 0) -> false
4.63/2.10	   le(s(x), s(y)) -> le(x, y)
4.63/2.10	   minus(0, y) -> 0
4.63/2.10	   minus(s(x), y) -> if_minus(le(s(x), y), s(x), y)
4.63/2.10	   if_minus(true, s(x), y) -> 0
4.63/2.10	   if_minus(false, s(x), y) -> s(minus(x, y))
4.63/2.10	   gcd(0, y) -> y
4.63/2.10	   gcd(s(x), 0) -> s(x)
4.63/2.10	   gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y))
4.63/2.10	   if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y))
4.63/2.10	   if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x))
4.63/2.10	
4.63/2.10	The set E consists of the following equations:
4.63/2.10	
4.63/2.10	   gcd(x, y) == gcd(y, x)
4.63/2.10	
4.63/2.10	The set E# consists of the following equations:
4.63/2.10	
4.63/2.10	   GCD(x, y) == GCD(y, x)
4.63/2.10	
4.63/2.10	We have to consider all minimal (P,E#,R,E)-chains
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(6) ESharpUsableEquationsProof (EQUIVALENT)
4.63/2.10	We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
4.63/2.10	   GCD(x, y) == GCD(y, x)
4.63/2.10	
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(7)
4.63/2.10	Obligation:
4.63/2.10	The TRS P consists of the following rules:
4.63/2.10	
4.63/2.10	   LE(s(x), s(y)) -> LE(x, y)
4.63/2.10	
4.63/2.10	The TRS R consists of the following rules:
4.63/2.10	
4.63/2.10	   le(0, y) -> true
4.63/2.10	   le(s(x), 0) -> false
4.63/2.10	   le(s(x), s(y)) -> le(x, y)
4.63/2.10	   minus(0, y) -> 0
4.63/2.10	   minus(s(x), y) -> if_minus(le(s(x), y), s(x), y)
4.63/2.10	   if_minus(true, s(x), y) -> 0
4.63/2.10	   if_minus(false, s(x), y) -> s(minus(x, y))
4.63/2.10	   gcd(0, y) -> y
4.63/2.10	   gcd(s(x), 0) -> s(x)
4.63/2.10	   gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y))
4.63/2.10	   if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y))
4.63/2.10	   if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x))
4.63/2.10	
4.63/2.10	The set E consists of the following equations:
4.63/2.10	
4.63/2.10	   gcd(x, y) == gcd(y, x)
4.63/2.10	
4.63/2.10	E# is empty.
4.63/2.10	We have to consider all minimal (P,E#,R,E)-chains
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(8) EUsableRulesReductionPairsProof (EQUIVALENT)
4.63/2.10	By using the improved usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding improved usable rules can be oriented non-strictly, the improved  usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and improved usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.
4.63/2.10	
4.63/2.10	The following dependency pairs can be deleted:
4.63/2.10	
4.63/2.10	   LE(s(x), s(y)) -> LE(x, y)
4.63/2.10	The following rules are removed from R:
4.63/2.10	
4.63/2.10	   le(0, y) -> true
4.63/2.10	   le(s(x), 0) -> false
4.63/2.10	   le(s(x), s(y)) -> le(x, y)
4.63/2.10	   minus(0, y) -> 0
4.63/2.10	   minus(s(x), y) -> if_minus(le(s(x), y), s(x), y)
4.63/2.10	   if_minus(true, s(x), y) -> 0
4.63/2.10	   if_minus(false, s(x), y) -> s(minus(x, y))
4.63/2.10	   gcd(0, y) -> y
4.63/2.10	   gcd(s(x), 0) -> s(x)
4.63/2.10	   gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y))
4.63/2.10	   if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y))
4.63/2.10	   if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x))
4.63/2.10	The following equations are removed from E:
4.63/2.10	
4.63/2.10	   gcd(x, y) == gcd(y, x)
4.63/2.10	Used ordering: POLO with Polynomial interpretation [POLO]:
4.63/2.10	
4.63/2.10	   POL(LE(x_1, x_2)) = 3*x_1 + 3*x_2
4.63/2.10	   POL(s(x_1)) = x_1
4.63/2.10	
4.63/2.10	
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(9)
4.63/2.10	Obligation:
4.63/2.10	P is empty.
4.63/2.10	R is empty.
4.63/2.10	E is empty.
4.63/2.10	E# is empty.
4.63/2.10	We have to consider all minimal (P,E#,R,E)-chains
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(10) PisEmptyProof (EQUIVALENT)
4.63/2.10	The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(11)
4.63/2.10	YES
4.63/2.10	
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(12)
4.63/2.10	Obligation:
4.63/2.10	The TRS P consists of the following rules:
4.63/2.10	
4.63/2.10	   IF_MINUS(false, s(x), y) -> MINUS(x, y)
4.63/2.10	   MINUS(s(x), y) -> IF_MINUS(le(s(x), y), s(x), y)
4.63/2.10	
4.63/2.10	The TRS R consists of the following rules:
4.63/2.10	
4.63/2.10	   le(0, y) -> true
4.63/2.10	   le(s(x), 0) -> false
4.63/2.10	   le(s(x), s(y)) -> le(x, y)
4.63/2.10	   minus(0, y) -> 0
4.63/2.10	   minus(s(x), y) -> if_minus(le(s(x), y), s(x), y)
4.63/2.10	   if_minus(true, s(x), y) -> 0
4.63/2.10	   if_minus(false, s(x), y) -> s(minus(x, y))
4.63/2.10	   gcd(0, y) -> y
4.63/2.10	   gcd(s(x), 0) -> s(x)
4.63/2.10	   gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y))
4.63/2.10	   if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y))
4.63/2.10	   if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x))
4.63/2.10	
4.63/2.10	The set E consists of the following equations:
4.63/2.10	
4.63/2.10	   gcd(x, y) == gcd(y, x)
4.63/2.10	
4.63/2.10	The set E# consists of the following equations:
4.63/2.10	
4.63/2.10	   GCD(x, y) == GCD(y, x)
4.63/2.10	
4.63/2.10	We have to consider all minimal (P,E#,R,E)-chains
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(13) ESharpUsableEquationsProof (EQUIVALENT)
4.63/2.10	We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
4.63/2.10	   GCD(x, y) == GCD(y, x)
4.63/2.10	
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(14)
4.63/2.10	Obligation:
4.63/2.10	The TRS P consists of the following rules:
4.63/2.10	
4.63/2.10	   IF_MINUS(false, s(x), y) -> MINUS(x, y)
4.63/2.10	   MINUS(s(x), y) -> IF_MINUS(le(s(x), y), s(x), y)
4.63/2.10	
4.63/2.10	The TRS R consists of the following rules:
4.63/2.10	
4.63/2.10	   le(0, y) -> true
4.63/2.10	   le(s(x), 0) -> false
4.63/2.10	   le(s(x), s(y)) -> le(x, y)
4.63/2.10	   minus(0, y) -> 0
4.63/2.10	   minus(s(x), y) -> if_minus(le(s(x), y), s(x), y)
4.63/2.10	   if_minus(true, s(x), y) -> 0
4.63/2.10	   if_minus(false, s(x), y) -> s(minus(x, y))
4.63/2.10	   gcd(0, y) -> y
4.63/2.10	   gcd(s(x), 0) -> s(x)
4.63/2.10	   gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y))
4.63/2.10	   if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y))
4.63/2.10	   if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x))
4.63/2.10	
4.63/2.10	The set E consists of the following equations:
4.63/2.10	
4.63/2.10	   gcd(x, y) == gcd(y, x)
4.63/2.10	
4.63/2.10	E# is empty.
4.63/2.10	We have to consider all minimal (P,E#,R,E)-chains
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(15) EDPPoloProof (EQUIVALENT)
4.63/2.10	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented.
4.63/2.10	
4.63/2.10	
4.63/2.10	   IF_MINUS(false, s(x), y) -> MINUS(x, y)
4.63/2.10	   MINUS(s(x), y) -> IF_MINUS(le(s(x), y), s(x), y)
4.63/2.10	With the implicit AFS there is no usable rule of R.
4.63/2.10	
4.63/2.10	
4.63/2.10	There is no equation of E#.
4.63/2.10	
4.63/2.10	
4.63/2.10	With the implicit AFS there is no usable equation of E.
4.63/2.10	
4.63/2.10	
4.63/2.10	Used ordering: POLO with Polynomial interpretation [POLO]:
4.63/2.10	
4.63/2.10	   POL(0) = 0
4.63/2.10	   POL(IF_MINUS(x_1, x_2, x_3)) = 2*x_2 + 3*x_3
4.63/2.10	   POL(MINUS(x_1, x_2)) = 3*x_1 + 3*x_2
4.63/2.10	   POL(false) = 0
4.63/2.10	   POL(le(x_1, x_2)) = 0
4.63/2.10	   POL(s(x_1)) = 3 + 2*x_1
4.63/2.10	   POL(true) = 3
4.63/2.10	
4.63/2.10	
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(16)
4.63/2.10	Obligation:
4.63/2.10	P is empty.
4.63/2.10	The TRS R consists of the following rules:
4.63/2.10	
4.63/2.10	   le(0, y) -> true
4.63/2.10	   le(s(x), 0) -> false
4.63/2.10	   le(s(x), s(y)) -> le(x, y)
4.63/2.10	   minus(0, y) -> 0
4.63/2.10	   minus(s(x), y) -> if_minus(le(s(x), y), s(x), y)
4.63/2.10	   if_minus(true, s(x), y) -> 0
4.63/2.10	   if_minus(false, s(x), y) -> s(minus(x, y))
4.63/2.10	   gcd(0, y) -> y
4.63/2.10	   gcd(s(x), 0) -> s(x)
4.63/2.10	   gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y))
4.63/2.10	   if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y))
4.63/2.10	   if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x))
4.63/2.10	
4.63/2.10	The set E consists of the following equations:
4.63/2.10	
4.63/2.10	   gcd(x, y) == gcd(y, x)
4.63/2.10	
4.63/2.10	E# is empty.
4.63/2.10	We have to consider all minimal (P,E#,R,E)-chains
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(17) PisEmptyProof (EQUIVALENT)
4.63/2.10	The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(18)
4.63/2.10	YES
4.63/2.10	
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(19)
4.63/2.10	Obligation:
4.63/2.10	The TRS P consists of the following rules:
4.63/2.10	
4.63/2.10	   IF_GCD(false, s(x), s(y)) -> GCD(minus(y, x), s(x))
4.63/2.10	   GCD(s(x), s(y)) -> IF_GCD(le(y, x), s(x), s(y))
4.63/2.10	   IF_GCD(true, s(x), s(y)) -> GCD(minus(x, y), s(y))
4.63/2.10	
4.63/2.10	The TRS R consists of the following rules:
4.63/2.10	
4.63/2.10	   le(0, y) -> true
4.63/2.10	   le(s(x), 0) -> false
4.63/2.10	   le(s(x), s(y)) -> le(x, y)
4.63/2.10	   minus(0, y) -> 0
4.63/2.10	   minus(s(x), y) -> if_minus(le(s(x), y), s(x), y)
4.63/2.10	   if_minus(true, s(x), y) -> 0
4.63/2.10	   if_minus(false, s(x), y) -> s(minus(x, y))
4.63/2.10	   gcd(0, y) -> y
4.63/2.10	   gcd(s(x), 0) -> s(x)
4.63/2.10	   gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y))
4.63/2.10	   if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y))
4.63/2.10	   if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x))
4.63/2.10	
4.63/2.10	The set E consists of the following equations:
4.63/2.10	
4.63/2.10	   gcd(x, y) == gcd(y, x)
4.63/2.10	
4.63/2.10	The set E# consists of the following equations:
4.63/2.10	
4.63/2.10	   GCD(x, y) == GCD(y, x)
4.63/2.10	
4.63/2.10	We have to consider all minimal (P,E#,R,E)-chains
4.63/2.10	----------------------------------------
4.63/2.10	
4.63/2.10	(20) EDPPoloProof (EQUIVALENT)
4.63/2.10	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented.
4.63/2.10	
4.63/2.10	
4.63/2.10	   IF_GCD(false, s(x), s(y)) -> GCD(minus(y, x), s(x))
4.63/2.10	   IF_GCD(true, s(x), s(y)) -> GCD(minus(x, y), s(y))
4.63/2.10	The remaining Dependency Pairs were at least non-strictly oriented.
4.63/2.10	
4.63/2.10	
4.63/2.10	   GCD(s(x), s(y)) -> IF_GCD(le(y, x), s(x), s(y))
4.63/2.10	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
4.63/2.10	
4.63/2.10	
4.63/2.10	   if_minus(false, s(x), y) -> s(minus(x, y))
4.63/2.10	   if_minus(true, s(x), y) -> 0
4.63/2.10	   minus(s(x), y) -> if_minus(le(s(x), y), s(x), y)
4.63/2.10	   minus(0, y) -> 0
4.63/2.10	We had to orient the following equations of E# equivalently.
4.63/2.10	
4.63/2.10	
4.63/2.10	   GCD(x, y) == GCD(y, x)
4.63/2.10	With the implicit AFS there is no usable equation of E.
4.63/2.10	
4.63/2.10	
4.63/2.10	Used ordering: POLO with Polynomial interpretation [POLO]:
4.63/2.10	
4.63/2.10	   POL(0) = 0
4.63/2.10	   POL(GCD(x_1, x_2)) = 2*x_1 + 2*x_2
4.63/2.10	   POL(IF_GCD(x_1, x_2, x_3)) = 2*x_2 + 2*x_3
4.63/2.10	   POL(false) = 0
4.63/2.10	   POL(if_minus(x_1, x_2, x_3)) = x_2
4.63/2.10	   POL(le(x_1, x_2)) = 0
4.63/2.10	   POL(minus(x_1, x_2)) = x_1
4.63/2.11	   POL(s(x_1)) = 2 + x_1
4.63/2.11	   POL(true) = 0
4.63/2.11	
4.63/2.11	
4.63/2.11	----------------------------------------
4.63/2.11	
4.63/2.11	(21)
4.63/2.11	Obligation:
4.63/2.11	The TRS P consists of the following rules:
4.63/2.11	
4.63/2.11	   GCD(s(x), s(y)) -> IF_GCD(le(y, x), s(x), s(y))
4.63/2.11	
4.63/2.11	The TRS R consists of the following rules:
4.63/2.11	
4.63/2.11	   le(0, y) -> true
4.63/2.11	   le(s(x), 0) -> false
4.63/2.11	   le(s(x), s(y)) -> le(x, y)
4.63/2.11	   minus(0, y) -> 0
4.63/2.11	   minus(s(x), y) -> if_minus(le(s(x), y), s(x), y)
4.63/2.11	   if_minus(true, s(x), y) -> 0
4.63/2.11	   if_minus(false, s(x), y) -> s(minus(x, y))
4.63/2.11	   gcd(0, y) -> y
4.63/2.11	   gcd(s(x), 0) -> s(x)
4.63/2.11	   gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y))
4.63/2.11	   if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y))
4.63/2.11	   if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x))
4.63/2.11	
4.63/2.11	The set E consists of the following equations:
4.63/2.11	
4.63/2.11	   gcd(x, y) == gcd(y, x)
4.63/2.11	
4.63/2.11	The set E# consists of the following equations:
4.63/2.11	
4.63/2.11	   GCD(x, y) == GCD(y, x)
4.63/2.11	
4.63/2.11	We have to consider all minimal (P,E#,R,E)-chains
4.63/2.11	----------------------------------------
4.63/2.11	
4.63/2.11	(22) EDependencyGraphProof (EQUIVALENT)
4.63/2.11	The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 1 less node.
4.63/2.11	----------------------------------------
4.63/2.11	
4.63/2.11	(23)
4.63/2.11	TRUE
4.63/2.13	EOF