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


Termination of the given ETRS could be proven:

(0) ETRS
(1) EquationalDependencyPairsProof [EQUIVALENT, 23 ms]
(2) EDP
(3) EDPPoloProof [EQUIVALENT, 50 ms]
(4) EDP
(5) EDPPoloProof [EQUIVALENT, 0 ms]
(6) EDP
(7) PisEmptyProof [EQUIVALENT, 3 ms]
(8) YES


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

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

   times(plus(x, y), z) -> plus(times(x, z), times(y, z))
   times(z, plus(x, f(y))) -> times(g(z, y), plus(x, a))

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:

   TIMES(plus(x, y), z) -> TIMES(x, z)
   TIMES(plus(x, y), z) -> TIMES(y, z)
   TIMES(z, plus(x, f(y))) -> TIMES(g(z, y), plus(x, a))
   TIMES(times(plus(x, y), z), ext) -> TIMES(plus(times(x, z), times(y, z)), ext)
   TIMES(times(plus(x, y), z), ext) -> TIMES(x, z)
   TIMES(times(plus(x, y), z), ext) -> TIMES(y, z)
   TIMES(times(z, plus(x, f(y))), ext) -> TIMES(times(g(z, y), plus(x, a)), ext)
   TIMES(times(z, plus(x, f(y))), ext) -> TIMES(g(z, y), plus(x, a))

The TRS R consists of the following rules:

   times(plus(x, y), z) -> plus(times(x, z), times(y, z))
   times(z, plus(x, f(y))) -> times(g(z, y), plus(x, a))
   times(times(plus(x, y), z), ext) -> times(plus(times(x, z), times(y, z)), ext)
   times(times(z, plus(x, f(y))), ext) -> times(times(g(z, y), plus(x, a)), 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(x, y) == TIMES(y, x)
   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:

   TIMES(plus(x, y), z) -> TIMES(x, z)
   TIMES(plus(x, y), z) -> TIMES(y, z)
   TIMES(z, plus(x, f(y))) -> TIMES(g(z, y), plus(x, a))
   TIMES(times(plus(x, y), z), ext) -> TIMES(plus(times(x, z), times(y, z)), ext)
   TIMES(times(plus(x, y), z), ext) -> TIMES(x, z)
   TIMES(times(plus(x, y), z), ext) -> TIMES(y, z)
   TIMES(times(z, plus(x, f(y))), ext) -> TIMES(times(g(z, y), plus(x, a)), ext)
   TIMES(times(z, plus(x, f(y))), ext) -> TIMES(g(z, y), plus(x, a))

The TRS R consists of the following rules:

   times(plus(x, y), z) -> plus(times(x, z), times(y, z))
   times(z, plus(x, f(y))) -> times(g(z, y), plus(x, a))
   times(times(plus(x, y), z), ext) -> times(plus(times(x, z), times(y, z)), ext)
   times(times(z, plus(x, f(y))), ext) -> times(times(g(z, y), plus(x, a)), 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(x, y) == TIMES(y, x)
   TIMES(times(x, y), z) == TIMES(x, times(y, z))

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

(3) 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(plus(x, y), z) -> TIMES(x, z)
   TIMES(plus(x, y), z) -> TIMES(y, z)
   TIMES(z, plus(x, f(y))) -> TIMES(g(z, y), plus(x, a))
   TIMES(times(plus(x, y), z), ext) -> TIMES(x, z)
   TIMES(times(plus(x, y), z), ext) -> TIMES(y, z)
   TIMES(times(z, plus(x, f(y))), ext) -> TIMES(times(g(z, y), plus(x, a)), ext)
   TIMES(times(z, plus(x, f(y))), ext) -> TIMES(g(z, y), plus(x, a))
The remaining Dependency Pairs were at least non-strictly oriented.


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


   times(z, plus(x, f(y))) -> times(g(z, y), plus(x, a))
   times(times(plus(x, y), z), ext) -> times(plus(times(x, z), times(y, z)), ext)
   times(times(z, plus(x, f(y))), ext) -> times(times(g(z, y), plus(x, a)), ext)
   times(plus(x, y), z) -> plus(times(x, z), times(y, z))
We had to orient the following equations of E# equivalently.


   TIMES(x, y) == TIMES(y, x)
   TIMES(times(x, y), z) == TIMES(x, times(y, z))
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(TIMES(x_1, x_2)) = x_1 + x_1*x_2 + x_2
   POL(a) = 0
   POL(f(x_1)) = 1
   POL(g(x_1, x_2)) = 0
   POL(plus(x_1, x_2)) = 1 + x_1 + x_2
   POL(times(x_1, x_2)) = x_1 + x_1*x_2 + x_2


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

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

   TIMES(times(plus(x, y), z), ext) -> TIMES(plus(times(x, z), times(y, z)), ext)

The TRS R consists of the following rules:

   times(plus(x, y), z) -> plus(times(x, z), times(y, z))
   times(z, plus(x, f(y))) -> times(g(z, y), plus(x, a))
   times(times(plus(x, y), z), ext) -> times(plus(times(x, z), times(y, z)), ext)
   times(times(z, plus(x, f(y))), ext) -> times(times(g(z, y), plus(x, a)), 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(x, y) == TIMES(y, x)
   TIMES(times(x, y), z) == TIMES(x, times(y, z))

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

(5) 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(plus(x, y), z), ext) -> TIMES(plus(times(x, z), times(y, z)), ext)
With the implicit AFS we had to orient the following set of usable rules of R non-strictly.


   times(z, plus(x, f(y))) -> times(g(z, y), plus(x, a))
   times(times(plus(x, y), z), ext) -> times(plus(times(x, z), times(y, z)), ext)
   times(times(z, plus(x, f(y))), ext) -> times(times(g(z, y), plus(x, a)), ext)
   times(plus(x, y), z) -> plus(times(x, z), times(y, z))
We had to orient the following equations of E# equivalently.


   TIMES(x, y) == TIMES(y, x)
   TIMES(times(x, y), z) == TIMES(x, times(y, z))
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)
   times(x, y) == times(y, x)
   times(times(x, y), z) == times(x, times(y, z))
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(TIMES(x_1, x_2)) = 2*x_1 + 2*x_2
   POL(a) = 0
   POL(f(x_1)) = 0
   POL(g(x_1, x_2)) = x_1
   POL(plus(x_1, x_2)) = 1
   POL(times(x_1, x_2)) = 1 + x_1 + x_2


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

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

   times(plus(x, y), z) -> plus(times(x, z), times(y, z))
   times(z, plus(x, f(y))) -> times(g(z, y), plus(x, a))
   times(times(plus(x, y), z), ext) -> times(plus(times(x, z), times(y, z)), ext)
   times(times(z, plus(x, f(y))), ext) -> times(times(g(z, y), plus(x, a)), 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(x, y) == TIMES(y, x)
   TIMES(times(x, y), z) == TIMES(x, times(y, z))

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

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

(8)
YES