The rewrite relation of the following TRS is considered.
zeros |
→ |
cons(0,n__zeros) |
(1) |
U11(tt) |
→ |
tt |
(2) |
U21(tt) |
→ |
tt |
(3) |
U31(tt) |
→ |
tt |
(4) |
U41(tt,V2) |
→ |
U42(isNatIList(activate(V2))) |
(5) |
U42(tt) |
→ |
tt |
(6) |
U51(tt,V2) |
→ |
U52(isNatList(activate(V2))) |
(7) |
U52(tt) |
→ |
tt |
(8) |
U61(tt,L,N) |
→ |
U62(isNat(activate(N)),activate(L)) |
(9) |
U62(tt,L) |
→ |
s(length(activate(L))) |
(10) |
isNat(n__0) |
→ |
tt |
(11) |
isNat(n__length(V1)) |
→ |
U11(isNatList(activate(V1))) |
(12) |
isNat(n__s(V1)) |
→ |
U21(isNat(activate(V1))) |
(13) |
isNatIList(V) |
→ |
U31(isNatList(activate(V))) |
(14) |
isNatIList(n__zeros) |
→ |
tt |
(15) |
isNatIList(n__cons(V1,V2)) |
→ |
U41(isNat(activate(V1)),activate(V2)) |
(16) |
isNatList(n__nil) |
→ |
tt |
(17) |
isNatList(n__cons(V1,V2)) |
→ |
U51(isNat(activate(V1)),activate(V2)) |
(18) |
length(nil) |
→ |
0 |
(19) |
length(cons(N,L)) |
→ |
U61(isNatList(activate(L)),activate(L),N) |
(20) |
zeros |
→ |
n__zeros |
(21) |
0 |
→ |
n__0 |
(22) |
length(X) |
→ |
n__length(X) |
(23) |
s(X) |
→ |
n__s(X) |
(24) |
cons(X1,X2) |
→ |
n__cons(X1,X2) |
(25) |
nil |
→ |
n__nil |
(26) |
activate(n__zeros) |
→ |
zeros |
(27) |
activate(n__0) |
→ |
0 |
(28) |
activate(n__length(X)) |
→ |
length(X) |
(29) |
activate(n__s(X)) |
→ |
s(X) |
(30) |
activate(n__cons(X1,X2)) |
→ |
cons(X1,X2) |
(31) |
activate(n__nil) |
→ |
nil |
(32) |
activate(X) |
→ |
X |
(33) |
zeros# |
→ |
cons#(0,n__zeros) |
(34) |
zeros# |
→ |
0# |
(35) |
U41#(tt,V2) |
→ |
U42#(isNatIList(activate(V2))) |
(36) |
U41#(tt,V2) |
→ |
isNatIList#(activate(V2)) |
(37) |
U41#(tt,V2) |
→ |
activate#(V2) |
(38) |
U51#(tt,V2) |
→ |
U52#(isNatList(activate(V2))) |
(39) |
U51#(tt,V2) |
→ |
isNatList#(activate(V2)) |
(40) |
U51#(tt,V2) |
→ |
activate#(V2) |
(41) |
U61#(tt,L,N) |
→ |
U62#(isNat(activate(N)),activate(L)) |
(42) |
U61#(tt,L,N) |
→ |
isNat#(activate(N)) |
(43) |
U61#(tt,L,N) |
→ |
activate#(N) |
(44) |
U61#(tt,L,N) |
→ |
activate#(L) |
(45) |
U62#(tt,L) |
→ |
s#(length(activate(L))) |
(46) |
U62#(tt,L) |
→ |
length#(activate(L)) |
(47) |
U62#(tt,L) |
→ |
activate#(L) |
(48) |
isNat#(n__s(V1)) |
→ |
U21#(isNat(activate(V1))) |
(49) |
isNat#(n__s(V1)) |
→ |
isNat#(activate(V1)) |
(50) |
isNat#(n__s(V1)) |
→ |
activate#(V1) |
(51) |
isNatIList#(n__cons(V1,V2)) |
→ |
U41#(isNat(activate(V1)),activate(V2)) |
(52) |
isNatIList#(n__cons(V1,V2)) |
→ |
isNat#(activate(V1)) |
(53) |
isNatIList#(n__cons(V1,V2)) |
→ |
activate#(V1) |
(54) |
isNatIList#(n__cons(V1,V2)) |
→ |
activate#(V2) |
(55) |
isNatList#(n__cons(V1,V2)) |
→ |
U51#(isNat(activate(V1)),activate(V2)) |
(56) |
isNatList#(n__cons(V1,V2)) |
→ |
isNat#(activate(V1)) |
(57) |
isNatList#(n__cons(V1,V2)) |
→ |
activate#(V1) |
(58) |
isNatList#(n__cons(V1,V2)) |
→ |
activate#(V2) |
(59) |
length#(cons(N,L)) |
→ |
U61#(isNatList(activate(L)),activate(L),N) |
(60) |
length#(cons(N,L)) |
→ |
isNatList#(activate(L)) |
(61) |
length#(cons(N,L)) |
→ |
activate#(L) |
(62) |
activate#(n__zeros) |
→ |
zeros# |
(63) |
activate#(n__0) |
→ |
0# |
(64) |
activate#(n__length(X)) |
→ |
length#(X) |
(65) |
activate#(n__s(X)) |
→ |
s#(X) |
(66) |
activate#(n__cons(X1,X2)) |
→ |
cons#(X1,X2) |
(67) |
activate#(n__nil) |
→ |
nil# |
(68) |
It remains to prove infiniteness of the resulting DP problem.
zeros# |
→ |
cons#(0,n__zeros) |
(34) |
zeros# |
→ |
0# |
(35) |
U41#(tt,V2) |
→ |
U42#(isNatIList(activate(V2))) |
(36) |
U41#(tt,V2) |
→ |
isNatIList#(activate(V2)) |
(37) |
U41#(tt,V2) |
→ |
activate#(V2) |
(38) |
U51#(tt,V2) |
→ |
U52#(isNatList(activate(V2))) |
(39) |
U62#(tt,L) |
→ |
s#(length(activate(L))) |
(46) |
isNat#(n__s(V1)) |
→ |
U21#(isNat(activate(V1))) |
(49) |
isNatIList#(n__cons(V1,V2)) |
→ |
U41#(isNat(activate(V1)),activate(V2)) |
(52) |
isNatIList#(n__cons(V1,V2)) |
→ |
isNat#(activate(V1)) |
(53) |
isNatIList#(n__cons(V1,V2)) |
→ |
activate#(V1) |
(54) |
isNatIList#(n__cons(V1,V2)) |
→ |
activate#(V2) |
(55) |
activate#(n__zeros) |
→ |
zeros# |
(63) |
activate#(n__0) |
→ |
0# |
(64) |
activate#(n__s(X)) |
→ |
s#(X) |
(66) |
activate#(n__cons(X1,X2)) |
→ |
cons#(X1,X2) |
(67) |
activate#(n__nil) |
→ |
nil# |
(68) |
and the following rules have been deleted.
isNatList#(n__cons(n__zeros,y1)) |
→ |
U51#(isNat(zeros),activate(y1)) |
(76) |
isNatList#(n__cons(n__0,y1)) |
→ |
U51#(isNat(0),activate(y1)) |
(77) |
isNatList#(n__cons(n__length(x0),y1)) |
→ |
U51#(isNat(length(x0)),activate(y1)) |
(78) |
isNatList#(n__cons(n__s(x0),y1)) |
→ |
U51#(isNat(s(x0)),activate(y1)) |
(79) |
isNatList#(n__cons(n__cons(x0,x1),y1)) |
→ |
U51#(isNat(cons(x0,x1)),activate(y1)) |
(80) |
isNatList#(n__cons(n__nil,y1)) |
→ |
U51#(isNat(nil),activate(y1)) |
(81) |
isNatList#(n__cons(x0,y1)) |
→ |
U51#(isNat(x0),activate(y1)) |
(82) |