/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR IL L M N V V1 V2) (STRATEGY CONTEXTSENSITIVE (U11 1) (U21 1) (U31 1) (U41 1) (U42 1) (U51 1) (U52 1) (U61 1) (U62 1) (U71 1) (U72 1) (U81 1) (U91 1) (U92 1) (U93 1) (isNat) (isNatIList) (isNatList) (length 1) (take 1 2) (zeros) (0) (cons 1) (nil) (s 1) (tt) ) (RULES U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) ) Problem 1: Dependency Pairs Processor: -> Pairs: U41#(tt,V2) -> U42#(isNatIList(V2)) U41#(tt,V2) -> ISNATILIST(V2) U51#(tt,V2) -> U52#(isNatList(V2)) U51#(tt,V2) -> ISNATLIST(V2) U61#(tt,V2) -> U62#(isNatIList(V2)) U61#(tt,V2) -> ISNATILIST(V2) U71#(tt,L,N) -> U72#(isNat(N),L) U71#(tt,L,N) -> ISNAT(N) U72#(tt,L) -> LENGTH(L) U72#(tt,L) -> L U91#(tt,IL,M,N) -> U92#(isNat(M),IL,M,N) U91#(tt,IL,M,N) -> ISNAT(M) U92#(tt,IL,M,N) -> U93#(isNat(N),IL,M,N) U92#(tt,IL,M,N) -> ISNAT(N) U93#(tt,IL,M,N) -> N ISNAT(length(V1)) -> U11#(isNatList(V1)) ISNAT(length(V1)) -> ISNATLIST(V1) ISNAT(s(V1)) -> U21#(isNat(V1)) ISNAT(s(V1)) -> ISNAT(V1) ISNATILIST(cons(V1,V2)) -> U41#(isNat(V1),V2) ISNATILIST(cons(V1,V2)) -> ISNAT(V1) ISNATILIST(V) -> U31#(isNatList(V)) ISNATILIST(V) -> ISNATLIST(V) ISNATLIST(take(V1,V2)) -> U61#(isNat(V1),V2) ISNATLIST(take(V1,V2)) -> ISNAT(V1) ISNATLIST(cons(V1,V2)) -> U51#(isNat(V1),V2) ISNATLIST(cons(V1,V2)) -> ISNAT(V1) LENGTH(cons(N,L)) -> U71#(isNatList(L),L,N) LENGTH(cons(N,L)) -> ISNATLIST(L) TAKE(0,IL) -> U81#(isNatIList(IL)) TAKE(0,IL) -> ISNATILIST(IL) TAKE(s(M),cons(N,IL)) -> U91#(isNatIList(IL),IL,M,N) TAKE(s(M),cons(N,IL)) -> ISNATILIST(IL) -> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) -> Unhiding Rules: take(M,IL) -> TAKE(M,IL) take(M,x7) -> x7 take(x7,IL) -> x7 zeros -> ZEROS Problem 1: SCC Processor: -> Pairs: U41#(tt,V2) -> U42#(isNatIList(V2)) U41#(tt,V2) -> ISNATILIST(V2) U51#(tt,V2) -> U52#(isNatList(V2)) U51#(tt,V2) -> ISNATLIST(V2) U61#(tt,V2) -> U62#(isNatIList(V2)) U61#(tt,V2) -> ISNATILIST(V2) U71#(tt,L,N) -> U72#(isNat(N),L) U71#(tt,L,N) -> ISNAT(N) U72#(tt,L) -> LENGTH(L) U72#(tt,L) -> L U91#(tt,IL,M,N) -> U92#(isNat(M),IL,M,N) U91#(tt,IL,M,N) -> ISNAT(M) U92#(tt,IL,M,N) -> U93#(isNat(N),IL,M,N) U92#(tt,IL,M,N) -> ISNAT(N) U93#(tt,IL,M,N) -> N ISNAT(length(V1)) -> U11#(isNatList(V1)) ISNAT(length(V1)) -> ISNATLIST(V1) ISNAT(s(V1)) -> U21#(isNat(V1)) ISNAT(s(V1)) -> ISNAT(V1) ISNATILIST(cons(V1,V2)) -> U41#(isNat(V1),V2) ISNATILIST(cons(V1,V2)) -> ISNAT(V1) ISNATILIST(V) -> U31#(isNatList(V)) ISNATILIST(V) -> ISNATLIST(V) ISNATLIST(take(V1,V2)) -> U61#(isNat(V1),V2) ISNATLIST(take(V1,V2)) -> ISNAT(V1) ISNATLIST(cons(V1,V2)) -> U51#(isNat(V1),V2) ISNATLIST(cons(V1,V2)) -> ISNAT(V1) LENGTH(cons(N,L)) -> U71#(isNatList(L),L,N) LENGTH(cons(N,L)) -> ISNATLIST(L) TAKE(0,IL) -> U81#(isNatIList(IL)) TAKE(0,IL) -> ISNATILIST(IL) TAKE(s(M),cons(N,IL)) -> U91#(isNatIList(IL),IL,M,N) TAKE(s(M),cons(N,IL)) -> ISNATILIST(IL) -> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) -> Unhiding rules: take(M,IL) -> TAKE(M,IL) take(M,x7) -> x7 take(x7,IL) -> x7 zeros -> ZEROS ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U41#(tt,V2) -> ISNATILIST(V2) U51#(tt,V2) -> ISNATLIST(V2) U61#(tt,V2) -> ISNATILIST(V2) ISNAT(length(V1)) -> ISNATLIST(V1) ISNAT(s(V1)) -> ISNAT(V1) ISNATILIST(cons(V1,V2)) -> U41#(isNat(V1),V2) ISNATILIST(cons(V1,V2)) -> ISNAT(V1) ISNATILIST(V) -> ISNATLIST(V) ISNATLIST(take(V1,V2)) -> U61#(isNat(V1),V2) ISNATLIST(take(V1,V2)) -> ISNAT(V1) ISNATLIST(cons(V1,V2)) -> U51#(isNat(V1),V2) ISNATLIST(cons(V1,V2)) -> ISNAT(V1) ->->-> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) ->->-> Unhiding rules: Empty ->->Cycle: ->->-> Pairs: U91#(tt,IL,M,N) -> U92#(isNat(M),IL,M,N) U92#(tt,IL,M,N) -> U93#(isNat(N),IL,M,N) U93#(tt,IL,M,N) -> N TAKE(s(M),cons(N,IL)) -> U91#(isNatIList(IL),IL,M,N) ->->-> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) ->->-> Unhiding rules: take(M,IL) -> TAKE(M,IL) take(M,x7) -> x7 take(x7,IL) -> x7 ->->Cycle: ->->-> Pairs: U71#(tt,L,N) -> U72#(isNat(N),L) U72#(tt,L) -> LENGTH(L) LENGTH(cons(N,L)) -> U71#(isNatList(L),L,N) ->->-> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) ->->-> Unhiding rules: Empty The problem is decomposed in 3 subproblems. Problem 1.1: Reduction Pairs Processor: -> Pairs: U41#(tt,V2) -> ISNATILIST(V2) U51#(tt,V2) -> ISNATLIST(V2) U61#(tt,V2) -> ISNATILIST(V2) ISNAT(length(V1)) -> ISNATLIST(V1) ISNAT(s(V1)) -> ISNAT(V1) ISNATILIST(cons(V1,V2)) -> U41#(isNat(V1),V2) ISNATILIST(cons(V1,V2)) -> ISNAT(V1) ISNATILIST(V) -> ISNATLIST(V) ISNATLIST(take(V1,V2)) -> U61#(isNat(V1),V2) ISNATLIST(take(V1,V2)) -> ISNAT(V1) ISNATLIST(cons(V1,V2)) -> U51#(isNat(V1),V2) ISNATLIST(cons(V1,V2)) -> ISNAT(V1) -> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) -> Unhiding rules: Empty -> Usable rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X) = 2 [U21](X) = X [U31](X) = 2 [U41](X1,X2) = 2.X1 + 2.X2 + 1 [U42](X) = X + 1 [U51](X1,X2) = 2.X1 + X2 + 2 [U52](X) = 2 [U61](X1,X2) = 2.X1 + 2.X2 + 2 [U62](X) = 2 [isNat](X) = 2 [isNatIList](X) = 2.X + 2 [isNatList](X) = 2.X + 2 [length](X) = 2.X + 2 [take](X1,X2) = 2.X1 + 2.X2 + 2 [zeros] = 2 [0] = 2 [cons](X1,X2) = 2.X1 + 2.X2 + 2 [nil] = 1 [s](X) = X + 2 [tt] = 2 [U41#](X1,X2) = 2.X1 + 2.X2 [U51#](X1,X2) = 2.X1 + 2.X2 + 2 [U61#](X1,X2) = 2.X1 + 2.X2 [ISNAT](X) = X + 2 [ISNATILIST](X) = 2.X + 2 [ISNATLIST](X) = 2.X + 2 Problem 1.1: SCC Processor: -> Pairs: U51#(tt,V2) -> ISNATLIST(V2) U61#(tt,V2) -> ISNATILIST(V2) ISNAT(length(V1)) -> ISNATLIST(V1) ISNAT(s(V1)) -> ISNAT(V1) ISNATILIST(cons(V1,V2)) -> U41#(isNat(V1),V2) ISNATILIST(cons(V1,V2)) -> ISNAT(V1) ISNATILIST(V) -> ISNATLIST(V) ISNATLIST(take(V1,V2)) -> U61#(isNat(V1),V2) ISNATLIST(take(V1,V2)) -> ISNAT(V1) ISNATLIST(cons(V1,V2)) -> U51#(isNat(V1),V2) ISNATLIST(cons(V1,V2)) -> ISNAT(V1) -> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U51#(tt,V2) -> ISNATLIST(V2) U61#(tt,V2) -> ISNATILIST(V2) ISNAT(length(V1)) -> ISNATLIST(V1) ISNAT(s(V1)) -> ISNAT(V1) ISNATILIST(cons(V1,V2)) -> ISNAT(V1) ISNATILIST(V) -> ISNATLIST(V) ISNATLIST(take(V1,V2)) -> U61#(isNat(V1),V2) ISNATLIST(take(V1,V2)) -> ISNAT(V1) ISNATLIST(cons(V1,V2)) -> U51#(isNat(V1),V2) ISNATLIST(cons(V1,V2)) -> ISNAT(V1) ->->-> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) ->->-> Unhiding rules: Empty Problem 1.1: Reduction Pairs Processor: -> Pairs: U51#(tt,V2) -> ISNATLIST(V2) U61#(tt,V2) -> ISNATILIST(V2) ISNAT(length(V1)) -> ISNATLIST(V1) ISNAT(s(V1)) -> ISNAT(V1) ISNATILIST(cons(V1,V2)) -> ISNAT(V1) ISNATILIST(V) -> ISNATLIST(V) ISNATLIST(take(V1,V2)) -> U61#(isNat(V1),V2) ISNATLIST(take(V1,V2)) -> ISNAT(V1) ISNATLIST(cons(V1,V2)) -> U51#(isNat(V1),V2) ISNATLIST(cons(V1,V2)) -> ISNAT(V1) -> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) -> Unhiding rules: Empty -> Usable rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X) = X + 1 [U21](X) = 2.X + 2 [U31](X) = X [U41](X1,X2) = 2.X2 + 2 [U42](X) = 2.X + 2 [U51](X1,X2) = X1 + 2.X2 [U52](X) = 2.X + 2 [U61](X1,X2) = 2.X2 [U62](X) = 2.X [isNat](X) = 2.X + 2 [isNatIList](X) = X [isNatList](X) = X [length](X) = X + 2 [take](X1,X2) = X1 + 2.X2 [zeros] = 2 [0] = 2 [cons](X1,X2) = 2.X1 + 2.X2 + 2 [nil] = 2 [s](X) = 2.X + 2 [tt] = 2 [U51#](X1,X2) = 2.X1 + 2.X2 [U61#](X1,X2) = 2.X2 + 1 [ISNAT](X) = 2.X [ISNATILIST](X) = 2.X + 1 [ISNATLIST](X) = 2.X + 1 Problem 1.1: SCC Processor: -> Pairs: U61#(tt,V2) -> ISNATILIST(V2) ISNAT(length(V1)) -> ISNATLIST(V1) ISNAT(s(V1)) -> ISNAT(V1) ISNATILIST(cons(V1,V2)) -> ISNAT(V1) ISNATILIST(V) -> ISNATLIST(V) ISNATLIST(take(V1,V2)) -> U61#(isNat(V1),V2) ISNATLIST(take(V1,V2)) -> ISNAT(V1) ISNATLIST(cons(V1,V2)) -> U51#(isNat(V1),V2) ISNATLIST(cons(V1,V2)) -> ISNAT(V1) -> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U61#(tt,V2) -> ISNATILIST(V2) ISNAT(length(V1)) -> ISNATLIST(V1) ISNAT(s(V1)) -> ISNAT(V1) ISNATILIST(cons(V1,V2)) -> ISNAT(V1) ISNATILIST(V) -> ISNATLIST(V) ISNATLIST(take(V1,V2)) -> U61#(isNat(V1),V2) ISNATLIST(take(V1,V2)) -> ISNAT(V1) ISNATLIST(cons(V1,V2)) -> ISNAT(V1) ->->-> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) ->->-> Unhiding rules: Empty Problem 1.1: SubNColl Processor: -> Pairs: U61#(tt,V2) -> ISNATILIST(V2) ISNAT(length(V1)) -> ISNATLIST(V1) ISNAT(s(V1)) -> ISNAT(V1) ISNATILIST(cons(V1,V2)) -> ISNAT(V1) ISNATILIST(V) -> ISNATLIST(V) ISNATLIST(take(V1,V2)) -> U61#(isNat(V1),V2) ISNATLIST(take(V1,V2)) -> ISNAT(V1) ISNATLIST(cons(V1,V2)) -> ISNAT(V1) -> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Projection: pi(U61#) = 2 pi(ISNAT) = 1 pi(ISNATILIST) = 1 pi(ISNATLIST) = 1 Problem 1.1: SCC Processor: -> Pairs: U61#(tt,V2) -> ISNATILIST(V2) ISNATILIST(V) -> ISNATLIST(V) -> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: SubNColl Processor: -> Pairs: U91#(tt,IL,M,N) -> U92#(isNat(M),IL,M,N) U92#(tt,IL,M,N) -> U93#(isNat(N),IL,M,N) U93#(tt,IL,M,N) -> N TAKE(s(M),cons(N,IL)) -> U91#(isNatIList(IL),IL,M,N) -> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) -> Unhiding rules: take(M,IL) -> TAKE(M,IL) take(M,x7) -> x7 take(x7,IL) -> x7 ->Projection: pi(U91#) = 4 pi(U92#) = 4 pi(U93#) = 4 pi(TAKE) = 2 Problem 1.2: SCC Processor: -> Pairs: U91#(tt,IL,M,N) -> U92#(isNat(M),IL,M,N) U92#(tt,IL,M,N) -> U93#(isNat(N),IL,M,N) U93#(tt,IL,M,N) -> N -> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) 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: U71#(tt,L,N) -> U72#(isNat(N),L) U72#(tt,L) -> LENGTH(L) LENGTH(cons(N,L)) -> U71#(isNatList(L),L,N) -> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) -> Unhiding rules: Empty -> Usable rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X) = X [U21](X) = X [U31](X) = 2 [U41](X1,X2) = 2 [U42](X) = X [U51](X1,X2) = 2.X2 + 1 [U52](X) = X [U61](X1,X2) = X1 + 2.X2 [U62](X) = 2 [U71](X1,X2,X3) = 2.X2 [U72](X1,X2) = 2.X2 [U81](X) = 2 [U91](X1,X2,X3,X4) = 2.X2 + 2.X3 [U92](X1,X2,X3,X4) = 2.X2 + 2.X3 [U93](X1,X2,X3,X4) = 2.X2 + 2.X3 [isNat](X) = 2.X + 1 [isNatIList](X) = 2 [isNatList](X) = 2.X + 1 [length](X) = X [take](X1,X2) = X1 + X2 [zeros] = 0 [0] = 2 [cons](X1,X2) = 2.X2 [nil] = 2 [s](X) = 2.X [tt] = 2 [U71#](X1,X2,X3) = X1 + 2.X2 + 1 [U72#](X1,X2) = 2.X2 + 2 [LENGTH](X) = 2.X + 2 Problem 1.3: SCC Processor: -> Pairs: U72#(tt,L) -> LENGTH(L) LENGTH(cons(N,L)) -> U71#(isNatList(L),L,N) -> Rules: U11(tt) -> tt U21(tt) -> tt U31(tt) -> tt U41(tt,V2) -> U42(isNatIList(V2)) U42(tt) -> tt U51(tt,V2) -> U52(isNatList(V2)) U52(tt) -> tt U61(tt,V2) -> U62(isNatIList(V2)) U62(tt) -> tt U71(tt,L,N) -> U72(isNat(N),L) U72(tt,L) -> s(length(L)) U81(tt) -> nil U91(tt,IL,M,N) -> U92(isNat(M),IL,M,N) U92(tt,IL,M,N) -> U93(isNat(N),IL,M,N) U93(tt,IL,M,N) -> cons(N,take(M,IL)) isNat(length(V1)) -> U11(isNatList(V1)) isNat(0) -> tt isNat(s(V1)) -> U21(isNat(V1)) isNatIList(zeros) -> tt isNatIList(cons(V1,V2)) -> U41(isNat(V1),V2) isNatIList(V) -> U31(isNatList(V)) isNatList(take(V1,V2)) -> U61(isNat(V1),V2) isNatList(cons(V1,V2)) -> U51(isNat(V1),V2) isNatList(nil) -> tt length(cons(N,L)) -> U71(isNatList(L),L,N) length(nil) -> 0 take(0,IL) -> U81(isNatIList(IL)) take(s(M),cons(N,IL)) -> U91(isNatIList(IL),IL,M,N) zeros -> cons(0,zeros) -> Unhiding rules: Empty ->Strongly Connected Components: There is no strongly connected component The problem is finite.