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, 17 ms]
(2) EDP
(3) ERuleRemovalProof [EQUIVALENT, 22 ms]
(4) EDP
(5) EDPPoloProof [EQUIVALENT, 15 ms]
(6) EDP
(7) PisEmptyProof [EQUIVALENT, 0 ms]
(8) YES


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

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

   +(g(x), g(y)) -> g(+(g(a), +(x, y)))

The set E consists of the following equations:

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

   +^1(g(x), g(y)) -> +^1(g(a), +(x, y))
   +^1(g(x), g(y)) -> +^1(x, y)
   +^1(+(g(x), g(y)), ext) -> +^1(g(+(g(a), +(x, y))), ext)
   +^1(+(g(x), g(y)), ext) -> +^1(g(a), +(x, y))
   +^1(+(g(x), g(y)), ext) -> +^1(x, y)

The TRS R consists of the following rules:

   +(g(x), g(y)) -> g(+(g(a), +(x, y)))
   +(+(g(x), g(y)), ext) -> +(g(+(g(a), +(x, y))), ext)

The set E consists of the following equations:

   +(x, y) == +(y, x)
   +(+(x, y), z) == +(x, +(y, z))

The set E# consists of the following equations:

   +^1(x, y) == +^1(y, x)
   +^1(+(x, y), z) == +^1(x, +(y, z))

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

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

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

   +^1(g(x), g(y)) -> +^1(g(a), +(x, y))
   +^1(g(x), g(y)) -> +^1(x, y)
   +^1(+(g(x), g(y)), ext) -> +^1(g(+(g(a), +(x, y))), ext)
   +^1(+(g(x), g(y)), ext) -> +^1(g(a), +(x, y))
   +^1(+(g(x), g(y)), ext) -> +^1(x, y)

The TRS R consists of the following rules:

   +(g(x), g(y)) -> g(+(g(a), +(x, y)))
   +(+(g(x), g(y)), ext) -> +(g(+(g(a), +(x, y))), ext)

The set E consists of the following equations:

   +(x, y) == +(y, x)
   +(+(x, y), z) == +(x, +(y, z))

The set E# consists of the following equations:

   +^1(x, y) == +^1(y, x)
   +^1(+(x, y), z) == +^1(x, +(y, z))

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

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

   +^1(g(x), g(y)) -> +^1(g(a), +(x, y))
   +^1(g(x), g(y)) -> +^1(x, y)
   +^1(+(g(x), g(y)), ext) -> +^1(g(a), +(x, y))
   +^1(+(g(x), g(y)), ext) -> +^1(x, y)


Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(+(x_1, x_2)) = x_1 + x_2
   POL(+^1(x_1, x_2)) = x_1 + x_2
   POL(a) = 0
   POL(g(x_1)) = 1 + x_1


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

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

   +^1(+(g(x), g(y)), ext) -> +^1(g(+(g(a), +(x, y))), ext)

The TRS R consists of the following rules:

   +(g(x), g(y)) -> g(+(g(a), +(x, y)))
   +(+(g(x), g(y)), ext) -> +(g(+(g(a), +(x, y))), ext)

The set E consists of the following equations:

   +(x, y) == +(y, x)
   +(+(x, y), z) == +(x, +(y, z))

The set E# consists of the following equations:

   +^1(x, y) == +^1(y, x)
   +^1(+(x, y), z) == +^1(x, +(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.


   +^1(+(g(x), g(y)), ext) -> +^1(g(+(g(a), +(x, y))), ext)
With the implicit AFS we had to orient the following set of usable rules of R non-strictly.


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


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


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

   POL(+(x_1, x_2)) = x_1 + x_2
   POL(+^1(x_1, x_2)) = x_1 + x_2
   POL(a) = 0
   POL(g(x_1)) = 2


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

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

   +(g(x), g(y)) -> g(+(g(a), +(x, y)))
   +(+(g(x), g(y)), ext) -> +(g(+(g(a), +(x, y))), ext)

The set E consists of the following equations:

   +(x, y) == +(y, x)
   +(+(x, y), z) == +(x, +(y, z))

The set E# consists of the following equations:

   +^1(x, y) == +^1(y, x)
   +^1(+(x, y), z) == +^1(x, +(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