/export/starexec/sandbox2/solver/bin/starexec_run_default /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR L N V V1 V2 X) (STRATEGY CONTEXTSENSITIVE (U11 1) (U12 1) (U21 1) (U22 1) (U31 1) (U32 1) (U41 1) (U42 1) (U43 1) (U51 1) (U52 1) (U53 1) (U61 1) (and 1) (isNat) (isNatIList) (isNatIListKind) (isNatKind) (isNatList) (length 1) (zeros) (0) (cons 1) (nil) (s 1) (tt) ) (RULES U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ) Problem 1: Dependency Pairs Processor: -> Pairs: U11#(tt,V1) -> U12#(isNatList(V1)) U11#(tt,V1) -> ISNATLIST(V1) U21#(tt,V1) -> U22#(isNat(V1)) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V) -> U32#(isNatList(V)) U31#(tt,V) -> ISNATLIST(V) U41#(tt,V1,V2) -> U42#(isNat(V1),V2) U41#(tt,V1,V2) -> ISNAT(V1) U42#(tt,V2) -> U43#(isNatIList(V2)) U42#(tt,V2) -> ISNATILIST(V2) U51#(tt,V1,V2) -> U52#(isNat(V1),V2) U51#(tt,V1,V2) -> ISNAT(V1) U52#(tt,V2) -> U53#(isNatList(V2)) U52#(tt,V2) -> ISNATLIST(V2) U61#(tt,L) -> LENGTH(L) U61#(tt,L) -> L AND(tt,X) -> X ISNAT(length(V1)) -> U11#(isNatIListKind(V1),V1) ISNAT(length(V1)) -> ISNATILISTKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATILIST(cons(V1,V2)) -> U41#(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) ISNATILIST(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATILIST(cons(V1,V2)) -> ISNATKIND(V1) ISNATILIST(V) -> U31#(isNatIListKind(V),V) ISNATILIST(V) -> ISNATILISTKIND(V) ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ISNATLIST(cons(V1,V2)) -> U51#(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) ISNATLIST(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATLIST(cons(V1,V2)) -> ISNATKIND(V1) LENGTH(cons(N,L)) -> U61#(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) LENGTH(cons(N,L)) -> AND(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))) LENGTH(cons(N,L)) -> AND(isNatList(L),isNatIListKind(L)) LENGTH(cons(N,L)) -> ISNATLIST(L) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding Rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) zeros -> ZEROS Problem 1: SCC Processor: -> Pairs: U11#(tt,V1) -> U12#(isNatList(V1)) U11#(tt,V1) -> ISNATLIST(V1) U21#(tt,V1) -> U22#(isNat(V1)) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V) -> U32#(isNatList(V)) U31#(tt,V) -> ISNATLIST(V) U41#(tt,V1,V2) -> U42#(isNat(V1),V2) U41#(tt,V1,V2) -> ISNAT(V1) U42#(tt,V2) -> U43#(isNatIList(V2)) U42#(tt,V2) -> ISNATILIST(V2) U51#(tt,V1,V2) -> U52#(isNat(V1),V2) U51#(tt,V1,V2) -> ISNAT(V1) U52#(tt,V2) -> U53#(isNatList(V2)) U52#(tt,V2) -> ISNATLIST(V2) U61#(tt,L) -> LENGTH(L) U61#(tt,L) -> L AND(tt,X) -> X ISNAT(length(V1)) -> U11#(isNatIListKind(V1),V1) ISNAT(length(V1)) -> ISNATILISTKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATILIST(cons(V1,V2)) -> U41#(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) ISNATILIST(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATILIST(cons(V1,V2)) -> ISNATKIND(V1) ISNATILIST(V) -> U31#(isNatIListKind(V),V) ISNATILIST(V) -> ISNATILISTKIND(V) ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ISNATLIST(cons(V1,V2)) -> U51#(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) ISNATLIST(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATLIST(cons(V1,V2)) -> ISNATKIND(V1) LENGTH(cons(N,L)) -> U61#(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) LENGTH(cons(N,L)) -> AND(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))) LENGTH(cons(N,L)) -> AND(isNatList(L),isNatIListKind(L)) LENGTH(cons(N,L)) -> ISNATLIST(L) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) zeros -> ZEROS ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U11#(tt,V1) -> ISNATLIST(V1) U21#(tt,V1) -> ISNAT(V1) U51#(tt,V1,V2) -> U52#(isNat(V1),V2) U51#(tt,V1,V2) -> ISNAT(V1) U52#(tt,V2) -> ISNATLIST(V2) AND(tt,X) -> X ISNAT(length(V1)) -> U11#(isNatIListKind(V1),V1) ISNAT(length(V1)) -> ISNATILISTKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ISNATLIST(cons(V1,V2)) -> U51#(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) ISNATLIST(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATLIST(cons(V1,V2)) -> ISNATKIND(V1) ->->-> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) ->->Cycle: ->->-> Pairs: U41#(tt,V1,V2) -> U42#(isNat(V1),V2) U42#(tt,V2) -> ISNATILIST(V2) ISNATILIST(cons(V1,V2)) -> U41#(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) ->->-> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: Empty ->->Cycle: ->->-> Pairs: U61#(tt,L) -> LENGTH(L) LENGTH(cons(N,L)) -> U61#(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) ->->-> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: Empty The problem is decomposed in 3 subproblems. Problem 1.1: Reduction Pairs Processor: -> Pairs: U11#(tt,V1) -> ISNATLIST(V1) U21#(tt,V1) -> ISNAT(V1) U51#(tt,V1,V2) -> U52#(isNat(V1),V2) U51#(tt,V1,V2) -> ISNAT(V1) U52#(tt,V2) -> ISNATLIST(V2) AND(tt,X) -> X ISNAT(length(V1)) -> U11#(isNatIListKind(V1),V1) ISNAT(length(V1)) -> ISNATILISTKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ISNATLIST(cons(V1,V2)) -> U51#(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) ISNATLIST(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATLIST(cons(V1,V2)) -> ISNATKIND(V1) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) -> Usable rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2) = 2.X1 + 2.X2 + 2 [U12](X) = X + 2 [U21](X1,X2) = 2.X2 + 2 [U22](X) = 2 [U51](X1,X2,X3) = X1 + X2 + X3 [U52](X1,X2) = 2 [U53](X) = 2 [U61](X1,X2) = 2.X2 + 2 [and](X1,X2) = X2 [isNat](X) = 2.X + 2 [isNatIListKind](X) = 2 [isNatKind](X) = 2.X + 2 [isNatList](X) = 2.X + 2 [length](X) = 2.X + 2 [zeros] = 0 [0] = 0 [cons](X1,X2) = 2.X1 + 2.X2 [nil] = 2 [s](X) = X [tt] = 2 [U11#](X1,X2) = 2.X1 + 2.X2 + 2 [U21#](X1,X2) = 2.X2 + 2 [U51#](X1,X2,X3) = X1 + 2.X2 + 2.X3 [U52#](X1,X2) = X1 + 2.X2 [AND](X1,X2) = X2 [ISNAT](X) = 2.X + 2 [ISNATILISTKIND](X) = 2 [ISNATKIND](X) = 2 [ISNATLIST](X) = X + 2 Problem 1.1: SCC Processor: -> Pairs: U21#(tt,V1) -> ISNAT(V1) U51#(tt,V1,V2) -> U52#(isNat(V1),V2) U51#(tt,V1,V2) -> ISNAT(V1) U52#(tt,V2) -> ISNATLIST(V2) AND(tt,X) -> X ISNAT(length(V1)) -> U11#(isNatIListKind(V1),V1) ISNAT(length(V1)) -> ISNATILISTKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ISNATLIST(cons(V1,V2)) -> U51#(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) ISNATLIST(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATLIST(cons(V1,V2)) -> ISNATKIND(V1) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U21#(tt,V1) -> ISNAT(V1) AND(tt,X) -> X ISNAT(length(V1)) -> ISNATILISTKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ->->-> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) ->->Cycle: ->->-> Pairs: U51#(tt,V1,V2) -> U52#(isNat(V1),V2) U52#(tt,V2) -> ISNATLIST(V2) ISNATLIST(cons(V1,V2)) -> U51#(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) ->->-> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: Empty The problem is decomposed in 2 subproblems. Problem 1.1.1: Reduction Pairs Processor: -> Pairs: U21#(tt,V1) -> ISNAT(V1) AND(tt,X) -> X ISNAT(length(V1)) -> ISNATILISTKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) -> Usable rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2) = X1 + 2 [U12](X) = 2 [U21](X1,X2) = X1 [U22](X) = 0 [U51](X1,X2,X3) = 2.X3 + 2 [U52](X1,X2) = 2.X2 + 2 [U53](X) = 1 [U61](X1,X2) = 2 [and](X1,X2) = X2 [isNat](X) = 2.X + 2 [isNatIListKind](X) = 2 [isNatKind](X) = 2.X + 2 [isNatList](X) = 2.X + 2 [length](X) = 2 [zeros] = 0 [0] = 0 [cons](X1,X2) = 2.X2 [nil] = 1 [s](X) = X [tt] = 0 [U21#](X1,X2) = 2.X2 + 2 [AND](X1,X2) = X2 [ISNAT](X) = 2.X + 2 [ISNATILISTKIND](X) = 2 [ISNATKIND](X) = 2 Problem 1.1.1: SCC Processor: -> Pairs: U21#(tt,V1) -> ISNAT(V1) AND(tt,X) -> X ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U21#(tt,V1) -> ISNAT(V1) AND(tt,X) -> X ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ->->-> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) Problem 1.1.1: Reduction Pairs Processor: -> Pairs: U21#(tt,V1) -> ISNAT(V1) AND(tt,X) -> X ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) -> Usable rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2) = X1 + 1 [U12](X) = 1 [U21](X1,X2) = 1 [U22](X) = X [U51](X1,X2,X3) = 2.X1 + X2 + 2 [U52](X1,X2) = 2.X1 [U53](X) = 0 [U61](X1,X2) = 2 [and](X1,X2) = 2.X2 [isNat](X) = 1 [isNatIListKind](X) = 0 [isNatKind](X) = 2.X + 2 [isNatList](X) = 2.X + 2 [length](X) = 2 [zeros] = 2 [0] = 2 [cons](X1,X2) = X1 [nil] = 1 [s](X) = X [tt] = 0 [U21#](X1,X2) = X2 + 2 [AND](X1,X2) = X2 [ISNAT](X) = X + 2 [ISNATILISTKIND](X) = 0 [ISNATKIND](X) = 0 Problem 1.1.1: SCC Processor: -> Pairs: U21#(tt,V1) -> ISNAT(V1) AND(tt,X) -> X ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U21#(tt,V1) -> ISNAT(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ->->-> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: Empty ->->Cycle: ->->-> Pairs: AND(tt,X) -> X ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ->->-> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) The problem is decomposed in 2 subproblems. Problem 1.1.1.1: SubNColl Processor: -> Pairs: U21#(tt,V1) -> ISNAT(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Projection: pi(U21#) = 2 pi(ISNAT) = 1 Problem 1.1.1.1: SCC Processor: -> Pairs: U21#(tt,V1) -> ISNAT(V1) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.1.1.2: Reduction Pairs Processor: -> Pairs: AND(tt,X) -> X ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) -> Usable rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2) = X2 + 2 [U12](X) = 2 [U21](X1,X2) = X1 + 1 [U22](X) = 2 [U51](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U52](X1,X2) = 2.X2 + 2 [U53](X) = X [U61](X1,X2) = 2.X1 + 2.X2 [and](X1,X2) = X2 [isNat](X) = 2.X + 2 [isNatIListKind](X) = 2.X + 2 [isNatKind](X) = 2.X + 1 [isNatList](X) = 2.X + 2 [length](X) = 2.X + 2 [zeros] = 0 [0] = 0 [cons](X1,X2) = 2.X1 + 2.X2 [nil] = 2 [s](X) = X [tt] = 1 [AND](X1,X2) = X2 [ISNATILISTKIND](X) = 2.X + 2 [ISNATKIND](X) = 2.X + 1 Problem 1.1.1.2: SCC Processor: -> Pairs: AND(tt,X) -> X ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: AND(tt,X) -> X ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ->->-> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) ->->Cycle: ->->-> Pairs: ISNATKIND(s(V1)) -> ISNATKIND(V1) ->->-> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: Empty The problem is decomposed in 2 subproblems. Problem 1.1.1.2.1: Reduction Pairs Processor: -> Pairs: AND(tt,X) -> X ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) -> Usable rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2) = X1 + 2 [U12](X) = 2 [U21](X1,X2) = 2.X2 + 2 [U22](X) = X [U51](X1,X2,X3) = 2.X1 [U52](X1,X2) = 0 [U53](X) = 0 [U61](X1,X2) = 2 [and](X1,X2) = 2.X2 [isNat](X) = 2.X + 2 [isNatIListKind](X) = 0 [isNatKind](X) = 2 [isNatList](X) = 2 [length](X) = 2 [zeros] = 0 [0] = 0 [cons](X1,X2) = 2.X1 [nil] = 0 [s](X) = X [tt] = 0 [AND](X1,X2) = X2 [ISNATILISTKIND](X) = 0 Problem 1.1.1.2.1: SCC Processor: -> Pairs: AND(tt,X) -> X ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: AND(tt,X) -> X ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) ->->-> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) Problem 1.1.1.2.1: Non-Replacing Projection Processor: -> Pairs: AND(tt,X) -> X ISNATILISTKIND(cons(V1,V2)) -> AND(isNatKind(V1),isNatIListKind(V2)) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) ->Projection: pi(AND) = 2 pi(ISNATILISTKIND) = 1 ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2) = 0 [U12](X) = 0 [U21](X1,X2) = 0 [U22](X) = 0 [U31](X1,X2) = 0 [U32](X) = 0 [U41](X1,X2,X3) = 0 [U42](X1,X2) = 0 [U43](X) = 0 [U51](X1,X2,X3) = 0 [U52](X1,X2) = 0 [U53](X) = 0 [U61](X1,X2) = 0 [and](X1,X2) = 0 [isNat](X) = 0 [isNatIList](X) = 0 [isNatIListKind](X) = 2.X [isNatKind](X) = 0 [isNatList](X) = 0 [length](X) = 0 [zeros] = 0 [0] = 0 [cons](X1,X2) = 2.X2 + 1 [nil] = 0 [s](X) = 0 [tt] = 0 [U11#](X1,X2) = 0 [U12#](X) = 0 [U21#](X1,X2) = 0 [U22#](X) = 0 [U31#](X1,X2) = 0 [U32#](X) = 0 [U41#](X1,X2,X3) = 0 [U42#](X1,X2) = 0 [U43#](X) = 0 [U51#](X1,X2,X3) = 0 [U52#](X1,X2) = 0 [U53#](X) = 0 [U61#](X1,X2) = 0 [AND](X1,X2) = 0 [ISNAT](X) = 0 [ISNATILIST](X) = 0 [ISNATILISTKIND](X) = 0 [ISNATKIND](X) = 0 [ISNATLIST](X) = 0 [LENGTH](X) = 0 [ZEROS] = 0 Problem 1.1.1.2.1: Basic Processor: -> Pairs: AND(tt,X) -> X -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: isNatIListKind(L) -> ISNATILISTKIND(L) isNatIListKind(V2) -> ISNATILISTKIND(V2) -> Result: All pairs P are from Px1 The problem is finite. Problem 1.1.1.2.2: SubNColl Processor: -> Pairs: ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Projection: pi(ISNATKIND) = 1 Problem 1.1.1.2.2: Basic Processor: -> Pairs: Empty -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty -> Result: Set P is empty The problem is finite. Problem 1.1.2: Non-Replacing Projection Processor: -> Pairs: U51#(tt,V1,V2) -> U52#(isNat(V1),V2) U52#(tt,V2) -> ISNATLIST(V2) ISNATLIST(cons(V1,V2)) -> U51#(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Projection: pi(U51#) = 3 pi(U52#) = 2 pi(ISNATLIST) = 1 ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2) = 0 [U12](X) = 0 [U21](X1,X2) = 0 [U22](X) = 0 [U31](X1,X2) = 0 [U32](X) = 0 [U41](X1,X2,X3) = 0 [U42](X1,X2) = 0 [U43](X) = 0 [U51](X1,X2,X3) = 0 [U52](X1,X2) = 0 [U53](X) = 0 [U61](X1,X2) = 0 [and](X1,X2) = 0 [isNat](X) = 0 [isNatIList](X) = 0 [isNatIListKind](X) = 0 [isNatKind](X) = 0 [isNatList](X) = 0 [length](X) = 0 [zeros] = 0 [0] = 0 [cons](X1,X2) = 2.X2 + 2 [nil] = 0 [s](X) = 0 [tt] = 0 [U11#](X1,X2) = 0 [U12#](X) = 0 [U21#](X1,X2) = 0 [U22#](X) = 0 [U31#](X1,X2) = 0 [U32#](X) = 0 [U41#](X1,X2,X3) = 0 [U42#](X1,X2) = 0 [U43#](X) = 0 [U51#](X1,X2,X3) = 0 [U52#](X1,X2) = 0 [U53#](X) = 0 [U61#](X1,X2) = 0 [AND](X1,X2) = 0 [ISNAT](X) = 0 [ISNATILIST](X) = 0 [ISNATILISTKIND](X) = 0 [ISNATKIND](X) = 0 [ISNATLIST](X) = 0 [LENGTH](X) = 0 [ZEROS] = 0 Problem 1.1.2: SCC Processor: -> Pairs: U51#(tt,V1,V2) -> U52#(isNat(V1),V2) U52#(tt,V2) -> ISNATLIST(V2) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Non-Replacing Projection Processor: -> Pairs: U41#(tt,V1,V2) -> U42#(isNat(V1),V2) U42#(tt,V2) -> ISNATILIST(V2) ISNATILIST(cons(V1,V2)) -> U41#(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Projection: pi(U41#) = 3 pi(U42#) = 2 pi(ISNATILIST) = 1 ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2) = 0 [U12](X) = 0 [U21](X1,X2) = 0 [U22](X) = 0 [U31](X1,X2) = 0 [U32](X) = 0 [U41](X1,X2,X3) = 0 [U42](X1,X2) = 0 [U43](X) = 0 [U51](X1,X2,X3) = 0 [U52](X1,X2) = 0 [U53](X) = 0 [U61](X1,X2) = 0 [and](X1,X2) = 0 [isNat](X) = 0 [isNatIList](X) = 0 [isNatIListKind](X) = 0 [isNatKind](X) = 0 [isNatList](X) = 0 [length](X) = 0 [zeros] = 0 [0] = 0 [cons](X1,X2) = 2.X2 + 2 [nil] = 0 [s](X) = 0 [tt] = 0 [U11#](X1,X2) = 0 [U12#](X) = 0 [U21#](X1,X2) = 0 [U22#](X) = 0 [U31#](X1,X2) = 0 [U32#](X) = 0 [U41#](X1,X2,X3) = 0 [U42#](X1,X2) = 0 [U43#](X) = 0 [U51#](X1,X2,X3) = 0 [U52#](X1,X2) = 0 [U53#](X) = 0 [U61#](X1,X2) = 0 [AND](X1,X2) = 0 [ISNAT](X) = 0 [ISNATILIST](X) = 0 [ISNATILISTKIND](X) = 0 [ISNATKIND](X) = 0 [ISNATLIST](X) = 0 [LENGTH](X) = 0 [ZEROS] = 0 Problem 1.2: SCC Processor: -> Pairs: U41#(tt,V1,V2) -> U42#(isNat(V1),V2) U42#(tt,V2) -> ISNATILIST(V2) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Reduction Pairs Processor: -> Pairs: U61#(tt,L) -> LENGTH(L) LENGTH(cons(N,L)) -> U61#(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty -> Usable rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2) = 2.X1.X2 + 2.X1 + 1 [U12](X) = 2 [U21](X1,X2) = X1 + 2 [U22](X) = 2 [U51](X1,X2,X3) = 2.X1.X2.X3 + 2.X1.X3 + X2.X3 + 2.X3 [U52](X1,X2) = 2.X1.X2 + 2.X2 [U53](X) = 2.X [U61](X1,X2) = 2 [and](X1,X2) = X1.X2 [isNat](X) = X + 1 [isNatIListKind](X) = 1 [isNatKind](X) = 1 [isNatList](X) = 2.X [length](X) = 2.X + 2 [zeros] = 0 [0] = 2 [cons](X1,X2) = 2.X1.X2 + 2.X2 [nil] = 2 [s](X) = 2 [tt] = 1 [U61#](X1,X2) = X1 + 2.X2 + 2 [LENGTH](X) = 2.X + 2 Problem 1.3: SCC Processor: -> Pairs: LENGTH(cons(N,L)) -> U61#(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) -> Rules: U11(tt,V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt,V1,V2) -> U42(isNat(V1),V2) U42(tt,V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt,V1,V2) -> U52(isNat(V1),V2) U52(tt,V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt,L) -> s(length(L)) and(tt,X) -> X isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> and(isNatKind(V1),isNatIListKind(V2)) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1,V2)) -> U51(and(isNatKind(V1),isNatIListKind(V2)),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U61(and(and(isNatList(L),isNatIListKind(L)),and(isNat(N),isNatKind(N))),L) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Strongly Connected Components: There is no strongly connected component The problem is finite.