/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR M N V1 V2 X) (STRATEGY CONTEXTSENSITIVE (U11 1) (U12 1) (U13 1) (U21 1) (U22 1) (U31 1) (U32 1) (U33 1) (U41 1) (U51 1) (U61 1) (U71 1) (and 1) (isNat) (isNatKind) (plus 1 2) (x 1 2) (0) (s 1) (tt) ) (RULES U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ) Problem 1: Dependency Pairs Processor: -> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> U13#(isNat(V2)) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> U22#(isNat(V1)) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> U33#(isNat(V2)) U32#(tt,V2) -> ISNAT(V2) U41#(tt,N) -> N U51#(tt,M,N) -> PLUS(N,M) U51#(tt,M,N) -> M U51#(tt,M,N) -> N U71#(tt,M,N) -> PLUS(x(N,M),N) U71#(tt,M,N) -> X(N,M) U71#(tt,M,N) -> M U71#(tt,M,N) -> N AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNAT(plus(V1,V2)) -> ISNATKIND(V1) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNAT(x(V1,V2)) -> ISNATKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) PLUS(N,0) -> U41#(and(isNat(N),isNatKind(N)),N) PLUS(N,0) -> AND(isNat(N),isNatKind(N)) PLUS(N,0) -> ISNAT(N) PLUS(N,s(M)) -> U51#(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) PLUS(N,s(M)) -> AND(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))) PLUS(N,s(M)) -> AND(isNat(M),isNatKind(M)) PLUS(N,s(M)) -> ISNAT(M) X(N,0) -> U61#(and(isNat(N),isNatKind(N))) X(N,0) -> AND(isNat(N),isNatKind(N)) X(N,0) -> ISNAT(N) X(N,s(M)) -> U71#(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) X(N,s(M)) -> AND(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))) X(N,s(M)) -> AND(isNat(M),isNatKind(M)) X(N,s(M)) -> ISNAT(M) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding Rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) Problem 1: SCC Processor: -> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> U13#(isNat(V2)) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> U22#(isNat(V1)) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> U33#(isNat(V2)) U32#(tt,V2) -> ISNAT(V2) U41#(tt,N) -> N U51#(tt,M,N) -> PLUS(N,M) U51#(tt,M,N) -> M U51#(tt,M,N) -> N U71#(tt,M,N) -> PLUS(x(N,M),N) U71#(tt,M,N) -> X(N,M) U71#(tt,M,N) -> M U71#(tt,M,N) -> N AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNAT(plus(V1,V2)) -> ISNATKIND(V1) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNAT(x(V1,V2)) -> ISNATKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) PLUS(N,0) -> U41#(and(isNat(N),isNatKind(N)),N) PLUS(N,0) -> AND(isNat(N),isNatKind(N)) PLUS(N,0) -> ISNAT(N) PLUS(N,s(M)) -> U51#(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) PLUS(N,s(M)) -> AND(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))) PLUS(N,s(M)) -> AND(isNat(M),isNatKind(M)) PLUS(N,s(M)) -> ISNAT(M) X(N,0) -> U61#(and(isNat(N),isNatKind(N))) X(N,0) -> AND(isNat(N),isNatKind(N)) X(N,0) -> ISNAT(N) X(N,s(M)) -> U71#(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) X(N,s(M)) -> AND(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))) X(N,s(M)) -> AND(isNat(M),isNatKind(M)) X(N,s(M)) -> ISNAT(M) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNAT(plus(V1,V2)) -> ISNATKIND(V1) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNAT(x(V1,V2)) -> ISNATKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ->->-> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->->-> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) ->->Cycle: ->->-> Pairs: U51#(tt,M,N) -> PLUS(N,M) PLUS(N,s(M)) -> U51#(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->->-> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->->-> Unhiding rules: Empty ->->Cycle: ->->-> Pairs: U71#(tt,M,N) -> X(N,M) X(N,s(M)) -> U71#(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->->-> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->->-> Unhiding rules: Empty The problem is decomposed in 3 subproblems. Problem 1.1: Reduction Pairs Processor: -> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNAT(plus(V1,V2)) -> ISNATKIND(V1) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNAT(x(V1,V2)) -> ISNATKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) -> Usable rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2,X3) = 2.X1 + 1 [U12](X1,X2) = 1 [U13](X) = 1 [U21](X1,X2) = X1 + 2 [U22](X) = X [U31](X1,X2,X3) = 2.X1 + 2 [U32](X1,X2) = 2 [U33](X) = 2 [U41](X1,X2) = 2.X2 [U51](X1,X2,X3) = 2.X3 [U61](X) = 0 [U71](X1,X2,X3) = 0 [and](X1,X2) = 2.X1 + 2.X2 [isNat](X) = 2 [isNatKind](X) = 0 [plus](X1,X2) = 2.X1 [x](X1,X2) = 0 [0] = 0 [s](X) = 0 [tt] = 0 [U11#](X1,X2,X3) = 2.X1 + 2 [U12#](X1,X2) = 2 [U21#](X1,X2) = 2 [U31#](X1,X2,X3) = 2 [U32#](X1,X2) = 2 [AND](X1,X2) = 2.X1 + X2 [ISNAT](X) = 2 [ISNATKIND](X) = 0 Problem 1.1: SCC Processor: -> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(plus(V1,V2)) -> ISNATKIND(V1) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNAT(x(V1,V2)) -> ISNATKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(plus(V1,V2)) -> ISNATKIND(V1) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNAT(x(V1,V2)) -> ISNATKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ->->-> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->->-> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) Problem 1.1: Reduction Pairs Processor: -> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(plus(V1,V2)) -> ISNATKIND(V1) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNAT(x(V1,V2)) -> ISNATKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) -> Usable rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2,X3) = X1 + 1 [U12](X1,X2) = 1 [U13](X) = 1 [U21](X1,X2) = 2.X1 + 1 [U22](X) = 1 [U31](X1,X2,X3) = 2.X1 + X2 + 2 [U32](X1,X2) = X1 [U33](X) = 0 [U41](X1,X2) = X2 [U51](X1,X2,X3) = 0 [U61](X) = 2.X [U71](X1,X2,X3) = 2.X3 + 2 [and](X1,X2) = X1 + 2.X2 [isNat](X) = X + 1 [isNatKind](X) = 0 [plus](X1,X2) = X1 [x](X1,X2) = 2.X1 + 2 [0] = 0 [s](X) = 0 [tt] = 0 [U11#](X1,X2,X3) = 2.X1 + 1 [U12#](X1,X2) = 1 [U21#](X1,X2) = X1 + 1 [U31#](X1,X2,X3) = 1 [U32#](X1,X2) = 1 [AND](X1,X2) = X1 + 2.X2 [ISNAT](X) = 1 [ISNATKIND](X) = 0 Problem 1.1: SCC Processor: -> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNAT(x(V1,V2)) -> ISNATKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNAT(x(V1,V2)) -> ISNATKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ->->-> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->->-> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) Problem 1.1: Reduction Pairs Processor: -> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNAT(x(V1,V2)) -> ISNATKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) -> Usable rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2,X3) = 2.X1 + 2 [U12](X1,X2) = 1 [U13](X) = 1 [U21](X1,X2) = 2 [U22](X) = X [U31](X1,X2,X3) = 2.X1 + 2 [U32](X1,X2) = X1 [U33](X) = 0 [U41](X1,X2) = 2.X2 [U51](X1,X2,X3) = 2.X3 [U61](X) = 0 [U71](X1,X2,X3) = 0 [and](X1,X2) = 2.X1 + 2.X2 [isNat](X) = 2 [isNatKind](X) = 0 [plus](X1,X2) = 2.X1 [x](X1,X2) = 0 [0] = 0 [s](X) = 0 [tt] = 0 [U11#](X1,X2,X3) = 2.X1 + 2 [U12#](X1,X2) = 2 [U21#](X1,X2) = 2.X1 + 2 [U31#](X1,X2,X3) = 2.X1 + 2 [U32#](X1,X2) = 2 [AND](X1,X2) = 2.X1 + X2 [ISNAT](X) = 2 [ISNATKIND](X) = 0 Problem 1.1: SCC Processor: -> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> ISNATKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> ISNATKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ->->-> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->->-> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) Problem 1.1: Reduction Pairs Processor: -> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> ISNATKIND(V1) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) -> Usable rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2,X3) = X1 + 2.X2 + 2 [U12](X1,X2) = 2 [U13](X) = 2 [U21](X1,X2) = 2.X1 + 2.X2 + 2 [U22](X) = X [U31](X1,X2,X3) = X2 + 2.X3 [U32](X1,X2) = 0 [U33](X) = 0 [U41](X1,X2) = X2 [U51](X1,X2,X3) = X3 [U61](X) = 1 [U71](X1,X2,X3) = 2.X2 + 2.X3 + 2 [and](X1,X2) = 2.X1 + X2 [isNat](X) = 2.X + 2 [isNatKind](X) = 0 [plus](X1,X2) = X1 [x](X1,X2) = 2.X1 + 2.X2 + 2 [0] = 0 [s](X) = X [tt] = 0 [U11#](X1,X2,X3) = 2 [U12#](X1,X2) = 2 [U21#](X1,X2) = 2 [U31#](X1,X2,X3) = 2 [U32#](X1,X2) = 2 [AND](X1,X2) = 2.X1 + X2 [ISNAT](X) = 2 [ISNATKIND](X) = 0 Problem 1.1: SCC Processor: -> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ->->-> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->->-> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) Problem 1.1: Reduction Pairs Processor: -> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNAT(s(V1)) -> ISNATKIND(V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) -> Usable rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2,X3) = 2.X1 + 2.X2 + 2 [U12](X1,X2) = X1 [U13](X) = 0 [U21](X1,X2) = X1 + 2 [U22](X) = 2 [U31](X1,X2,X3) = X1 + X2 + 2.X3 + 2 [U32](X1,X2) = 2.X2 + 2 [U33](X) = 2 [U41](X1,X2) = X2 [U51](X1,X2,X3) = X3 [U61](X) = 2 [U71](X1,X2,X3) = 2.X2 + 2.X3 + 2 [and](X1,X2) = 2.X1 + 2.X2 [isNat](X) = 2.X + 2 [isNatKind](X) = 0 [plus](X1,X2) = X1 [x](X1,X2) = 2.X1 + 2.X2 + 2 [0] = 2 [s](X) = X [tt] = 0 [U11#](X1,X2,X3) = 2 [U12#](X1,X2) = 2 [U21#](X1,X2) = X1 + 2 [U31#](X1,X2,X3) = 2.X1 + 2 [U32#](X1,X2) = 2 [AND](X1,X2) = 2.X1 + 2.X2 [ISNAT](X) = 2 [ISNATKIND](X) = 0 Problem 1.1: SCC Processor: -> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) AND(tt,X) -> X ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) and(isNat(N),isNatKind(N)) -> ISNAT(N) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ->->-> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->->-> Unhiding rules: Empty ->->Cycle: ->->-> Pairs: AND(tt,X) -> X ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ->->-> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->->-> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) The problem is decomposed in 2 subproblems. Problem 1.1.1: Reduction Pairs Processor: -> Pairs: U11#(tt,V1,V2) -> U12#(isNat(V1),V2) U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: Empty -> Usable rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2,X3) = 2.X1.X2.X3 + X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2.X3 [U12](X1,X2) = X2 [U13](X) = 0 [U21](X1,X2) = 2.X1.X2 + 2.X2 + 2 [U22](X) = 2 [U31](X1,X2,X3) = X1.X2.X3 + 2.X2.X3 + 2.X1 + 2.X3 + 2 [U32](X1,X2) = 2.X2 + 2 [U33](X) = 0 [U41](X1,X2) = X2 [U51](X1,X2,X3) = 2.X1.X2.X3 + 2.X1.X2 + X2 + X3 + 2 [U61](X) = 2 [U71](X1,X2,X3) = 2.X2.X3 + X1 + 2.X2 + 2.X3 + 2 [and](X1,X2) = 2.X2 [isNat](X) = 2.X.X + 2 [isNatKind](X) = 0 [plus](X1,X2) = X1 + X2 + 1 [x](X1,X2) = 2.X1.X2 + X1 + 2.X2 + 1 [0] = 1 [s](X) = X + 1 [tt] = 0 [U11#](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U12#](X1,X2) = 2.X2 + 1 [U21#](X1,X2) = 2.X2 + 1 [U31#](X1,X2,X3) = 2.X1.X2.X3 + X2.X3 + 2.X1 + 2.X2 + 2.X3 + 2 [U32#](X1,X2) = 2.X2 + 2 [ISNAT](X) = 2.X + 1 Problem 1.1.1: SCC Processor: -> Pairs: U11#(tt,V1,V2) -> ISNAT(V1) U12#(tt,V2) -> ISNAT(V2) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: Empty ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U11#(tt,V1,V2) -> ISNAT(V1) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ->->-> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->->-> Unhiding rules: Empty Problem 1.1.1: Reduction Pairs Processor: -> Pairs: U11#(tt,V1,V2) -> ISNAT(V1) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> U32#(isNat(V1),V2) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: Empty -> Usable rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2,X3) = X1 [U12](X1,X2) = 2 [U13](X) = 2 [U21](X1,X2) = X1 [U22](X) = 2 [U31](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 [U32](X1,X2) = 2.X1 + 2.X2 [U33](X) = 2.X [U41](X1,X2) = X2 [U51](X1,X2,X3) = X3 [U61](X) = 2.X + 2 [U71](X1,X2,X3) = X1 + 2.X2 + 2.X3 [and](X1,X2) = X2 [isNat](X) = X + 2 [isNatKind](X) = 2 [plus](X1,X2) = X1 [x](X1,X2) = 2.X1 + 2.X2 + 2 [0] = 2 [s](X) = X [tt] = 2 [U11#](X1,X2,X3) = 2.X2 + 1 [U21#](X1,X2) = 2.X2 + 1 [U31#](X1,X2,X3) = 2.X2 + 2.X3 + 2 [U32#](X1,X2) = 2.X2 + 1 [ISNAT](X) = 2.X + 1 Problem 1.1.1: SCC Processor: -> Pairs: U11#(tt,V1,V2) -> ISNAT(V1) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> ISNAT(V1) U32#(tt,V2) -> ISNAT(V2) ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: Empty ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U11#(tt,V1,V2) -> ISNAT(V1) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> ISNAT(V1) ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) ->->-> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->->-> Unhiding rules: Empty Problem 1.1.1: SubNColl Processor: -> Pairs: U11#(tt,V1,V2) -> ISNAT(V1) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> ISNAT(V1) ISNAT(plus(V1,V2)) -> U11#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(x(V1,V2)) -> U31#(and(isNatKind(V1),isNatKind(V2)),V1,V2) ISNAT(s(V1)) -> U21#(isNatKind(V1),V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: Empty ->Projection: pi(U11#) = 2 pi(U21#) = 2 pi(U31#) = 2 pi(ISNAT) = 1 Problem 1.1.1: SCC Processor: -> Pairs: U11#(tt,V1,V2) -> ISNAT(V1) U21#(tt,V1) -> ISNAT(V1) U31#(tt,V1,V2) -> ISNAT(V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: Empty ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.1.2: Reduction Pairs Processor: -> Pairs: AND(tt,X) -> X ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: and(isNat(N),isNatKind(N)) -> AND(isNat(N),isNatKind(N)) isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) -> Usable rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2,X3) = X1 + 1 [U12](X1,X2) = 1 [U13](X) = 0 [U21](X1,X2) = X1 + 1 [U22](X) = 1 [U31](X1,X2,X3) = 2.X3 + 2 [U32](X1,X2) = 2.X2 + 2 [U33](X) = 2.X [U41](X1,X2) = X2 [U51](X1,X2,X3) = X3 [U61](X) = 2 [U71](X1,X2,X3) = 2.X2 + 2 [and](X1,X2) = X1 + X2 [isNat](X) = X + 1 [isNatKind](X) = 0 [plus](X1,X2) = X1 [x](X1,X2) = 2.X2 + 2 [0] = 1 [s](X) = X [tt] = 0 [AND](X1,X2) = X2 [ISNATKIND](X) = 0 Problem 1.1.2: SCC Processor: -> Pairs: AND(tt,X) -> X ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: AND(tt,X) -> X ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ->->-> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->->-> Unhiding rules: isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) Problem 1.1.2: Reduction Pairs Processor: -> Pairs: AND(tt,X) -> X ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) -> Usable rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [U11](X1,X2,X3) = 2.X2.X3 + X1 + 2.X2 + X3 + 2 [U12](X1,X2) = 1 [U13](X) = 0 [U21](X1,X2) = X1 [U22](X) = 0 [U31](X1,X2,X3) = 2.X1.X2 + 2.X2.X3 + 2.X2 + 2 [U32](X1,X2) = 2 [U33](X) = 2 [U41](X1,X2) = X2 + 2 [U51](X1,X2,X3) = X2 + X3 + 2 [U61](X) = 2 [U71](X1,X2,X3) = 2.X2.X3 + 2.X2 + 2.X3 + 2 [and](X1,X2) = X2 + 2 [isNat](X) = 2.X.X + 2.X [isNatKind](X) = 2.X.X [plus](X1,X2) = X1 + X2 + 1 [x](X1,X2) = 2.X1.X2 + X1 + 2.X2 + 1 [0] = 2 [s](X) = X + 1 [tt] = 0 [AND](X1,X2) = X2 + 1 [ISNATKIND](X) = 2.X.X Problem 1.1.2: SCC Processor: -> Pairs: ISNATKIND(plus(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> AND(isNatKind(V1),isNatKind(V2)) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: isNatKind(M) -> ISNATKIND(M) isNatKind(N) -> ISNATKIND(N) isNatKind(V2) -> ISNATKIND(V2) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) ->->-> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) ->->-> Unhiding rules: Empty Problem 1.1.2: SubNColl Processor: -> Pairs: ISNATKIND(plus(V1,V2)) -> ISNATKIND(V1) ISNATKIND(x(V1,V2)) -> ISNATKIND(V1) ISNATKIND(s(V1)) -> ISNATKIND(V1) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: Empty ->Projection: pi(ISNATKIND) = 1 Problem 1.1.2: Basic Processor: -> Pairs: Empty -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: Empty -> Result: Set P is empty The problem is finite. Problem 1.2: SubNColl Processor: -> Pairs: U51#(tt,M,N) -> PLUS(N,M) PLUS(N,s(M)) -> U51#(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: Empty ->Projection: pi(U51#) = 2 pi(PLUS) = 2 Problem 1.2: SCC Processor: -> Pairs: U51#(tt,M,N) -> PLUS(N,M) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: Empty ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: SubNColl Processor: -> Pairs: U71#(tt,M,N) -> X(N,M) X(N,s(M)) -> U71#(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: Empty ->Projection: pi(U71#) = 2 pi(X) = 2 Problem 1.3: SCC Processor: -> Pairs: U71#(tt,M,N) -> X(N,M) -> Rules: U11(tt,V1,V2) -> U12(isNat(V1),V2) U12(tt,V2) -> U13(isNat(V2)) U13(tt) -> tt U21(tt,V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt,V1,V2) -> U32(isNat(V1),V2) U32(tt,V2) -> U33(isNat(V2)) U33(tt) -> tt U41(tt,N) -> N U51(tt,M,N) -> s(plus(N,M)) U61(tt) -> 0 U71(tt,M,N) -> plus(x(N,M),N) and(tt,X) -> X isNat(plus(V1,V2)) -> U11(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(x(V1,V2)) -> U31(and(isNatKind(V1),isNatKind(V2)),V1,V2) isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1),V1) isNatKind(plus(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(x(V1,V2)) -> and(isNatKind(V1),isNatKind(V2)) isNatKind(0) -> tt isNatKind(s(V1)) -> isNatKind(V1) plus(N,0) -> U41(and(isNat(N),isNatKind(N)),N) plus(N,s(M)) -> U51(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) x(N,0) -> U61(and(isNat(N),isNatKind(N))) x(N,s(M)) -> U71(and(and(isNat(M),isNatKind(M)),and(isNat(N),isNatKind(N))),M,N) -> Unhiding rules: Empty ->Strongly Connected Components: There is no strongly connected component The problem is finite.