3.92/4.42 YES 3.92/4.42 3.92/4.42 Problem 1: 3.92/4.42 3.92/4.42 (VAR L N V V1 V2 X) 3.92/4.42 (STRATEGY CONTEXTSENSITIVE 3.92/4.42 (U11 1) 3.92/4.42 (and 1) 3.92/4.42 (isNat) 3.92/4.42 (isNatIList) 3.92/4.42 (isNatList) 3.92/4.42 (length 1) 3.92/4.42 (zeros) 3.92/4.42 (0) 3.92/4.42 (cons 1) 3.92/4.42 (nil) 3.92/4.42 (s 1) 3.92/4.42 (tt) 3.92/4.42 ) 3.92/4.42 (RULES 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 ) 3.92/4.42 3.92/4.42 Problem 1: 3.92/4.42 3.92/4.42 Dependency Pairs Processor: 3.92/4.42 -> Pairs: 3.92/4.42 U11#(tt,L) -> LENGTH(L) 3.92/4.42 U11#(tt,L) -> L 3.92/4.42 AND(tt,X) -> X 3.92/4.42 ISNAT(length(V1)) -> ISNATLIST(V1) 3.92/4.42 ISNAT(s(V1)) -> ISNAT(V1) 3.92/4.42 ISNATILIST(cons(V1,V2)) -> AND(isNat(V1),isNatIList(V2)) 3.92/4.42 ISNATILIST(cons(V1,V2)) -> ISNAT(V1) 3.92/4.42 ISNATILIST(V) -> ISNATLIST(V) 3.92/4.42 ISNATLIST(cons(V1,V2)) -> AND(isNat(V1),isNatList(V2)) 3.92/4.42 ISNATLIST(cons(V1,V2)) -> ISNAT(V1) 3.92/4.42 LENGTH(cons(N,L)) -> U11#(and(isNatList(L),isNat(N)),L) 3.92/4.42 LENGTH(cons(N,L)) -> AND(isNatList(L),isNat(N)) 3.92/4.42 LENGTH(cons(N,L)) -> ISNATLIST(L) 3.92/4.42 -> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 -> Unhiding Rules: 3.92/4.42 isNat(N) -> ISNAT(N) 3.92/4.42 isNatIList(V2) -> ISNATILIST(V2) 3.92/4.42 isNatList(V2) -> ISNATLIST(V2) 3.92/4.42 zeros -> ZEROS 3.92/4.42 3.92/4.42 Problem 1: 3.92/4.42 3.92/4.42 SCC Processor: 3.92/4.42 -> Pairs: 3.92/4.42 U11#(tt,L) -> LENGTH(L) 3.92/4.42 U11#(tt,L) -> L 3.92/4.42 AND(tt,X) -> X 3.92/4.42 ISNAT(length(V1)) -> ISNATLIST(V1) 3.92/4.42 ISNAT(s(V1)) -> ISNAT(V1) 3.92/4.42 ISNATILIST(cons(V1,V2)) -> AND(isNat(V1),isNatIList(V2)) 3.92/4.42 ISNATILIST(cons(V1,V2)) -> ISNAT(V1) 3.92/4.42 ISNATILIST(V) -> ISNATLIST(V) 3.92/4.42 ISNATLIST(cons(V1,V2)) -> AND(isNat(V1),isNatList(V2)) 3.92/4.42 ISNATLIST(cons(V1,V2)) -> ISNAT(V1) 3.92/4.42 LENGTH(cons(N,L)) -> U11#(and(isNatList(L),isNat(N)),L) 3.92/4.42 LENGTH(cons(N,L)) -> AND(isNatList(L),isNat(N)) 3.92/4.42 LENGTH(cons(N,L)) -> ISNATLIST(L) 3.92/4.42 -> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 -> Unhiding rules: 3.92/4.42 isNat(N) -> ISNAT(N) 3.92/4.42 isNatIList(V2) -> ISNATILIST(V2) 3.92/4.42 isNatList(V2) -> ISNATLIST(V2) 3.92/4.42 zeros -> ZEROS 3.92/4.42 ->Strongly Connected Components: 3.92/4.42 ->->Cycle: 3.92/4.42 ->->-> Pairs: 3.92/4.42 AND(tt,X) -> X 3.92/4.42 ISNAT(length(V1)) -> ISNATLIST(V1) 3.92/4.42 ISNAT(s(V1)) -> ISNAT(V1) 3.92/4.42 ISNATILIST(cons(V1,V2)) -> AND(isNat(V1),isNatIList(V2)) 3.92/4.42 ISNATILIST(cons(V1,V2)) -> ISNAT(V1) 3.92/4.42 ISNATILIST(V) -> ISNATLIST(V) 3.92/4.42 ISNATLIST(cons(V1,V2)) -> AND(isNat(V1),isNatList(V2)) 3.92/4.42 ISNATLIST(cons(V1,V2)) -> ISNAT(V1) 3.92/4.42 ->->-> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 ->->-> Unhiding rules: 3.92/4.42 isNat(N) -> ISNAT(N) 3.92/4.42 isNatIList(V2) -> ISNATILIST(V2) 3.92/4.42 isNatList(V2) -> ISNATLIST(V2) 3.92/4.42 ->->Cycle: 3.92/4.42 ->->-> Pairs: 3.92/4.42 U11#(tt,L) -> LENGTH(L) 3.92/4.42 LENGTH(cons(N,L)) -> U11#(and(isNatList(L),isNat(N)),L) 3.92/4.42 ->->-> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 ->->-> Unhiding rules: 3.92/4.42 Empty 3.92/4.42 3.92/4.42 3.92/4.42 The problem is decomposed in 2 subproblems. 3.92/4.42 3.92/4.42 Problem 1.1: 3.92/4.42 3.92/4.42 Reduction Pairs Processor: 3.92/4.42 -> Pairs: 3.92/4.42 AND(tt,X) -> X 3.92/4.42 ISNAT(length(V1)) -> ISNATLIST(V1) 3.92/4.42 ISNAT(s(V1)) -> ISNAT(V1) 3.92/4.42 ISNATILIST(cons(V1,V2)) -> AND(isNat(V1),isNatIList(V2)) 3.92/4.42 ISNATILIST(cons(V1,V2)) -> ISNAT(V1) 3.92/4.42 ISNATILIST(V) -> ISNATLIST(V) 3.92/4.42 ISNATLIST(cons(V1,V2)) -> AND(isNat(V1),isNatList(V2)) 3.92/4.42 ISNATLIST(cons(V1,V2)) -> ISNAT(V1) 3.92/4.42 -> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 -> Unhiding rules: 3.92/4.42 isNat(N) -> ISNAT(N) 3.92/4.42 isNatIList(V2) -> ISNATILIST(V2) 3.92/4.42 isNatList(V2) -> ISNATLIST(V2) 3.92/4.42 -> Usable rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 ->Interpretation type: 3.92/4.42 Linear 3.92/4.42 ->Coefficients: 3.92/4.42 Natural Numbers 3.92/4.42 ->Dimension: 3.92/4.42 1 3.92/4.42 ->Bound: 3.92/4.42 2 3.92/4.42 ->Interpretation: 3.92/4.42 3.92/4.42 [U11](X1,X2) = X1 + 2.X2 3.92/4.42 [and](X1,X2) = X2 3.92/4.42 [isNat](X) = 2.X + 2 3.92/4.42 [isNatIList](X) = 2.X + 2 3.92/4.42 [isNatList](X) = 2.X + 2 3.92/4.42 [length](X) = 2.X + 2 3.92/4.42 [zeros] = 0 3.92/4.42 [0] = 0 3.92/4.42 [cons](X1,X2) = X1 + 2.X2 3.92/4.42 [nil] = 1 3.92/4.42 [s](X) = X 3.92/4.42 [tt] = 2 3.92/4.42 [AND](X1,X2) = X2 3.92/4.42 [ISNAT](X) = 2.X + 2 3.92/4.42 [ISNATILIST](X) = 2.X + 2 3.92/4.42 [ISNATLIST](X) = 2.X + 2 3.92/4.42 3.92/4.42 Problem 1.1: 3.92/4.42 3.92/4.42 SCC Processor: 3.92/4.42 -> Pairs: 3.92/4.42 AND(tt,X) -> X 3.92/4.42 ISNAT(s(V1)) -> ISNAT(V1) 3.92/4.42 ISNATILIST(cons(V1,V2)) -> AND(isNat(V1),isNatIList(V2)) 3.92/4.42 ISNATILIST(cons(V1,V2)) -> ISNAT(V1) 3.92/4.42 ISNATILIST(V) -> ISNATLIST(V) 3.92/4.42 ISNATLIST(cons(V1,V2)) -> AND(isNat(V1),isNatList(V2)) 3.92/4.42 ISNATLIST(cons(V1,V2)) -> ISNAT(V1) 3.92/4.42 -> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 -> Unhiding rules: 3.92/4.42 isNat(N) -> ISNAT(N) 3.92/4.42 isNatIList(V2) -> ISNATILIST(V2) 3.92/4.42 isNatList(V2) -> ISNATLIST(V2) 3.92/4.42 ->Strongly Connected Components: 3.92/4.42 ->->Cycle: 3.92/4.42 ->->-> Pairs: 3.92/4.42 ISNAT(s(V1)) -> ISNAT(V1) 3.92/4.42 ->->-> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 ->->-> Unhiding rules: 3.92/4.42 Empty 3.92/4.42 ->->Cycle: 3.92/4.42 ->->-> Pairs: 3.92/4.42 AND(tt,X) -> X 3.92/4.42 ISNATILIST(cons(V1,V2)) -> AND(isNat(V1),isNatIList(V2)) 3.92/4.42 ISNATILIST(V) -> ISNATLIST(V) 3.92/4.42 ISNATLIST(cons(V1,V2)) -> AND(isNat(V1),isNatList(V2)) 3.92/4.42 ->->-> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 ->->-> Unhiding rules: 3.92/4.42 isNatIList(V2) -> ISNATILIST(V2) 3.92/4.42 isNatList(V2) -> ISNATLIST(V2) 3.92/4.42 3.92/4.42 3.92/4.42 The problem is decomposed in 2 subproblems. 3.92/4.42 3.92/4.42 Problem 1.1.1: 3.92/4.42 3.92/4.42 SubNColl Processor: 3.92/4.42 -> Pairs: 3.92/4.42 ISNAT(s(V1)) -> ISNAT(V1) 3.92/4.42 -> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 -> Unhiding rules: 3.92/4.42 Empty 3.92/4.42 ->Projection: 3.92/4.42 pi(ISNAT) = 1 3.92/4.42 3.92/4.42 Problem 1.1.1: 3.92/4.42 3.92/4.42 Basic Processor: 3.92/4.42 -> Pairs: 3.92/4.42 Empty 3.92/4.42 -> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 -> Unhiding rules: 3.92/4.42 Empty 3.92/4.42 -> Result: 3.92/4.42 Set P is empty 3.92/4.42 3.92/4.42 The problem is finite. 3.92/4.42 3.92/4.42 Problem 1.1.2: 3.92/4.42 3.92/4.42 Reduction Pairs Processor: 3.92/4.42 -> Pairs: 3.92/4.42 AND(tt,X) -> X 3.92/4.42 ISNATILIST(cons(V1,V2)) -> AND(isNat(V1),isNatIList(V2)) 3.92/4.42 ISNATILIST(V) -> ISNATLIST(V) 3.92/4.42 ISNATLIST(cons(V1,V2)) -> AND(isNat(V1),isNatList(V2)) 3.92/4.42 -> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 -> Unhiding rules: 3.92/4.42 isNatIList(V2) -> ISNATILIST(V2) 3.92/4.42 isNatList(V2) -> ISNATLIST(V2) 3.92/4.42 -> Usable rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 ->Interpretation type: 3.92/4.42 Linear 3.92/4.42 ->Coefficients: 3.92/4.42 Natural Numbers 3.92/4.42 ->Dimension: 3.92/4.42 1 3.92/4.42 ->Bound: 3.92/4.42 2 3.92/4.42 ->Interpretation: 3.92/4.42 3.92/4.42 [U11](X1,X2) = 2 3.92/4.42 [and](X1,X2) = X2 3.92/4.42 [isNat](X) = 2.X + 2 3.92/4.42 [isNatIList](X) = 2 3.92/4.42 [isNatList](X) = 1 3.92/4.42 [length](X) = 2 3.92/4.42 [zeros] = 2 3.92/4.42 [0] = 0 3.92/4.42 [cons](X1,X2) = 2.X1 + 2 3.92/4.42 [nil] = 2 3.92/4.42 [s](X) = X 3.92/4.42 [tt] = 1 3.92/4.42 [AND](X1,X2) = X2 3.92/4.42 [ISNATILIST](X) = 2 3.92/4.42 [ISNATLIST](X) = 1 3.92/4.42 3.92/4.42 Problem 1.1.2: 3.92/4.42 3.92/4.42 SCC Processor: 3.92/4.42 -> Pairs: 3.92/4.42 AND(tt,X) -> X 3.92/4.42 ISNATILIST(cons(V1,V2)) -> AND(isNat(V1),isNatIList(V2)) 3.92/4.42 ISNATLIST(cons(V1,V2)) -> AND(isNat(V1),isNatList(V2)) 3.92/4.42 -> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 -> Unhiding rules: 3.92/4.42 isNatIList(V2) -> ISNATILIST(V2) 3.92/4.42 isNatList(V2) -> ISNATLIST(V2) 3.92/4.42 ->Strongly Connected Components: 3.92/4.42 ->->Cycle: 3.92/4.42 ->->-> Pairs: 3.92/4.42 AND(tt,X) -> X 3.92/4.42 ISNATILIST(cons(V1,V2)) -> AND(isNat(V1),isNatIList(V2)) 3.92/4.42 ISNATLIST(cons(V1,V2)) -> AND(isNat(V1),isNatList(V2)) 3.92/4.42 ->->-> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 ->->-> Unhiding rules: 3.92/4.42 isNatIList(V2) -> ISNATILIST(V2) 3.92/4.42 isNatList(V2) -> ISNATLIST(V2) 3.92/4.42 3.92/4.42 Problem 1.1.2: 3.92/4.42 3.92/4.42 Non-Replacing Projection Processor: 3.92/4.42 -> Pairs: 3.92/4.42 AND(tt,X) -> X 3.92/4.42 ISNATILIST(cons(V1,V2)) -> AND(isNat(V1),isNatIList(V2)) 3.92/4.42 ISNATLIST(cons(V1,V2)) -> AND(isNat(V1),isNatList(V2)) 3.92/4.42 -> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 -> Unhiding rules: 3.92/4.42 isNatIList(V2) -> ISNATILIST(V2) 3.92/4.42 isNatList(V2) -> ISNATLIST(V2) 3.92/4.42 ->Projection: 3.92/4.42 pi(AND) = 2 3.92/4.42 pi(ISNATILIST) = 1 3.92/4.42 pi(ISNATLIST) = 1 3.92/4.42 ->Interpretation type: 3.92/4.42 Linear 3.92/4.42 ->Coefficients: 3.92/4.42 Natural Numbers 3.92/4.42 ->Dimension: 3.92/4.42 1 3.92/4.42 ->Bound: 3.92/4.42 2 3.92/4.42 ->Interpretation: 3.92/4.42 3.92/4.42 [U11](X1,X2) = 0 3.92/4.42 [and](X1,X2) = 0 3.92/4.42 [isNat](X) = 0 3.92/4.42 [isNatIList](X) = 2.X + 1 3.92/4.42 [isNatList](X) = 2.X + 2 3.92/4.42 [length](X) = 0 3.92/4.42 [zeros] = 0 3.92/4.42 [0] = 0 3.92/4.42 [cons](X1,X2) = 2.X2 + 2 3.92/4.42 [nil] = 0 3.92/4.42 [s](X) = 0 3.92/4.42 [tt] = 0 3.92/4.42 [U11#](X1,X2) = 0 3.92/4.42 [AND](X1,X2) = 0 3.92/4.42 [ISNAT](X) = 0 3.92/4.42 [ISNATILIST](X) = 0 3.92/4.42 [ISNATLIST](X) = 0 3.92/4.42 [LENGTH](X) = 0 3.92/4.42 [ZEROS] = 0 3.92/4.42 3.92/4.42 Problem 1.1.2: 3.92/4.42 3.92/4.42 SCC Processor: 3.92/4.42 -> Pairs: 3.92/4.42 AND(tt,X) -> X 3.92/4.42 ISNATLIST(cons(V1,V2)) -> AND(isNat(V1),isNatList(V2)) 3.92/4.42 -> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 -> Unhiding rules: 3.92/4.42 isNatIList(V2) -> ISNATILIST(V2) 3.92/4.42 isNatList(V2) -> ISNATLIST(V2) 3.92/4.42 ->Strongly Connected Components: 3.92/4.42 ->->Cycle: 3.92/4.42 ->->-> Pairs: 3.92/4.42 AND(tt,X) -> X 3.92/4.42 ISNATLIST(cons(V1,V2)) -> AND(isNat(V1),isNatList(V2)) 3.92/4.42 ->->-> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 ->->-> Unhiding rules: 3.92/4.42 isNatList(V2) -> ISNATLIST(V2) 3.92/4.42 3.92/4.42 Problem 1.1.2: 3.92/4.42 3.92/4.42 Non-Replacing Projection Processor: 3.92/4.42 -> Pairs: 3.92/4.42 AND(tt,X) -> X 3.92/4.42 ISNATLIST(cons(V1,V2)) -> AND(isNat(V1),isNatList(V2)) 3.92/4.42 -> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 -> Unhiding rules: 3.92/4.42 isNatList(V2) -> ISNATLIST(V2) 3.92/4.42 ->Projection: 3.92/4.42 pi(AND) = 2 3.92/4.42 pi(ISNATLIST) = 1 3.92/4.42 ->Interpretation type: 3.92/4.42 Linear 3.92/4.42 ->Coefficients: 3.92/4.42 Natural Numbers 3.92/4.42 ->Dimension: 3.92/4.42 1 3.92/4.42 ->Bound: 3.92/4.42 2 3.92/4.42 ->Interpretation: 3.92/4.42 3.92/4.42 [U11](X1,X2) = 0 3.92/4.42 [and](X1,X2) = 0 3.92/4.42 [isNat](X) = 0 3.92/4.42 [isNatIList](X) = 0 3.92/4.42 [isNatList](X) = 2.X 3.92/4.42 [length](X) = 0 3.92/4.42 [zeros] = 0 3.92/4.42 [0] = 0 3.92/4.42 [cons](X1,X2) = 2.X2 + 1 3.92/4.42 [nil] = 0 3.92/4.42 [s](X) = 0 3.92/4.42 [tt] = 0 3.92/4.42 [U11#](X1,X2) = 0 3.92/4.42 [AND](X1,X2) = 0 3.92/4.42 [ISNAT](X) = 0 3.92/4.42 [ISNATILIST](X) = 0 3.92/4.42 [ISNATLIST](X) = 0 3.92/4.42 [LENGTH](X) = 0 3.92/4.42 [ZEROS] = 0 3.92/4.42 3.92/4.42 Problem 1.1.2: 3.92/4.42 3.92/4.42 Basic Processor: 3.92/4.42 -> Pairs: 3.92/4.42 AND(tt,X) -> X 3.92/4.42 -> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 -> Unhiding rules: 3.92/4.42 isNatList(V2) -> ISNATLIST(V2) 3.92/4.42 -> Result: 3.92/4.42 All pairs P are from Px1 3.92/4.42 3.92/4.42 The problem is finite. 3.92/4.42 3.92/4.42 Problem 1.2: 3.92/4.42 3.92/4.42 Reduction Pairs Processor: 3.92/4.42 -> Pairs: 3.92/4.42 U11#(tt,L) -> LENGTH(L) 3.92/4.42 LENGTH(cons(N,L)) -> U11#(and(isNatList(L),isNat(N)),L) 3.92/4.42 -> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 -> Unhiding rules: 3.92/4.42 Empty 3.92/4.42 -> Usable rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 ->Interpretation type: 3.92/4.42 Simple mixed 3.92/4.42 ->Coefficients: 3.92/4.42 Natural Numbers 3.92/4.42 ->Dimension: 3.92/4.42 1 3.92/4.42 ->Bound: 3.92/4.42 2 3.92/4.42 ->Interpretation: 3.92/4.42 3.92/4.42 [U11](X1,X2) = 2.X1 + 2.X2 + 2 3.92/4.42 [and](X1,X2) = X1.X2 3.92/4.42 [isNat](X) = X + 1 3.92/4.42 [isNatIList](X) = 2.X.X + 2.X + 1 3.92/4.42 [isNatList](X) = X 3.92/4.42 [length](X) = 2.X + 2 3.92/4.42 [zeros] = 0 3.92/4.42 [0] = 0 3.92/4.42 [cons](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 3.92/4.42 [nil] = 2 3.92/4.42 [s](X) = X + 1 3.92/4.42 [tt] = 1 3.92/4.42 [U11#](X1,X2) = 2.X1 + 2.X2 + 1 3.92/4.42 [LENGTH](X) = 2.X + 2 3.92/4.42 3.92/4.42 Problem 1.2: 3.92/4.42 3.92/4.42 SCC Processor: 3.92/4.42 -> Pairs: 3.92/4.42 LENGTH(cons(N,L)) -> U11#(and(isNatList(L),isNat(N)),L) 3.92/4.42 -> Rules: 3.92/4.42 U11(tt,L) -> s(length(L)) 3.92/4.42 and(tt,X) -> X 3.92/4.42 isNat(length(V1)) -> isNatList(V1) 3.92/4.42 isNat(0) -> tt 3.92/4.42 isNat(s(V1)) -> isNat(V1) 3.92/4.42 isNatIList(zeros) -> tt 3.92/4.42 isNatIList(cons(V1,V2)) -> and(isNat(V1),isNatIList(V2)) 3.92/4.42 isNatIList(V) -> isNatList(V) 3.92/4.42 isNatList(cons(V1,V2)) -> and(isNat(V1),isNatList(V2)) 3.92/4.42 isNatList(nil) -> tt 3.92/4.42 length(cons(N,L)) -> U11(and(isNatList(L),isNat(N)),L) 3.92/4.42 length(nil) -> 0 3.92/4.42 zeros -> cons(0,zeros) 3.92/4.42 -> Unhiding rules: 3.92/4.42 Empty 3.92/4.42 ->Strongly Connected Components: 3.92/4.42 There is no strongly connected component 3.92/4.42 3.92/4.42 The problem is finite. 3.92/4.42 EOF