(0) Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
h(e(x), y) → h(d(x, y), s(y))
d(g(g(0, x), y), s(z)) → g(e(x), d(g(g(0, x), y), z))
d(g(g(0, x), y), 0) → e(y)
d(g(0, x), y) → e(x)
d(g(x, y), z) → g(d(x, z), e(y))
g(e(x), e(y)) → e(g(x, y))
Q is empty.
(1) DependencyPairsProof (EQUIVALENT transformation)
Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
(2) Obligation:
Q DP problem:
The TRS P consists of the following rules:
H(e(x), y) → H(d(x, y), s(y))
H(e(x), y) → D(x, y)
D(g(g(0, x), y), s(z)) → G(e(x), d(g(g(0, x), y), z))
D(g(g(0, x), y), s(z)) → D(g(g(0, x), y), z)
D(g(x, y), z) → G(d(x, z), e(y))
D(g(x, y), z) → D(x, z)
G(e(x), e(y)) → G(x, y)
The TRS R consists of the following rules:
h(e(x), y) → h(d(x, y), s(y))
d(g(g(0, x), y), s(z)) → g(e(x), d(g(g(0, x), y), z))
d(g(g(0, x), y), 0) → e(y)
d(g(0, x), y) → e(x)
d(g(x, y), z) → g(d(x, z), e(y))
g(e(x), e(y)) → e(g(x, y))
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(3) DependencyGraphProof (EQUIVALENT transformation)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 3 less nodes.
(4) Complex Obligation (AND)
(5) Obligation:
Q DP problem:
The TRS P consists of the following rules:
G(e(x), e(y)) → G(x, y)
The TRS R consists of the following rules:
h(e(x), y) → h(d(x, y), s(y))
d(g(g(0, x), y), s(z)) → g(e(x), d(g(g(0, x), y), z))
d(g(g(0, x), y), 0) → e(y)
d(g(0, x), y) → e(x)
d(g(x, y), z) → g(d(x, z), e(y))
g(e(x), e(y)) → e(g(x, y))
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(6) UsableRulesProof (EQUIVALENT transformation)
We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
(7) Obligation:
Q DP problem:
The TRS P consists of the following rules:
G(e(x), e(y)) → G(x, y)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(8) 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:
- G(e(x), e(y)) → G(x, y)
The graph contains the following edges 1 > 1, 2 > 2
(9) TRUE
(10) Obligation:
Q DP problem:
The TRS P consists of the following rules:
D(g(x, y), z) → D(x, z)
D(g(g(0, x), y), s(z)) → D(g(g(0, x), y), z)
The TRS R consists of the following rules:
h(e(x), y) → h(d(x, y), s(y))
d(g(g(0, x), y), s(z)) → g(e(x), d(g(g(0, x), y), z))
d(g(g(0, x), y), 0) → e(y)
d(g(0, x), y) → e(x)
d(g(x, y), z) → g(d(x, z), e(y))
g(e(x), e(y)) → e(g(x, y))
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(11) UsableRulesProof (EQUIVALENT transformation)
We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
(12) Obligation:
Q DP problem:
The TRS P consists of the following rules:
D(g(x, y), z) → D(x, z)
D(g(g(0, x), y), s(z)) → D(g(g(0, x), y), z)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(13) 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:
- D(g(x, y), z) → D(x, z)
The graph contains the following edges 1 > 1, 2 >= 2
- D(g(g(0, x), y), s(z)) → D(g(g(0, x), y), z)
The graph contains the following edges 1 >= 1, 2 > 2
(14) TRUE
(15) Obligation:
Q DP problem:
The TRS P consists of the following rules:
H(e(x), y) → H(d(x, y), s(y))
The TRS R consists of the following rules:
h(e(x), y) → h(d(x, y), s(y))
d(g(g(0, x), y), s(z)) → g(e(x), d(g(g(0, x), y), z))
d(g(g(0, x), y), 0) → e(y)
d(g(0, x), y) → e(x)
d(g(x, y), z) → g(d(x, z), e(y))
g(e(x), e(y)) → e(g(x, y))
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(16) Instantiation (EQUIVALENT transformation)
By instantiating [LPAR04] the rule
H(
e(
x),
y) →
H(
d(
x,
y),
s(
y)) we obtained the following new rules [LPAR04]:
H(e(x0), s(y_3)) → H(d(x0, s(y_3)), s(s(y_3)))
(17) Obligation:
Q DP problem:
The TRS P consists of the following rules:
H(e(x0), s(y_3)) → H(d(x0, s(y_3)), s(s(y_3)))
The TRS R consists of the following rules:
h(e(x), y) → h(d(x, y), s(y))
d(g(g(0, x), y), s(z)) → g(e(x), d(g(g(0, x), y), z))
d(g(g(0, x), y), 0) → e(y)
d(g(0, x), y) → e(x)
d(g(x, y), z) → g(d(x, z), e(y))
g(e(x), e(y)) → e(g(x, y))
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(18) Instantiation (EQUIVALENT transformation)
By instantiating [LPAR04] the rule
H(
e(
x0),
s(
y_3)) →
H(
d(
x0,
s(
y_3)),
s(
s(
y_3))) we obtained the following new rules [LPAR04]:
H(e(x0), s(s(y_3))) → H(d(x0, s(s(y_3))), s(s(s(y_3))))
(19) Obligation:
Q DP problem:
The TRS P consists of the following rules:
H(e(x0), s(s(y_3))) → H(d(x0, s(s(y_3))), s(s(s(y_3))))
The TRS R consists of the following rules:
h(e(x), y) → h(d(x, y), s(y))
d(g(g(0, x), y), s(z)) → g(e(x), d(g(g(0, x), y), z))
d(g(g(0, x), y), 0) → e(y)
d(g(0, x), y) → e(x)
d(g(x, y), z) → g(d(x, z), e(y))
g(e(x), e(y)) → e(g(x, y))
Q is empty.
We have to consider all minimal (P,Q,R)-chains.