The rewrite relation of the following TRS is considered.
zeros |
→ |
cons(0,n__zeros) |
(1) |
U11(tt,L) |
→ |
s(length(activate(L))) |
(2) |
U21(tt) |
→ |
nil |
(3) |
U31(tt,IL,M,N) |
→ |
cons(activate(N),n__take(activate(M),activate(IL))) |
(4) |
and(tt,X) |
→ |
activate(X) |
(5) |
isNat(n__0) |
→ |
tt |
(6) |
isNat(n__length(V1)) |
→ |
isNatList(activate(V1)) |
(7) |
isNat(n__s(V1)) |
→ |
isNat(activate(V1)) |
(8) |
isNatIList(V) |
→ |
isNatList(activate(V)) |
(9) |
isNatIList(n__zeros) |
→ |
tt |
(10) |
isNatIList(n__cons(V1,V2)) |
→ |
and(isNat(activate(V1)),n__isNatIList(activate(V2))) |
(11) |
isNatList(n__nil) |
→ |
tt |
(12) |
isNatList(n__cons(V1,V2)) |
→ |
and(isNat(activate(V1)),n__isNatList(activate(V2))) |
(13) |
isNatList(n__take(V1,V2)) |
→ |
and(isNat(activate(V1)),n__isNatIList(activate(V2))) |
(14) |
length(nil) |
→ |
0 |
(15) |
length(cons(N,L)) |
→ |
U11(and(isNatList(activate(L)),n__isNat(N)),activate(L)) |
(16) |
take(0,IL) |
→ |
U21(isNatIList(IL)) |
(17) |
take(s(M),cons(N,IL)) |
→ |
U31(and(isNatIList(activate(IL)),n__and(isNat(M),n__isNat(N))),activate(IL),M,N) |
(18) |
zeros |
→ |
n__zeros |
(19) |
take(X1,X2) |
→ |
n__take(X1,X2) |
(20) |
0 |
→ |
n__0 |
(21) |
length(X) |
→ |
n__length(X) |
(22) |
s(X) |
→ |
n__s(X) |
(23) |
cons(X1,X2) |
→ |
n__cons(X1,X2) |
(24) |
isNatIList(X) |
→ |
n__isNatIList(X) |
(25) |
nil |
→ |
n__nil |
(26) |
isNatList(X) |
→ |
n__isNatList(X) |
(27) |
isNat(X) |
→ |
n__isNat(X) |
(28) |
and(X1,X2) |
→ |
n__and(X1,X2) |
(29) |
activate(n__zeros) |
→ |
zeros |
(30) |
activate(n__take(X1,X2)) |
→ |
take(X1,X2) |
(31) |
activate(n__0) |
→ |
0 |
(32) |
activate(n__length(X)) |
→ |
length(X) |
(33) |
activate(n__s(X)) |
→ |
s(X) |
(34) |
activate(n__cons(X1,X2)) |
→ |
cons(X1,X2) |
(35) |
activate(n__isNatIList(X)) |
→ |
isNatIList(X) |
(36) |
activate(n__nil) |
→ |
nil |
(37) |
activate(n__isNatList(X)) |
→ |
isNatList(X) |
(38) |
activate(n__isNat(X)) |
→ |
isNat(X) |
(39) |
activate(n__and(X1,X2)) |
→ |
and(X1,X2) |
(40) |
activate(X) |
→ |
X |
(41) |
zeros# |
→ |
cons#(0,n__zeros) |
(42) |
zeros# |
→ |
0# |
(43) |
U11#(tt,L) |
→ |
s#(length(activate(L))) |
(44) |
U11#(tt,L) |
→ |
length#(activate(L)) |
(45) |
U11#(tt,L) |
→ |
activate#(L) |
(46) |
U21#(tt) |
→ |
nil# |
(47) |
U31#(tt,IL,M,N) |
→ |
cons#(activate(N),n__take(activate(M),activate(IL))) |
(48) |
U31#(tt,IL,M,N) |
→ |
activate#(N) |
(49) |
U31#(tt,IL,M,N) |
→ |
activate#(M) |
(50) |
U31#(tt,IL,M,N) |
→ |
activate#(IL) |
(51) |
and#(tt,X) |
→ |
activate#(X) |
(52) |
isNat#(n__length(V1)) |
→ |
isNatList#(activate(V1)) |
(53) |
isNat#(n__length(V1)) |
→ |
activate#(V1) |
(54) |
isNat#(n__s(V1)) |
→ |
isNat#(activate(V1)) |
(55) |
isNat#(n__s(V1)) |
→ |
activate#(V1) |
(56) |
isNatIList#(V) |
→ |
isNatList#(activate(V)) |
(57) |
isNatIList#(V) |
→ |
activate#(V) |
(58) |
isNatIList#(n__cons(V1,V2)) |
→ |
and#(isNat(activate(V1)),n__isNatIList(activate(V2))) |
(59) |
isNatIList#(n__cons(V1,V2)) |
→ |
isNat#(activate(V1)) |
(60) |
isNatIList#(n__cons(V1,V2)) |
→ |
activate#(V1) |
(61) |
isNatIList#(n__cons(V1,V2)) |
→ |
activate#(V2) |
(62) |
isNatList#(n__cons(V1,V2)) |
→ |
and#(isNat(activate(V1)),n__isNatList(activate(V2))) |
(63) |
isNatList#(n__cons(V1,V2)) |
→ |
isNat#(activate(V1)) |
(64) |
isNatList#(n__cons(V1,V2)) |
→ |
activate#(V1) |
(65) |
isNatList#(n__cons(V1,V2)) |
→ |
activate#(V2) |
(66) |
isNatList#(n__take(V1,V2)) |
→ |
and#(isNat(activate(V1)),n__isNatIList(activate(V2))) |
(67) |
isNatList#(n__take(V1,V2)) |
→ |
isNat#(activate(V1)) |
(68) |
isNatList#(n__take(V1,V2)) |
→ |
activate#(V1) |
(69) |
isNatList#(n__take(V1,V2)) |
→ |
activate#(V2) |
(70) |
length#(nil) |
→ |
0# |
(71) |
length#(cons(N,L)) |
→ |
U11#(and(isNatList(activate(L)),n__isNat(N)),activate(L)) |
(72) |
length#(cons(N,L)) |
→ |
and#(isNatList(activate(L)),n__isNat(N)) |
(73) |
length#(cons(N,L)) |
→ |
isNatList#(activate(L)) |
(74) |
length#(cons(N,L)) |
→ |
activate#(L) |
(75) |
take#(0,IL) |
→ |
U21#(isNatIList(IL)) |
(76) |
take#(0,IL) |
→ |
isNatIList#(IL) |
(77) |
take#(s(M),cons(N,IL)) |
→ |
U31#(and(isNatIList(activate(IL)),n__and(isNat(M),n__isNat(N))),activate(IL),M,N) |
(78) |
take#(s(M),cons(N,IL)) |
→ |
and#(isNatIList(activate(IL)),n__and(isNat(M),n__isNat(N))) |
(79) |
take#(s(M),cons(N,IL)) |
→ |
isNatIList#(activate(IL)) |
(80) |
take#(s(M),cons(N,IL)) |
→ |
activate#(IL) |
(81) |
take#(s(M),cons(N,IL)) |
→ |
isNat#(M) |
(82) |
activate#(n__zeros) |
→ |
zeros# |
(83) |
activate#(n__take(X1,X2)) |
→ |
take#(X1,X2) |
(84) |
activate#(n__0) |
→ |
0# |
(85) |
activate#(n__length(X)) |
→ |
length#(X) |
(86) |
activate#(n__s(X)) |
→ |
s#(X) |
(87) |
activate#(n__cons(X1,X2)) |
→ |
cons#(X1,X2) |
(88) |
activate#(n__isNatIList(X)) |
→ |
isNatIList#(X) |
(89) |
activate#(n__nil) |
→ |
nil# |
(90) |
activate#(n__isNatList(X)) |
→ |
isNatList#(X) |
(91) |
activate#(n__isNat(X)) |
→ |
isNat#(X) |
(92) |
activate#(n__and(X1,X2)) |
→ |
and#(X1,X2) |
(93) |
It remains to prove infiniteness of the resulting DP problem.
length#(cons(N,L)) |
→ |
and#(isNatList(activate(L)),n__isNat(N)) |
(73) |
isNatList#(n__cons(V1,V2)) |
→ |
isNat#(activate(V1)) |
(64) |
isNat#(n__length(V1)) |
→ |
isNatList#(activate(V1)) |
(53) |
isNatList#(n__cons(V1,V2)) |
→ |
activate#(V1) |
(65) |
isNatIList#(V) |
→ |
activate#(V) |
(58) |
isNatList#(n__cons(V1,V2)) |
→ |
activate#(V2) |
(66) |
isNat#(n__length(V1)) |
→ |
activate#(V1) |
(54) |
isNatList#(n__take(V1,V2)) |
→ |
and#(isNat(activate(V1)),n__isNatIList(activate(V2))) |
(67) |
isNatList#(n__take(V1,V2)) |
→ |
isNat#(activate(V1)) |
(68) |
isNatList#(n__take(V1,V2)) |
→ |
activate#(V1) |
(69) |
isNatList#(n__take(V1,V2)) |
→ |
activate#(V2) |
(70) |
isNatIList#(n__cons(V1,V2)) |
→ |
isNat#(activate(V1)) |
(60) |
isNatIList#(n__cons(V1,V2)) |
→ |
activate#(V1) |
(61) |
isNatIList#(n__cons(V1,V2)) |
→ |
activate#(V2) |
(62) |
length#(cons(N,L)) |
→ |
activate#(L) |
(75) |
U11#(tt,L) |
→ |
activate#(L) |
(46) |
take#(s(M),cons(N,IL)) |
→ |
U31#(and(isNatIList(activate(IL)),n__and(isNat(M),n__isNat(N))),activate(IL),M,N) |
(78) |
take#(s(M),cons(N,IL)) |
→ |
and#(isNatIList(activate(IL)),n__and(isNat(M),n__isNat(N))) |
(79) |
take#(s(M),cons(N,IL)) |
→ |
activate#(IL) |
(81) |
take#(s(M),cons(N,IL)) |
→ |
isNat#(M) |
(82) |
and the following rules have been deleted.
isNatList#(n__cons(y0,y1)) |
→ |
and#(n__isNat(activate(y0)),n__isNatList(activate(y1))) |
(94) |
isNatList#(n__cons(n__zeros,y1)) |
→ |
and#(isNat(zeros),n__isNatList(activate(y1))) |
(95) |
isNatList#(n__cons(n__take(x0,x1),y1)) |
→ |
and#(isNat(take(x0,x1)),n__isNatList(activate(y1))) |
(96) |
isNatList#(n__cons(n__0,y1)) |
→ |
and#(isNat(0),n__isNatList(activate(y1))) |
(97) |
isNatList#(n__cons(n__length(x0),y1)) |
→ |
and#(isNat(length(x0)),n__isNatList(activate(y1))) |
(98) |
isNatList#(n__cons(n__s(x0),y1)) |
→ |
and#(isNat(s(x0)),n__isNatList(activate(y1))) |
(99) |
isNatList#(n__cons(n__cons(x0,x1),y1)) |
→ |
and#(isNat(cons(x0,x1)),n__isNatList(activate(y1))) |
(100) |
isNatList#(n__cons(n__isNatIList(x0),y1)) |
→ |
and#(isNat(isNatIList(x0)),n__isNatList(activate(y1))) |
(101) |
isNatList#(n__cons(n__nil,y1)) |
→ |
and#(isNat(nil),n__isNatList(activate(y1))) |
(102) |
isNatList#(n__cons(n__isNatList(x0),y1)) |
→ |
and#(isNat(isNatList(x0)),n__isNatList(activate(y1))) |
(103) |
isNatList#(n__cons(n__isNat(x0),y1)) |
→ |
and#(isNat(isNat(x0)),n__isNatList(activate(y1))) |
(104) |
isNatList#(n__cons(n__and(x0,x1),y1)) |
→ |
and#(isNat(and(x0,x1)),n__isNatList(activate(y1))) |
(105) |
isNatList#(n__cons(x0,y1)) |
→ |
and#(isNat(x0),n__isNatList(activate(y1))) |
(106) |
isNatIList#(n__cons(y0,y1)) |
→ |
and#(n__isNat(activate(y0)),n__isNatIList(activate(y1))) |
(107) |
isNatIList#(n__cons(n__zeros,y1)) |
→ |
and#(isNat(zeros),n__isNatIList(activate(y1))) |
(108) |
isNatIList#(n__cons(n__take(x0,x1),y1)) |
→ |
and#(isNat(take(x0,x1)),n__isNatIList(activate(y1))) |
(109) |
isNatIList#(n__cons(n__0,y1)) |
→ |
and#(isNat(0),n__isNatIList(activate(y1))) |
(110) |
isNatIList#(n__cons(n__length(x0),y1)) |
→ |
and#(isNat(length(x0)),n__isNatIList(activate(y1))) |
(111) |
isNatIList#(n__cons(n__s(x0),y1)) |
→ |
and#(isNat(s(x0)),n__isNatIList(activate(y1))) |
(112) |
isNatIList#(n__cons(n__cons(x0,x1),y1)) |
→ |
and#(isNat(cons(x0,x1)),n__isNatIList(activate(y1))) |
(113) |
isNatIList#(n__cons(n__isNatIList(x0),y1)) |
→ |
and#(isNat(isNatIList(x0)),n__isNatIList(activate(y1))) |
(114) |
isNatIList#(n__cons(n__nil,y1)) |
→ |
and#(isNat(nil),n__isNatIList(activate(y1))) |
(115) |
isNatIList#(n__cons(n__isNatList(x0),y1)) |
→ |
and#(isNat(isNatList(x0)),n__isNatIList(activate(y1))) |
(116) |
isNatIList#(n__cons(n__isNat(x0),y1)) |
→ |
and#(isNat(isNat(x0)),n__isNatIList(activate(y1))) |
(117) |
isNatIList#(n__cons(n__and(x0,x1),y1)) |
→ |
and#(isNat(and(x0,x1)),n__isNatIList(activate(y1))) |
(118) |
isNatIList#(n__cons(x0,y1)) |
→ |
and#(isNat(x0),n__isNatIList(activate(y1))) |
(119) |
isNatIList#(n__cons(n__zeros,y1)) |
→ |
and#(isNat(zeros),n__isNatIList(activate(y1))) |
(108) |
activate#(n__isNatIList(X)) |
→ |
isNatIList#(X) |
(89) |
isNatIList#(n__cons(n__take(x0,x1),y1)) |
→ |
and#(isNat(take(x0,x1)),n__isNatIList(activate(y1))) |
(109) |
isNatIList#(n__cons(n__0,y1)) |
→ |
and#(isNat(0),n__isNatIList(activate(y1))) |
(110) |
isNatIList#(n__cons(n__length(x0),y1)) |
→ |
and#(isNat(length(x0)),n__isNatIList(activate(y1))) |
(111) |
isNatIList#(n__cons(n__s(x0),y1)) |
→ |
and#(isNat(s(x0)),n__isNatIList(activate(y1))) |
(112) |
isNatIList#(n__cons(n__cons(x0,x1),y1)) |
→ |
and#(isNat(cons(x0,x1)),n__isNatIList(activate(y1))) |
(113) |
isNatIList#(n__cons(n__isNatIList(x0),y1)) |
→ |
and#(isNat(isNatIList(x0)),n__isNatIList(activate(y1))) |
(114) |
isNatIList#(n__cons(n__nil,y1)) |
→ |
and#(isNat(nil),n__isNatIList(activate(y1))) |
(115) |
isNatIList#(n__cons(n__isNatList(x0),y1)) |
→ |
and#(isNat(isNatList(x0)),n__isNatIList(activate(y1))) |
(116) |
isNatIList#(n__cons(n__isNat(x0),y1)) |
→ |
and#(isNat(isNat(x0)),n__isNatIList(activate(y1))) |
(117) |
isNatIList#(n__cons(n__and(x0,x1),y1)) |
→ |
and#(isNat(and(x0,x1)),n__isNatIList(activate(y1))) |
(118) |
isNatIList#(n__cons(x0,y1)) |
→ |
and#(isNat(x0),n__isNatIList(activate(y1))) |
(119) |
activate#(n__isNatList(X)) |
→ |
isNatList#(X) |
(91) |
isNatList#(n__cons(n__zeros,y1)) |
→ |
and#(isNat(zeros),n__isNatList(activate(y1))) |
(95) |
isNatList#(n__cons(n__take(x0,x1),y1)) |
→ |
and#(isNat(take(x0,x1)),n__isNatList(activate(y1))) |
(96) |
isNatList#(n__cons(n__0,y1)) |
→ |
and#(isNat(0),n__isNatList(activate(y1))) |
(97) |
isNatList#(n__cons(n__length(x0),y1)) |
→ |
and#(isNat(length(x0)),n__isNatList(activate(y1))) |
(98) |
isNatList#(n__cons(n__s(x0),y1)) |
→ |
and#(isNat(s(x0)),n__isNatList(activate(y1))) |
(99) |
isNatList#(n__cons(n__cons(x0,x1),y1)) |
→ |
and#(isNat(cons(x0,x1)),n__isNatList(activate(y1))) |
(100) |
isNatList#(n__cons(n__isNatIList(x0),y1)) |
→ |
and#(isNat(isNatIList(x0)),n__isNatList(activate(y1))) |
(101) |
isNatList#(n__cons(n__nil,y1)) |
→ |
and#(isNat(nil),n__isNatList(activate(y1))) |
(102) |
isNatList#(n__cons(n__isNatList(x0),y1)) |
→ |
and#(isNat(isNatList(x0)),n__isNatList(activate(y1))) |
(103) |
isNatList#(n__cons(n__isNat(x0),y1)) |
→ |
and#(isNat(isNat(x0)),n__isNatList(activate(y1))) |
(104) |
isNatList#(n__cons(n__and(x0,x1),y1)) |
→ |
and#(isNat(and(x0,x1)),n__isNatList(activate(y1))) |
(105) |
isNatList#(n__cons(x0,y1)) |
→ |
and#(isNat(x0),n__isNatList(activate(y1))) |
(106) |
and#(tt,n__isNatIList(y_3)) |
→ |
activate#(n__isNatIList(y_3)) |
(120) |
and#(tt,n__isNatList(y_3)) |
→ |
activate#(n__isNatList(y_3)) |
(121) |
activate#(n__isNatList(X)) |
→ |
isNatList#(X) |
(91) |
isNatList#(n__cons(n__zeros,y1)) |
→ |
and#(isNat(zeros),n__isNatList(activate(y1))) |
(95) |
isNatList#(n__cons(n__take(x0,x1),y1)) |
→ |
and#(isNat(take(x0,x1)),n__isNatList(activate(y1))) |
(96) |
isNatList#(n__cons(n__0,y1)) |
→ |
and#(isNat(0),n__isNatList(activate(y1))) |
(97) |
isNatList#(n__cons(n__length(x0),y1)) |
→ |
and#(isNat(length(x0)),n__isNatList(activate(y1))) |
(98) |
isNatList#(n__cons(n__s(x0),y1)) |
→ |
and#(isNat(s(x0)),n__isNatList(activate(y1))) |
(99) |
isNatList#(n__cons(n__cons(x0,x1),y1)) |
→ |
and#(isNat(cons(x0,x1)),n__isNatList(activate(y1))) |
(100) |
isNatList#(n__cons(n__isNatIList(x0),y1)) |
→ |
and#(isNat(isNatIList(x0)),n__isNatList(activate(y1))) |
(101) |
isNatList#(n__cons(n__nil,y1)) |
→ |
and#(isNat(nil),n__isNatList(activate(y1))) |
(102) |
isNatList#(n__cons(n__isNatList(x0),y1)) |
→ |
and#(isNat(isNatList(x0)),n__isNatList(activate(y1))) |
(103) |
isNatList#(n__cons(n__isNat(x0),y1)) |
→ |
and#(isNat(isNat(x0)),n__isNatList(activate(y1))) |
(104) |
isNatList#(n__cons(n__and(x0,x1),y1)) |
→ |
and#(isNat(and(x0,x1)),n__isNatList(activate(y1))) |
(105) |
isNatList#(n__cons(x0,y1)) |
→ |
and#(isNat(x0),n__isNatList(activate(y1))) |
(106) |
and#(tt,n__isNatList(y_3)) |
→ |
activate#(n__isNatList(y_3)) |
(121) |
and the following rules have been deleted.