MAYBE
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


Termination of the given ETRS could not be shown:

(0) ETRS
(1) EquationalDependencyPairsProof [EQUIVALENT, 0 ms]
(2) EDP
(3) EDependencyGraphProof [EQUIVALENT, 0 ms]
(4) AND
    (5) EDP
        (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
        (7) EDP
        (8) EUsableRulesReductionPairsProof [EQUIVALENT, 9 ms]
        (9) EDP
        (10) PisEmptyProof [EQUIVALENT, 0 ms]
        (11) YES
    (12) EDP
        (13) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
        (14) EDP
        (15) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
        (16) EDP
        (17) PisEmptyProof [EQUIVALENT, 0 ms]
        (18) YES
    (19) EDP
        (20) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
        (21) EDP
        (22) EUsableRulesProof [EQUIVALENT, 0 ms]
        (23) EDP
    (24) EDP
    (25) EDP
    (26) EDP


----------------------------------------

(0)
Obligation:
Equational rewrite system:
The TRS R consists of the following rules:

   p(s(N)) -> N
   +(N, 0) -> N
   +(s(N), s(M)) -> s(s(+(N, M)))
   *(N, 0) -> 0
   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
   gt(0, M) -> False
   gt(NzN, 0) -> u_4(is_NzNat(NzN))
   u_4(True) -> True
   is_NzNat(0) -> False
   is_NzNat(s(N)) -> True
   gt(s(N), s(M)) -> gt(N, M)
   lt(N, M) -> gt(M, N)
   d(0, N) -> N
   d(s(N), s(M)) -> d(N, M)
   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
   u_01(True) -> s(0)
   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
   u_21(True, NzM, N) -> u_2(gt(NzM, N))
   u_2(True) -> 0
   gcd(0, N) -> 0
   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
   u_02(True, NzM) -> NzM
   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

The set E consists of the following equations:

   *(x, y) == *(y, x)
   +(x, y) == +(y, x)
   d(x, y) == d(y, x)
   gcd(x, y) == gcd(y, x)


----------------------------------------

(1) EquationalDependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem:
The TRS P consists of the following rules:

   +^1(s(N), s(M)) -> +^1(N, M)
   *^1(s(N), s(M)) -> +^1(N, +(M, *(N, M)))
   *^1(s(N), s(M)) -> +^1(M, *(N, M))
   *^1(s(N), s(M)) -> *^1(N, M)
   GT(NzN, 0) -> U_4(is_NzNat(NzN))
   GT(NzN, 0) -> IS_NZNAT(NzN)
   GT(s(N), s(M)) -> GT(N, M)
   LT(N, M) -> GT(M, N)
   D(s(N), s(M)) -> D(N, M)
   QUOT(N, NzM) -> U_11(is_NzNat(NzM), N, NzM)
   QUOT(N, NzM) -> IS_NZNAT(NzM)
   U_11(True, N, NzM) -> U_1(gt(N, NzM), N, NzM)
   U_11(True, N, NzM) -> GT(N, NzM)
   U_1(True, N, NzM) -> QUOT(d(N, NzM), NzM)
   U_1(True, N, NzM) -> D(N, NzM)
   QUOT(NzM, NzM) -> U_01(is_NzNat(NzM))
   QUOT(NzM, NzM) -> IS_NZNAT(NzM)
   QUOT(N, NzM) -> U_21(is_NzNat(NzM), NzM, N)
   U_21(True, NzM, N) -> U_2(gt(NzM, N))
   U_21(True, NzM, N) -> GT(NzM, N)
   GCD(NzM, NzM) -> U_02(is_NzNat(NzM), NzM)
   GCD(NzM, NzM) -> IS_NZNAT(NzM)
   GCD(NzN, NzM) -> U_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   GCD(NzN, NzM) -> IS_NZNAT(NzN)
   GCD(NzN, NzM) -> IS_NZNAT(NzM)
   U_31(True, True, NzN, NzM) -> U_3(gt(NzN, NzM), NzN, NzM)
   U_31(True, True, NzN, NzM) -> GT(NzN, NzM)
   U_3(True, NzN, NzM) -> GCD(d(NzN, NzM), NzM)
   U_3(True, NzN, NzM) -> D(NzN, NzM)

The TRS R consists of the following rules:

   p(s(N)) -> N
   +(N, 0) -> N
   +(s(N), s(M)) -> s(s(+(N, M)))
   *(N, 0) -> 0
   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
   gt(0, M) -> False
   gt(NzN, 0) -> u_4(is_NzNat(NzN))
   u_4(True) -> True
   is_NzNat(0) -> False
   is_NzNat(s(N)) -> True
   gt(s(N), s(M)) -> gt(N, M)
   lt(N, M) -> gt(M, N)
   d(0, N) -> N
   d(s(N), s(M)) -> d(N, M)
   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
   u_01(True) -> s(0)
   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
   u_21(True, NzM, N) -> u_2(gt(NzM, N))
   u_2(True) -> 0
   gcd(0, N) -> 0
   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
   u_02(True, NzM) -> NzM
   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

The set E consists of the following equations:

   *(x, y) == *(y, x)
   +(x, y) == +(y, x)
   d(x, y) == d(y, x)
   gcd(x, y) == gcd(y, x)

The set E# consists of the following equations:

   *^1(x, y) == *^1(y, x)
   +^1(x, y) == +^1(y, x)
   D(x, y) == D(y, x)
   GCD(x, y) == GCD(y, x)

We have to consider all minimal (P,E#,R,E)-chains

----------------------------------------

(2)
Obligation:
The TRS P consists of the following rules:

   +^1(s(N), s(M)) -> +^1(N, M)
   *^1(s(N), s(M)) -> +^1(N, +(M, *(N, M)))
   *^1(s(N), s(M)) -> +^1(M, *(N, M))
   *^1(s(N), s(M)) -> *^1(N, M)
   GT(NzN, 0) -> U_4(is_NzNat(NzN))
   GT(NzN, 0) -> IS_NZNAT(NzN)
   GT(s(N), s(M)) -> GT(N, M)
   LT(N, M) -> GT(M, N)
   D(s(N), s(M)) -> D(N, M)
   QUOT(N, NzM) -> U_11(is_NzNat(NzM), N, NzM)
   QUOT(N, NzM) -> IS_NZNAT(NzM)
   U_11(True, N, NzM) -> U_1(gt(N, NzM), N, NzM)
   U_11(True, N, NzM) -> GT(N, NzM)
   U_1(True, N, NzM) -> QUOT(d(N, NzM), NzM)
   U_1(True, N, NzM) -> D(N, NzM)
   QUOT(NzM, NzM) -> U_01(is_NzNat(NzM))
   QUOT(NzM, NzM) -> IS_NZNAT(NzM)
   QUOT(N, NzM) -> U_21(is_NzNat(NzM), NzM, N)
   U_21(True, NzM, N) -> U_2(gt(NzM, N))
   U_21(True, NzM, N) -> GT(NzM, N)
   GCD(NzM, NzM) -> U_02(is_NzNat(NzM), NzM)
   GCD(NzM, NzM) -> IS_NZNAT(NzM)
   GCD(NzN, NzM) -> U_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   GCD(NzN, NzM) -> IS_NZNAT(NzN)
   GCD(NzN, NzM) -> IS_NZNAT(NzM)
   U_31(True, True, NzN, NzM) -> U_3(gt(NzN, NzM), NzN, NzM)
   U_31(True, True, NzN, NzM) -> GT(NzN, NzM)
   U_3(True, NzN, NzM) -> GCD(d(NzN, NzM), NzM)
   U_3(True, NzN, NzM) -> D(NzN, NzM)

The TRS R consists of the following rules:

   p(s(N)) -> N
   +(N, 0) -> N
   +(s(N), s(M)) -> s(s(+(N, M)))
   *(N, 0) -> 0
   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
   gt(0, M) -> False
   gt(NzN, 0) -> u_4(is_NzNat(NzN))
   u_4(True) -> True
   is_NzNat(0) -> False
   is_NzNat(s(N)) -> True
   gt(s(N), s(M)) -> gt(N, M)
   lt(N, M) -> gt(M, N)
   d(0, N) -> N
   d(s(N), s(M)) -> d(N, M)
   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
   u_01(True) -> s(0)
   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
   u_21(True, NzM, N) -> u_2(gt(NzM, N))
   u_2(True) -> 0
   gcd(0, N) -> 0
   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
   u_02(True, NzM) -> NzM
   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

The set E consists of the following equations:

   *(x, y) == *(y, x)
   +(x, y) == +(y, x)
   d(x, y) == d(y, x)
   gcd(x, y) == gcd(y, x)

The set E# consists of the following equations:

   *^1(x, y) == *^1(y, x)
   +^1(x, y) == +^1(y, x)
   D(x, y) == D(y, x)
   GCD(x, y) == GCD(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(3) EDependencyGraphProof (EQUIVALENT)
The approximation of the Equational Dependency Graph [DA_STEIN] contains 6 SCCs with 19 less nodes.
----------------------------------------

(4)
Complex Obligation (AND)

----------------------------------------

(5)
Obligation:
The TRS P consists of the following rules:

   D(s(N), s(M)) -> D(N, M)

The TRS R consists of the following rules:

   p(s(N)) -> N
   +(N, 0) -> N
   +(s(N), s(M)) -> s(s(+(N, M)))
   *(N, 0) -> 0
   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
   gt(0, M) -> False
   gt(NzN, 0) -> u_4(is_NzNat(NzN))
   u_4(True) -> True
   is_NzNat(0) -> False
   is_NzNat(s(N)) -> True
   gt(s(N), s(M)) -> gt(N, M)
   lt(N, M) -> gt(M, N)
   d(0, N) -> N
   d(s(N), s(M)) -> d(N, M)
   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
   u_01(True) -> s(0)
   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
   u_21(True, NzM, N) -> u_2(gt(NzM, N))
   u_2(True) -> 0
   gcd(0, N) -> 0
   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
   u_02(True, NzM) -> NzM
   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

The set E consists of the following equations:

   *(x, y) == *(y, x)
   +(x, y) == +(y, x)
   d(x, y) == d(y, x)
   gcd(x, y) == gcd(y, x)

The set E# consists of the following equations:

   *^1(x, y) == *^1(y, x)
   +^1(x, y) == +^1(y, x)
   D(x, y) == D(y, x)
   GCD(x, y) == GCD(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(6) ESharpUsableEquationsProof (EQUIVALENT)
We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
   *^1(x, y) == *^1(y, x)
   +^1(x, y) == +^1(y, x)
   GCD(x, y) == GCD(y, x)

----------------------------------------

(7)
Obligation:
The TRS P consists of the following rules:

   D(s(N), s(M)) -> D(N, M)

The TRS R consists of the following rules:

   p(s(N)) -> N
   +(N, 0) -> N
   +(s(N), s(M)) -> s(s(+(N, M)))
   *(N, 0) -> 0
   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
   gt(0, M) -> False
   gt(NzN, 0) -> u_4(is_NzNat(NzN))
   u_4(True) -> True
   is_NzNat(0) -> False
   is_NzNat(s(N)) -> True
   gt(s(N), s(M)) -> gt(N, M)
   lt(N, M) -> gt(M, N)
   d(0, N) -> N
   d(s(N), s(M)) -> d(N, M)
   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
   u_01(True) -> s(0)
   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
   u_21(True, NzM, N) -> u_2(gt(NzM, N))
   u_2(True) -> 0
   gcd(0, N) -> 0
   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
   u_02(True, NzM) -> NzM
   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

The set E consists of the following equations:

   *(x, y) == *(y, x)
   +(x, y) == +(y, x)
   d(x, y) == d(y, x)
   gcd(x, y) == gcd(y, x)

The set E# consists of the following equations:

   D(x, y) == D(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(8) EUsableRulesReductionPairsProof (EQUIVALENT)
By using the improved usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding improved usable rules can be oriented non-strictly, the improved  usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and improved usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.

The following dependency pairs can be deleted:

   D(s(N), s(M)) -> D(N, M)
The following rules are removed from R:

   p(s(N)) -> N
   +(N, 0) -> N
   +(s(N), s(M)) -> s(s(+(N, M)))
   *(N, 0) -> 0
   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
   gt(0, M) -> False
   gt(NzN, 0) -> u_4(is_NzNat(NzN))
   u_4(True) -> True
   is_NzNat(0) -> False
   is_NzNat(s(N)) -> True
   gt(s(N), s(M)) -> gt(N, M)
   lt(N, M) -> gt(M, N)
   d(0, N) -> N
   d(s(N), s(M)) -> d(N, M)
   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
   u_01(True) -> s(0)
   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
   u_21(True, NzM, N) -> u_2(gt(NzM, N))
   u_2(True) -> 0
   gcd(0, N) -> 0
   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
   u_02(True, NzM) -> NzM
   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)
The following equations are removed from E:

   *(x, y) == *(y, x)
   +(x, y) == +(y, x)
   d(x, y) == d(y, x)
   gcd(x, y) == gcd(y, x)
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(D(x_1, x_2)) = 3*x_1 + 3*x_2
   POL(s(x_1)) = 3*x_1


----------------------------------------

(9)
Obligation:
P is empty.
R is empty.
E is empty.
The set E# consists of the following equations:

   D(x, y) == D(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(10) PisEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
----------------------------------------

(11)
YES

----------------------------------------

(12)
Obligation:
The TRS P consists of the following rules:

   GT(s(N), s(M)) -> GT(N, M)

The TRS R consists of the following rules:

   p(s(N)) -> N
   +(N, 0) -> N
   +(s(N), s(M)) -> s(s(+(N, M)))
   *(N, 0) -> 0
   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
   gt(0, M) -> False
   gt(NzN, 0) -> u_4(is_NzNat(NzN))
   u_4(True) -> True
   is_NzNat(0) -> False
   is_NzNat(s(N)) -> True
   gt(s(N), s(M)) -> gt(N, M)
   lt(N, M) -> gt(M, N)
   d(0, N) -> N
   d(s(N), s(M)) -> d(N, M)
   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
   u_01(True) -> s(0)
   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
   u_21(True, NzM, N) -> u_2(gt(NzM, N))
   u_2(True) -> 0
   gcd(0, N) -> 0
   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
   u_02(True, NzM) -> NzM
   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

The set E consists of the following equations:

   *(x, y) == *(y, x)
   +(x, y) == +(y, x)
   d(x, y) == d(y, x)
   gcd(x, y) == gcd(y, x)

The set E# consists of the following equations:

   *^1(x, y) == *^1(y, x)
   +^1(x, y) == +^1(y, x)
   D(x, y) == D(y, x)
   GCD(x, y) == GCD(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(13) ESharpUsableEquationsProof (EQUIVALENT)
We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
   *^1(x, y) == *^1(y, x)
   +^1(x, y) == +^1(y, x)
   D(x, y) == D(y, x)
   GCD(x, y) == GCD(y, x)

----------------------------------------

(14)
Obligation:
The TRS P consists of the following rules:

   GT(s(N), s(M)) -> GT(N, M)

The TRS R consists of the following rules:

   p(s(N)) -> N
   +(N, 0) -> N
   +(s(N), s(M)) -> s(s(+(N, M)))
   *(N, 0) -> 0
   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
   gt(0, M) -> False
   gt(NzN, 0) -> u_4(is_NzNat(NzN))
   u_4(True) -> True
   is_NzNat(0) -> False
   is_NzNat(s(N)) -> True
   gt(s(N), s(M)) -> gt(N, M)
   lt(N, M) -> gt(M, N)
   d(0, N) -> N
   d(s(N), s(M)) -> d(N, M)
   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
   u_01(True) -> s(0)
   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
   u_21(True, NzM, N) -> u_2(gt(NzM, N))
   u_2(True) -> 0
   gcd(0, N) -> 0
   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
   u_02(True, NzM) -> NzM
   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

The set E consists of the following equations:

   *(x, y) == *(y, x)
   +(x, y) == +(y, x)
   d(x, y) == d(y, x)
   gcd(x, y) == gcd(y, x)

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

(15) EUsableRulesReductionPairsProof (EQUIVALENT)
By using the improved usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding improved usable rules can be oriented non-strictly, the improved  usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and improved usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.

The following dependency pairs can be deleted:

   GT(s(N), s(M)) -> GT(N, M)
The following rules are removed from R:

   p(s(N)) -> N
   +(N, 0) -> N
   +(s(N), s(M)) -> s(s(+(N, M)))
   *(N, 0) -> 0
   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
   gt(0, M) -> False
   gt(NzN, 0) -> u_4(is_NzNat(NzN))
   u_4(True) -> True
   is_NzNat(0) -> False
   is_NzNat(s(N)) -> True
   gt(s(N), s(M)) -> gt(N, M)
   lt(N, M) -> gt(M, N)
   d(0, N) -> N
   d(s(N), s(M)) -> d(N, M)
   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
   u_01(True) -> s(0)
   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
   u_21(True, NzM, N) -> u_2(gt(NzM, N))
   u_2(True) -> 0
   gcd(0, N) -> 0
   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
   u_02(True, NzM) -> NzM
   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)
The following equations are removed from E:

   *(x, y) == *(y, x)
   +(x, y) == +(y, x)
   d(x, y) == d(y, x)
   gcd(x, y) == gcd(y, x)
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(GT(x_1, x_2)) = 3*x_1 + 3*x_2
   POL(s(x_1)) = x_1


----------------------------------------

(16)
Obligation:
P is empty.
R is empty.
E is empty.
E# is empty.
We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(17) PisEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
----------------------------------------

(18)
YES

----------------------------------------

(19)
Obligation:
The TRS P consists of the following rules:

   U_31(True, True, NzN, NzM) -> U_3(gt(NzN, NzM), NzN, NzM)
   U_3(True, NzN, NzM) -> GCD(d(NzN, NzM), NzM)
   GCD(NzN, NzM) -> U_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)

The TRS R consists of the following rules:

   p(s(N)) -> N
   +(N, 0) -> N
   +(s(N), s(M)) -> s(s(+(N, M)))
   *(N, 0) -> 0
   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
   gt(0, M) -> False
   gt(NzN, 0) -> u_4(is_NzNat(NzN))
   u_4(True) -> True
   is_NzNat(0) -> False
   is_NzNat(s(N)) -> True
   gt(s(N), s(M)) -> gt(N, M)
   lt(N, M) -> gt(M, N)
   d(0, N) -> N
   d(s(N), s(M)) -> d(N, M)
   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
   u_01(True) -> s(0)
   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
   u_21(True, NzM, N) -> u_2(gt(NzM, N))
   u_2(True) -> 0
   gcd(0, N) -> 0
   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
   u_02(True, NzM) -> NzM
   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

The set E consists of the following equations:

   *(x, y) == *(y, x)
   +(x, y) == +(y, x)
   d(x, y) == d(y, x)
   gcd(x, y) == gcd(y, x)

The set E# consists of the following equations:

   *^1(x, y) == *^1(y, x)
   +^1(x, y) == +^1(y, x)
   D(x, y) == D(y, x)
   GCD(x, y) == GCD(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(20) ESharpUsableEquationsProof (EQUIVALENT)
We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
   *^1(x, y) == *^1(y, x)
   +^1(x, y) == +^1(y, x)
   D(x, y) == D(y, x)

----------------------------------------

(21)
Obligation:
The TRS P consists of the following rules:

   U_31(True, True, NzN, NzM) -> U_3(gt(NzN, NzM), NzN, NzM)
   U_3(True, NzN, NzM) -> GCD(d(NzN, NzM), NzM)
   GCD(NzN, NzM) -> U_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)

The TRS R consists of the following rules:

   p(s(N)) -> N
   +(N, 0) -> N
   +(s(N), s(M)) -> s(s(+(N, M)))
   *(N, 0) -> 0
   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
   gt(0, M) -> False
   gt(NzN, 0) -> u_4(is_NzNat(NzN))
   u_4(True) -> True
   is_NzNat(0) -> False
   is_NzNat(s(N)) -> True
   gt(s(N), s(M)) -> gt(N, M)
   lt(N, M) -> gt(M, N)
   d(0, N) -> N
   d(s(N), s(M)) -> d(N, M)
   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
   u_01(True) -> s(0)
   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
   u_21(True, NzM, N) -> u_2(gt(NzM, N))
   u_2(True) -> 0
   gcd(0, N) -> 0
   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
   u_02(True, NzM) -> NzM
   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

The set E consists of the following equations:

   *(x, y) == *(y, x)
   +(x, y) == +(y, x)
   d(x, y) == d(y, x)
   gcd(x, y) == gcd(y, x)

The set E# consists of the following equations:

   GCD(x, y) == GCD(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(22) EUsableRulesProof (EQUIVALENT)
We use the improved usable rules and equations processor [DA_STEIN] to delete all non-usable rules from R and all non-usable equations from E, but we lose minimality and add the following 2 Ce-rules:
   c(x, y) -> x
   c(x, y) -> y

----------------------------------------

(23)
Obligation:
The TRS P consists of the following rules:

   U_31(True, True, NzN, NzM) -> U_3(gt(NzN, NzM), NzN, NzM)
   U_3(True, NzN, NzM) -> GCD(d(NzN, NzM), NzM)
   GCD(NzN, NzM) -> U_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)

The TRS R consists of the following rules:

   is_NzNat(0) -> False
   gt(NzN, 0) -> u_4(is_NzNat(NzN))
   is_NzNat(s(N)) -> True
   gt(0, M) -> False
   u_4(True) -> True
   d(s(N), s(M)) -> d(N, M)
   gt(s(N), s(M)) -> gt(N, M)
   d(0, N) -> N
   c(x, y) -> x
   c(x, y) -> y

The set E consists of the following equations:

   d(x, y) == d(y, x)

The set E# consists of the following equations:

   GCD(x, y) == GCD(y, x)

We have to consider all (P,E#,R,E)-chains
----------------------------------------

(24)
Obligation:
The TRS P consists of the following rules:

   QUOT(N, NzM) -> U_11(is_NzNat(NzM), N, NzM)
   U_11(True, N, NzM) -> U_1(gt(N, NzM), N, NzM)
   U_1(True, N, NzM) -> QUOT(d(N, NzM), NzM)

The TRS R consists of the following rules:

   p(s(N)) -> N
   +(N, 0) -> N
   +(s(N), s(M)) -> s(s(+(N, M)))
   *(N, 0) -> 0
   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
   gt(0, M) -> False
   gt(NzN, 0) -> u_4(is_NzNat(NzN))
   u_4(True) -> True
   is_NzNat(0) -> False
   is_NzNat(s(N)) -> True
   gt(s(N), s(M)) -> gt(N, M)
   lt(N, M) -> gt(M, N)
   d(0, N) -> N
   d(s(N), s(M)) -> d(N, M)
   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
   u_01(True) -> s(0)
   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
   u_21(True, NzM, N) -> u_2(gt(NzM, N))
   u_2(True) -> 0
   gcd(0, N) -> 0
   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
   u_02(True, NzM) -> NzM
   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

The set E consists of the following equations:

   *(x, y) == *(y, x)
   +(x, y) == +(y, x)
   d(x, y) == d(y, x)
   gcd(x, y) == gcd(y, x)

The set E# consists of the following equations:

   *^1(x, y) == *^1(y, x)
   +^1(x, y) == +^1(y, x)
   D(x, y) == D(y, x)
   GCD(x, y) == GCD(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(25)
Obligation:
The TRS P consists of the following rules:

   +^1(s(N), s(M)) -> +^1(N, M)

The TRS R consists of the following rules:

   p(s(N)) -> N
   +(N, 0) -> N
   +(s(N), s(M)) -> s(s(+(N, M)))
   *(N, 0) -> 0
   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
   gt(0, M) -> False
   gt(NzN, 0) -> u_4(is_NzNat(NzN))
   u_4(True) -> True
   is_NzNat(0) -> False
   is_NzNat(s(N)) -> True
   gt(s(N), s(M)) -> gt(N, M)
   lt(N, M) -> gt(M, N)
   d(0, N) -> N
   d(s(N), s(M)) -> d(N, M)
   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
   u_01(True) -> s(0)
   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
   u_21(True, NzM, N) -> u_2(gt(NzM, N))
   u_2(True) -> 0
   gcd(0, N) -> 0
   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
   u_02(True, NzM) -> NzM
   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

The set E consists of the following equations:

   *(x, y) == *(y, x)
   +(x, y) == +(y, x)
   d(x, y) == d(y, x)
   gcd(x, y) == gcd(y, x)

The set E# consists of the following equations:

   *^1(x, y) == *^1(y, x)
   +^1(x, y) == +^1(y, x)
   D(x, y) == D(y, x)
   GCD(x, y) == GCD(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(26)
Obligation:
The TRS P consists of the following rules:

   *^1(s(N), s(M)) -> *^1(N, M)

The TRS R consists of the following rules:

   p(s(N)) -> N
   +(N, 0) -> N
   +(s(N), s(M)) -> s(s(+(N, M)))
   *(N, 0) -> 0
   *(s(N), s(M)) -> s(+(N, +(M, *(N, M))))
   gt(0, M) -> False
   gt(NzN, 0) -> u_4(is_NzNat(NzN))
   u_4(True) -> True
   is_NzNat(0) -> False
   is_NzNat(s(N)) -> True
   gt(s(N), s(M)) -> gt(N, M)
   lt(N, M) -> gt(M, N)
   d(0, N) -> N
   d(s(N), s(M)) -> d(N, M)
   quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM)
   u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM)
   u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM))
   quot(NzM, NzM) -> u_01(is_NzNat(NzM))
   u_01(True) -> s(0)
   quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N)
   u_21(True, NzM, N) -> u_2(gt(NzM, N))
   u_2(True) -> 0
   gcd(0, N) -> 0
   gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM)
   u_02(True, NzM) -> NzM
   gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM)
   u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM)
   u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM)

The set E consists of the following equations:

   *(x, y) == *(y, x)
   +(x, y) == +(y, x)
   d(x, y) == d(y, x)
   gcd(x, y) == gcd(y, x)

The set E# consists of the following equations:

   *^1(x, y) == *^1(y, x)
   +^1(x, y) == +^1(y, x)
   D(x, y) == D(y, x)
   GCD(x, y) == GCD(y, x)

We have to consider all minimal (P,E#,R,E)-chains