/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR L N V V1 V2) (STRATEGY CONTEXTSENSITIVE (U11 1) (U12 1) (U13 1) (U21 1) (U22 1) (U23 1) (U31 1) (U32 1) (U33 1) (U41 1) (U42 1) (U43 1) (U44 1) (U45 1) (U46 1) (U51 1) (U52 1) (U61 1) (U71 1) (U81 1) (U82 1) (U83 1) (U84 1) (U85 1) (U86 1) (U91 1) (U92 1) (U93 1) (U94 1) (isNat) (isNatIList) (isNatIListKind) (isNatKind) (isNatList) (length 1) (zeros) (0) (cons 1) (nil) (s 1) (tt) ) (RULES U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) ) Problem 1: Dependency Pairs Processor: -> Pairs: U11#(tt,V1) -> U12#(isNatIListKind(V1),V1) U11#(tt,V1) -> ISNATILISTKIND(V1) U12#(tt,V1) -> U13#(isNatList(V1)) U12#(tt,V1) -> ISNATLIST(V1) U21#(tt,V1) -> U22#(isNatKind(V1),V1) U21#(tt,V1) -> ISNATKIND(V1) U22#(tt,V1) -> U23#(isNat(V1)) U22#(tt,V1) -> ISNAT(V1) U31#(tt,V) -> U32#(isNatIListKind(V),V) U31#(tt,V) -> ISNATILISTKIND(V) U32#(tt,V) -> U33#(isNatList(V)) U32#(tt,V) -> ISNATLIST(V) U41#(tt,V1,V2) -> U42#(isNatKind(V1),V1,V2) U41#(tt,V1,V2) -> ISNATKIND(V1) U42#(tt,V1,V2) -> U43#(isNatIListKind(V2),V1,V2) U42#(tt,V1,V2) -> ISNATILISTKIND(V2) U43#(tt,V1,V2) -> U44#(isNatIListKind(V2),V1,V2) U43#(tt,V1,V2) -> ISNATILISTKIND(V2) U44#(tt,V1,V2) -> U45#(isNat(V1),V2) U44#(tt,V1,V2) -> ISNAT(V1) U45#(tt,V2) -> U46#(isNatIList(V2)) U45#(tt,V2) -> ISNATILIST(V2) U51#(tt,V2) -> U52#(isNatIListKind(V2)) U51#(tt,V2) -> ISNATILISTKIND(V2) U81#(tt,V1,V2) -> U82#(isNatKind(V1),V1,V2) U81#(tt,V1,V2) -> ISNATKIND(V1) U82#(tt,V1,V2) -> U83#(isNatIListKind(V2),V1,V2) U82#(tt,V1,V2) -> ISNATILISTKIND(V2) U83#(tt,V1,V2) -> U84#(isNatIListKind(V2),V1,V2) U83#(tt,V1,V2) -> ISNATILISTKIND(V2) U84#(tt,V1,V2) -> U85#(isNat(V1),V2) U84#(tt,V1,V2) -> ISNAT(V1) U85#(tt,V2) -> U86#(isNatList(V2)) U85#(tt,V2) -> ISNATLIST(V2) U91#(tt,L,N) -> U92#(isNatIListKind(L),L,N) U91#(tt,L,N) -> ISNATILISTKIND(L) U92#(tt,L,N) -> U93#(isNat(N),L,N) U92#(tt,L,N) -> ISNAT(N) U93#(tt,L,N) -> U94#(isNatKind(N),L) U93#(tt,L,N) -> ISNATKIND(N) U94#(tt,L) -> LENGTH(L) U94#(tt,L) -> L 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#(isNatKind(V1),V1,V2) ISNATILIST(cons(V1,V2)) -> ISNATKIND(V1) ISNATILIST(V) -> U31#(isNatIListKind(V),V) ISNATILIST(V) -> ISNATILISTKIND(V) ISNATILISTKIND(cons(V1,V2)) -> U51#(isNatKind(V1),V2) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> U61#(isNatIListKind(V1)) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> U71#(isNatKind(V1)) ISNATKIND(s(V1)) -> ISNATKIND(V1) ISNATLIST(cons(V1,V2)) -> U81#(isNatKind(V1),V1,V2) ISNATLIST(cons(V1,V2)) -> ISNATKIND(V1) LENGTH(cons(N,L)) -> U91#(isNatList(L),L,N) LENGTH(cons(N,L)) -> ISNATLIST(L) -> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding Rules: zeros -> ZEROS Problem 1: SCC Processor: -> Pairs: U11#(tt,V1) -> U12#(isNatIListKind(V1),V1) U11#(tt,V1) -> ISNATILISTKIND(V1) U12#(tt,V1) -> U13#(isNatList(V1)) U12#(tt,V1) -> ISNATLIST(V1) U21#(tt,V1) -> U22#(isNatKind(V1),V1) U21#(tt,V1) -> ISNATKIND(V1) U22#(tt,V1) -> U23#(isNat(V1)) U22#(tt,V1) -> ISNAT(V1) U31#(tt,V) -> U32#(isNatIListKind(V),V) U31#(tt,V) -> ISNATILISTKIND(V) U32#(tt,V) -> U33#(isNatList(V)) U32#(tt,V) -> ISNATLIST(V) U41#(tt,V1,V2) -> U42#(isNatKind(V1),V1,V2) U41#(tt,V1,V2) -> ISNATKIND(V1) U42#(tt,V1,V2) -> U43#(isNatIListKind(V2),V1,V2) U42#(tt,V1,V2) -> ISNATILISTKIND(V2) U43#(tt,V1,V2) -> U44#(isNatIListKind(V2),V1,V2) U43#(tt,V1,V2) -> ISNATILISTKIND(V2) U44#(tt,V1,V2) -> U45#(isNat(V1),V2) U44#(tt,V1,V2) -> ISNAT(V1) U45#(tt,V2) -> U46#(isNatIList(V2)) U45#(tt,V2) -> ISNATILIST(V2) U51#(tt,V2) -> U52#(isNatIListKind(V2)) U51#(tt,V2) -> ISNATILISTKIND(V2) U81#(tt,V1,V2) -> U82#(isNatKind(V1),V1,V2) U81#(tt,V1,V2) -> ISNATKIND(V1) U82#(tt,V1,V2) -> U83#(isNatIListKind(V2),V1,V2) U82#(tt,V1,V2) -> ISNATILISTKIND(V2) U83#(tt,V1,V2) -> U84#(isNatIListKind(V2),V1,V2) U83#(tt,V1,V2) -> ISNATILISTKIND(V2) U84#(tt,V1,V2) -> U85#(isNat(V1),V2) U84#(tt,V1,V2) -> ISNAT(V1) U85#(tt,V2) -> U86#(isNatList(V2)) U85#(tt,V2) -> ISNATLIST(V2) U91#(tt,L,N) -> U92#(isNatIListKind(L),L,N) U91#(tt,L,N) -> ISNATILISTKIND(L) U92#(tt,L,N) -> U93#(isNat(N),L,N) U92#(tt,L,N) -> ISNAT(N) U93#(tt,L,N) -> U94#(isNatKind(N),L) U93#(tt,L,N) -> ISNATKIND(N) U94#(tt,L) -> LENGTH(L) U94#(tt,L) -> L 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#(isNatKind(V1),V1,V2) ISNATILIST(cons(V1,V2)) -> ISNATKIND(V1) ISNATILIST(V) -> U31#(isNatIListKind(V),V) ISNATILIST(V) -> ISNATILISTKIND(V) ISNATILISTKIND(cons(V1,V2)) -> U51#(isNatKind(V1),V2) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> U61#(isNatIListKind(V1)) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> U71#(isNatKind(V1)) ISNATKIND(s(V1)) -> ISNATKIND(V1) ISNATLIST(cons(V1,V2)) -> U81#(isNatKind(V1),V1,V2) ISNATLIST(cons(V1,V2)) -> ISNATKIND(V1) LENGTH(cons(N,L)) -> U91#(isNatList(L),L,N) LENGTH(cons(N,L)) -> ISNATLIST(L) -> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: zeros -> ZEROS ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U51#(tt,V2) -> ISNATILISTKIND(V2) ISNATILISTKIND(cons(V1,V2)) -> U51#(isNatKind(V1),V2) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ->->-> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: Empty ->->Cycle: ->->-> Pairs: U11#(tt,V1) -> U12#(isNatIListKind(V1),V1) U12#(tt,V1) -> ISNATLIST(V1) U21#(tt,V1) -> U22#(isNatKind(V1),V1) U22#(tt,V1) -> ISNAT(V1) U81#(tt,V1,V2) -> U82#(isNatKind(V1),V1,V2) U82#(tt,V1,V2) -> U83#(isNatIListKind(V2),V1,V2) U83#(tt,V1,V2) -> U84#(isNatIListKind(V2),V1,V2) U84#(tt,V1,V2) -> U85#(isNat(V1),V2) U84#(tt,V1,V2) -> ISNAT(V1) U85#(tt,V2) -> ISNATLIST(V2) ISNAT(length(V1)) -> U11#(isNatIListKind(V1),V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNATLIST(cons(V1,V2)) -> U81#(isNatKind(V1),V1,V2) ->->-> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: Empty ->->Cycle: ->->-> Pairs: U41#(tt,V1,V2) -> U42#(isNatKind(V1),V1,V2) U42#(tt,V1,V2) -> U43#(isNatIListKind(V2),V1,V2) U43#(tt,V1,V2) -> U44#(isNatIListKind(V2),V1,V2) U44#(tt,V1,V2) -> U45#(isNat(V1),V2) U45#(tt,V2) -> ISNATILIST(V2) ISNATILIST(cons(V1,V2)) -> U41#(isNatKind(V1),V1,V2) ->->-> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: Empty ->->Cycle: ->->-> Pairs: U91#(tt,L,N) -> U92#(isNatIListKind(L),L,N) U92#(tt,L,N) -> U93#(isNat(N),L,N) U93#(tt,L,N) -> U94#(isNatKind(N),L) U94#(tt,L) -> LENGTH(L) LENGTH(cons(N,L)) -> U91#(isNatList(L),L,N) ->->-> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: Empty The problem is decomposed in 4 subproblems. Problem 1.1: Reduction Pairs Processor: -> Pairs: U51#(tt,V2) -> ISNATILISTKIND(V2) ISNATILISTKIND(cons(V1,V2)) -> U51#(isNatKind(V1),V2) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty -> Usable rules: U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U51](X1,X2) = 2 [U52](X) = 2 [U61](X) = 2.X + 1 [U71](X) = 2.X + 1 [isNatIListKind](X) = 2 [isNatKind](X) = 2.X + 2 [length](X) = 2.X + 2 [zeros] = 0 [0] = 2 [cons](X1,X2) = 2.X1 + X2 + 1 [nil] = 0 [s](X) = 2.X + 2 [tt] = 2 [U51#](X1,X2) = X1 + X2 [ISNATILISTKIND](X) = X + 1 [ISNATKIND](X) = 2.X + 1 Problem 1.1: SCC Processor: -> Pairs: ISNATILISTKIND(cons(V1,V2)) -> U51#(isNatKind(V1),V2) ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ->->-> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: Empty Problem 1.1: SubNColl Processor: -> Pairs: ISNATILISTKIND(cons(V1,V2)) -> ISNATKIND(V1) ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Projection: pi(ISNATILISTKIND) = 1 pi(ISNATKIND) = 1 Problem 1.1: Basic Processor: -> Pairs: Empty -> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty -> Result: Set P is empty The problem is finite. Problem 1.2: Reduction Pairs Processor: -> Pairs: U11#(tt,V1) -> U12#(isNatIListKind(V1),V1) U12#(tt,V1) -> ISNATLIST(V1) U21#(tt,V1) -> U22#(isNatKind(V1),V1) U22#(tt,V1) -> ISNAT(V1) U81#(tt,V1,V2) -> U82#(isNatKind(V1),V1,V2) U82#(tt,V1,V2) -> U83#(isNatIListKind(V2),V1,V2) U83#(tt,V1,V2) -> U84#(isNatIListKind(V2),V1,V2) U84#(tt,V1,V2) -> U85#(isNat(V1),V2) U84#(tt,V1,V2) -> ISNAT(V1) U85#(tt,V2) -> ISNATLIST(V2) ISNAT(length(V1)) -> U11#(isNatIListKind(V1),V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNATLIST(cons(V1,V2)) -> U81#(isNatKind(V1),V1,V2) -> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty -> Usable rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2) = 2.X1 + 2.X2 + 2 [U12](X1,X2) = 2.X1 + 2 [U13](X) = 2 [U21](X1,X2) = X1 + 2.X2 + 2 [U22](X1,X2) = X1 [U23](X) = 2 [U51](X1,X2) = X1 + 2.X2 + 1 [U52](X) = 2.X + 1 [U61](X) = 2.X + 2 [U71](X) = 2.X + 2 [U81](X1,X2,X3) = X1 + 2.X2 + 2.X3 + 2 [U82](X1,X2,X3) = X1 + 2.X3 + 2 [U83](X1,X2,X3) = 2.X1 + 2 [U84](X1,X2,X3) = 2 [U85](X1,X2) = 2 [U86](X) = 2 [isNat](X) = 2.X + 2 [isNatIListKind](X) = X + 1 [isNatKind](X) = 2.X + 2 [isNatList](X) = 2.X + 2 [length](X) = 2.X + 2 [zeros] = 2 [0] = 2 [cons](X1,X2) = 2.X1 + 2.X2 + 2 [nil] = 2 [s](X) = 2.X + 2 [tt] = 2 [U11#](X1,X2) = 2.X1 + 2.X2 + 2 [U12#](X1,X2) = 2.X2 + 1 [U21#](X1,X2) = X1 + 2.X2 + 1 [U22#](X1,X2) = 2.X2 + 2 [U81#](X1,X2,X3) = X1 + 2.X2 + 2.X3 + 2 [U82#](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U83#](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U84#](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U85#](X1,X2) = 2.X2 + 1 [ISNAT](X) = 2.X + 2 [ISNATLIST](X) = 2.X Problem 1.2: SCC Processor: -> Pairs: U12#(tt,V1) -> ISNATLIST(V1) U21#(tt,V1) -> U22#(isNatKind(V1),V1) U22#(tt,V1) -> ISNAT(V1) U81#(tt,V1,V2) -> U82#(isNatKind(V1),V1,V2) U82#(tt,V1,V2) -> U83#(isNatIListKind(V2),V1,V2) U83#(tt,V1,V2) -> U84#(isNatIListKind(V2),V1,V2) U84#(tt,V1,V2) -> U85#(isNat(V1),V2) U84#(tt,V1,V2) -> ISNAT(V1) U85#(tt,V2) -> ISNATLIST(V2) ISNAT(length(V1)) -> U11#(isNatIListKind(V1),V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNATLIST(cons(V1,V2)) -> U81#(isNatKind(V1),V1,V2) -> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U21#(tt,V1) -> U22#(isNatKind(V1),V1) U22#(tt,V1) -> ISNAT(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ->->-> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: Empty ->->Cycle: ->->-> Pairs: U81#(tt,V1,V2) -> U82#(isNatKind(V1),V1,V2) U82#(tt,V1,V2) -> U83#(isNatIListKind(V2),V1,V2) U83#(tt,V1,V2) -> U84#(isNatIListKind(V2),V1,V2) U84#(tt,V1,V2) -> U85#(isNat(V1),V2) U85#(tt,V2) -> ISNATLIST(V2) ISNATLIST(cons(V1,V2)) -> U81#(isNatKind(V1),V1,V2) ->->-> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) ->->-> Unhiding rules: Empty The problem is decomposed in 2 subproblems. Problem 1.2.1: SubNColl Processor: -> Pairs: U21#(tt,V1) -> U22#(isNatKind(V1),V1) U22#(tt,V1) -> ISNAT(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) -> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Projection: pi(U21#) = 2 pi(U22#) = 2 pi(ISNAT) = 1 Problem 1.2.1: SCC Processor: -> Pairs: U21#(tt,V1) -> U22#(isNatKind(V1),V1) U22#(tt,V1) -> ISNAT(V1) -> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) 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.2: Reduction Pairs Processor: -> Pairs: U81#(tt,V1,V2) -> U82#(isNatKind(V1),V1,V2) U82#(tt,V1,V2) -> U83#(isNatIListKind(V2),V1,V2) U83#(tt,V1,V2) -> U84#(isNatIListKind(V2),V1,V2) U84#(tt,V1,V2) -> U85#(isNat(V1),V2) U85#(tt,V2) -> ISNATLIST(V2) ISNATLIST(cons(V1,V2)) -> U81#(isNatKind(V1),V1,V2) -> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty -> Usable rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2) = X1 + 2.X2 + 1 [U12](X1,X2) = X1 + X2 + 2 [U13](X) = 2 [U21](X1,X2) = 2.X1 + 2.X2 + 2 [U22](X1,X2) = X1 + X2 + 2 [U23](X) = 2 [U51](X1,X2) = 2.X1 + 2.X2 [U52](X) = 2.X + 1 [U61](X) = 2.X [U71](X) = X + 2 [U81](X1,X2,X3) = X1 + 2.X2 + 2.X3 + 2 [U82](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U83](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U84](X1,X2,X3) = X1 + 2.X2 + X3 + 2 [U85](X1,X2) = X1 + X2 [U86](X) = 2 [isNat](X) = 2.X + 1 [isNatIListKind](X) = X [isNatKind](X) = X + 1 [isNatList](X) = 2.X + 2 [length](X) = 2.X + 1 [zeros] = 2 [0] = 2 [cons](X1,X2) = 2.X1 + 2.X2 + 2 [nil] = 2 [s](X) = 2.X + 2 [tt] = 2 [U81#](X1,X2,X3) = X1 + X2 + 2.X3 + 2 [U82#](X1,X2,X3) = X1 + 2.X3 + 2 [U83#](X1,X2,X3) = X1 + X3 + 2 [U84#](X1,X2,X3) = X3 + 2 [U85#](X1,X2) = X2 + 2 [ISNATLIST](X) = X + 2 Problem 1.2.2: SCC Processor: -> Pairs: U82#(tt,V1,V2) -> U83#(isNatIListKind(V2),V1,V2) U83#(tt,V1,V2) -> U84#(isNatIListKind(V2),V1,V2) U84#(tt,V1,V2) -> U85#(isNat(V1),V2) U85#(tt,V2) -> ISNATLIST(V2) ISNATLIST(cons(V1,V2)) -> U81#(isNatKind(V1),V1,V2) -> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) 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: U41#(tt,V1,V2) -> U42#(isNatKind(V1),V1,V2) U42#(tt,V1,V2) -> U43#(isNatIListKind(V2),V1,V2) U43#(tt,V1,V2) -> U44#(isNatIListKind(V2),V1,V2) U44#(tt,V1,V2) -> U45#(isNat(V1),V2) U45#(tt,V2) -> ISNATILIST(V2) ISNATILIST(cons(V1,V2)) -> U41#(isNatKind(V1),V1,V2) -> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty -> Usable rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2) = X1 + 2.X2 + 1 [U12](X1,X2) = X1 + X2 + 2 [U13](X) = 2 [U21](X1,X2) = 2.X1 + 2.X2 + 2 [U22](X1,X2) = X1 + X2 + 2 [U23](X) = 2 [U51](X1,X2) = 2.X1 + 2.X2 [U52](X) = 2.X + 1 [U61](X) = 2.X [U71](X) = X + 2 [U81](X1,X2,X3) = X1 + 2.X2 + 2.X3 + 2 [U82](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U83](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U84](X1,X2,X3) = X1 + 2.X2 + X3 + 2 [U85](X1,X2) = X1 + X2 [U86](X) = 2 [isNat](X) = 2.X + 1 [isNatIListKind](X) = X [isNatKind](X) = X + 1 [isNatList](X) = 2.X + 2 [length](X) = 2.X + 1 [zeros] = 2 [0] = 2 [cons](X1,X2) = 2.X1 + 2.X2 + 2 [nil] = 2 [s](X) = 2.X + 2 [tt] = 2 [U41#](X1,X2,X3) = X1 + X2 + 2.X3 + 2 [U42#](X1,X2,X3) = X1 + 2.X3 + 2 [U43#](X1,X2,X3) = X1 + X3 + 2 [U44#](X1,X2,X3) = X3 + 2 [U45#](X1,X2) = X2 + 2 [ISNATILIST](X) = X + 2 Problem 1.3: SCC Processor: -> Pairs: U42#(tt,V1,V2) -> U43#(isNatIListKind(V2),V1,V2) U43#(tt,V1,V2) -> U44#(isNatIListKind(V2),V1,V2) U44#(tt,V1,V2) -> U45#(isNat(V1),V2) U45#(tt,V2) -> ISNATILIST(V2) ISNATILIST(cons(V1,V2)) -> U41#(isNatKind(V1),V1,V2) -> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) 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.4: Reduction Pairs Processor: -> Pairs: U91#(tt,L,N) -> U92#(isNatIListKind(L),L,N) U92#(tt,L,N) -> U93#(isNat(N),L,N) U93#(tt,L,N) -> U94#(isNatKind(N),L) U94#(tt,L) -> LENGTH(L) LENGTH(cons(N,L)) -> U91#(isNatList(L),L,N) -> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty -> Usable rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) isNat(length(V1)) -> U11(isNatIListKind(V1),V1) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) 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 [U12](X1,X2) = 2.X1 + 2.X2 [U13](X) = 2.X + 2 [U21](X1,X2) = 2.X1 + 2 [U22](X1,X2) = 2 [U23](X) = 2 [U51](X1,X2) = 2 [U52](X) = 2 [U61](X) = 2 [U71](X) = 2 [U81](X1,X2,X3) = 2.X3 [U82](X1,X2,X3) = 2.X3 [U83](X1,X2,X3) = 2.X3 [U84](X1,X2,X3) = 2.X3 [U85](X1,X2) = 2.X2 [U86](X) = 2.X [U91](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 1 [U92](X1,X2,X3) = X1 + 2.X2 + 2.X3 + 2 [U93](X1,X2,X3) = X1 + 2.X2 + 1 [U94](X1,X2) = X1 + 2.X2 + 1 [isNat](X) = 2.X + 2 [isNatIListKind](X) = 2 [isNatKind](X) = 2 [isNatList](X) = X [length](X) = 2.X + 1 [zeros] = 0 [0] = 0 [cons](X1,X2) = X1 + 2.X2 [nil] = 2 [s](X) = X + 2 [tt] = 2 [U91#](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 [U92#](X1,X2,X3) = 2.X2 + 2 [U93#](X1,X2,X3) = 2.X2 + 2 [U94#](X1,X2) = X1 + 2.X2 [LENGTH](X) = 2.X Problem 1.4: SCC Processor: -> Pairs: U92#(tt,L,N) -> U93#(isNat(N),L,N) U93#(tt,L,N) -> U94#(isNatKind(N),L) U94#(tt,L) -> LENGTH(L) LENGTH(cons(N,L)) -> U91#(isNatList(L),L,N) -> Rules: U11(tt,V1) -> U12(isNatIListKind(V1),V1) U12(tt,V1) -> U13(isNatList(V1)) U13(tt) -> tt U21(tt,V1) -> U22(isNatKind(V1),V1) U22(tt,V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt,V) -> U32(isNatIListKind(V),V) U32(tt,V) -> U33(isNatList(V)) U33(tt) -> tt U41(tt,V1,V2) -> U42(isNatKind(V1),V1,V2) U42(tt,V1,V2) -> U43(isNatIListKind(V2),V1,V2) U43(tt,V1,V2) -> U44(isNatIListKind(V2),V1,V2) U44(tt,V1,V2) -> U45(isNat(V1),V2) U45(tt,V2) -> U46(isNatIList(V2)) U46(tt) -> tt U51(tt,V2) -> U52(isNatIListKind(V2)) U52(tt) -> tt U61(tt) -> tt U71(tt) -> tt U81(tt,V1,V2) -> U82(isNatKind(V1),V1,V2) U82(tt,V1,V2) -> U83(isNatIListKind(V2),V1,V2) U83(tt,V1,V2) -> U84(isNatIListKind(V2),V1,V2) U84(tt,V1,V2) -> U85(isNat(V1),V2) U85(tt,V2) -> U86(isNatList(V2)) U86(tt) -> tt U91(tt,L,N) -> U92(isNatIListKind(L),L,N) U92(tt,L,N) -> U93(isNat(N),L,N) U93(tt,L,N) -> U94(isNatKind(N),L) U94(tt,L) -> s(length(L)) 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(isNatKind(V1),V1,V2) isNatIList(V) -> U31(isNatIListKind(V),V) isNatIListKind(zeros) -> tt isNatIListKind(cons(V1,V2)) -> U51(isNatKind(V1),V2) isNatIListKind(nil) -> tt isNatKind(length(V1)) -> U61(isNatIListKind(V1)) isNatKind(0) -> tt isNatKind(s(V1)) -> U71(isNatKind(V1)) isNatList(cons(V1,V2)) -> U81(isNatKind(V1),V1,V2) isNatList(nil) -> tt length(cons(N,L)) -> U91(isNatList(L),L,N) length(nil) -> 0 zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Strongly Connected Components: There is no strongly connected component The problem is finite.