(0) Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
a(h, h, h, x) → s(x)
a(l, x, s(y), h) → a(l, x, y, s(h))
a(l, x, s(y), s(z)) → a(l, x, y, a(l, x, s(y), z))
a(l, s(x), h, z) → a(l, x, z, z)
a(s(l), h, h, z) → a(l, z, h, z)
+(x, h) → x
+(h, x) → x
+(s(x), s(y)) → s(s(+(x, y)))
+(+(x, y), z) → +(x, +(y, z))
s(h) → 1
app(nil, k) → k
app(l, nil) → l
app(cons(x, l), k) → cons(x, app(l, k))
sum(cons(x, nil)) → cons(x, nil)
sum(cons(x, cons(y, l))) → sum(cons(a(x, y, h, h), l))
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:
A(h, h, h, x) → S(x)
A(l, x, s(y), h) → A(l, x, y, s(h))
A(l, x, s(y), h) → S(h)
A(l, x, s(y), s(z)) → A(l, x, y, a(l, x, s(y), z))
A(l, x, s(y), s(z)) → A(l, x, s(y), z)
A(l, s(x), h, z) → A(l, x, z, z)
A(s(l), h, h, z) → A(l, z, h, z)
+1(s(x), s(y)) → S(s(+(x, y)))
+1(s(x), s(y)) → S(+(x, y))
+1(s(x), s(y)) → +1(x, y)
+1(+(x, y), z) → +1(x, +(y, z))
+1(+(x, y), z) → +1(y, z)
APP(cons(x, l), k) → APP(l, k)
SUM(cons(x, cons(y, l))) → SUM(cons(a(x, y, h, h), l))
SUM(cons(x, cons(y, l))) → A(x, y, h, h)
The TRS R consists of the following rules:
a(h, h, h, x) → s(x)
a(l, x, s(y), h) → a(l, x, y, s(h))
a(l, x, s(y), s(z)) → a(l, x, y, a(l, x, s(y), z))
a(l, s(x), h, z) → a(l, x, z, z)
a(s(l), h, h, z) → a(l, z, h, z)
+(x, h) → x
+(h, x) → x
+(s(x), s(y)) → s(s(+(x, y)))
+(+(x, y), z) → +(x, +(y, z))
s(h) → 1
app(nil, k) → k
app(l, nil) → l
app(cons(x, l), k) → cons(x, app(l, k))
sum(cons(x, nil)) → cons(x, nil)
sum(cons(x, cons(y, l))) → sum(cons(a(x, y, h, h), l))
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 4 SCCs with 5 less nodes.
(4) Complex Obligation (AND)
(5) Obligation:
Q DP problem:
The TRS P consists of the following rules:
APP(cons(x, l), k) → APP(l, k)
The TRS R consists of the following rules:
a(h, h, h, x) → s(x)
a(l, x, s(y), h) → a(l, x, y, s(h))
a(l, x, s(y), s(z)) → a(l, x, y, a(l, x, s(y), z))
a(l, s(x), h, z) → a(l, x, z, z)
a(s(l), h, h, z) → a(l, z, h, z)
+(x, h) → x
+(h, x) → x
+(s(x), s(y)) → s(s(+(x, y)))
+(+(x, y), z) → +(x, +(y, z))
s(h) → 1
app(nil, k) → k
app(l, nil) → l
app(cons(x, l), k) → cons(x, app(l, k))
sum(cons(x, nil)) → cons(x, nil)
sum(cons(x, cons(y, l))) → sum(cons(a(x, y, h, h), l))
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:
APP(cons(x, l), k) → APP(l, k)
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:
- APP(cons(x, l), k) → APP(l, k)
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:
+1(+(x, y), z) → +1(x, +(y, z))
+1(s(x), s(y)) → +1(x, y)
+1(+(x, y), z) → +1(y, z)
The TRS R consists of the following rules:
a(h, h, h, x) → s(x)
a(l, x, s(y), h) → a(l, x, y, s(h))
a(l, x, s(y), s(z)) → a(l, x, y, a(l, x, s(y), z))
a(l, s(x), h, z) → a(l, x, z, z)
a(s(l), h, h, z) → a(l, z, h, z)
+(x, h) → x
+(h, x) → x
+(s(x), s(y)) → s(s(+(x, y)))
+(+(x, y), z) → +(x, +(y, z))
s(h) → 1
app(nil, k) → k
app(l, nil) → l
app(cons(x, l), k) → cons(x, app(l, k))
sum(cons(x, nil)) → cons(x, nil)
sum(cons(x, cons(y, l))) → sum(cons(a(x, y, h, h), l))
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:
+1(+(x, y), z) → +1(x, +(y, z))
+1(s(x), s(y)) → +1(x, y)
+1(+(x, y), z) → +1(y, z)
The TRS R consists of the following rules:
+(x, h) → x
+(h, x) → x
+(s(x), s(y)) → s(s(+(x, y)))
+(+(x, y), z) → +(x, +(y, z))
s(h) → 1
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:
- +1(+(x, y), z) → +1(x, +(y, z))
The graph contains the following edges 1 > 1
- +1(s(x), s(y)) → +1(x, y)
The graph contains the following edges 1 > 1, 2 > 2
- +1(+(x, y), z) → +1(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:
A(l, x, s(y), s(z)) → A(l, x, y, a(l, x, s(y), z))
A(l, x, s(y), h) → A(l, x, y, s(h))
A(l, x, s(y), s(z)) → A(l, x, s(y), z)
A(l, s(x), h, z) → A(l, x, z, z)
A(s(l), h, h, z) → A(l, z, h, z)
The TRS R consists of the following rules:
a(h, h, h, x) → s(x)
a(l, x, s(y), h) → a(l, x, y, s(h))
a(l, x, s(y), s(z)) → a(l, x, y, a(l, x, s(y), z))
a(l, s(x), h, z) → a(l, x, z, z)
a(s(l), h, h, z) → a(l, z, h, z)
+(x, h) → x
+(h, x) → x
+(s(x), s(y)) → s(s(+(x, y)))
+(+(x, y), z) → +(x, +(y, z))
s(h) → 1
app(nil, k) → k
app(l, nil) → l
app(cons(x, l), k) → cons(x, app(l, k))
sum(cons(x, nil)) → cons(x, nil)
sum(cons(x, cons(y, l))) → sum(cons(a(x, y, h, h), l))
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(16) 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:
- A(s(l), h, h, z) → A(l, z, h, z)
The graph contains the following edges 1 > 1, 4 >= 2, 2 >= 3, 3 >= 3, 4 >= 4
- A(l, s(x), h, z) → A(l, x, z, z)
The graph contains the following edges 1 >= 1, 2 > 2, 4 >= 3, 4 >= 4
- A(l, x, s(y), s(z)) → A(l, x, y, a(l, x, s(y), z))
The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3
- A(l, x, s(y), h) → A(l, x, y, s(h))
The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3
- A(l, x, s(y), s(z)) → A(l, x, s(y), z)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 > 4
(17) TRUE
(18) Obligation:
Q DP problem:
The TRS P consists of the following rules:
SUM(cons(x, cons(y, l))) → SUM(cons(a(x, y, h, h), l))
The TRS R consists of the following rules:
a(h, h, h, x) → s(x)
a(l, x, s(y), h) → a(l, x, y, s(h))
a(l, x, s(y), s(z)) → a(l, x, y, a(l, x, s(y), z))
a(l, s(x), h, z) → a(l, x, z, z)
a(s(l), h, h, z) → a(l, z, h, z)
+(x, h) → x
+(h, x) → x
+(s(x), s(y)) → s(s(+(x, y)))
+(+(x, y), z) → +(x, +(y, z))
s(h) → 1
app(nil, k) → k
app(l, nil) → l
app(cons(x, l), k) → cons(x, app(l, k))
sum(cons(x, nil)) → cons(x, nil)
sum(cons(x, cons(y, l))) → sum(cons(a(x, y, h, h), l))
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(19) QDPOrderProof (EQUIVALENT transformation)
We use the reduction pair processor [LPAR04].
The following pairs can be oriented strictly and are deleted.
SUM(cons(x, cons(y, l))) → SUM(cons(a(x, y, h, h), l))
The remaining pairs can at least be oriented weakly.
Used ordering: Matrix interpretation [MATRO]:
POL(cons(x1, x2)) = | | + | | · | x1 | + | | · | x2 |
POL(a(x1, x2, x3, x4)) = | | + | | · | x1 | + | | · | x2 | + | | · | x3 | + | | · | x4 |
The following usable rules [FROCOS05] were oriented:
none
(20) Obligation:
Q DP problem:
P is empty.
The TRS R consists of the following rules:
a(h, h, h, x) → s(x)
a(l, x, s(y), h) → a(l, x, y, s(h))
a(l, x, s(y), s(z)) → a(l, x, y, a(l, x, s(y), z))
a(l, s(x), h, z) → a(l, x, z, z)
a(s(l), h, h, z) → a(l, z, h, z)
+(x, h) → x
+(h, x) → x
+(s(x), s(y)) → s(s(+(x, y)))
+(+(x, y), z) → +(x, +(y, z))
s(h) → 1
app(nil, k) → k
app(l, nil) → l
app(cons(x, l), k) → cons(x, app(l, k))
sum(cons(x, nil)) → cons(x, nil)
sum(cons(x, cons(y, l))) → sum(cons(a(x, y, h, h), l))
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(21) PisEmptyProof (EQUIVALENT transformation)
The TRS P is empty. Hence, there is no (P,Q,R) chain.
(22) TRUE