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