2.06/2.18 YES 2.06/2.18 2.06/2.18 Problem 1: 2.06/2.18 2.06/2.18 (VAR IL L M N T) 2.06/2.18 (STRATEGY CONTEXTSENSITIVE 2.06/2.18 (and 1 2) 2.06/2.18 (isNat) 2.06/2.18 (isNatIList) 2.06/2.18 (isNatList) 2.06/2.18 (length 1) 2.06/2.18 (take 1 2) 2.06/2.18 (uLength 1) 2.06/2.18 (uTake1 1) 2.06/2.18 (uTake2 1) 2.06/2.18 (zeros) 2.06/2.18 (0) 2.06/2.18 (cons 1) 2.06/2.18 (nil) 2.06/2.18 (s 1) 2.06/2.18 (tt) 2.06/2.18 ) 2.06/2.18 (RULES 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 ) 2.06/2.18 2.06/2.18 Problem 1: 2.06/2.18 2.06/2.18 Dependency Pairs Processor: 2.06/2.18 -> Pairs: 2.06/2.18 ISNAT(length(L)) -> ISNATLIST(L) 2.06/2.18 ISNAT(s(N)) -> ISNAT(N) 2.06/2.18 ISNATILIST(cons(N,IL)) -> AND(isNat(N),isNatIList(IL)) 2.06/2.18 ISNATILIST(cons(N,IL)) -> ISNAT(N) 2.06/2.18 ISNATILIST(cons(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATILIST(IL) -> ISNATLIST(IL) 2.06/2.18 ISNATLIST(take(N,IL)) -> AND(isNat(N),isNatIList(IL)) 2.06/2.18 ISNATLIST(take(N,IL)) -> ISNAT(N) 2.06/2.18 ISNATLIST(take(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATLIST(cons(N,L)) -> AND(isNat(N),isNatList(L)) 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNAT(N) 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNATLIST(L) 2.06/2.18 LENGTH(cons(N,L)) -> AND(isNat(N),isNatList(L)) 2.06/2.18 LENGTH(cons(N,L)) -> ISNAT(N) 2.06/2.18 LENGTH(cons(N,L)) -> ISNATLIST(L) 2.06/2.18 LENGTH(cons(N,L)) -> ULENGTH(and(isNat(N),isNatList(L)),L) 2.06/2.18 TAKE(0,IL) -> ISNATILIST(IL) 2.06/2.18 TAKE(0,IL) -> UTAKE1(isNatIList(IL)) 2.06/2.18 TAKE(s(M),cons(N,IL)) -> AND(isNat(M),and(isNat(N),isNatIList(IL))) 2.06/2.18 TAKE(s(M),cons(N,IL)) -> AND(isNat(N),isNatIList(IL)) 2.06/2.18 TAKE(s(M),cons(N,IL)) -> ISNAT(M) 2.06/2.18 TAKE(s(M),cons(N,IL)) -> ISNAT(N) 2.06/2.18 TAKE(s(M),cons(N,IL)) -> ISNATILIST(IL) 2.06/2.18 TAKE(s(M),cons(N,IL)) -> UTAKE2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 ULENGTH(tt,L) -> LENGTH(L) 2.06/2.18 ULENGTH(tt,L) -> L 2.06/2.18 UTAKE2(tt,M,N,IL) -> N 2.06/2.18 -> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 -> Unhiding Rules: 2.06/2.18 take(M,IL) -> TAKE(M,IL) 2.06/2.18 take(M,x5) -> x5 2.06/2.18 take(x5,IL) -> x5 2.06/2.18 zeros -> ZEROS 2.06/2.18 2.06/2.18 Problem 1: 2.06/2.18 2.06/2.18 SCC Processor: 2.06/2.18 -> Pairs: 2.06/2.18 ISNAT(length(L)) -> ISNATLIST(L) 2.06/2.18 ISNAT(s(N)) -> ISNAT(N) 2.06/2.18 ISNATILIST(cons(N,IL)) -> AND(isNat(N),isNatIList(IL)) 2.06/2.18 ISNATILIST(cons(N,IL)) -> ISNAT(N) 2.06/2.18 ISNATILIST(cons(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATILIST(IL) -> ISNATLIST(IL) 2.06/2.18 ISNATLIST(take(N,IL)) -> AND(isNat(N),isNatIList(IL)) 2.06/2.18 ISNATLIST(take(N,IL)) -> ISNAT(N) 2.06/2.18 ISNATLIST(take(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATLIST(cons(N,L)) -> AND(isNat(N),isNatList(L)) 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNAT(N) 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNATLIST(L) 2.06/2.18 LENGTH(cons(N,L)) -> AND(isNat(N),isNatList(L)) 2.06/2.18 LENGTH(cons(N,L)) -> ISNAT(N) 2.06/2.18 LENGTH(cons(N,L)) -> ISNATLIST(L) 2.06/2.18 LENGTH(cons(N,L)) -> ULENGTH(and(isNat(N),isNatList(L)),L) 2.06/2.18 TAKE(0,IL) -> ISNATILIST(IL) 2.06/2.18 TAKE(0,IL) -> UTAKE1(isNatIList(IL)) 2.06/2.18 TAKE(s(M),cons(N,IL)) -> AND(isNat(M),and(isNat(N),isNatIList(IL))) 2.06/2.18 TAKE(s(M),cons(N,IL)) -> AND(isNat(N),isNatIList(IL)) 2.06/2.18 TAKE(s(M),cons(N,IL)) -> ISNAT(M) 2.06/2.18 TAKE(s(M),cons(N,IL)) -> ISNAT(N) 2.06/2.18 TAKE(s(M),cons(N,IL)) -> ISNATILIST(IL) 2.06/2.18 TAKE(s(M),cons(N,IL)) -> UTAKE2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 ULENGTH(tt,L) -> LENGTH(L) 2.06/2.18 ULENGTH(tt,L) -> L 2.06/2.18 UTAKE2(tt,M,N,IL) -> N 2.06/2.18 -> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 -> Unhiding rules: 2.06/2.18 take(M,IL) -> TAKE(M,IL) 2.06/2.18 take(M,x5) -> x5 2.06/2.18 take(x5,IL) -> x5 2.06/2.18 zeros -> ZEROS 2.06/2.18 ->Strongly Connected Components: 2.06/2.18 ->->Cycle: 2.06/2.18 ->->-> Pairs: 2.06/2.18 ISNAT(length(L)) -> ISNATLIST(L) 2.06/2.18 ISNAT(s(N)) -> ISNAT(N) 2.06/2.18 ISNATILIST(cons(N,IL)) -> ISNAT(N) 2.06/2.18 ISNATILIST(cons(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATILIST(IL) -> ISNATLIST(IL) 2.06/2.18 ISNATLIST(take(N,IL)) -> ISNAT(N) 2.06/2.18 ISNATLIST(take(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNAT(N) 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNATLIST(L) 2.06/2.18 ->->-> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 ->->-> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 ->->Cycle: 2.06/2.18 ->->-> Pairs: 2.06/2.18 TAKE(s(M),cons(N,IL)) -> UTAKE2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 UTAKE2(tt,M,N,IL) -> N 2.06/2.18 ->->-> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 ->->-> Unhiding rules: 2.06/2.18 take(M,IL) -> TAKE(M,IL) 2.06/2.18 take(M,x5) -> x5 2.06/2.18 take(x5,IL) -> x5 2.06/2.18 ->->Cycle: 2.06/2.18 ->->-> Pairs: 2.06/2.18 LENGTH(cons(N,L)) -> ULENGTH(and(isNat(N),isNatList(L)),L) 2.06/2.18 ULENGTH(tt,L) -> LENGTH(L) 2.06/2.18 ->->-> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 ->->-> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 2.06/2.18 2.06/2.18 The problem is decomposed in 3 subproblems. 2.06/2.18 2.06/2.18 Problem 1.1: 2.06/2.18 2.06/2.18 Reduction Pairs Processor: 2.06/2.18 -> Pairs: 2.06/2.18 ISNAT(length(L)) -> ISNATLIST(L) 2.06/2.18 ISNAT(s(N)) -> ISNAT(N) 2.06/2.18 ISNATILIST(cons(N,IL)) -> ISNAT(N) 2.06/2.18 ISNATILIST(cons(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATILIST(IL) -> ISNATLIST(IL) 2.06/2.18 ISNATLIST(take(N,IL)) -> ISNAT(N) 2.06/2.18 ISNATLIST(take(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNAT(N) 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNATLIST(L) 2.06/2.18 -> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 -> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 -> Usable rules: 2.06/2.18 Empty 2.06/2.18 ->Interpretation type: 2.06/2.18 Linear 2.06/2.18 ->Coefficients: 2.06/2.18 Natural Numbers 2.06/2.18 ->Dimension: 2.06/2.18 1 2.06/2.18 ->Bound: 2.06/2.18 2 2.06/2.18 ->Interpretation: 2.06/2.18 2.06/2.18 [length](X) = 2.X + 2 2.06/2.18 [take](X1,X2) = 2.X1 + 2.X2 + 2 2.06/2.18 [cons](X1,X2) = 2.X1 + 2.X2 + 2 2.06/2.18 [s](X) = 2.X 2.06/2.18 [ISNAT](X) = 2.X + 2 2.06/2.18 [ISNATILIST](X) = 2.X + 2 2.06/2.18 [ISNATLIST](X) = 2.X + 2 2.06/2.18 2.06/2.18 Problem 1.1: 2.06/2.18 2.06/2.18 SCC Processor: 2.06/2.18 -> Pairs: 2.06/2.18 ISNAT(s(N)) -> ISNAT(N) 2.06/2.18 ISNATILIST(cons(N,IL)) -> ISNAT(N) 2.06/2.18 ISNATILIST(cons(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATILIST(IL) -> ISNATLIST(IL) 2.06/2.18 ISNATLIST(take(N,IL)) -> ISNAT(N) 2.06/2.18 ISNATLIST(take(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNAT(N) 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNATLIST(L) 2.06/2.18 -> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 -> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 ->Strongly Connected Components: 2.06/2.18 ->->Cycle: 2.06/2.18 ->->-> Pairs: 2.06/2.18 ISNAT(s(N)) -> ISNAT(N) 2.06/2.18 ->->-> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 ->->-> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 ->->Cycle: 2.06/2.18 ->->-> Pairs: 2.06/2.18 ISNATILIST(cons(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATILIST(IL) -> ISNATLIST(IL) 2.06/2.18 ISNATLIST(take(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNATLIST(L) 2.06/2.18 ->->-> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 ->->-> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 2.06/2.18 2.06/2.18 The problem is decomposed in 2 subproblems. 2.06/2.18 2.06/2.18 Problem 1.1.1: 2.06/2.18 2.06/2.18 SubNColl Processor: 2.06/2.18 -> Pairs: 2.06/2.18 ISNAT(s(N)) -> ISNAT(N) 2.06/2.18 -> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 -> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 ->Projection: 2.06/2.18 pi(ISNAT) = 1 2.06/2.18 2.06/2.18 Problem 1.1.1: 2.06/2.18 2.06/2.18 Basic Processor: 2.06/2.18 -> Pairs: 2.06/2.18 Empty 2.06/2.18 -> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 -> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 -> Result: 2.06/2.18 Set P is empty 2.06/2.18 2.06/2.18 The problem is finite. 2.06/2.18 2.06/2.18 Problem 1.1.2: 2.06/2.18 2.06/2.18 Reduction Pairs Processor: 2.06/2.18 -> Pairs: 2.06/2.18 ISNATILIST(cons(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATILIST(IL) -> ISNATLIST(IL) 2.06/2.18 ISNATLIST(take(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNATLIST(L) 2.06/2.18 -> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 -> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 -> Usable rules: 2.06/2.18 Empty 2.06/2.18 ->Interpretation type: 2.06/2.18 Linear 2.06/2.18 ->Coefficients: 2.06/2.18 Natural Numbers 2.06/2.18 ->Dimension: 2.06/2.18 1 2.06/2.18 ->Bound: 2.06/2.18 2 2.06/2.18 ->Interpretation: 2.06/2.18 2.06/2.18 [take](X1,X2) = 2.X2 + 2 2.06/2.18 [cons](X1,X2) = 2.X2 + 2 2.06/2.18 [ISNATILIST](X) = 2.X + 2 2.06/2.18 [ISNATLIST](X) = 2.X + 1 2.06/2.18 2.06/2.18 Problem 1.1.2: 2.06/2.18 2.06/2.18 SCC Processor: 2.06/2.18 -> Pairs: 2.06/2.18 ISNATILIST(IL) -> ISNATLIST(IL) 2.06/2.18 ISNATLIST(take(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNATLIST(L) 2.06/2.18 -> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 -> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 ->Strongly Connected Components: 2.06/2.18 ->->Cycle: 2.06/2.18 ->->-> Pairs: 2.06/2.18 ISNATILIST(IL) -> ISNATLIST(IL) 2.06/2.18 ISNATLIST(take(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNATLIST(L) 2.06/2.18 ->->-> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 ->->-> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 2.06/2.18 Problem 1.1.2: 2.06/2.18 2.06/2.18 Reduction Pairs Processor: 2.06/2.18 -> Pairs: 2.06/2.18 ISNATILIST(IL) -> ISNATLIST(IL) 2.06/2.18 ISNATLIST(take(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNATLIST(L) 2.06/2.18 -> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 -> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 -> Usable rules: 2.06/2.18 Empty 2.06/2.18 ->Interpretation type: 2.06/2.18 Linear 2.06/2.18 ->Coefficients: 2.06/2.18 Natural Numbers 2.06/2.18 ->Dimension: 2.06/2.18 1 2.06/2.18 ->Bound: 2.06/2.18 2 2.06/2.18 ->Interpretation: 2.06/2.18 2.06/2.18 [take](X1,X2) = 2.X2 + 2 2.06/2.18 [cons](X1,X2) = 2.X2 2.06/2.18 [ISNATILIST](X) = 2.X + 2 2.06/2.18 [ISNATLIST](X) = 2.X + 1 2.06/2.18 2.06/2.18 Problem 1.1.2: 2.06/2.18 2.06/2.18 SCC Processor: 2.06/2.18 -> Pairs: 2.06/2.18 ISNATLIST(take(N,IL)) -> ISNATILIST(IL) 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNATLIST(L) 2.06/2.18 -> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 -> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 ->Strongly Connected Components: 2.06/2.18 ->->Cycle: 2.06/2.18 ->->-> Pairs: 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNATLIST(L) 2.06/2.18 ->->-> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 ->->-> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 2.06/2.18 Problem 1.1.2: 2.06/2.18 2.06/2.18 Reduction Pairs Processor: 2.06/2.18 -> Pairs: 2.06/2.18 ISNATLIST(cons(N,L)) -> ISNATLIST(L) 2.06/2.18 -> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 -> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 -> Usable rules: 2.06/2.18 Empty 2.06/2.18 ->Interpretation type: 2.06/2.18 Linear 2.06/2.18 ->Coefficients: 2.06/2.18 Natural Numbers 2.06/2.18 ->Dimension: 2.06/2.18 1 2.06/2.18 ->Bound: 2.06/2.18 2 2.06/2.18 ->Interpretation: 2.06/2.18 2.06/2.18 [cons](X1,X2) = 2.X2 + 2 2.06/2.18 [ISNATLIST](X) = 2.X 2.06/2.18 2.06/2.18 Problem 1.1.2: 2.06/2.18 2.06/2.18 Basic Processor: 2.06/2.18 -> Pairs: 2.06/2.18 Empty 2.06/2.18 -> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 -> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 -> Result: 2.06/2.18 Set P is empty 2.06/2.18 2.06/2.18 The problem is finite. 2.06/2.18 2.06/2.18 Problem 1.2: 2.06/2.18 2.06/2.18 SubNColl Processor: 2.06/2.18 -> Pairs: 2.06/2.18 TAKE(s(M),cons(N,IL)) -> UTAKE2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 UTAKE2(tt,M,N,IL) -> N 2.06/2.18 -> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 -> Unhiding rules: 2.06/2.18 take(M,IL) -> TAKE(M,IL) 2.06/2.18 take(M,x5) -> x5 2.06/2.18 take(x5,IL) -> x5 2.06/2.18 ->Projection: 2.06/2.18 pi(TAKE) = 2 2.06/2.18 pi(UTAKE2) = 3 2.06/2.18 2.06/2.18 Problem 1.2: 2.06/2.18 2.06/2.18 Basic Processor: 2.06/2.18 -> Pairs: 2.06/2.18 UTAKE2(tt,M,N,IL) -> N 2.06/2.18 -> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 -> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 -> Result: 2.06/2.18 All pairs P are from Px1 2.06/2.18 2.06/2.18 The problem is finite. 2.06/2.18 2.06/2.18 Problem 1.3: 2.06/2.18 2.06/2.18 Reduction Pairs Processor: 2.06/2.18 -> Pairs: 2.06/2.18 LENGTH(cons(N,L)) -> ULENGTH(and(isNat(N),isNatList(L)),L) 2.06/2.18 ULENGTH(tt,L) -> LENGTH(L) 2.06/2.18 -> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 -> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 -> Usable rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 ->Interpretation type: 2.06/2.18 Linear 2.06/2.18 ->Coefficients: 2.06/2.18 Natural Numbers 2.06/2.18 ->Dimension: 2.06/2.18 2 2.06/2.18 ->Bound: 2.06/2.18 1 2.06/2.18 ->Interpretation: 2.06/2.18 2.06/2.18 [and](X1,X2) = [1 0;0 1].X2 2.06/2.18 [isNat](X) = [0 1;0 1].X 2.06/2.18 [isNatIList](X) = [0 0;0 1].X + [1;1] 2.06/2.18 [isNatList](X) = [0 0;0 1].X + [1;0] 2.06/2.18 [length](X) = [1 1;1 1].X + [1;1] 2.06/2.18 [take](X1,X2) = [0 1;0 0].X1 + [1 0;0 1].X2 + [1;1] 2.06/2.18 [uLength](X1,X2) = [1 1;1 1].X1 + [1 1;1 1].X2 2.06/2.18 [uTake1](X) = [0 0;0 1].X + [1;0] 2.06/2.18 [uTake2](X1,X2,X3,X4) = [1 0;1 0].X1 + [0 1;0 0].X2 + [0 0;1 0].X3 + [1 1;0 1].X4 + [1;0] 2.06/2.18 [zeros] = 0 2.06/2.18 [0] = [0;1] 2.06/2.18 [cons](X1,X2) = [0 0;1 0].X1 + [1 1;0 1].X2 2.06/2.18 [nil] = [0;1] 2.06/2.18 [s](X) = [0 1;0 1].X + [1;1] 2.06/2.18 [tt] = [1;1] 2.06/2.18 [LENGTH](X) = [1 1;1 1].X + [1;1] 2.06/2.18 [ULENGTH](X1,X2) = [0 1;0 1].X1 + [1 1;1 1].X2 + [0;1] 2.06/2.18 2.06/2.18 Problem 1.3: 2.06/2.18 2.06/2.18 SCC Processor: 2.06/2.18 -> Pairs: 2.06/2.18 ULENGTH(tt,L) -> LENGTH(L) 2.06/2.18 -> Rules: 2.06/2.18 and(tt,T) -> T 2.06/2.18 isNat(length(L)) -> isNatList(L) 2.06/2.18 isNat(0) -> tt 2.06/2.18 isNat(s(N)) -> isNat(N) 2.06/2.18 isNatIList(zeros) -> tt 2.06/2.18 isNatIList(cons(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatIList(IL) -> isNatList(IL) 2.06/2.18 isNatList(take(N,IL)) -> and(isNat(N),isNatIList(IL)) 2.06/2.18 isNatList(cons(N,L)) -> and(isNat(N),isNatList(L)) 2.06/2.18 isNatList(nil) -> tt 2.06/2.18 length(cons(N,L)) -> uLength(and(isNat(N),isNatList(L)),L) 2.06/2.18 take(0,IL) -> uTake1(isNatIList(IL)) 2.06/2.18 take(s(M),cons(N,IL)) -> uTake2(and(isNat(M),and(isNat(N),isNatIList(IL))),M,N,IL) 2.06/2.18 uLength(tt,L) -> s(length(L)) 2.06/2.18 uTake1(tt) -> nil 2.06/2.18 uTake2(tt,M,N,IL) -> cons(N,take(M,IL)) 2.06/2.18 zeros -> cons(0,zeros) 2.06/2.18 -> Unhiding rules: 2.06/2.18 Empty 2.06/2.18 ->Strongly Connected Components: 2.06/2.18 There is no strongly connected component 2.06/2.18 2.06/2.18 The problem is finite. 2.06/2.19 EOF