YES Input TRS: 1: a__zeros() -> cons(0(),zeros()) 2: a__U11(tt(),V1) -> a__U12(a__isNatList(V1)) 3: a__U12(tt()) -> tt() 4: a__U21(tt(),V1) -> a__U22(a__isNat(V1)) 5: a__U22(tt()) -> tt() 6: a__U31(tt(),V) -> a__U32(a__isNatList(V)) 7: a__U32(tt()) -> tt() 8: a__U41(tt(),V1,V2) -> a__U42(a__isNat(V1),V2) 9: a__U42(tt(),V2) -> a__U43(a__isNatIList(V2)) 10: a__U43(tt()) -> tt() 11: a__U51(tt(),V1,V2) -> a__U52(a__isNat(V1),V2) 12: a__U52(tt(),V2) -> a__U53(a__isNatList(V2)) 13: a__U53(tt()) -> tt() 14: a__U61(tt(),L) -> s(a__length(mark(L))) 15: a__and(tt(),X) -> mark(X) 16: a__isNat(0()) -> tt() 17: a__isNat(length(V1)) -> a__U11(a__isNatIListKind(V1),V1) 18: a__isNat(s(V1)) -> a__U21(a__isNatKind(V1),V1) 19: a__isNatIList(V) -> a__U31(a__isNatIListKind(V),V) 20: a__isNatIList(zeros()) -> tt() 21: a__isNatIList(cons(V1,V2)) -> a__U41(a__and(a__isNatKind(V1),isNatIListKind(V2)),V1,V2) 22: a__isNatIListKind(nil()) -> tt() 23: a__isNatIListKind(zeros()) -> tt() 24: a__isNatIListKind(cons(V1,V2)) -> a__and(a__isNatKind(V1),isNatIListKind(V2)) 25: a__isNatKind(0()) -> tt() 26: a__isNatKind(length(V1)) -> a__isNatIListKind(V1) 27: a__isNatKind(s(V1)) -> a__isNatKind(V1) 28: a__isNatList(nil()) -> tt() 29: a__isNatList(cons(V1,V2)) -> a__U51(a__and(a__isNatKind(V1),isNatIListKind(V2)),V1,V2) 30: a__length(nil()) -> 0() 31: a__length(cons(N,L)) -> a__U61(a__and(a__and(a__isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) 32: mark(zeros()) -> a__zeros() 33: mark(U11(X1,X2)) -> a__U11(mark(X1),X2) 34: mark(U12(X)) -> a__U12(mark(X)) 35: mark(isNatList(X)) -> a__isNatList(X) 36: mark(U21(X1,X2)) -> a__U21(mark(X1),X2) 37: mark(U22(X)) -> a__U22(mark(X)) 38: mark(isNat(X)) -> a__isNat(X) 39: mark(U31(X1,X2)) -> a__U31(mark(X1),X2) 40: mark(U32(X)) -> a__U32(mark(X)) 41: mark(U41(X1,X2,X3)) -> a__U41(mark(X1),X2,X3) 42: mark(U42(X1,X2)) -> a__U42(mark(X1),X2) 43: mark(U43(X)) -> a__U43(mark(X)) 44: mark(isNatIList(X)) -> a__isNatIList(X) 45: mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3) 46: mark(U52(X1,X2)) -> a__U52(mark(X1),X2) 47: mark(U53(X)) -> a__U53(mark(X)) 48: mark(U61(X1,X2)) -> a__U61(mark(X1),X2) 49: mark(length(X)) -> a__length(mark(X)) 50: mark(and(X1,X2)) -> a__and(mark(X1),X2) 51: mark(isNatIListKind(X)) -> a__isNatIListKind(X) 52: mark(isNatKind(X)) -> a__isNatKind(X) 53: mark(cons(X1,X2)) -> cons(mark(X1),X2) 54: mark(0()) -> 0() 55: mark(tt()) -> tt() 56: mark(s(X)) -> s(mark(X)) 57: mark(nil()) -> nil() 58: a__zeros() -> zeros() 59: a__U11(X1,X2) -> U11(X1,X2) 60: a__U12(X) -> U12(X) 61: a__isNatList(X) -> isNatList(X) 62: a__U21(X1,X2) -> U21(X1,X2) 63: a__U22(X) -> U22(X) 64: a__isNat(X) -> isNat(X) 65: a__U31(X1,X2) -> U31(X1,X2) 66: a__U32(X) -> U32(X) 67: a__U41(X1,X2,X3) -> U41(X1,X2,X3) 68: a__U42(X1,X2) -> U42(X1,X2) 69: a__U43(X) -> U43(X) 70: a__isNatIList(X) -> isNatIList(X) 71: a__U51(X1,X2,X3) -> U51(X1,X2,X3) 72: a__U52(X1,X2) -> U52(X1,X2) 73: a__U53(X) -> U53(X) 74: a__U61(X1,X2) -> U61(X1,X2) 75: a__length(X) -> length(X) 76: a__and(X1,X2) -> and(X1,X2) 77: a__isNatIListKind(X) -> isNatIListKind(X) 78: a__isNatKind(X) -> isNatKind(X) Number of strict rules: 78 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #a__U11(tt(),V1) -> #a__U12(a__isNatList(V1)) #2: #a__U11(tt(),V1) -> #a__isNatList(V1) #3: #mark(U43(X)) -> #a__U43(mark(X)) #4: #mark(U43(X)) -> #mark(X) #5: #a__isNatList(cons(V1,V2)) -> #a__U51(a__and(a__isNatKind(V1),isNatIListKind(V2)),V1,V2) #6: #a__isNatList(cons(V1,V2)) -> #a__and(a__isNatKind(V1),isNatIListKind(V2)) #7: #a__isNatList(cons(V1,V2)) -> #a__isNatKind(V1) #8: #mark(isNatList(X)) -> #a__isNatList(X) #9: #mark(U52(X1,X2)) -> #a__U52(mark(X1),X2) #10: #mark(U52(X1,X2)) -> #mark(X1) #11: #mark(U42(X1,X2)) -> #a__U42(mark(X1),X2) #12: #mark(U42(X1,X2)) -> #mark(X1) #13: #mark(U41(X1,X2,X3)) -> #a__U41(mark(X1),X2,X3) #14: #mark(U41(X1,X2,X3)) -> #mark(X1) #15: #mark(U22(X)) -> #a__U22(mark(X)) #16: #mark(U22(X)) -> #mark(X) #17: #mark(U53(X)) -> #a__U53(mark(X)) #18: #mark(U53(X)) -> #mark(X) #19: #mark(cons(X1,X2)) -> #mark(X1) #20: #mark(U61(X1,X2)) -> #a__U61(mark(X1),X2) #21: #mark(U61(X1,X2)) -> #mark(X1) #22: #mark(isNat(X)) -> #a__isNat(X) #23: #a__U31(tt(),V) -> #a__U32(a__isNatList(V)) #24: #a__U31(tt(),V) -> #a__isNatList(V) #25: #mark(U32(X)) -> #a__U32(mark(X)) #26: #mark(U32(X)) -> #mark(X) #27: #mark(isNatIListKind(X)) -> #a__isNatIListKind(X) #28: #a__U42(tt(),V2) -> #a__U43(a__isNatIList(V2)) #29: #a__U42(tt(),V2) -> #a__isNatIList(V2) #30: #a__U51(tt(),V1,V2) -> #a__U52(a__isNat(V1),V2) #31: #a__U51(tt(),V1,V2) -> #a__isNat(V1) #32: #a__isNatIListKind(cons(V1,V2)) -> #a__and(a__isNatKind(V1),isNatIListKind(V2)) #33: #a__isNatIListKind(cons(V1,V2)) -> #a__isNatKind(V1) #34: #mark(U51(X1,X2,X3)) -> #a__U51(mark(X1),X2,X3) #35: #mark(U51(X1,X2,X3)) -> #mark(X1) #36: #a__U52(tt(),V2) -> #a__U53(a__isNatList(V2)) #37: #a__U52(tt(),V2) -> #a__isNatList(V2) #38: #a__length(cons(N,L)) -> #a__U61(a__and(a__and(a__isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) #39: #a__length(cons(N,L)) -> #a__and(a__and(a__isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))) #40: #a__length(cons(N,L)) -> #a__and(a__isNatList(L),isNatIListKind(L)) #41: #a__length(cons(N,L)) -> #a__isNatList(L) #42: #mark(s(X)) -> #mark(X) #43: #a__U61(tt(),L) -> #a__length(mark(L)) #44: #a__U61(tt(),L) -> #mark(L) #45: #mark(isNatKind(X)) -> #a__isNatKind(X) #46: #mark(length(X)) -> #a__length(mark(X)) #47: #mark(length(X)) -> #mark(X) #48: #mark(U31(X1,X2)) -> #a__U31(mark(X1),X2) #49: #mark(U31(X1,X2)) -> #mark(X1) #50: #mark(U11(X1,X2)) -> #a__U11(mark(X1),X2) #51: #mark(U11(X1,X2)) -> #mark(X1) #52: #mark(isNatIList(X)) -> #a__isNatIList(X) #53: #mark(U12(X)) -> #a__U12(mark(X)) #54: #mark(U12(X)) -> #mark(X) #55: #a__isNatKind(s(V1)) -> #a__isNatKind(V1) #56: #a__isNat(length(V1)) -> #a__U11(a__isNatIListKind(V1),V1) #57: #a__isNat(length(V1)) -> #a__isNatIListKind(V1) #58: #mark(zeros()) -> #a__zeros() #59: #a__isNatIList(V) -> #a__U31(a__isNatIListKind(V),V) #60: #a__isNatIList(V) -> #a__isNatIListKind(V) #61: #a__isNatKind(length(V1)) -> #a__isNatIListKind(V1) #62: #mark(U21(X1,X2)) -> #a__U21(mark(X1),X2) #63: #mark(U21(X1,X2)) -> #mark(X1) #64: #a__isNatIList(cons(V1,V2)) -> #a__U41(a__and(a__isNatKind(V1),isNatIListKind(V2)),V1,V2) #65: #a__isNatIList(cons(V1,V2)) -> #a__and(a__isNatKind(V1),isNatIListKind(V2)) #66: #a__isNatIList(cons(V1,V2)) -> #a__isNatKind(V1) #67: #a__U41(tt(),V1,V2) -> #a__U42(a__isNat(V1),V2) #68: #a__U41(tt(),V1,V2) -> #a__isNat(V1) #69: #a__and(tt(),X) -> #mark(X) #70: #a__U21(tt(),V1) -> #a__U22(a__isNat(V1)) #71: #a__U21(tt(),V1) -> #a__isNat(V1) #72: #mark(and(X1,X2)) -> #a__and(mark(X1),X2) #73: #mark(and(X1,X2)) -> #mark(X1) #74: #a__isNat(s(V1)) -> #a__U21(a__isNatKind(V1),V1) #75: #a__isNat(s(V1)) -> #a__isNatKind(V1) Number of SCCs: 1, DPs: 64 SCC { #2 #4..14 #16 #18..22 #24 #26 #27 #29..35 #37..52 #54..57 #59..69 #71..75 } POLO(Sum)... succeeded. #a__isNatKind w: 29299 isNatKind w: 0 U21 w: x1 isNatList w: 0 U11 w: x1 s w: x1 #a__U31 w: 29300 a__isNatIList w: x1 + 43322 #a__isNatIListKind w: 29299 U42 w: x1 + x2 + 14024 #a__isNat w: 29299 and w: x1 + x2 isNatIList w: x1 + 43322 #a__U43 w: 0 U43 w: x1 + 1 #a__U51 w: 29299 a__U22 w: x1 #a__U11 w: 29299 zeros w: 54448 a__U31 w: x1 + x2 + 14023 a__U51 w: x1 #a__U53 w: 0 U12 w: x1 a__isNatList w: 29299 a__U43 w: x1 + 1 #a__U42 w: x2 + 43323 a__U41 w: x1 + x3 + 43322 #a__U12 w: 0 #a__U21 w: 29299 #a__isNatIList w: x1 + 43323 #a__U61 w: x2 + 43563 #mark w: x1 + 29299 0 w: 0 #a__and w: x1 + x2 #a__zeros w: 0 a__U21 w: x1 a__U32 w: x1 + 1 isNatIListKind w: 0 nil w: 26727 #a__U52 w: 29299 mark w: x1 + 29299 a__U11 w: x1 U32 w: x1 + 1 a__U53 w: x1 a__U42 w: x1 + x2 + 14024 a__U52 w: x1 #a__length w: x1 + 14264 a__U12 w: x1 a__isNatIListKind w: 29299 isNat w: 0 U52 w: x1 U61 w: x1 + x2 + 14265 #a__U22 w: 0 U31 w: x1 + x2 + 14023 #a__isNatList w: 29299 cons w: x1 + x2 + 29299 a__U61 w: x1 + x2 + 14265 #a__U41 w: x3 + 43324 tt w: 29299 a__isNat w: 29299 a__isNatKind w: 29299 U22 w: x1 U51 w: x1 a__and w: x1 + x2 U53 w: x1 length w: x1 + 14265 U41 w: x1 + x3 + 43322 #a__U32 w: 0 a__zeros w: 83747 a__length w: x1 + 14265 USABLE RULES: { 1..78 } Removed DPs: #4 #12..14 #19..21 #24 #26 #39..41 #44 #46..49 #52 #59 #60 #64..68 Number of SCCs: 2, DPs: 37 SCC { #38 #43 } POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... Mat2b... succeeded. #a__isNatKind w: [0;0] isNatKind w: [1,0;0,0] * x1 + [1;4] U21 w: [30949;12357] isNatList w: [1,1;1,0] * x1 + [0;5841] U11 w: [30956;7983] s w: [1,0;0,0] * x1 + [0;1] #a__U31 w: [0;0] a__isNatIList w: x1 + [90438;147014] #a__isNatIListKind w: [0;0] U42 w: [1,0;0,0] * x1 + [0,0;1,1] * x2 + [28539;24896] #a__isNat w: [0;0] and w: [0,1;0,1] * x1 + x2 isNatIList w: x1 + [59488;116064] #a__U43 w: [0;0] U43 w: [30949;3] #a__U51 w: [0;0] a__U22 w: [0,0;0,1] * x1 + [61899;0] #a__U11 w: [0;0] zeros w: [1;0] a__U31 w: [0,0;1,0] * x1 + [1,0;0,0] * x2 + [61899;57974] a__U51 w: [0,0;1,0] * x2 + [0,0;1,0] * x3 + [61899;9606] #a__U53 w: [0;0] U12 w: [30949;8282] a__isNatList w: [1,1;1,0] * x1 + [30950;9606] a__U43 w: [61899;30950] #a__U42 w: [0;0] a__U41 w: [0,1;0,0] * x1 + [1,0;0,0] * x2 + [0,0;1,1] * x3 + [59488;30950] #a__U12 w: [0;0] #a__U21 w: [0;0] #a__isNatIList w: [0;0] #a__U61 w: [1,0;0,0] * x1 + [1,1;0,0] * x2 + [2;0] #mark w: [0;0] 0 w: [30948;0] #a__and w: [0;0] #a__zeros w: [0;0] a__U21 w: [61899;30950] a__U32 w: [61899;30950] isNatIListKind w: [58090;0] nil w: [31265;51571] #a__U52 w: [0;0] mark w: x1 + [30950;30950] a__U11 w: [61899;30950] U32 w: [30949;13578] a__U53 w: [0,0;0,1] * x1 + [61899;0] a__U42 w: [1,0;0,0] * x1 + [0,0;1,1] * x2 + [28539;30950] a__U52 w: [0,1;0,0] * x1 + [0,0;1,0] * x2 + [30949;9606] #a__length w: [1,1;0,0] * x1 a__U12 w: [61899;30950] a__isNatIListKind w: [89040;30950] isNat w: [1,0;0,0] * x1 + [30949;21339] U52 w: [0,1;0,0] * x1 + [0,0;1,0] * x2 + [30949;9606] U61 w: [0,1;0,0] * x1 + [0,1;0,0] * x2 + [58089;1] #a__U22 w: [0;0] U31 w: [0,0;1,0] * x1 + [1,0;0,0] * x2 + [30949;57974] #a__isNatList w: [0;0] cons w: [1,0;0,0] * x1 + [1,0;1,1] * x2 + [0;30949] a__U61 w: [0,1;0,0] * x1 + [0,1;0,0] * x2 + [58089;1] #a__U41 w: [0;0] tt w: [61899;30950] a__isNat w: [1,0;0,0] * x1 + [61899;30950] a__isNatKind w: [1,0;0,0] * x1 + [30951;30950] U22 w: [0,0;0,1] * x1 + [30949;0] U51 w: [0,0;1,0] * x2 + [0,0;1,0] * x3 + [30949;5577] a__and w: [0,1;0,1] * x1 + x2 U53 w: [0,0;0,1] * x1 + [30949;0] length w: [0,1;0,0] * x1 + [58089;1] U41 w: [0,1;0,0] * x1 + [1,0;0,0] * x2 + [0,0;1,1] * x3 + [59488;8664] #a__U32 w: [0;0] a__zeros w: [30949;30950] a__length w: [0,1;0,0] * x1 + [58089;1] USABLE RULES: { 1..78 } Removed DPs: #38 #43 Number of SCCs: 1, DPs: 35 SCC { #2 #5..10 #16 #18 #22 #27 #30..35 #37 #42 #45 #50 #51 #54..57 #61..63 #69 #71..75 } POLO(Sum)... succeeded. #a__isNatKind w: 29298 isNatKind w: 6 U21 w: x1 + 7 isNatList w: 5088 U11 w: x1 + 7 s w: x1 + 2 #a__U31 w: 29300 a__isNatIList w: 3 #a__isNatIListKind w: 29298 U42 w: x1 + 11 #a__isNat w: 29299 and w: x1 + x2 + 2 isNatIList w: x1 + 4 #a__U43 w: 0 U43 w: x1 + 21 #a__U51 w: 29299 a__U22 w: 3 #a__U11 w: 29299 zeros w: 4 a__U31 w: x1 + x2 + 14022 a__U51 w: x2 + x3 + 8 #a__U53 w: 0 U12 w: x1 + 6 a__isNatList w: x1 + 3 a__U43 w: 20 #a__U42 w: 43323 a__U41 w: x1 + x2 + x3 + 3 #a__U12 w: 0 #a__U21 w: 29299 #a__isNatIList w: 43323 #a__U61 w: 43563 #mark w: x1 + 29293 0 w: 1546 #a__and w: x2 + 29293 #a__zeros w: 0 a__U21 w: x1 + x2 + 1 a__U32 w: x1 + 14029 isNatIListKind w: 5 nil w: 3 #a__U52 w: 29299 mark w: 2 a__U11 w: x2 + 4 U32 w: x1 + 14030 a__U53 w: x1 + 7 a__U42 w: x1 + 10 a__U52 w: 9 #a__length w: 43563 a__U12 w: x1 + 5 a__isNatIListKind w: x1 + 4 isNat w: x1 + 28318 U52 w: x1 + x2 + 10 U61 w: x2 + 14265 #a__U22 w: 0 U31 w: x1 + 14023 #a__isNatList w: 29299 cons w: 4 a__U61 w: 1546 #a__U41 w: 43324 tt w: 9 a__isNat w: 3 a__isNatKind w: 3 U22 w: x1 + 4 U51 w: x1 + 9 a__and w: 1 U53 w: x1 + 8 length w: x1 + 1546 U41 w: x1 + 43322 #a__U32 w: 0 a__zeros w: 3 a__length w: 1545 USABLE RULES: { } Removed DPs: #6..10 #16 #18 #22 #34 #35 #42 #45 #50 #51 #54 #57 #62 #63 #72 #73 #75 Number of SCCs: 2, DPs: 14 SCC { #27 #32 #33 #55 #61 #69 } POLO(Sum)... succeeded. #a__isNatKind w: x1 + 2108 isNatKind w: 4 U21 w: x1 + 7 isNatList w: 5088 U11 w: x1 + 7 s w: x1 + 2 #a__U31 w: 29300 a__isNatIList w: 3 #a__isNatIListKind w: x1 + 29296 U42 w: x1 + 11 #a__isNat w: 29299 and w: x1 + x2 + 2 isNatIList w: x1 + 4 #a__U43 w: 0 U43 w: x1 + 20 #a__U51 w: 29299 a__U22 w: 3 #a__U11 w: 29299 zeros w: 0 a__U31 w: x1 + x2 + 14022 a__U51 w: x3 + 8 #a__U53 w: 0 U12 w: x1 + 6 a__isNatList w: x1 + 3 a__U43 w: 19 #a__U42 w: 43323 a__U41 w: x1 + x2 + x3 + 4 #a__U12 w: 0 #a__U21 w: 29299 #a__isNatIList w: 43323 #a__U61 w: 43563 #mark w: x1 + 29292 0 w: 1546 #a__and w: x2 + 29293 #a__zeros w: 0 a__U21 w: x1 + x2 + 1 a__U32 w: x1 + 14029 isNatIListKind w: x1 + 5 nil w: 3 #a__U52 w: 29299 mark w: 2 a__U11 w: x2 + 4 U32 w: x1 + 14030 a__U53 w: x1 + 7 a__U42 w: x1 + 10 a__U52 w: 9 #a__length w: 43563 a__U12 w: x1 + 5 a__isNatIListKind w: x1 + 4 isNat w: x1 + 28318 U52 w: x1 + x2 + 10 U61 w: x2 + 14265 #a__U22 w: 0 U31 w: x1 + 14023 #a__isNatList w: 29299 cons w: x1 + x2 + 3 a__U61 w: 1546 #a__U41 w: 43324 tt w: 8 a__isNat w: 3 a__isNatKind w: 3 U22 w: x1 + 4 U51 w: x1 + 9 a__and w: 1 U53 w: x1 + 8 length w: x1 + 27189 U41 w: x1 + 43322 #a__U32 w: 0 a__zeros w: 3 a__length w: 1545 USABLE RULES: { } Removed DPs: #27 #32 #33 #55 #61 #69 Number of SCCs: 1, DPs: 8 SCC { #2 #5 #30 #31 #37 #56 #71 #74 } POLO(Sum)... succeeded. #a__isNatKind w: 2108 isNatKind w: 4 U21 w: x1 + 7 isNatList w: 5088 U11 w: x1 + 7 s w: x1 + 2 #a__U31 w: 29300 a__isNatIList w: 3 #a__isNatIListKind w: 29296 U42 w: x1 + 11 #a__isNat w: x1 + 29299 and w: x1 + x2 + 2 isNatIList w: x1 + 4 #a__U43 w: 0 U43 w: x1 + 20 #a__U51 w: x2 + x3 + 29301 a__U22 w: 3 #a__U11 w: x2 + 29300 zeros w: 0 a__U31 w: x1 + x2 + 14022 a__U51 w: x3 + 8 #a__U53 w: 0 U12 w: x1 + 3 a__isNatList w: x1 + 3 a__U43 w: 19 #a__U42 w: 43323 a__U41 w: x1 + x2 + x3 + 4 #a__U12 w: 0 #a__U21 w: x2 + 29300 #a__isNatIList w: 43323 #a__U61 w: 43563 #mark w: 29292 0 w: 31498 #a__and w: 29293 #a__zeros w: 0 a__U21 w: x1 + x2 + 1 a__U32 w: x1 + 14029 isNatIListKind w: x1 + 5 nil w: 3 #a__U52 w: x2 + 29300 mark w: 2 a__U11 w: x2 + 4 U32 w: x1 + 14030 a__U53 w: x1 + 7 a__U42 w: x1 + 10 a__U52 w: 9 #a__length w: 43563 a__U12 w: x1 + 2 a__isNatIListKind w: x1 + 4 isNat w: x1 + 28318 U52 w: x1 + x2 + 10 U61 w: x2 + 14265 #a__U22 w: 0 U31 w: x1 + 14023 #a__isNatList w: x1 + 29299 cons w: x1 + x2 + 3 a__U61 w: 9023 #a__U41 w: 43324 tt w: 8 a__isNat w: 3 a__isNatKind w: 3 U22 w: x1 + 4 U51 w: x1 + 9 a__and w: 1 U53 w: x1 + 8 length w: x1 + 34666 U41 w: x1 + 43322 #a__U32 w: 0 a__zeros w: 3 a__length w: 9022 USABLE RULES: { } Removed DPs: #2 #5 #30 #31 #37 #56 #71 #74 Number of SCCs: 0, DPs: 0