The rewrite relation of the following TRS is considered.
|
min(0,y) |
→ |
0 |
(1) |
|
min(s(x),0) |
→ |
0 |
(2) |
|
min(s(x),s(y)) |
→ |
min(x,y) |
(3) |
|
len(nil) |
→ |
0 |
(4) |
|
len(cons(x,xs)) |
→ |
s(len(xs)) |
(5) |
|
sum(x,0) |
→ |
x |
(6) |
|
sum(x,s(y)) |
→ |
s(sum(x,y)) |
(7) |
|
le(0,x) |
→ |
true |
(8) |
|
le(s(x),0) |
→ |
false |
(9) |
|
le(s(x),s(y)) |
→ |
le(x,y) |
(10) |
|
take(0,cons(y,ys)) |
→ |
y |
(11) |
|
take(s(x),cons(y,ys)) |
→ |
take(x,ys) |
(12) |
|
addList(x,y) |
→ |
if(le(0,min(len(x),len(y))),0,x,y,nil) |
(13) |
|
if(false,c,x,y,z) |
→ |
z |
(14) |
|
if(true,c,xs,ys,z) |
→ |
if(le(s(c),min(len(xs),len(ys))),s(c),xs,ys,cons(sum(take(c,xs),take(c,ys)),z)) |
(15) |
Hence, it suffices to show innermost termination in the following.
|
min#(s(x),s(y)) |
→ |
min#(x,y) |
(16) |
|
len#(cons(x,xs)) |
→ |
len#(xs) |
(17) |
|
sum#(x,s(y)) |
→ |
sum#(x,y) |
(18) |
|
le#(s(x),s(y)) |
→ |
le#(x,y) |
(19) |
|
take#(s(x),cons(y,ys)) |
→ |
take#(x,ys) |
(20) |
|
addList#(x,y) |
→ |
if#(le(0,min(len(x),len(y))),0,x,y,nil) |
(21) |
|
addList#(x,y) |
→ |
le#(0,min(len(x),len(y))) |
(22) |
|
addList#(x,y) |
→ |
min#(len(x),len(y)) |
(23) |
|
addList#(x,y) |
→ |
len#(x) |
(24) |
|
addList#(x,y) |
→ |
len#(y) |
(25) |
|
if#(true,c,xs,ys,z) |
→ |
if#(le(s(c),min(len(xs),len(ys))),s(c),xs,ys,cons(sum(take(c,xs),take(c,ys)),z)) |
(26) |
|
if#(true,c,xs,ys,z) |
→ |
le#(s(c),min(len(xs),len(ys))) |
(27) |
|
if#(true,c,xs,ys,z) |
→ |
min#(len(xs),len(ys)) |
(28) |
|
if#(true,c,xs,ys,z) |
→ |
len#(xs) |
(29) |
|
if#(true,c,xs,ys,z) |
→ |
len#(ys) |
(30) |
|
if#(true,c,xs,ys,z) |
→ |
sum#(take(c,xs),take(c,ys)) |
(31) |
|
if#(true,c,xs,ys,z) |
→ |
take#(c,xs) |
(32) |
|
if#(true,c,xs,ys,z) |
→ |
take#(c,ys) |
(33) |
The dependency pairs are split into 6
components.
-
The
1st
component contains the
pair
|
if#(true,c,xs,ys,z) |
→ |
if#(le(s(c),min(len(xs),len(ys))),s(c),xs,ys,cons(sum(take(c,xs),take(c,ys)),z)) |
(26) |
1.1.1.1 Usable Rules Processor
We restrict the rewrite rules to the following usable rules of the DP problem.
|
len(nil) |
→ |
0 |
(4) |
|
len(cons(x,xs)) |
→ |
s(len(xs)) |
(5) |
|
min(0,y) |
→ |
0 |
(1) |
|
min(s(x),0) |
→ |
0 |
(2) |
|
min(s(x),s(y)) |
→ |
min(x,y) |
(3) |
|
le(s(x),0) |
→ |
false |
(9) |
|
le(s(x),s(y)) |
→ |
le(x,y) |
(10) |
|
take(0,cons(y,ys)) |
→ |
y |
(11) |
|
take(s(x),cons(y,ys)) |
→ |
take(x,ys) |
(12) |
|
sum(x,0) |
→ |
x |
(6) |
|
sum(x,s(y)) |
→ |
s(sum(x,y)) |
(7) |
|
le(0,x) |
→ |
true |
(8) |
1.1.1.1.1 Innermost Lhss Removal Processor
We restrict the innermost strategy to the following left hand sides.
|
min(0,x0) |
|
min(s(x0),0) |
|
min(s(x0),s(x1)) |
|
len(nil) |
|
len(cons(x0,x1)) |
|
sum(x0,0) |
|
sum(x0,s(x1)) |
|
le(0,x0) |
|
le(s(x0),0) |
|
le(s(x0),s(x1)) |
|
take(0,cons(x0,x1)) |
|
take(s(x0),cons(x1,x2)) |
1.1.1.1.1.1 Reduction Pair Processor
We apply the generic reduction pair processor using the
linear polynomial interpretation over the naturals
| [c] |
= |
-1 |
| [if#(x1,...,x5)] |
= |
-1 · x1 + -1 · x2 + -1 · x3 + -1 · x4 + -1 · x5 + -1 |
| [true] |
= |
1 |
| [le(x1, x2)] |
= |
1 |
| [s(x1)] |
= |
1 · x1 + 1 |
| [min(x1, x2)] |
= |
1 |
| [len(x1)] |
= |
1 · x1 + 1 |
| [cons(x1, x2)] |
= |
1 · x2 + 1 |
| [sum(x1, x2)] |
= |
1 |
| [take(x1, x2)] |
= |
1 · x1 + 1 · x2 + 1 |
| [nil] |
= |
1 |
| [0] |
= |
1 |
| [false] |
= |
1 |
The pair(s)
|
if#(true,c,xs,ys,z) |
→ |
if#(le(s(c),min(len(xs),len(ys))),s(c),xs,ys,cons(sum(take(c,xs),take(c,ys)),z)) |
(26) |
are strictly oriented and the pair(s)
|
if#(true,c,xs,ys,z) |
→ |
if#(le(s(c),min(len(xs),len(ys))),s(c),xs,ys,cons(sum(take(c,xs),take(c,ys)),z)) |
(26) |
are bounded w.r.t. the constant c.
The following constraints are generated for the pairs.
- (if#(true,s(x0),x1,x2,x7)≥c⟹if#(true,s(x0),x1,x2,x7)≥c)
- (if#(true,s(x0),x1,x2,x7) > if#(le(s(s(x0)),min(len(x1),len(x2))),s(s(x0)),x1,x2,cons(sum(take(s(x0),x1),take(s(x0),x2)),x7))⟹if#(true,s(x0),x1,x2,x7) > if#(le(s(s(x0)),min(len(x1),len(x2))),s(s(x0)),x1,x2,cons(sum(take(s(x0),x1),take(s(x0),x2)),x7)))
The details are shown below:
-
For the chain
we build the initial constraint
(if#(le(s(x0),min(len(x1),len(x2))),s(x0),x1,x2,cons(sum(take(x0,x1),take(x0,x2)),x3))→*if#(true,x4,x5,x6,x7)⟹if#(true,x4,x5,x6,x7)≥c)
which is simplified as follows.
-
Applying Rule "Same Constructor" results in
(le(s(x0),min(len(x1),len(x2)))→*true⟹s(x0)→*x4⟹x1→*x5⟹x2→*x6⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,x4,x5,x6,x7)≥c)
-
Applying Rule "Variable in Equation" allows to substitute
x4 by s(x0) which results in
(le(s(x0),min(len(x1),len(x2)))→*true⟹x1→*x5⟹x2→*x6⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,s(x0),x5,x6,x7)≥c)
-
Applying Rule "Variable in Equation" allows to substitute
x5 by x1 which results in
(le(s(x0),min(len(x1),len(x2)))→*true⟹x2→*x6⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,s(x0),x1,x6,x7)≥c)
-
Applying Rule "Variable in Equation" allows to substitute
x6 by x2 which results in
(le(s(x0),min(len(x1),len(x2)))→*true⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,s(x0),x1,x2,x7)≥c)
-
Applying Rule "Introduce fresh variable" results in
(cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹min(len(x1),len(x2))→*x9⟹le(s(x0),x9)→*true⟹if#(true,s(x0),x1,x2,x7)≥c)
-
Applying Rule "Introduce fresh variable" results in
(s(x0)→*x8⟹min(len(x1),len(x2))→*x9⟹le(x8,x9)→*true⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,s(x0),x1,x2,x7)≥c)
-
Applying Rule "Introduce fresh variable" results in
(s(x0)→*x8⟹le(x8,x9)→*true⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹len(x2)→*x11⟹min(len(x1),x11)→*x9⟹if#(true,s(x0),x1,x2,x7)≥c)
-
Applying Rule "Introduce fresh variable" results in
(s(x0)→*x8⟹len(x1)→*x10⟹len(x2)→*x11⟹min(x10,x11)→*x9⟹le(x8,x9)→*true⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,s(x0),x1,x2,x7)≥c)
-
Applying Rule "Delete Conditions" results in
(s(x0)→*x8⟹min(x10,x11)→*x9⟹le(x8,x9)→*true⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,s(x0),x1,x2,x7)≥c)
-
Applying Rule "Induction" on le(x8,x9)→*true results in the following 3 new constraints.
- (false→*true⟹if#(true,s(x0),x1,x2,x7)≥c)
- Applying Rule "Different Constructors" allows to drop this constraint.
- (le(x14,x13)→*true⟹s(x0)→*s(x14)⟹min(x10,x11)→*s(x13)⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹∀x15
.
∀x16
.
∀x17
.
∀x18
.
∀x19
.
∀x20
.
∀x21
.
(le(x14,x13)→*true⟹s(x15)→*x14⟹min(x16,x17)→*x13⟹cons(sum(take(x15,x18),take(x15,x19)),x20)→*x21⟹if#(true,s(x15),x18,x19,x21)≥c)⟹if#(true,s(x0),x1,x2,x7)≥c)
-
Applying Rule "Same Constructor" results in
(le(x14,x13)→*true⟹x0→*x14⟹min(x10,x11)→*s(x13)⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹∀x15
.
∀x16
.
∀x17
.
∀x18
.
∀x19
.
∀x20
.
∀x21
.
(le(x14,x13)→*true⟹s(x15)→*x14⟹min(x16,x17)→*x13⟹cons(sum(take(x15,x18),take(x15,x19)),x20)→*x21⟹if#(true,s(x15),x18,x19,x21)≥c)⟹if#(true,s(x0),x1,x2,x7)≥c)
-
Applying Rule "Induction" on min(x10,x11)→*s(x13) results in the following 3 new constraints.
- (0→*s(x13)⟹if#(true,s(x0),x1,x2,x7)≥c)
- Applying Rule "Different Constructors" allows to drop this constraint.
- (0→*s(x13)⟹if#(true,s(x0),x1,x2,x7)≥c)
- Applying Rule "Different Constructors" allows to drop this constraint.
- (min(x26,x25)→*s(x13)⟹le(x14,x13)→*true⟹x0→*x14⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹∀x15
.
∀x16
.
∀x17
.
∀x18
.
∀x19
.
∀x20
.
∀x21
.
(le(x14,x13)→*true⟹s(x15)→*x14⟹min(x16,x17)→*x13⟹cons(sum(take(x15,x18),take(x15,x19)),x20)→*x21⟹if#(true,s(x15),x18,x19,x21)≥c)⟹∀x27
.
∀x28
.
∀x29
.
∀x30
.
∀x31
.
∀x32
.
∀x33
.
∀x34
.
∀x35
.
∀x36
.
∀x37
.
∀x38
.
∀x39
.
∀x40
.
(min(x26,x25)→*s(x27)⟹le(x28,x27)→*true⟹x29→*x28⟹cons(sum(take(x29,x30),take(x29,x31)),x32)→*x33⟹∀x34
.
∀x35
.
∀x36
.
∀x37
.
∀x38
.
∀x39
.
∀x40
.
(le(x28,x27)→*true⟹s(x34)→*x28⟹min(x35,x36)→*x27⟹cons(sum(take(x34,x37),take(x34,x38)),x39)→*x40⟹if#(true,s(x34),x37,x38,x40)≥c)⟹if#(true,s(x29),x30,x31,x33)≥c)⟹if#(true,s(x0),x1,x2,x7)≥c)
- (true→*true⟹s(x0)→*0⟹min(x10,x11)→*x22⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,s(x0),x1,x2,x7)≥c)
-
Applying Rule "Same Constructor" results in
(s(x0)→*0⟹min(x10,x11)→*x22⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,s(x0),x1,x2,x7)≥c)
- Applying Rule "Different Constructors" allows to drop this constraint.
-
For the chain
we build the initial constraint
(if#(le(s(x0),min(len(x1),len(x2))),s(x0),x1,x2,cons(sum(take(x0,x1),take(x0,x2)),x3))→*if#(true,x4,x5,x6,x7)⟹if#(true,x4,x5,x6,x7) > if#(le(s(x4),min(len(x5),len(x6))),s(x4),x5,x6,cons(sum(take(x4,x5),take(x4,x6)),x7)))
which is simplified as follows.
-
Applying Rule "Same Constructor" results in
(le(s(x0),min(len(x1),len(x2)))→*true⟹s(x0)→*x4⟹x1→*x5⟹x2→*x6⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,x4,x5,x6,x7) > if#(le(s(x4),min(len(x5),len(x6))),s(x4),x5,x6,cons(sum(take(x4,x5),take(x4,x6)),x7)))
-
Applying Rule "Variable in Equation" allows to substitute
x4 by s(x0) which results in
(le(s(x0),min(len(x1),len(x2)))→*true⟹x1→*x5⟹x2→*x6⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,s(x0),x5,x6,x7) > if#(le(s(s(x0)),min(len(x5),len(x6))),s(s(x0)),x5,x6,cons(sum(take(s(x0),x5),take(s(x0),x6)),x7)))
-
Applying Rule "Variable in Equation" allows to substitute
x5 by x1 which results in
(le(s(x0),min(len(x1),len(x2)))→*true⟹x2→*x6⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,s(x0),x1,x6,x7) > if#(le(s(s(x0)),min(len(x1),len(x6))),s(s(x0)),x1,x6,cons(sum(take(s(x0),x1),take(s(x0),x6)),x7)))
-
Applying Rule "Variable in Equation" allows to substitute
x6 by x2 which results in
(le(s(x0),min(len(x1),len(x2)))→*true⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,s(x0),x1,x2,x7) > if#(le(s(s(x0)),min(len(x1),len(x2))),s(s(x0)),x1,x2,cons(sum(take(s(x0),x1),take(s(x0),x2)),x7)))
-
Applying Rule "Introduce fresh variable" results in
(cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹min(len(x1),len(x2))→*x9⟹le(s(x0),x9)→*true⟹if#(true,s(x0),x1,x2,x7) > if#(le(s(s(x0)),min(len(x1),len(x2))),s(s(x0)),x1,x2,cons(sum(take(s(x0),x1),take(s(x0),x2)),x7)))
-
Applying Rule "Introduce fresh variable" results in
(s(x0)→*x8⟹min(len(x1),len(x2))→*x9⟹le(x8,x9)→*true⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,s(x0),x1,x2,x7) > if#(le(s(s(x0)),min(len(x1),len(x2))),s(s(x0)),x1,x2,cons(sum(take(s(x0),x1),take(s(x0),x2)),x7)))
-
Applying Rule "Introduce fresh variable" results in
(s(x0)→*x8⟹le(x8,x9)→*true⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹len(x2)→*x11⟹min(len(x1),x11)→*x9⟹if#(true,s(x0),x1,x2,x7) > if#(le(s(s(x0)),min(len(x1),len(x2))),s(s(x0)),x1,x2,cons(sum(take(s(x0),x1),take(s(x0),x2)),x7)))
-
Applying Rule "Introduce fresh variable" results in
(s(x0)→*x8⟹len(x1)→*x10⟹len(x2)→*x11⟹min(x10,x11)→*x9⟹le(x8,x9)→*true⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,s(x0),x1,x2,x7) > if#(le(s(s(x0)),min(len(x1),len(x2))),s(s(x0)),x1,x2,cons(sum(take(s(x0),x1),take(s(x0),x2)),x7)))
-
Applying Rule "Delete Conditions" results in
(s(x0)→*x8⟹min(x10,x11)→*x9⟹le(x8,x9)→*true⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,s(x0),x1,x2,x7) > if#(le(s(s(x0)),min(len(x1),len(x2))),s(s(x0)),x1,x2,cons(sum(take(s(x0),x1),take(s(x0),x2)),x7)))
-
Applying Rule "Induction" on le(x8,x9)→*true results in the following 3 new constraints.
- (false→*true⟹if#(true,s(x0),x1,x2,x7) > if#(le(s(s(x0)),min(len(x1),len(x2))),s(s(x0)),x1,x2,cons(sum(take(s(x0),x1),take(s(x0),x2)),x7)))
- Applying Rule "Different Constructors" allows to drop this constraint.
- (le(x14,x13)→*true⟹s(x0)→*s(x14)⟹min(x10,x11)→*s(x13)⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹∀x15
.
∀x16
.
∀x17
.
∀x18
.
∀x19
.
∀x20
.
∀x21
.
(le(x14,x13)→*true⟹s(x15)→*x14⟹min(x16,x17)→*x13⟹cons(sum(take(x15,x18),take(x15,x19)),x20)→*x21⟹if#(true,s(x15),x18,x19,x21) > if#(le(s(s(x15)),min(len(x18),len(x19))),s(s(x15)),x18,x19,cons(sum(take(s(x15),x18),take(s(x15),x19)),x21)))⟹if#(true,s(x0),x1,x2,x7) > if#(le(s(s(x0)),min(len(x1),len(x2))),s(s(x0)),x1,x2,cons(sum(take(s(x0),x1),take(s(x0),x2)),x7)))
-
Applying Rule "Same Constructor" results in
(le(x14,x13)→*true⟹x0→*x14⟹min(x10,x11)→*s(x13)⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹∀x15
.
∀x16
.
∀x17
.
∀x18
.
∀x19
.
∀x20
.
∀x21
.
(le(x14,x13)→*true⟹s(x15)→*x14⟹min(x16,x17)→*x13⟹cons(sum(take(x15,x18),take(x15,x19)),x20)→*x21⟹if#(true,s(x15),x18,x19,x21) > if#(le(s(s(x15)),min(len(x18),len(x19))),s(s(x15)),x18,x19,cons(sum(take(s(x15),x18),take(s(x15),x19)),x21)))⟹if#(true,s(x0),x1,x2,x7) > if#(le(s(s(x0)),min(len(x1),len(x2))),s(s(x0)),x1,x2,cons(sum(take(s(x0),x1),take(s(x0),x2)),x7)))
-
Applying Rule "Induction" on min(x10,x11)→*s(x13) results in the following 3 new constraints.
- (0→*s(x13)⟹if#(true,s(x0),x1,x2,x7) > if#(le(s(s(x0)),min(len(x1),len(x2))),s(s(x0)),x1,x2,cons(sum(take(s(x0),x1),take(s(x0),x2)),x7)))
- Applying Rule "Different Constructors" allows to drop this constraint.
- (0→*s(x13)⟹if#(true,s(x0),x1,x2,x7) > if#(le(s(s(x0)),min(len(x1),len(x2))),s(s(x0)),x1,x2,cons(sum(take(s(x0),x1),take(s(x0),x2)),x7)))
- Applying Rule "Different Constructors" allows to drop this constraint.
- (min(x26,x25)→*s(x13)⟹le(x14,x13)→*true⟹x0→*x14⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹∀x15
.
∀x16
.
∀x17
.
∀x18
.
∀x19
.
∀x20
.
∀x21
.
(le(x14,x13)→*true⟹s(x15)→*x14⟹min(x16,x17)→*x13⟹cons(sum(take(x15,x18),take(x15,x19)),x20)→*x21⟹if#(true,s(x15),x18,x19,x21) > if#(le(s(s(x15)),min(len(x18),len(x19))),s(s(x15)),x18,x19,cons(sum(take(s(x15),x18),take(s(x15),x19)),x21)))⟹∀x27
.
∀x28
.
∀x29
.
∀x30
.
∀x31
.
∀x32
.
∀x33
.
∀x34
.
∀x35
.
∀x36
.
∀x37
.
∀x38
.
∀x39
.
∀x40
.
(min(x26,x25)→*s(x27)⟹le(x28,x27)→*true⟹x29→*x28⟹cons(sum(take(x29,x30),take(x29,x31)),x32)→*x33⟹∀x34
.
∀x35
.
∀x36
.
∀x37
.
∀x38
.
∀x39
.
∀x40
.
(le(x28,x27)→*true⟹s(x34)→*x28⟹min(x35,x36)→*x27⟹cons(sum(take(x34,x37),take(x34,x38)),x39)→*x40⟹if#(true,s(x34),x37,x38,x40) > if#(le(s(s(x34)),min(len(x37),len(x38))),s(s(x34)),x37,x38,cons(sum(take(s(x34),x37),take(s(x34),x38)),x40)))⟹if#(true,s(x29),x30,x31,x33) > if#(le(s(s(x29)),min(len(x30),len(x31))),s(s(x29)),x30,x31,cons(sum(take(s(x29),x30),take(s(x29),x31)),x33)))⟹if#(true,s(x0),x1,x2,x7) > if#(le(s(s(x0)),min(len(x1),len(x2))),s(s(x0)),x1,x2,cons(sum(take(s(x0),x1),take(s(x0),x2)),x7)))
- (true→*true⟹s(x0)→*0⟹min(x10,x11)→*x22⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,s(x0),x1,x2,x7) > if#(le(s(s(x0)),min(len(x1),len(x2))),s(s(x0)),x1,x2,cons(sum(take(s(x0),x1),take(s(x0),x2)),x7)))
-
Applying Rule "Same Constructor" results in
(s(x0)→*0⟹min(x10,x11)→*x22⟹cons(sum(take(x0,x1),take(x0,x2)),x3)→*x7⟹if#(true,s(x0),x1,x2,x7) > if#(le(s(s(x0)),min(len(x1),len(x2))),s(s(x0)),x1,x2,cons(sum(take(s(x0),x1),take(s(x0),x2)),x7)))
- Applying Rule "Different Constructors" allows to drop this constraint.
We remove those pairs which are strictly decreasing and bounded.
1.1.1.1.1.1.1 P is empty
There are no pairs anymore.
-
The
2nd
component contains the
pair
|
min#(s(x),s(y)) |
→ |
min#(x,y) |
(16) |
1.1.1.2 Usable Rules Processor
We restrict the rewrite rules to the following usable rules of the DP problem.
There are no rules.
1.1.1.2.1 Innermost Lhss Removal Processor
We restrict the innermost strategy to the following left hand sides.
There are no lhss.
1.1.1.2.1.1 Size-Change Termination
Using size-change termination in combination with
the subterm criterion
one obtains the following initial size-change graphs.
|
min#(s(x),s(y)) |
→ |
min#(x,y) |
(16) |
|
|
| 1 |
> |
1 |
| 2 |
> |
2 |
As there is no critical graph in the transitive closure, there are no infinite chains.
-
The
3rd
component contains the
pair
|
len#(cons(x,xs)) |
→ |
len#(xs) |
(17) |
1.1.1.3 Usable Rules Processor
We restrict the rewrite rules to the following usable rules of the DP problem.
There are no rules.
1.1.1.3.1 Innermost Lhss Removal Processor
We restrict the innermost strategy to the following left hand sides.
There are no lhss.
1.1.1.3.1.1 Size-Change Termination
Using size-change termination in combination with
the subterm criterion
one obtains the following initial size-change graphs.
|
len#(cons(x,xs)) |
→ |
len#(xs) |
(17) |
|
| 1 |
> |
1 |
As there is no critical graph in the transitive closure, there are no infinite chains.
-
The
4th
component contains the
pair
|
sum#(x,s(y)) |
→ |
sum#(x,y) |
(18) |
1.1.1.4 Usable Rules Processor
We restrict the rewrite rules to the following usable rules of the DP problem.
There are no rules.
1.1.1.4.1 Innermost Lhss Removal Processor
We restrict the innermost strategy to the following left hand sides.
There are no lhss.
1.1.1.4.1.1 Size-Change Termination
Using size-change termination in combination with
the subterm criterion
one obtains the following initial size-change graphs.
|
sum#(x,s(y)) |
→ |
sum#(x,y) |
(18) |
|
|
| 1 |
≥ |
1 |
| 2 |
> |
2 |
As there is no critical graph in the transitive closure, there are no infinite chains.
-
The
5th
component contains the
pair
|
le#(s(x),s(y)) |
→ |
le#(x,y) |
(19) |
1.1.1.5 Usable Rules Processor
We restrict the rewrite rules to the following usable rules of the DP problem.
There are no rules.
1.1.1.5.1 Innermost Lhss Removal Processor
We restrict the innermost strategy to the following left hand sides.
There are no lhss.
1.1.1.5.1.1 Size-Change Termination
Using size-change termination in combination with
the subterm criterion
one obtains the following initial size-change graphs.
|
le#(s(x),s(y)) |
→ |
le#(x,y) |
(19) |
|
|
| 1 |
> |
1 |
| 2 |
> |
2 |
As there is no critical graph in the transitive closure, there are no infinite chains.
-
The
6th
component contains the
pair
|
take#(s(x),cons(y,ys)) |
→ |
take#(x,ys) |
(20) |
1.1.1.6 Usable Rules Processor
We restrict the rewrite rules to the following usable rules of the DP problem.
There are no rules.
1.1.1.6.1 Innermost Lhss Removal Processor
We restrict the innermost strategy to the following left hand sides.
There are no lhss.
1.1.1.6.1.1 Size-Change Termination
Using size-change termination in combination with
the subterm criterion
one obtains the following initial size-change graphs.
|
take#(s(x),cons(y,ys)) |
→ |
take#(x,ys) |
(20) |
|
|
| 1 |
> |
1 |
| 2 |
> |
2 |
As there is no critical graph in the transitive closure, there are no infinite chains.