Termination w.r.t. Q of the given QTRS could not be shown:

(0) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(true, x, y) → x
if(false, x, y) → mod(minus(x, y), y)
gcd(x, 0) → x
gcd(0, s(y)) → s(y)
gcd(s(x), s(y)) → gcd(mod(s(x), s(y)), mod(s(y), s(x)))
lt(x, 0) → false
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)

Q is empty.

(1) Overlay + Local Confluence (EQUIVALENT transformation)

The TRS is overlay and locally confluent. By [NOC] we can switch to innermost.

(2) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(true, x, y) → x
if(false, x, y) → mod(minus(x, y), y)
gcd(x, 0) → x
gcd(0, s(y)) → s(y)
gcd(s(x), s(y)) → gcd(mod(s(x), s(y)), mod(s(y), s(x)))
lt(x, 0) → false
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
gcd(x0, 0)
gcd(0, s(x0))
gcd(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

(3) DependencyPairsProof (EQUIVALENT transformation)

Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.

(4) Obligation:

Q DP problem:
The TRS P consists of the following rules:

MINUS(s(x), s(y)) → MINUS(x, y)
MOD(x, s(y)) → IF(lt(x, s(y)), x, s(y))
MOD(x, s(y)) → LT(x, s(y))
IF(false, x, y) → MOD(minus(x, y), y)
IF(false, x, y) → MINUS(x, y)
GCD(s(x), s(y)) → GCD(mod(s(x), s(y)), mod(s(y), s(x)))
GCD(s(x), s(y)) → MOD(s(x), s(y))
GCD(s(x), s(y)) → MOD(s(y), s(x))
LT(s(x), s(y)) → LT(x, y)

The TRS R consists of the following rules:

minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(true, x, y) → x
if(false, x, y) → mod(minus(x, y), y)
gcd(x, 0) → x
gcd(0, s(y)) → s(y)
gcd(s(x), s(y)) → gcd(mod(s(x), s(y)), mod(s(y), s(x)))
lt(x, 0) → false
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
gcd(x0, 0)
gcd(0, s(x0))
gcd(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(5) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 4 less nodes.

(6) Complex Obligation (AND)

(7) Obligation:

Q DP problem:
The TRS P consists of the following rules:

LT(s(x), s(y)) → LT(x, y)

The TRS R consists of the following rules:

minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(true, x, y) → x
if(false, x, y) → mod(minus(x, y), y)
gcd(x, 0) → x
gcd(0, s(y)) → s(y)
gcd(s(x), s(y)) → gcd(mod(s(x), s(y)), mod(s(y), s(x)))
lt(x, 0) → false
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
gcd(x0, 0)
gcd(0, s(x0))
gcd(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(8) UsableRulesProof (EQUIVALENT transformation)

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.

(9) Obligation:

Q DP problem:
The TRS P consists of the following rules:

LT(s(x), s(y)) → LT(x, y)

R is empty.
The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
gcd(x0, 0)
gcd(0, s(x0))
gcd(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(10) QReductionProof (EQUIVALENT transformation)

We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
gcd(x0, 0)
gcd(0, s(x0))
gcd(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

(11) Obligation:

Q DP problem:
The TRS P consists of the following rules:

LT(s(x), s(y)) → LT(x, y)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(12) QDPSizeChangeProof (EQUIVALENT transformation)

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.

From the DPs we obtained the following set of size-change graphs:

• LT(s(x), s(y)) → LT(x, y)
  The graph contains the following edges 1 > 1, 2 > 2

(13) YES

(14) Obligation:

Q DP problem:
The TRS P consists of the following rules:

MINUS(s(x), s(y)) → MINUS(x, y)

The TRS R consists of the following rules:

minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(true, x, y) → x
if(false, x, y) → mod(minus(x, y), y)
gcd(x, 0) → x
gcd(0, s(y)) → s(y)
gcd(s(x), s(y)) → gcd(mod(s(x), s(y)), mod(s(y), s(x)))
lt(x, 0) → false
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
gcd(x0, 0)
gcd(0, s(x0))
gcd(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(15) UsableRulesProof (EQUIVALENT transformation)

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.

(16) Obligation:

Q DP problem:
The TRS P consists of the following rules:

MINUS(s(x), s(y)) → MINUS(x, y)

R is empty.
The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
gcd(x0, 0)
gcd(0, s(x0))
gcd(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(17) QReductionProof (EQUIVALENT transformation)

We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
gcd(x0, 0)
gcd(0, s(x0))
gcd(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

(18) Obligation:

Q DP problem:
The TRS P consists of the following rules:

MINUS(s(x), s(y)) → MINUS(x, y)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(19) QDPSizeChangeProof (EQUIVALENT transformation)

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.

From the DPs we obtained the following set of size-change graphs:

• MINUS(s(x), s(y)) → MINUS(x, y)
  The graph contains the following edges 1 > 1, 2 > 2

(20) YES

(21) Obligation:

Q DP problem:
The TRS P consists of the following rules:

IF(false, x, y) → MOD(minus(x, y), y)
MOD(x, s(y)) → IF(lt(x, s(y)), x, s(y))

The TRS R consists of the following rules:

minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(true, x, y) → x
if(false, x, y) → mod(minus(x, y), y)
gcd(x, 0) → x
gcd(0, s(y)) → s(y)
gcd(s(x), s(y)) → gcd(mod(s(x), s(y)), mod(s(y), s(x)))
lt(x, 0) → false
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
gcd(x0, 0)
gcd(0, s(x0))
gcd(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(22) UsableRulesProof (EQUIVALENT transformation)

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.

(23) Obligation:

Q DP problem:
The TRS P consists of the following rules:

IF(false, x, y) → MOD(minus(x, y), y)
MOD(x, s(y)) → IF(lt(x, s(y)), x, s(y))

The TRS R consists of the following rules:

lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
lt(x, 0) → false
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
gcd(x0, 0)
gcd(0, s(x0))
gcd(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(24) QReductionProof (EQUIVALENT transformation)

We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
gcd(x0, 0)
gcd(0, s(x0))
gcd(s(x0), s(x1))

(25) Obligation:

Q DP problem:
The TRS P consists of the following rules:

IF(false, x, y) → MOD(minus(x, y), y)
MOD(x, s(y)) → IF(lt(x, s(y)), x, s(y))

The TRS R consists of the following rules:

lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
lt(x, 0) → false
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(26) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule MOD(x, s(y)) → IF(lt(x, s(y)), x, s(y)) at position [0] we obtained the following new rules [LPAR04]:

MOD(0, s(x0)) → IF(true, 0, s(x0))
MOD(s(x0), s(x1)) → IF(lt(x0, x1), s(x0), s(x1))

(27) Obligation:

Q DP problem:
The TRS P consists of the following rules:

IF(false, x, y) → MOD(minus(x, y), y)
MOD(0, s(x0)) → IF(true, 0, s(x0))
MOD(s(x0), s(x1)) → IF(lt(x0, x1), s(x0), s(x1))

The TRS R consists of the following rules:

lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
lt(x, 0) → false
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(28) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.

(29) Obligation:

Q DP problem:
The TRS P consists of the following rules:

MOD(s(x0), s(x1)) → IF(lt(x0, x1), s(x0), s(x1))
IF(false, x, y) → MOD(minus(x, y), y)

The TRS R consists of the following rules:

lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
lt(x, 0) → false
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(30) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule IF(false, x, y) → MOD(minus(x, y), y) at position [0] we obtained the following new rules [LPAR04]:

IF(false, 0, x0) → MOD(0, x0)
IF(false, s(x0), 0) → MOD(s(x0), 0)
IF(false, s(x0), s(x1)) → MOD(minus(x0, x1), s(x1))

(31) Obligation:

Q DP problem:
The TRS P consists of the following rules:

MOD(s(x0), s(x1)) → IF(lt(x0, x1), s(x0), s(x1))
IF(false, 0, x0) → MOD(0, x0)
IF(false, s(x0), 0) → MOD(s(x0), 0)
IF(false, s(x0), s(x1)) → MOD(minus(x0, x1), s(x1))

The TRS R consists of the following rules:

lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
lt(x, 0) → false
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(32) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes.

(33) Obligation:

Q DP problem:
The TRS P consists of the following rules:

IF(false, s(x0), s(x1)) → MOD(minus(x0, x1), s(x1))
MOD(s(x0), s(x1)) → IF(lt(x0, x1), s(x0), s(x1))

The TRS R consists of the following rules:

lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
lt(x, 0) → false
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(34) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].

The following pairs can be oriented strictly and are deleted.

MOD(s(x0), s(x1)) → IF(lt(x0, x1), s(x0), s(x1))

The remaining pairs can at least be oriented weakly.
Used ordering: Polynomial interpretation [POLO]:

POL(0) = 0   
POL(IF(x₁, x₂, x₃)) = x₂ + x₃   
POL(MOD(x₁, x₂)) = 1 + x₁ + x₂   
POL(false) = 0   
POL(lt(x₁, x₂)) = 0   
POL(minus(x₁, x₂)) = x₁   
POL(s(x₁)) = 1 + x₁   
POL(true) = 0   

The following usable rules [FROCOS05] were oriented:

minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)

(35) Obligation:

Q DP problem:
The TRS P consists of the following rules:

IF(false, s(x0), s(x1)) → MOD(minus(x0, x1), s(x1))

The TRS R consists of the following rules:

lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
lt(x, 0) → false
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(36) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.

(37) TRUE

(38) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x), s(y)) → GCD(mod(s(x), s(y)), mod(s(y), s(x)))

The TRS R consists of the following rules:

minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(true, x, y) → x
if(false, x, y) → mod(minus(x, y), y)
gcd(x, 0) → x
gcd(0, s(y)) → s(y)
gcd(s(x), s(y)) → gcd(mod(s(x), s(y)), mod(s(y), s(x)))
lt(x, 0) → false
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
gcd(x0, 0)
gcd(0, s(x0))
gcd(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(39) UsableRulesProof (EQUIVALENT transformation)

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.

(40) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x), s(y)) → GCD(mod(s(x), s(y)), mod(s(y), s(x)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
gcd(x0, 0)
gcd(0, s(x0))
gcd(s(x0), s(x1))
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(41) QReductionProof (EQUIVALENT transformation)

We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

gcd(x0, 0)
gcd(0, s(x0))
gcd(s(x0), s(x1))

(42) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x), s(y)) → GCD(mod(s(x), s(y)), mod(s(y), s(x)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(43) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(x), s(y)) → GCD(mod(s(x), s(y)), mod(s(y), s(x))) at position [0] we obtained the following new rules [LPAR04]:

GCD(s(x), s(y)) → GCD(if(lt(s(x), s(y)), s(x), s(y)), mod(s(y), s(x)))

(44) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x), s(y)) → GCD(if(lt(s(x), s(y)), s(x), s(y)), mod(s(y), s(x)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(45) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(x), s(y)) → GCD(if(lt(s(x), s(y)), s(x), s(y)), mod(s(y), s(x))) at position [0,0] we obtained the following new rules [LPAR04]:

GCD(s(x), s(y)) → GCD(if(lt(x, y), s(x), s(y)), mod(s(y), s(x)))

(46) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x), s(y)) → GCD(if(lt(x, y), s(x), s(y)), mod(s(y), s(x)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(47) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(x), s(y)) → GCD(if(lt(x, y), s(x), s(y)), mod(s(y), s(x))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(x), s(y)) → GCD(if(lt(x, y), s(x), s(y)), if(lt(s(y), s(x)), s(y), s(x)))

(48) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x), s(y)) → GCD(if(lt(x, y), s(x), s(y)), if(lt(s(y), s(x)), s(y), s(x)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(49) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(x), s(y)) → GCD(if(lt(x, y), s(x), s(y)), if(lt(s(y), s(x)), s(y), s(x))) at position [1,0] we obtained the following new rules [LPAR04]:

GCD(s(x), s(y)) → GCD(if(lt(x, y), s(x), s(y)), if(lt(y, x), s(y), s(x)))

(50) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x), s(y)) → GCD(if(lt(x, y), s(x), s(y)), if(lt(y, x), s(y), s(x)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(51) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule GCD(s(x), s(y)) → GCD(if(lt(x, y), s(x), s(y)), if(lt(y, x), s(y), s(x))) at position [0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(if(true, s(0), s(s(x0))), if(lt(s(x0), 0), s(s(x0)), s(0)))
GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(s(x1), s(x0)), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(false, s(x0), s(0)), if(lt(0, x0), s(0), s(x0)))

(52) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(x0))) → GCD(if(true, s(0), s(s(x0))), if(lt(s(x0), 0), s(s(x0)), s(0)))
GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(s(x1), s(x0)), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(false, s(x0), s(0)), if(lt(0, x0), s(0), s(x0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(53) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(if(true, s(0), s(s(x0))), if(lt(s(x0), 0), s(s(x0)), s(0))) at position [0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(s(x0), 0), s(s(x0)), s(0)))

(54) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(s(x1), s(x0)), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(false, s(x0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(s(x0), 0), s(s(x0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(55) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(s(x1), s(x0)), s(s(x1)), s(s(x0)))) at position [1,0] we obtained the following new rules [LPAR04]:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))

(56) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(false, s(x0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(s(x0), 0), s(s(x0)), s(0)))
GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(57) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(x0), s(0)) → GCD(if(false, s(x0), s(0)), if(lt(0, x0), s(0), s(x0))) at position [0] we obtained the following new rules [LPAR04]:

GCD(s(x0), s(0)) → GCD(mod(minus(s(x0), s(0)), s(0)), if(lt(0, x0), s(0), s(x0)))

(58) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(s(x0), 0), s(s(x0)), s(0)))
GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(mod(minus(s(x0), s(0)), s(0)), if(lt(0, x0), s(0), s(x0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(59) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(s(x0), 0), s(s(x0)), s(0))) at position [1,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(s(0), if(false, s(s(x0)), s(0)))

(60) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(mod(minus(s(x0), s(0)), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(false, s(s(x0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(61) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(x0), s(0)) → GCD(mod(minus(s(x0), s(0)), s(0)), if(lt(0, x0), s(0), s(x0))) at position [0] we obtained the following new rules [LPAR04]:

GCD(s(x0), s(0)) → GCD(if(lt(minus(s(x0), s(0)), s(0)), minus(s(x0), s(0)), s(0)), if(lt(0, x0), s(0), s(x0)))

(62) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(0), s(s(x0))) → GCD(s(0), if(false, s(s(x0)), s(0)))
GCD(s(x0), s(0)) → GCD(if(lt(minus(s(x0), s(0)), s(0)), minus(s(x0), s(0)), s(0)), if(lt(0, x0), s(0), s(x0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(63) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(s(0), if(false, s(s(x0)), s(0))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(s(0), mod(minus(s(s(x0)), s(0)), s(0)))

(64) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(lt(minus(s(x0), s(0)), s(0)), minus(s(x0), s(0)), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), mod(minus(s(s(x0)), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(65) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(x0), s(0)) → GCD(if(lt(minus(s(x0), s(0)), s(0)), minus(s(x0), s(0)), s(0)), if(lt(0, x0), s(0), s(x0))) at position [0,0,0] we obtained the following new rules [LPAR04]:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(s(x0), s(0)), s(0)), if(lt(0, x0), s(0), s(x0)))

(66) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(0), s(s(x0))) → GCD(s(0), mod(minus(s(s(x0)), s(0)), s(0)))
GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(s(x0), s(0)), s(0)), if(lt(0, x0), s(0), s(x0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(67) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(s(0), mod(minus(s(s(x0)), s(0)), s(0))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(s(s(x0)), s(0)), s(0)), minus(s(s(x0)), s(0)), s(0)))

(68) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(s(x0), s(0)), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(s(s(x0)), s(0)), s(0)), minus(s(s(x0)), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(69) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(s(x0), s(0)), s(0)), if(lt(0, x0), s(0), s(x0))) at position [0,1] we obtained the following new rules [LPAR04]:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))

(70) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(s(s(x0)), s(0)), s(0)), minus(s(s(x0)), s(0)), s(0)))
GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(71) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(s(s(x0)), s(0)), s(0)), minus(s(s(x0)), s(0)), s(0))) at position [1,0,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(s(x0), 0), s(0)), minus(s(s(x0)), s(0)), s(0)))

(72) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(s(x0), 0), s(0)), minus(s(s(x0)), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(73) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(s(x0), 0), s(0)), minus(s(s(x0)), s(0)), s(0))) at position [1,0,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(s(x0), s(0)), minus(s(s(x0)), s(0)), s(0)))

(74) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(s(x0), s(0)), minus(s(s(x0)), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(75) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(s(x0), s(0)), minus(s(s(x0)), s(0)), s(0))) at position [1,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(x0, 0), minus(s(s(x0)), s(0)), s(0)))

(76) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(x0, 0), minus(s(s(x0)), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(77) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(x0, 0), minus(s(s(x0)), s(0)), s(0))) at position [1,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(s(0), if(false, minus(s(s(x0)), s(0)), s(0)))

(78) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(false, minus(s(s(x0)), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(79) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(s(0), if(false, minus(s(s(x0)), s(0)), s(0))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(s(0), mod(minus(minus(s(s(x0)), s(0)), s(0)), s(0)))

(80) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), mod(minus(minus(s(s(x0)), s(0)), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(81) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(s(0), mod(minus(minus(s(s(x0)), s(0)), s(0)), s(0))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(minus(s(s(x0)), s(0)), s(0)), s(0)), minus(minus(s(s(x0)), s(0)), s(0)), s(0)))

(82) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(minus(s(s(x0)), s(0)), s(0)), s(0)), minus(minus(s(s(x0)), s(0)), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(83) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(minus(s(s(x0)), s(0)), s(0)), s(0)), minus(minus(s(s(x0)), s(0)), s(0)), s(0))) at position [1,0,0,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(minus(s(x0), 0), s(0)), s(0)), minus(minus(s(s(x0)), s(0)), s(0)), s(0)))

(84) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(minus(s(x0), 0), s(0)), s(0)), minus(minus(s(s(x0)), s(0)), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(85) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(minus(s(x0), 0), s(0)), s(0)), minus(minus(s(s(x0)), s(0)), s(0)), s(0))) at position [1,0,0,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(s(x0), s(0)), s(0)), minus(minus(s(s(x0)), s(0)), s(0)), s(0)))

(86) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(s(x0), s(0)), s(0)), minus(minus(s(s(x0)), s(0)), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(87) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(s(x0), s(0)), s(0)), minus(minus(s(s(x0)), s(0)), s(0)), s(0))) at position [1,0,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(minus(s(s(x0)), s(0)), s(0)), s(0)))

(88) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(minus(s(s(x0)), s(0)), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(89) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(minus(s(s(x0)), s(0)), s(0)), s(0))) at position [1,1,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(minus(s(x0), 0), s(0)), s(0)))

(90) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(minus(s(x0), 0), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(91) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(minus(s(x0), 0), s(0)), s(0))) at position [1,1,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(s(x0), s(0)), s(0)))

(92) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(s(x0), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(93) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(s(x0), s(0)), s(0))) at position [1,1] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))

(94) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0))))
GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(95) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule GCD(s(s(x0)), s(s(x1))) → GCD(if(lt(x0, x1), s(s(x0)), s(s(x1))), if(lt(x1, x0), s(s(x1)), s(s(x0)))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(s(x0), 0), s(s(s(x0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(s(x1), s(x0)), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(false, s(s(x0)), s(s(0))))

(96) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(s(x0), 0), s(s(s(x0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(s(x1), s(x0)), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(false, s(s(x0)), s(s(0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(97) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(s(x0), 0), s(s(s(x0))), s(s(0))), if(true, s(s(0)), s(s(s(x0))))) at position [0,0] we obtained the following new rules [LPAR04]:

GCD(s(s(s(x0))), s(s(0))) → GCD(if(false, s(s(s(x0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

(98) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(s(x1), s(x0)), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(false, s(s(x0)), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(false, s(s(s(x0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(99) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(s(x1), s(x0)), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1))))) at position [0,0] we obtained the following new rules [LPAR04]:

GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))

(100) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(false, s(s(x0)), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(false, s(s(s(x0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(101) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(false, s(s(x0)), s(s(0)))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), mod(minus(s(s(x0)), s(s(0))), s(s(0))))

(102) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(false, s(s(s(x0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), mod(minus(s(s(x0)), s(s(0))), s(s(0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(103) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(s(x0))), s(s(0))) → GCD(if(false, s(s(s(x0))), s(s(0))), if(true, s(s(0)), s(s(s(x0))))) at position [0] we obtained the following new rules [LPAR04]:

GCD(s(s(s(x0))), s(s(0))) → GCD(mod(minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

(104) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), mod(minus(s(s(x0)), s(s(0))), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(mod(minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(105) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), mod(minus(s(s(x0)), s(s(0))), s(s(0)))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(s(s(x0)), s(s(0))), s(s(0))), minus(s(s(x0)), s(s(0))), s(s(0))))

(106) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(s(x0))), s(s(0))) → GCD(mod(minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(s(s(x0)), s(s(0))), s(s(0))), minus(s(s(x0)), s(s(0))), s(s(0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(107) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(s(x0))), s(s(0))) → GCD(mod(minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0))))) at position [0] we obtained the following new rules [LPAR04]:

GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(minus(s(s(s(x0))), s(s(0))), s(s(0))), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

(108) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(s(s(x0)), s(s(0))), s(s(0))), minus(s(s(x0)), s(s(0))), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(minus(s(s(s(x0))), s(s(0))), s(s(0))), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(109) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(s(s(x0)), s(s(0))), s(s(0))), minus(s(s(x0)), s(s(0))), s(s(0)))) at position [1,0,0] we obtained the following new rules [LPAR04]:

GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(s(x0), s(0)), s(s(0))), minus(s(s(x0)), s(s(0))), s(s(0))))

(110) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(minus(s(s(s(x0))), s(s(0))), s(s(0))), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(s(x0), s(0)), s(s(0))), minus(s(s(x0)), s(s(0))), s(s(0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(111) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(minus(s(s(s(x0))), s(s(0))), s(s(0))), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0))))) at position [0,0,0] we obtained the following new rules [LPAR04]:

GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(minus(s(s(x0)), s(0)), s(s(0))), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

(112) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(s(x0), s(0)), s(s(0))), minus(s(s(x0)), s(s(0))), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(minus(s(s(x0)), s(0)), s(s(0))), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(113) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(s(x0), s(0)), s(s(0))), minus(s(s(x0)), s(s(0))), s(s(0)))) at position [1,0,0] we obtained the following new rules [LPAR04]:

GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(s(s(x0)), s(s(0))), s(s(0))))

(114) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(minus(s(s(x0)), s(0)), s(s(0))), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(s(s(x0)), s(s(0))), s(s(0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(115) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(minus(s(s(x0)), s(0)), s(s(0))), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0))))) at position [0,0,0] we obtained the following new rules [LPAR04]:

GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(minus(s(x0), 0), s(s(0))), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

(116) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(s(s(x0)), s(s(0))), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(minus(s(x0), 0), s(s(0))), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(117) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(s(s(x0)), s(s(0))), s(s(0)))) at position [1,1] we obtained the following new rules [LPAR04]:

GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(s(x0), s(0)), s(s(0))))

(118) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(minus(s(x0), 0), s(s(0))), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(s(x0), s(0)), s(s(0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(119) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(minus(s(x0), 0), s(s(0))), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0))))) at position [0,0,0] we obtained the following new rules [LPAR04]:

GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(s(x0), s(s(0))), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

(120) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(s(x0), s(0)), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(s(x0), s(s(0))), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(121) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(s(x0), s(0)), s(s(0)))) at position [1,1] we obtained the following new rules [LPAR04]:

GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))

(122) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(s(x0), s(s(0))), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(123) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(s(x0), s(s(0))), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0))))) at position [0,0] we obtained the following new rules [LPAR04]:

GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

(124) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(125) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), minus(s(s(s(x0))), s(s(0))), s(s(0))), if(true, s(s(0)), s(s(s(x0))))) at position [0,1] we obtained the following new rules [LPAR04]:

GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), minus(s(s(x0)), s(0)), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

(126) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), minus(s(s(x0)), s(0)), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(127) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), minus(s(s(x0)), s(0)), s(s(0))), if(true, s(s(0)), s(s(s(x0))))) at position [0,1] we obtained the following new rules [LPAR04]:

GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), minus(s(x0), 0), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

(128) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), minus(s(x0), 0), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(129) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), minus(s(x0), 0), s(s(0))), if(true, s(s(0)), s(s(s(x0))))) at position [0,1] we obtained the following new rules [LPAR04]:

GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

(130) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), if(true, s(s(0)), s(s(s(x0)))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(131) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), if(true, s(s(0)), s(s(s(x0))))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))

(132) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0)))
GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(133) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule GCD(s(x0), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(lt(0, x0), s(0), s(x0))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(s(x0), 0), s(0)), minus(s(x0), 0), s(0)), if(true, s(0), s(s(x0))))
GCD(s(0), s(0)) → GCD(if(lt(minus(0, 0), s(0)), minus(0, 0), s(0)), if(false, s(0), s(0)))

(134) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))
GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(s(x0), 0), s(0)), minus(s(x0), 0), s(0)), if(true, s(0), s(s(x0))))
GCD(s(0), s(0)) → GCD(if(lt(minus(0, 0), s(0)), minus(0, 0), s(0)), if(false, s(0), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(135) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(s(x0), 0), s(0)), minus(s(x0), 0), s(0)), if(true, s(0), s(s(x0)))) at position [0,0,0] we obtained the following new rules [LPAR04]:

GCD(s(s(x0)), s(0)) → GCD(if(lt(s(x0), s(0)), minus(s(x0), 0), s(0)), if(true, s(0), s(s(x0))))

(136) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))
GCD(s(0), s(0)) → GCD(if(lt(minus(0, 0), s(0)), minus(0, 0), s(0)), if(false, s(0), s(0)))
GCD(s(s(x0)), s(0)) → GCD(if(lt(s(x0), s(0)), minus(s(x0), 0), s(0)), if(true, s(0), s(s(x0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(137) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(0)) → GCD(if(lt(minus(0, 0), s(0)), minus(0, 0), s(0)), if(false, s(0), s(0))) at position [0,0,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(0)) → GCD(if(lt(0, s(0)), minus(0, 0), s(0)), if(false, s(0), s(0)))

(138) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))
GCD(s(s(x0)), s(0)) → GCD(if(lt(s(x0), s(0)), minus(s(x0), 0), s(0)), if(true, s(0), s(s(x0))))
GCD(s(0), s(0)) → GCD(if(lt(0, s(0)), minus(0, 0), s(0)), if(false, s(0), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(139) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(x0)), s(0)) → GCD(if(lt(s(x0), s(0)), minus(s(x0), 0), s(0)), if(true, s(0), s(s(x0)))) at position [0,0] we obtained the following new rules [LPAR04]:

GCD(s(s(x0)), s(0)) → GCD(if(lt(x0, 0), minus(s(x0), 0), s(0)), if(true, s(0), s(s(x0))))

(140) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))
GCD(s(0), s(0)) → GCD(if(lt(0, s(0)), minus(0, 0), s(0)), if(false, s(0), s(0)))
GCD(s(s(x0)), s(0)) → GCD(if(lt(x0, 0), minus(s(x0), 0), s(0)), if(true, s(0), s(s(x0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(141) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(0)) → GCD(if(lt(0, s(0)), minus(0, 0), s(0)), if(false, s(0), s(0))) at position [0,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(0)) → GCD(if(true, minus(0, 0), s(0)), if(false, s(0), s(0)))

(142) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))
GCD(s(s(x0)), s(0)) → GCD(if(lt(x0, 0), minus(s(x0), 0), s(0)), if(true, s(0), s(s(x0))))
GCD(s(0), s(0)) → GCD(if(true, minus(0, 0), s(0)), if(false, s(0), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(143) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(x0)), s(0)) → GCD(if(lt(x0, 0), minus(s(x0), 0), s(0)), if(true, s(0), s(s(x0)))) at position [0,0] we obtained the following new rules [LPAR04]:

GCD(s(s(x0)), s(0)) → GCD(if(false, minus(s(x0), 0), s(0)), if(true, s(0), s(s(x0))))

(144) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))
GCD(s(0), s(0)) → GCD(if(true, minus(0, 0), s(0)), if(false, s(0), s(0)))
GCD(s(s(x0)), s(0)) → GCD(if(false, minus(s(x0), 0), s(0)), if(true, s(0), s(s(x0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(145) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(0)) → GCD(if(true, minus(0, 0), s(0)), if(false, s(0), s(0))) at position [0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(0)) → GCD(minus(0, 0), if(false, s(0), s(0)))

(146) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))
GCD(s(s(x0)), s(0)) → GCD(if(false, minus(s(x0), 0), s(0)), if(true, s(0), s(s(x0))))
GCD(s(0), s(0)) → GCD(minus(0, 0), if(false, s(0), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(147) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(x0)), s(0)) → GCD(if(false, minus(s(x0), 0), s(0)), if(true, s(0), s(s(x0)))) at position [0] we obtained the following new rules [LPAR04]:

GCD(s(s(x0)), s(0)) → GCD(mod(minus(minus(s(x0), 0), s(0)), s(0)), if(true, s(0), s(s(x0))))

(148) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))
GCD(s(0), s(0)) → GCD(minus(0, 0), if(false, s(0), s(0)))
GCD(s(s(x0)), s(0)) → GCD(mod(minus(minus(s(x0), 0), s(0)), s(0)), if(true, s(0), s(s(x0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(149) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(0)) → GCD(minus(0, 0), if(false, s(0), s(0))) at position [0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(0)) → GCD(0, if(false, s(0), s(0)))

(150) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))
GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))
GCD(s(s(x0)), s(0)) → GCD(mod(minus(minus(s(x0), 0), s(0)), s(0)), if(true, s(0), s(s(x0))))
GCD(s(0), s(0)) → GCD(0, if(false, s(0), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(151) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node.

(152) Complex Obligation (AND)

(153) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(154) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule GCD(s(0), s(s(x0))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(0))) → GCD(s(0), if(lt(0, s(0)), minus(0, 0), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(s(x0), s(0)), minus(s(x0), 0), s(0)))
GCD(s(0), s(s(0))) → GCD(s(0), if(lt(minus(0, 0), s(0)), 0, s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(s(x0), 0), s(0)), s(x0), s(0)))

(155) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(0))) → GCD(s(0), if(lt(0, s(0)), minus(0, 0), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(s(x0), s(0)), minus(s(x0), 0), s(0)))
GCD(s(0), s(s(0))) → GCD(s(0), if(lt(minus(0, 0), s(0)), 0, s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(s(x0), 0), s(0)), s(x0), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(156) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(0))) → GCD(s(0), if(lt(0, s(0)), minus(0, 0), s(0))) at position [1,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(0))) → GCD(s(0), if(true, minus(0, 0), s(0)))

(157) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(s(x0), s(0)), minus(s(x0), 0), s(0)))
GCD(s(0), s(s(0))) → GCD(s(0), if(lt(minus(0, 0), s(0)), 0, s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(s(x0), 0), s(0)), s(x0), s(0)))
GCD(s(0), s(s(0))) → GCD(s(0), if(true, minus(0, 0), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(158) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(s(x0), s(0)), minus(s(x0), 0), s(0))) at position [1,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(x0, 0), minus(s(x0), 0), s(0)))

(159) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(0))) → GCD(s(0), if(lt(minus(0, 0), s(0)), 0, s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(s(x0), 0), s(0)), s(x0), s(0)))
GCD(s(0), s(s(0))) → GCD(s(0), if(true, minus(0, 0), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(x0, 0), minus(s(x0), 0), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(160) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(0))) → GCD(s(0), if(lt(minus(0, 0), s(0)), 0, s(0))) at position [1,0,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(0))) → GCD(s(0), if(lt(0, s(0)), 0, s(0)))

(161) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(s(x0), 0), s(0)), s(x0), s(0)))
GCD(s(0), s(s(0))) → GCD(s(0), if(true, minus(0, 0), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(x0, 0), minus(s(x0), 0), s(0)))
GCD(s(0), s(s(0))) → GCD(s(0), if(lt(0, s(0)), 0, s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(162) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(s(x0), 0), s(0)), s(x0), s(0))) at position [1,0,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(s(x0), s(0)), s(x0), s(0)))

(163) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(0))) → GCD(s(0), if(true, minus(0, 0), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(x0, 0), minus(s(x0), 0), s(0)))
GCD(s(0), s(s(0))) → GCD(s(0), if(lt(0, s(0)), 0, s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(s(x0), s(0)), s(x0), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(164) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(0))) → GCD(s(0), if(true, minus(0, 0), s(0))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(0))) → GCD(s(0), minus(0, 0))

(165) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(x0, 0), minus(s(x0), 0), s(0)))
GCD(s(0), s(s(0))) → GCD(s(0), if(lt(0, s(0)), 0, s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(s(x0), s(0)), s(x0), s(0)))
GCD(s(0), s(s(0))) → GCD(s(0), minus(0, 0))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(166) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.

(167) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(x0, 0), minus(s(x0), 0), s(0)))
GCD(s(0), s(s(0))) → GCD(s(0), if(lt(0, s(0)), 0, s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(s(x0), s(0)), s(x0), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(168) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(x0, 0), minus(s(x0), 0), s(0))) at position [1,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(false, minus(s(x0), 0), s(0)))

(169) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(0))) → GCD(s(0), if(lt(0, s(0)), 0, s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(s(x0), s(0)), s(x0), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(false, minus(s(x0), 0), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(170) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(0))) → GCD(s(0), if(lt(0, s(0)), 0, s(0))) at position [1,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(0))) → GCD(s(0), if(true, 0, s(0)))

(171) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(s(x0), s(0)), s(x0), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(false, minus(s(x0), 0), s(0)))
GCD(s(0), s(s(0))) → GCD(s(0), if(true, 0, s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(172) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(s(x0), s(0)), s(x0), s(0))) at position [1,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(x0, 0), s(x0), s(0)))

(173) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(false, minus(s(x0), 0), s(0)))
GCD(s(0), s(s(0))) → GCD(s(0), if(true, 0, s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(x0, 0), s(x0), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(174) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(false, minus(s(x0), 0), s(0))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), mod(minus(minus(s(x0), 0), s(0)), s(0)))

(175) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(0))) → GCD(s(0), if(true, 0, s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(x0, 0), s(x0), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), mod(minus(minus(s(x0), 0), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(176) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(0))) → GCD(s(0), if(true, 0, s(0))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(0))) → GCD(s(0), 0)

(177) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(x0, 0), s(x0), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), mod(minus(minus(s(x0), 0), s(0)), s(0)))
GCD(s(0), s(s(0))) → GCD(s(0), 0)

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(178) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.

(179) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(x0, 0), s(x0), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), mod(minus(minus(s(x0), 0), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(180) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(x0, 0), s(x0), s(0))) at position [1,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(false, s(x0), s(0)))

(181) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), mod(minus(minus(s(x0), 0), s(0)), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(false, s(x0), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(182) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(s(x0)))) → GCD(s(0), mod(minus(minus(s(x0), 0), s(0)), s(0))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(minus(s(x0), 0), s(0)), s(0)), minus(minus(s(x0), 0), s(0)), s(0)))

(183) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(false, s(x0), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(minus(s(x0), 0), s(0)), s(0)), minus(minus(s(x0), 0), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(184) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(false, s(x0), s(0))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), mod(minus(s(x0), s(0)), s(0)))

(185) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(minus(s(x0), 0), s(0)), s(0)), minus(minus(s(x0), 0), s(0)), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), mod(minus(s(x0), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(186) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(minus(s(x0), 0), s(0)), s(0)), minus(minus(s(x0), 0), s(0)), s(0))) at position [1,0,0,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(s(x0), s(0)), s(0)), minus(minus(s(x0), 0), s(0)), s(0)))

(187) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), mod(minus(s(x0), s(0)), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(s(x0), s(0)), s(0)), minus(minus(s(x0), 0), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(188) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(s(x0)))) → GCD(s(0), mod(minus(s(x0), s(0)), s(0))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(s(x0), s(0)), s(0)), minus(s(x0), s(0)), s(0)))

(189) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(s(x0), s(0)), s(0)), minus(minus(s(x0), 0), s(0)), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(s(x0), s(0)), s(0)), minus(s(x0), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(190) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(s(x0), s(0)), s(0)), minus(minus(s(x0), 0), s(0)), s(0))) at position [1,0,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(minus(s(x0), 0), s(0)), s(0)))

(191) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(s(x0), s(0)), s(0)), minus(s(x0), s(0)), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(minus(s(x0), 0), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(192) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(s(x0), s(0)), s(0)), minus(s(x0), s(0)), s(0))) at position [1,0,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(s(x0), s(0)), s(0)))

(193) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(minus(s(x0), 0), s(0)), s(0)))
GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(s(x0), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(194) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(minus(s(x0), 0), s(0)), s(0))) at position [1,1,0] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(s(x0), s(0)), s(0)))

(195) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(s(x0), s(0)), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(196) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(s(x0), s(0)), s(0))) at position [1,1] we obtained the following new rules [LPAR04]:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))

(197) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(198) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].

The following pairs can be oriented strictly and are deleted.

GCD(s(0), s(s(s(x0)))) → GCD(s(0), if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)))

The remaining pairs can at least be oriented weakly.
Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation:

POL( GCD(x₁, x₂) ) = max{0, x₂ - 2}

POL( if(x₁, ..., x₃) ) = x₂

POL( mod(x₁, x₂) ) = x₁

POL( lt(x₁, x₂) ) = max{0, -2}

POL( minus(x₁, x₂) ) = x₁

POL( 0 ) = 0

POL( s(x₁) ) = x₁ + 2

POL( true ) = 1

POL( false ) = 1

The following usable rules [FROCOS05] were oriented:

minus(0, x) → 0
minus(s(x), 0) → s(x)
if(false, x, y) → mod(minus(x, y), y)
mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(true, x, y) → x
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0

(199) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(200) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(201) YES

(202) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))
GCD(s(s(x0)), s(0)) → GCD(mod(minus(minus(s(x0), 0), s(0)), s(0)), if(true, s(0), s(s(x0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(203) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(x0)), s(0)) → GCD(mod(minus(minus(s(x0), 0), s(0)), s(0)), if(true, s(0), s(s(x0)))) at position [0] we obtained the following new rules [LPAR04]:

GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(minus(s(x0), 0), s(0)), s(0)), minus(minus(s(x0), 0), s(0)), s(0)), if(true, s(0), s(s(x0))))

(204) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))
GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(minus(s(x0), 0), s(0)), s(0)), minus(minus(s(x0), 0), s(0)), s(0)), if(true, s(0), s(s(x0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(205) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(minus(s(x0), 0), s(0)), s(0)), minus(minus(s(x0), 0), s(0)), s(0)), if(true, s(0), s(s(x0)))) at position [0,0,0,0] we obtained the following new rules [LPAR04]:

GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(s(x0), s(0)), s(0)), minus(minus(s(x0), 0), s(0)), s(0)), if(true, s(0), s(s(x0))))

(206) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))
GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(s(x0), s(0)), s(0)), minus(minus(s(x0), 0), s(0)), s(0)), if(true, s(0), s(s(x0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(207) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(s(x0), s(0)), s(0)), minus(minus(s(x0), 0), s(0)), s(0)), if(true, s(0), s(s(x0)))) at position [0,0,0] we obtained the following new rules [LPAR04]:

GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(minus(s(x0), 0), s(0)), s(0)), if(true, s(0), s(s(x0))))

(208) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))
GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(minus(s(x0), 0), s(0)), s(0)), if(true, s(0), s(s(x0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(209) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(minus(s(x0), 0), s(0)), s(0)), if(true, s(0), s(s(x0)))) at position [0,1,0] we obtained the following new rules [LPAR04]:

GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(s(x0), s(0)), s(0)), if(true, s(0), s(s(x0))))

(210) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))
GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(s(x0), s(0)), s(0)), if(true, s(0), s(s(x0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(211) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(s(x0), s(0)), s(0)), if(true, s(0), s(s(x0)))) at position [0,1] we obtained the following new rules [LPAR04]:

GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(true, s(0), s(s(x0))))

(212) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))
GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(true, s(0), s(s(x0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(213) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), if(true, s(0), s(s(x0)))) at position [1] we obtained the following new rules [LPAR04]:

GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), s(0))

(214) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))
GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), s(0))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(215) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs.

(216) Complex Obligation (AND)

(217) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), s(0))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(218) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].

The following pairs can be oriented strictly and are deleted.

GCD(s(s(x0)), s(0)) → GCD(if(lt(minus(x0, 0), s(0)), minus(x0, 0), s(0)), s(0))

The remaining pairs can at least be oriented weakly.
Used ordering: Polynomial interpretation [POLO]:

POL(0) = 0   
POL(GCD(x₁, x₂)) = x₁   
POL(false) = 0   
POL(if(x₁, x₂, x₃)) = x₂   
POL(lt(x₁, x₂)) = 0   
POL(minus(x₁, x₂)) = x₁   
POL(mod(x₁, x₂)) = x₁   
POL(s(x₁)) = 1 + x₁   
POL(true) = 0   

The following usable rules [FROCOS05] were oriented:

minus(0, x) → 0
minus(s(x), 0) → s(x)
if(false, x, y) → mod(minus(x, y), y)
mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(true, x, y) → x
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0

(219) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(220) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(221) YES

(222) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))
GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(223) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].

The following pairs can be oriented strictly and are deleted.

GCD(s(s(s(x0))), s(s(0))) → GCD(if(lt(x0, s(0)), s(x0), s(s(0))), s(s(0)))

The remaining pairs can at least be oriented weakly.
Used ordering: Polynomial interpretation [POLO]:

POL(0) = 0   
POL(GCD(x₁, x₂)) = x₁   
POL(false) = 0   
POL(if(x₁, x₂, x₃)) = x₂   
POL(lt(x₁, x₂)) = 0   
POL(minus(x₁, x₂)) = x₁   
POL(mod(x₁, x₂)) = x₁   
POL(s(x₁)) = 1 + x₁   
POL(true) = 0   

The following usable rules [FROCOS05] were oriented:

if(false, x, y) → mod(minus(x, y), y)
mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0

(224) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))
GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(225) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].

The following pairs can be oriented strictly and are deleted.

GCD(s(s(0)), s(s(x0))) → GCD(if(lt(0, x0), s(s(0)), s(s(x0))), if(lt(minus(x0, 0), s(s(0))), minus(x0, 0), s(s(0))))

The remaining pairs can at least be oriented weakly.
Used ordering: Polynomial interpretation [POLO]:

POL(0) = 0   
POL(GCD(x₁, x₂)) = x₁ + x₂   
POL(false) = 0   
POL(if(x₁, x₂, x₃)) = x₂   
POL(lt(x₁, x₂)) = 0   
POL(minus(x₁, x₂)) = x₁   
POL(mod(x₁, x₂)) = x₁   
POL(s(x₁)) = 1 + x₁   
POL(true) = 0   

The following usable rules [FROCOS05] were oriented:

if(false, x, y) → mod(minus(x, y), y)
mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0

(226) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

The set Q consists of the following terms:

minus(0, x0)
minus(s(x0), 0)
minus(s(x0), s(x1))
mod(x0, 0)
mod(x0, s(x1))
if(true, x0, x1)
if(false, x0, x1)
lt(x0, 0)
lt(0, s(x0))
lt(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.

(227) MNOCProof (EQUIVALENT transformation)

We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set.

(228) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

Q is empty.
We have to consider all (P,Q,R)-chains.

(229) MNOCProof (EQUIVALENT transformation)

We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set.

(230) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GCD(s(s(s(x1))), s(s(s(x0)))) → GCD(if(lt(x1, x0), s(s(s(x1))), s(s(s(x0)))), if(lt(x0, x1), s(s(s(x0))), s(s(s(x1)))))

The TRS R consists of the following rules:

mod(x, s(y)) → if(lt(x, s(y)), x, s(y))
if(false, x, y) → mod(minus(x, y), y)
lt(0, s(x)) → true
lt(s(x), s(y)) → lt(x, y)
if(true, x, y) → x
minus(0, x) → 0
minus(s(x), 0) → s(x)
minus(s(x), s(y)) → minus(x, y)
mod(x, 0) → 0
lt(x, 0) → false

Q is empty.
We have to consider all (P,Q,R)-chains.