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


Termination of the given ETRS could be proven:

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


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

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

   plus(x, 0) -> x
   plus(0, y) -> y
   plus(s(x), y) -> s(plus(x, y))
   times(0, y) -> 0
   times(s(0), y) -> y
   times(s(x), y) -> plus(y, times(x, y))
   div(0, y) -> 0
   div(x, y) -> quot(x, y, y)
   quot(0, s(y), z) -> 0
   quot(s(x), s(y), z) -> quot(x, y, z)
   quot(x, 0, s(z)) -> s(div(x, s(z)))
   div(div(x, y), z) -> div(x, times(y, z))

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   times(x, y) == times(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))
   times(times(x, y), z) == times(x, times(y, z))


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

(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:

   PLUS(s(x), y) -> PLUS(x, y)
   TIMES(s(x), y) -> PLUS(y, times(x, y))
   TIMES(s(x), y) -> TIMES(x, y)
   DIV(x, y) -> QUOT(x, y, y)
   QUOT(s(x), s(y), z) -> QUOT(x, y, z)
   QUOT(x, 0, s(z)) -> DIV(x, s(z))
   DIV(div(x, y), z) -> DIV(x, times(y, z))
   DIV(div(x, y), z) -> TIMES(y, z)
   PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext)
   PLUS(plus(s(x), y), ext) -> PLUS(x, y)
   TIMES(times(0, y), ext) -> TIMES(0, ext)
   TIMES(times(s(x), y), ext) -> TIMES(plus(y, times(x, y)), ext)
   TIMES(times(s(x), y), ext) -> PLUS(y, times(x, y))
   TIMES(times(s(x), y), ext) -> TIMES(x, y)

The TRS R consists of the following rules:

   plus(x, 0) -> x
   plus(0, y) -> y
   plus(s(x), y) -> s(plus(x, y))
   times(0, y) -> 0
   times(s(0), y) -> y
   times(s(x), y) -> plus(y, times(x, y))
   div(0, y) -> 0
   div(x, y) -> quot(x, y, y)
   quot(0, s(y), z) -> 0
   quot(s(x), s(y), z) -> quot(x, y, z)
   quot(x, 0, s(z)) -> s(div(x, s(z)))
   div(div(x, y), z) -> div(x, times(y, z))
   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   times(times(0, y), ext) -> times(0, ext)
   times(times(s(x), y), ext) -> times(plus(y, times(x, y)), ext)

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   times(x, y) == times(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))
   times(times(x, y), z) == times(x, times(y, z))

The set E# consists of the following equations:

   PLUS(x, y) == PLUS(y, x)
   TIMES(x, y) == TIMES(y, x)
   PLUS(plus(x, y), z) == PLUS(x, plus(y, z))
   TIMES(times(x, y), z) == TIMES(x, times(y, z))

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

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

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

   PLUS(s(x), y) -> PLUS(x, y)
   TIMES(s(x), y) -> PLUS(y, times(x, y))
   TIMES(s(x), y) -> TIMES(x, y)
   DIV(x, y) -> QUOT(x, y, y)
   QUOT(s(x), s(y), z) -> QUOT(x, y, z)
   QUOT(x, 0, s(z)) -> DIV(x, s(z))
   DIV(div(x, y), z) -> DIV(x, times(y, z))
   DIV(div(x, y), z) -> TIMES(y, z)
   PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext)
   PLUS(plus(s(x), y), ext) -> PLUS(x, y)
   TIMES(times(0, y), ext) -> TIMES(0, ext)
   TIMES(times(s(x), y), ext) -> TIMES(plus(y, times(x, y)), ext)
   TIMES(times(s(x), y), ext) -> PLUS(y, times(x, y))
   TIMES(times(s(x), y), ext) -> TIMES(x, y)

The TRS R consists of the following rules:

   plus(x, 0) -> x
   plus(0, y) -> y
   plus(s(x), y) -> s(plus(x, y))
   times(0, y) -> 0
   times(s(0), y) -> y
   times(s(x), y) -> plus(y, times(x, y))
   div(0, y) -> 0
   div(x, y) -> quot(x, y, y)
   quot(0, s(y), z) -> 0
   quot(s(x), s(y), z) -> quot(x, y, z)
   quot(x, 0, s(z)) -> s(div(x, s(z)))
   div(div(x, y), z) -> div(x, times(y, z))
   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   times(times(0, y), ext) -> times(0, ext)
   times(times(s(x), y), ext) -> times(plus(y, times(x, y)), ext)

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   times(x, y) == times(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))
   times(times(x, y), z) == times(x, times(y, z))

The set E# consists of the following equations:

   PLUS(x, y) == PLUS(y, x)
   TIMES(x, y) == TIMES(y, x)
   PLUS(plus(x, y), z) == PLUS(x, plus(y, z))
   TIMES(times(x, y), z) == TIMES(x, times(y, z))

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

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

(4)
Complex Obligation (AND)

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

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

   PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext)
   PLUS(s(x), y) -> PLUS(x, y)
   PLUS(plus(s(x), y), ext) -> PLUS(x, y)

The TRS R consists of the following rules:

   plus(x, 0) -> x
   plus(0, y) -> y
   plus(s(x), y) -> s(plus(x, y))
   times(0, y) -> 0
   times(s(0), y) -> y
   times(s(x), y) -> plus(y, times(x, y))
   div(0, y) -> 0
   div(x, y) -> quot(x, y, y)
   quot(0, s(y), z) -> 0
   quot(s(x), s(y), z) -> quot(x, y, z)
   quot(x, 0, s(z)) -> s(div(x, s(z)))
   div(div(x, y), z) -> div(x, times(y, z))
   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   times(times(0, y), ext) -> times(0, ext)
   times(times(s(x), y), ext) -> times(plus(y, times(x, y)), ext)

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   times(x, y) == times(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))
   times(times(x, y), z) == times(x, times(y, z))

The set E# consists of the following equations:

   PLUS(x, y) == PLUS(y, x)
   TIMES(x, y) == TIMES(y, x)
   PLUS(plus(x, y), z) == PLUS(x, plus(y, z))
   TIMES(times(x, y), z) == TIMES(x, times(y, z))

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]:
   TIMES(x, y) == TIMES(y, x)
   TIMES(times(x, y), z) == TIMES(x, times(y, z))

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

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

   PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext)
   PLUS(s(x), y) -> PLUS(x, y)
   PLUS(plus(s(x), y), ext) -> PLUS(x, y)

The TRS R consists of the following rules:

   plus(x, 0) -> x
   plus(0, y) -> y
   plus(s(x), y) -> s(plus(x, y))
   times(0, y) -> 0
   times(s(0), y) -> y
   times(s(x), y) -> plus(y, times(x, y))
   div(0, y) -> 0
   div(x, y) -> quot(x, y, y)
   quot(0, s(y), z) -> 0
   quot(s(x), s(y), z) -> quot(x, y, z)
   quot(x, 0, s(z)) -> s(div(x, s(z)))
   div(div(x, y), z) -> div(x, times(y, z))
   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   times(times(0, y), ext) -> times(0, ext)
   times(times(s(x), y), ext) -> times(plus(y, times(x, y)), ext)

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   times(x, y) == times(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))
   times(times(x, y), z) == times(x, times(y, z))

The set E# consists of the following equations:

   PLUS(plus(x, y), z) == PLUS(x, plus(y, z))
   PLUS(x, y) == PLUS(y, x)

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

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

No dependency pairs are removed.

The following rules are removed from R:

   plus(x, 0) -> x
   plus(0, y) -> y
   times(0, y) -> 0
   times(s(0), y) -> y
   times(s(x), y) -> plus(y, times(x, y))
   div(0, y) -> 0
   div(x, y) -> quot(x, y, y)
   quot(0, s(y), z) -> 0
   quot(s(x), s(y), z) -> quot(x, y, z)
   quot(x, 0, s(z)) -> s(div(x, s(z)))
   div(div(x, y), z) -> div(x, times(y, z))
   times(times(0, y), ext) -> times(0, ext)
   times(times(s(x), y), ext) -> times(plus(y, times(x, y)), ext)
The following equations are removed from E:

   times(x, y) == times(y, x)
   times(times(x, y), z) == times(x, times(y, z))
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(PLUS(x_1, x_2)) = x_1 + x_2
   POL(plus(x_1, x_2)) = x_1 + x_2
   POL(s(x_1)) = x_1


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

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

   PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext)
   PLUS(s(x), y) -> PLUS(x, y)
   PLUS(plus(s(x), y), ext) -> PLUS(x, y)

The TRS R consists of the following rules:

   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   plus(s(x), y) -> s(plus(x, y))

The set E consists of the following equations:

   plus(plus(x, y), z) == plus(x, plus(y, z))
   plus(x, y) == plus(y, x)

The set E# consists of the following equations:

   PLUS(plus(x, y), z) == PLUS(x, plus(y, z))
   PLUS(x, y) == PLUS(y, x)

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

(10) ERuleRemovalProof (EQUIVALENT)
By using the rule removal processor [DA_STEIN] with the following polynomial ordering [POLO], at least one Dependency Pair or term rewrite system rule of this EDP problem can be strictly oriented.

Strictly oriented dependency pairs:

   PLUS(s(x), y) -> PLUS(x, y)
   PLUS(plus(s(x), y), ext) -> PLUS(x, y)


Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(PLUS(x_1, x_2)) = 2*x_1 + 2*x_2
   POL(plus(x_1, x_2)) = x_1 + x_2
   POL(s(x_1)) = 1 + x_1


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

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

   PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext)

The TRS R consists of the following rules:

   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   plus(s(x), y) -> s(plus(x, y))

The set E consists of the following equations:

   plus(plus(x, y), z) == plus(x, plus(y, z))
   plus(x, y) == plus(y, x)

The set E# consists of the following equations:

   PLUS(plus(x, y), z) == PLUS(x, plus(y, z))
   PLUS(x, y) == PLUS(y, x)

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

(12) EDPPoloProof (EQUIVALENT)
We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented.


   PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext)
With the implicit AFS we had to orient the following set of usable rules of R non-strictly.


   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   plus(s(x), y) -> s(plus(x, y))
We had to orient the following equations of E# equivalently.


   PLUS(plus(x, y), z) == PLUS(x, plus(y, z))
   PLUS(x, y) == PLUS(y, x)
With the implicit AFS we had to orient the following usable equations of E equivalently.


   plus(plus(x, y), z) == plus(x, plus(y, z))
   plus(x, y) == plus(y, x)
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(PLUS(x_1, x_2)) = x_1 + x_2
   POL(plus(x_1, x_2)) = 1 + x_1 + x_2
   POL(s(x_1)) = 0


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

(13)
Obligation:
P is empty.
The TRS R consists of the following rules:

   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   plus(s(x), y) -> s(plus(x, y))

The set E consists of the following equations:

   plus(plus(x, y), z) == plus(x, plus(y, z))
   plus(x, y) == plus(y, x)

The set E# consists of the following equations:

   PLUS(plus(x, y), z) == PLUS(x, plus(y, z))
   PLUS(x, y) == PLUS(y, x)

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

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

(15)
YES

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

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

   TIMES(times(s(x), y), ext) -> TIMES(plus(y, times(x, y)), ext)
   TIMES(s(x), y) -> TIMES(x, y)
   TIMES(times(s(x), y), ext) -> TIMES(x, y)
   TIMES(times(0, y), ext) -> TIMES(0, ext)

The TRS R consists of the following rules:

   plus(x, 0) -> x
   plus(0, y) -> y
   plus(s(x), y) -> s(plus(x, y))
   times(0, y) -> 0
   times(s(0), y) -> y
   times(s(x), y) -> plus(y, times(x, y))
   div(0, y) -> 0
   div(x, y) -> quot(x, y, y)
   quot(0, s(y), z) -> 0
   quot(s(x), s(y), z) -> quot(x, y, z)
   quot(x, 0, s(z)) -> s(div(x, s(z)))
   div(div(x, y), z) -> div(x, times(y, z))
   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   times(times(0, y), ext) -> times(0, ext)
   times(times(s(x), y), ext) -> times(plus(y, times(x, y)), ext)

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   times(x, y) == times(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))
   times(times(x, y), z) == times(x, times(y, z))

The set E# consists of the following equations:

   PLUS(x, y) == PLUS(y, x)
   TIMES(x, y) == TIMES(y, x)
   PLUS(plus(x, y), z) == PLUS(x, plus(y, z))
   TIMES(times(x, y), z) == TIMES(x, times(y, z))

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

(17) ESharpUsableEquationsProof (EQUIVALENT)
We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
   PLUS(x, y) == PLUS(y, x)
   PLUS(plus(x, y), z) == PLUS(x, plus(y, z))

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

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

   TIMES(times(s(x), y), ext) -> TIMES(plus(y, times(x, y)), ext)
   TIMES(s(x), y) -> TIMES(x, y)
   TIMES(times(s(x), y), ext) -> TIMES(x, y)
   TIMES(times(0, y), ext) -> TIMES(0, ext)

The TRS R consists of the following rules:

   plus(x, 0) -> x
   plus(0, y) -> y
   plus(s(x), y) -> s(plus(x, y))
   times(0, y) -> 0
   times(s(0), y) -> y
   times(s(x), y) -> plus(y, times(x, y))
   div(0, y) -> 0
   div(x, y) -> quot(x, y, y)
   quot(0, s(y), z) -> 0
   quot(s(x), s(y), z) -> quot(x, y, z)
   quot(x, 0, s(z)) -> s(div(x, s(z)))
   div(div(x, y), z) -> div(x, times(y, z))
   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   times(times(0, y), ext) -> times(0, ext)
   times(times(s(x), y), ext) -> times(plus(y, times(x, y)), ext)

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   times(x, y) == times(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))
   times(times(x, y), z) == times(x, times(y, z))

The set E# consists of the following equations:

   TIMES(times(x, y), z) == TIMES(x, times(y, z))
   TIMES(x, y) == TIMES(y, x)

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

(19) EDPPoloProof (EQUIVALENT)
We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented.


   TIMES(times(s(x), y), ext) -> TIMES(plus(y, times(x, y)), ext)
   TIMES(s(x), y) -> TIMES(x, y)
   TIMES(times(s(x), y), ext) -> TIMES(x, y)
The remaining Dependency Pairs were at least non-strictly oriented.


   TIMES(times(0, y), ext) -> TIMES(0, ext)
With the implicit AFS we had to orient the following set of usable rules of R non-strictly.


   times(s(x), y) -> plus(y, times(x, y))
   times(times(0, y), ext) -> times(0, ext)
   times(times(s(x), y), ext) -> times(plus(y, times(x, y)), ext)
   times(s(0), y) -> y
   times(0, y) -> 0
   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   plus(s(x), y) -> s(plus(x, y))
   plus(x, 0) -> x
   plus(0, y) -> y
We had to orient the following equations of E# equivalently.


   TIMES(times(x, y), z) == TIMES(x, times(y, z))
   TIMES(x, y) == TIMES(y, x)
With the implicit AFS we had to orient the following usable equations of E equivalently.


   times(x, y) == times(y, x)
   times(times(x, y), z) == times(x, times(y, z))
   plus(plus(x, y), z) == plus(x, plus(y, z))
   plus(x, y) == plus(y, x)
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(TIMES(x_1, x_2)) = x_1 + x_1*x_2 + x_2
   POL(plus(x_1, x_2)) = x_1 + x_2
   POL(s(x_1)) = 1 + x_1
   POL(times(x_1, x_2)) = x_1 + x_1*x_2 + x_2


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

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

   TIMES(times(0, y), ext) -> TIMES(0, ext)

The TRS R consists of the following rules:

   plus(x, 0) -> x
   plus(0, y) -> y
   plus(s(x), y) -> s(plus(x, y))
   times(0, y) -> 0
   times(s(0), y) -> y
   times(s(x), y) -> plus(y, times(x, y))
   div(0, y) -> 0
   div(x, y) -> quot(x, y, y)
   quot(0, s(y), z) -> 0
   quot(s(x), s(y), z) -> quot(x, y, z)
   quot(x, 0, s(z)) -> s(div(x, s(z)))
   div(div(x, y), z) -> div(x, times(y, z))
   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   times(times(0, y), ext) -> times(0, ext)
   times(times(s(x), y), ext) -> times(plus(y, times(x, y)), ext)

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   times(x, y) == times(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))
   times(times(x, y), z) == times(x, times(y, z))

The set E# consists of the following equations:

   TIMES(times(x, y), z) == TIMES(x, times(y, z))
   TIMES(x, y) == TIMES(y, x)

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

(21) EDPPoloProof (EQUIVALENT)
We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented.


   TIMES(times(0, y), ext) -> TIMES(0, ext)
With the implicit AFS we had to orient the following set of usable rules of R non-strictly.


   times(s(x), y) -> plus(y, times(x, y))
   times(times(0, y), ext) -> times(0, ext)
   times(times(s(x), y), ext) -> times(plus(y, times(x, y)), ext)
   times(s(0), y) -> y
   times(0, y) -> 0
   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   plus(s(x), y) -> s(plus(x, y))
   plus(x, 0) -> x
   plus(0, y) -> y
We had to orient the following equations of E# equivalently.


   TIMES(times(x, y), z) == TIMES(x, times(y, z))
   TIMES(x, y) == TIMES(y, x)
With the implicit AFS we had to orient the following usable equations of E equivalently.


   times(x, y) == times(y, x)
   times(times(x, y), z) == times(x, times(y, z))
   plus(plus(x, y), z) == plus(x, plus(y, z))
   plus(x, y) == plus(y, x)
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(0) = 1
   POL(TIMES(x_1, x_2)) = x_1 + x_1*x_2 + x_2
   POL(plus(x_1, x_2)) = 2 + x_1 + x_2
   POL(s(x_1)) = 2 + x_1
   POL(times(x_1, x_2)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_2


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

(22)
Obligation:
P is empty.
The TRS R consists of the following rules:

   plus(x, 0) -> x
   plus(0, y) -> y
   plus(s(x), y) -> s(plus(x, y))
   times(0, y) -> 0
   times(s(0), y) -> y
   times(s(x), y) -> plus(y, times(x, y))
   div(0, y) -> 0
   div(x, y) -> quot(x, y, y)
   quot(0, s(y), z) -> 0
   quot(s(x), s(y), z) -> quot(x, y, z)
   quot(x, 0, s(z)) -> s(div(x, s(z)))
   div(div(x, y), z) -> div(x, times(y, z))
   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   times(times(0, y), ext) -> times(0, ext)
   times(times(s(x), y), ext) -> times(plus(y, times(x, y)), ext)

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   times(x, y) == times(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))
   times(times(x, y), z) == times(x, times(y, z))

The set E# consists of the following equations:

   TIMES(times(x, y), z) == TIMES(x, times(y, z))
   TIMES(x, y) == TIMES(y, x)

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

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

(24)
YES

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

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

   QUOT(s(x), s(y), z) -> QUOT(x, y, z)
   QUOT(x, 0, s(z)) -> DIV(x, s(z))
   DIV(x, y) -> QUOT(x, y, y)
   DIV(div(x, y), z) -> DIV(x, times(y, z))

The TRS R consists of the following rules:

   plus(x, 0) -> x
   plus(0, y) -> y
   plus(s(x), y) -> s(plus(x, y))
   times(0, y) -> 0
   times(s(0), y) -> y
   times(s(x), y) -> plus(y, times(x, y))
   div(0, y) -> 0
   div(x, y) -> quot(x, y, y)
   quot(0, s(y), z) -> 0
   quot(s(x), s(y), z) -> quot(x, y, z)
   quot(x, 0, s(z)) -> s(div(x, s(z)))
   div(div(x, y), z) -> div(x, times(y, z))
   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   times(times(0, y), ext) -> times(0, ext)
   times(times(s(x), y), ext) -> times(plus(y, times(x, y)), ext)

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   times(x, y) == times(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))
   times(times(x, y), z) == times(x, times(y, z))

The set E# consists of the following equations:

   PLUS(x, y) == PLUS(y, x)
   TIMES(x, y) == TIMES(y, x)
   PLUS(plus(x, y), z) == PLUS(x, plus(y, z))
   TIMES(times(x, y), z) == TIMES(x, times(y, z))

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

(26) ESharpUsableEquationsProof (EQUIVALENT)
We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
   PLUS(x, y) == PLUS(y, x)
   TIMES(x, y) == TIMES(y, x)
   PLUS(plus(x, y), z) == PLUS(x, plus(y, z))
   TIMES(times(x, y), z) == TIMES(x, times(y, z))

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

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

   QUOT(s(x), s(y), z) -> QUOT(x, y, z)
   QUOT(x, 0, s(z)) -> DIV(x, s(z))
   DIV(x, y) -> QUOT(x, y, y)
   DIV(div(x, y), z) -> DIV(x, times(y, z))

The TRS R consists of the following rules:

   plus(x, 0) -> x
   plus(0, y) -> y
   plus(s(x), y) -> s(plus(x, y))
   times(0, y) -> 0
   times(s(0), y) -> y
   times(s(x), y) -> plus(y, times(x, y))
   div(0, y) -> 0
   div(x, y) -> quot(x, y, y)
   quot(0, s(y), z) -> 0
   quot(s(x), s(y), z) -> quot(x, y, z)
   quot(x, 0, s(z)) -> s(div(x, s(z)))
   div(div(x, y), z) -> div(x, times(y, z))
   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   times(times(0, y), ext) -> times(0, ext)
   times(times(s(x), y), ext) -> times(plus(y, times(x, y)), ext)

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   times(x, y) == times(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))
   times(times(x, y), z) == times(x, times(y, z))

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

(28) EDPPoloProof (EQUIVALENT)
We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented.


   QUOT(s(x), s(y), z) -> QUOT(x, y, z)
   DIV(div(x, y), z) -> DIV(x, times(y, z))
The remaining Dependency Pairs were at least non-strictly oriented.


   QUOT(x, 0, s(z)) -> DIV(x, s(z))
   DIV(x, y) -> QUOT(x, y, y)
With the implicit AFS there is no usable rule of R.


There is no equation of E#.


With the implicit AFS there is no usable equation of E.


Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(0) = 3
   POL(DIV(x_1, x_2)) = 3 + 2*x_1
   POL(QUOT(x_1, x_2, x_3)) = 3 + 2*x_1
   POL(div(x_1, x_2)) = 3 + 3*x_1 + 3*x_2
   POL(plus(x_1, x_2)) = 2 + 3*x_1 + 2*x_2
   POL(s(x_1)) = 3 + 3*x_1
   POL(times(x_1, x_2)) = 3 + 2*x_1 + 3*x_2


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

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

   QUOT(x, 0, s(z)) -> DIV(x, s(z))
   DIV(x, y) -> QUOT(x, y, y)

The TRS R consists of the following rules:

   plus(x, 0) -> x
   plus(0, y) -> y
   plus(s(x), y) -> s(plus(x, y))
   times(0, y) -> 0
   times(s(0), y) -> y
   times(s(x), y) -> plus(y, times(x, y))
   div(0, y) -> 0
   div(x, y) -> quot(x, y, y)
   quot(0, s(y), z) -> 0
   quot(s(x), s(y), z) -> quot(x, y, z)
   quot(x, 0, s(z)) -> s(div(x, s(z)))
   div(div(x, y), z) -> div(x, times(y, z))
   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   times(times(0, y), ext) -> times(0, ext)
   times(times(s(x), y), ext) -> times(plus(y, times(x, y)), ext)

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   times(x, y) == times(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))
   times(times(x, y), z) == times(x, times(y, z))

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

(30) EDPPoloProof (EQUIVALENT)
We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented.


   QUOT(x, 0, s(z)) -> DIV(x, s(z))
   DIV(x, y) -> QUOT(x, y, y)
With the implicit AFS there is no usable rule of R.


There is no equation of E#.


With the implicit AFS there is no usable equation of E.


Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(0) = 3
   POL(DIV(x_1, x_2)) = 2 + 2*x_2
   POL(QUOT(x_1, x_2, x_3)) = 1 + 2*x_2
   POL(s(x_1)) = 1


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

(31)
Obligation:
P is empty.
The TRS R consists of the following rules:

   plus(x, 0) -> x
   plus(0, y) -> y
   plus(s(x), y) -> s(plus(x, y))
   times(0, y) -> 0
   times(s(0), y) -> y
   times(s(x), y) -> plus(y, times(x, y))
   div(0, y) -> 0
   div(x, y) -> quot(x, y, y)
   quot(0, s(y), z) -> 0
   quot(s(x), s(y), z) -> quot(x, y, z)
   quot(x, 0, s(z)) -> s(div(x, s(z)))
   div(div(x, y), z) -> div(x, times(y, z))
   plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext)
   times(times(0, y), ext) -> times(0, ext)
   times(times(s(x), y), ext) -> times(plus(y, times(x, y)), ext)

The set E consists of the following equations:

   plus(x, y) == plus(y, x)
   times(x, y) == times(y, x)
   plus(plus(x, y), z) == plus(x, plus(y, z))
   times(times(x, y), z) == times(x, times(y, z))

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

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

(33)
YES