/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 X1 X2 X3)
(RULES
a__U11(tt,V2) -> a__U12(a__isNat(V2))
a__U11(X1,X2) -> U11(X1,X2)
a__U12(tt) -> tt
a__U12(X) -> U12(X)
a__U21(tt) -> tt
a__U21(X) -> U21(X)
a__U31(tt,V2) -> a__U32(a__isNat(V2))
a__U31(X1,X2) -> U31(X1,X2)
a__U32(tt) -> tt
a__U32(X) -> U32(X)
a__U41(tt,N) -> mark(N)
a__U41(X1,X2) -> U41(X1,X2)
a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
a__U51(X1,X2,X3) -> U51(X1,X2,X3)
a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
a__U52(X1,X2,X3) -> U52(X1,X2,X3)
a__U61(tt) -> 0
a__U61(X) -> U61(X)
a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
a__U71(X1,X2,X3) -> U71(X1,X2,X3)
a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
a__U72(X1,X2,X3) -> U72(X1,X2,X3)
a__isNat(0) -> tt
a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
a__isNat(s(V1)) -> a__U21(a__isNat(V1))
a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
a__isNat(X) -> isNat(X)
a__plus(N,0) -> a__U41(a__isNat(N),N)
a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
a__plus(X1,X2) -> plus(X1,X2)
a__x(N,0) -> a__U61(a__isNat(N))
a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
a__x(X1,X2) -> x(X1,X2)
mark(0) -> 0
mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
mark(U12(X)) -> a__U12(mark(X))
mark(U21(X)) -> a__U21(mark(X))
mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
mark(U32(X)) -> a__U32(mark(X))
mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
mark(U61(X)) -> a__U61(mark(X))
mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
mark(isNat(X)) -> a__isNat(X)
mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
mark(s(X)) -> s(mark(X))
mark(tt) -> tt
mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
)

Problem 1: 

Dependency Pairs Processor:
-> Pairs:
 A__U11(tt,V2) -> A__U12(a__isNat(V2))
 A__U11(tt,V2) -> A__ISNAT(V2)
 A__U31(tt,V2) -> A__U32(a__isNat(V2))
 A__U31(tt,V2) -> A__ISNAT(V2)
 A__U41(tt,N) -> MARK(N)
 A__U51(tt,M,N) -> A__U52(a__isNat(N),M,N)
 A__U51(tt,M,N) -> A__ISNAT(N)
 A__U52(tt,M,N) -> A__PLUS(mark(N),mark(M))
 A__U52(tt,M,N) -> MARK(M)
 A__U52(tt,M,N) -> MARK(N)
 A__U71(tt,M,N) -> A__U72(a__isNat(N),M,N)
 A__U71(tt,M,N) -> A__ISNAT(N)
 A__U72(tt,M,N) -> A__PLUS(a__x(mark(N),mark(M)),mark(N))
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__ISNAT(plus(V1,V2)) -> A__U11(a__isNat(V1),V2)
 A__ISNAT(plus(V1,V2)) -> A__ISNAT(V1)
 A__ISNAT(s(V1)) -> A__U21(a__isNat(V1))
 A__ISNAT(s(V1)) -> A__ISNAT(V1)
 A__ISNAT(x(V1,V2)) -> A__U31(a__isNat(V1),V2)
 A__ISNAT(x(V1,V2)) -> A__ISNAT(V1)
 A__PLUS(N,0) -> A__U41(a__isNat(N),N)
 A__PLUS(N,0) -> A__ISNAT(N)
 A__PLUS(N,s(M)) -> A__U51(a__isNat(M),M,N)
 A__PLUS(N,s(M)) -> A__ISNAT(M)
 A__X(N,0) -> A__U61(a__isNat(N))
 A__X(N,0) -> A__ISNAT(N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 A__X(N,s(M)) -> A__ISNAT(M)
 MARK(U11(X1,X2)) -> A__U11(mark(X1),X2)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> A__U12(mark(X))
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> A__U21(mark(X))
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> A__U31(mark(X1),X2)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> A__U32(mark(X))
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> A__U41(mark(X1),X2)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> A__U51(mark(X1),X2,X3)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> A__U52(mark(X1),X2,X3)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> A__U61(mark(X))
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(isNat(X)) -> A__ISNAT(X)
 MARK(plus(X1,X2)) -> A__PLUS(mark(X1),mark(X2))
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))

Problem 1: 

SCC Processor:
-> Pairs:
 A__U11(tt,V2) -> A__U12(a__isNat(V2))
 A__U11(tt,V2) -> A__ISNAT(V2)
 A__U31(tt,V2) -> A__U32(a__isNat(V2))
 A__U31(tt,V2) -> A__ISNAT(V2)
 A__U41(tt,N) -> MARK(N)
 A__U51(tt,M,N) -> A__U52(a__isNat(N),M,N)
 A__U51(tt,M,N) -> A__ISNAT(N)
 A__U52(tt,M,N) -> A__PLUS(mark(N),mark(M))
 A__U52(tt,M,N) -> MARK(M)
 A__U52(tt,M,N) -> MARK(N)
 A__U71(tt,M,N) -> A__U72(a__isNat(N),M,N)
 A__U71(tt,M,N) -> A__ISNAT(N)
 A__U72(tt,M,N) -> A__PLUS(a__x(mark(N),mark(M)),mark(N))
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__ISNAT(plus(V1,V2)) -> A__U11(a__isNat(V1),V2)
 A__ISNAT(plus(V1,V2)) -> A__ISNAT(V1)
 A__ISNAT(s(V1)) -> A__U21(a__isNat(V1))
 A__ISNAT(s(V1)) -> A__ISNAT(V1)
 A__ISNAT(x(V1,V2)) -> A__U31(a__isNat(V1),V2)
 A__ISNAT(x(V1,V2)) -> A__ISNAT(V1)
 A__PLUS(N,0) -> A__U41(a__isNat(N),N)
 A__PLUS(N,0) -> A__ISNAT(N)
 A__PLUS(N,s(M)) -> A__U51(a__isNat(M),M,N)
 A__PLUS(N,s(M)) -> A__ISNAT(M)
 A__X(N,0) -> A__U61(a__isNat(N))
 A__X(N,0) -> A__ISNAT(N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 A__X(N,s(M)) -> A__ISNAT(M)
 MARK(U11(X1,X2)) -> A__U11(mark(X1),X2)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> A__U12(mark(X))
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> A__U21(mark(X))
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> A__U31(mark(X1),X2)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> A__U32(mark(X))
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> A__U41(mark(X1),X2)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> A__U51(mark(X1),X2,X3)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> A__U52(mark(X1),X2,X3)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> A__U61(mark(X))
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(isNat(X)) -> A__ISNAT(X)
 MARK(plus(X1,X2)) -> A__PLUS(mark(X1),mark(X2))
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 A__U11(tt,V2) -> A__ISNAT(V2)
 A__U31(tt,V2) -> A__ISNAT(V2)
 A__ISNAT(plus(V1,V2)) -> A__U11(a__isNat(V1),V2)
 A__ISNAT(plus(V1,V2)) -> A__ISNAT(V1)
 A__ISNAT(s(V1)) -> A__ISNAT(V1)
 A__ISNAT(x(V1,V2)) -> A__U31(a__isNat(V1),V2)
 A__ISNAT(x(V1,V2)) -> A__ISNAT(V1)
->->-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->->Cycle:
->->-> Pairs:
 A__U41(tt,N) -> MARK(N)
 A__U51(tt,M,N) -> A__U52(a__isNat(N),M,N)
 A__U52(tt,M,N) -> A__PLUS(mark(N),mark(M))
 A__U52(tt,M,N) -> MARK(M)
 A__U52(tt,M,N) -> MARK(N)
 A__U71(tt,M,N) -> A__U72(a__isNat(N),M,N)
 A__U72(tt,M,N) -> A__PLUS(a__x(mark(N),mark(M)),mark(N))
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__PLUS(N,0) -> A__U41(a__isNat(N),N)
 A__PLUS(N,s(M)) -> A__U51(a__isNat(M),M,N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> A__U41(mark(X1),X2)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> A__U51(mark(X1),X2,X3)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> A__U52(mark(X1),X2,X3)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> A__PLUS(mark(X1),mark(X2))
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
->->-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))


The problem is decomposed in 2 subproblems.

Problem 1.1: 

Subterm Processor:
-> Pairs:
 A__U11(tt,V2) -> A__ISNAT(V2)
 A__U31(tt,V2) -> A__ISNAT(V2)
 A__ISNAT(plus(V1,V2)) -> A__U11(a__isNat(V1),V2)
 A__ISNAT(plus(V1,V2)) -> A__ISNAT(V1)
 A__ISNAT(s(V1)) -> A__ISNAT(V1)
 A__ISNAT(x(V1,V2)) -> A__U31(a__isNat(V1),V2)
 A__ISNAT(x(V1,V2)) -> A__ISNAT(V1)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Projection:
 pi(A__U11) = 2
 pi(A__U31) = 2
 pi(A__ISNAT) = 1

Problem 1.1: 

SCC Processor:
-> Pairs:
 A__U11(tt,V2) -> A__ISNAT(V2)
 A__U31(tt,V2) -> A__ISNAT(V2)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.2: 

Reduction Pair Processor:
-> Pairs:
 A__U41(tt,N) -> MARK(N)
 A__U51(tt,M,N) -> A__U52(a__isNat(N),M,N)
 A__U52(tt,M,N) -> A__PLUS(mark(N),mark(M))
 A__U52(tt,M,N) -> MARK(M)
 A__U52(tt,M,N) -> MARK(N)
 A__U71(tt,M,N) -> A__U72(a__isNat(N),M,N)
 A__U72(tt,M,N) -> A__PLUS(a__x(mark(N),mark(M)),mark(N))
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__PLUS(N,0) -> A__U41(a__isNat(N),N)
 A__PLUS(N,s(M)) -> A__U51(a__isNat(M),M,N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> A__U41(mark(X1),X2)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> A__U51(mark(X1),X2,X3)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> A__U52(mark(X1),X2,X3)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> A__PLUS(mark(X1),mark(X2))
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
-> Usable rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Interpretation type:
 Simple mixed
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[a__U11](X1,X2) = X1
[a__U12](X) = X
[a__U21](X) = X
[a__U31](X1,X2) = X1
[a__U32](X) = X
[a__U41](X1,X2) = X1 + X2 + 2
[a__U51](X1,X2,X3) = 2.X1 + 2.X2 + X3 + 2
[a__U52](X1,X2,X3) = 2.X1 + 2.X2 + X3 + 2
[a__U61](X) = 2.X
[a__U71](X1,X2,X3) = X1.X3 + X2.X3 + X1 + X2 + 2.X3 + 2
[a__U72](X1,X2,X3) = X1.X3 + X2.X3 + X1 + X2 + 2.X3 + 2
[a__isNat](X) = 2
[a__plus](X1,X2) = X1 + 2.X2 + 2
[a__x](X1,X2) = X1.X2 + 2.X1 + X2 + 2
[mark](X) = X
[0] = 2
[U11](X1,X2) = X1
[U12](X) = X
[U21](X) = X
[U31](X1,X2) = X1
[U32](X) = X
[U41](X1,X2) = X1 + X2 + 2
[U51](X1,X2,X3) = 2.X1 + 2.X2 + X3 + 2
[U52](X1,X2,X3) = 2.X1 + 2.X2 + X3 + 2
[U61](X) = 2.X
[U71](X1,X2,X3) = X1.X3 + X2.X3 + X1 + X2 + 2.X3 + 2
[U72](X1,X2,X3) = X1.X3 + X2.X3 + X1 + X2 + 2.X3 + 2
[isNat](X) = 2
[plus](X1,X2) = X1 + 2.X2 + 2
[s](X) = X + 2
[tt] = 2
[x](X1,X2) = X1.X2 + 2.X1 + X2 + 2
[A__U41](X1,X2) = X1 + 2.X2 + 2
[A__U51](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3
[A__U52](X1,X2,X3) = X1 + 2.X2 + 2.X3 + 1
[A__U71](X1,X2,X3) = 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2.X3 + 1
[A__U72](X1,X2,X3) = 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2.X3 + 1
[A__PLUS](X1,X2) = 2.X1 + 2.X2 + 1
[A__X](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2
[MARK](X) = 2.X

Problem 1.2: 

SCC Processor:
-> Pairs:
 A__U51(tt,M,N) -> A__U52(a__isNat(N),M,N)
 A__U52(tt,M,N) -> A__PLUS(mark(N),mark(M))
 A__U52(tt,M,N) -> MARK(M)
 A__U52(tt,M,N) -> MARK(N)
 A__U71(tt,M,N) -> A__U72(a__isNat(N),M,N)
 A__U72(tt,M,N) -> A__PLUS(a__x(mark(N),mark(M)),mark(N))
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__PLUS(N,0) -> A__U41(a__isNat(N),N)
 A__PLUS(N,s(M)) -> A__U51(a__isNat(M),M,N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> A__U41(mark(X1),X2)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> A__U51(mark(X1),X2,X3)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> A__U52(mark(X1),X2,X3)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> A__PLUS(mark(X1),mark(X2))
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 A__U51(tt,M,N) -> A__U52(a__isNat(N),M,N)
 A__U52(tt,M,N) -> A__PLUS(mark(N),mark(M))
 A__U52(tt,M,N) -> MARK(M)
 A__U52(tt,M,N) -> MARK(N)
 A__U71(tt,M,N) -> A__U72(a__isNat(N),M,N)
 A__U72(tt,M,N) -> A__PLUS(a__x(mark(N),mark(M)),mark(N))
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__PLUS(N,s(M)) -> A__U51(a__isNat(M),M,N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> A__U51(mark(X1),X2,X3)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> A__U52(mark(X1),X2,X3)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> A__PLUS(mark(X1),mark(X2))
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
->->-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))

Problem 1.2: 

Reduction Pair Processor:
-> Pairs:
 A__U51(tt,M,N) -> A__U52(a__isNat(N),M,N)
 A__U52(tt,M,N) -> A__PLUS(mark(N),mark(M))
 A__U52(tt,M,N) -> MARK(M)
 A__U52(tt,M,N) -> MARK(N)
 A__U71(tt,M,N) -> A__U72(a__isNat(N),M,N)
 A__U72(tt,M,N) -> A__PLUS(a__x(mark(N),mark(M)),mark(N))
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__PLUS(N,s(M)) -> A__U51(a__isNat(M),M,N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> A__U51(mark(X1),X2,X3)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> A__U52(mark(X1),X2,X3)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> A__PLUS(mark(X1),mark(X2))
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
-> Usable rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Interpretation type:
 Simple mixed
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[a__U11](X1,X2) = X1
[a__U12](X) = X
[a__U21](X) = X
[a__U31](X1,X2) = X1
[a__U32](X) = X
[a__U41](X1,X2) = 2.X1 + X2 + 2
[a__U51](X1,X2,X3) = X1.X2 + 2.X1 + X3 + 2
[a__U52](X1,X2,X3) = X1.X2 + 2.X1 + X3 + 2
[a__U61](X) = X + 2
[a__U71](X1,X2,X3) = X1.X3 + X2.X3 + X1 + X2 + 2.X3 + 2
[a__U72](X1,X2,X3) = X1.X3 + X2.X3 + 2.X1 + X2 + 2.X3
[a__isNat](X) = 2
[a__plus](X1,X2) = X1 + 2.X2 + 2
[a__x](X1,X2) = X1.X2 + 2.X1 + X2 + 2
[mark](X) = X
[0] = 2
[U11](X1,X2) = X1
[U12](X) = X
[U21](X) = X
[U31](X1,X2) = X1
[U32](X) = X
[U41](X1,X2) = 2.X1 + X2 + 2
[U51](X1,X2,X3) = X1.X2 + 2.X1 + X3 + 2
[U52](X1,X2,X3) = X1.X2 + 2.X1 + X3 + 2
[U61](X) = X + 2
[U71](X1,X2,X3) = X1.X3 + X2.X3 + X1 + X2 + 2.X3 + 2
[U72](X1,X2,X3) = X1.X3 + X2.X3 + 2.X1 + X2 + 2.X3
[isNat](X) = 2
[plus](X1,X2) = X1 + 2.X2 + 2
[s](X) = X + 2
[tt] = 2
[x](X1,X2) = X1.X2 + 2.X1 + X2 + 2
[A__U51](X1,X2,X3) = X1.X2 + 2.X1 + 2.X3 + 2
[A__U52](X1,X2,X3) = X1.X2 + 2.X3 + 2
[A__U71](X1,X2,X3) = 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2.X3 + 2
[A__U72](X1,X2,X3) = 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2.X3 + 2
[A__PLUS](X1,X2) = 2.X1 + 2.X2 + 2
[A__X](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2
[MARK](X) = 2.X + 2

Problem 1.2: 

SCC Processor:
-> Pairs:
 A__U52(tt,M,N) -> A__PLUS(mark(N),mark(M))
 A__U52(tt,M,N) -> MARK(M)
 A__U52(tt,M,N) -> MARK(N)
 A__U71(tt,M,N) -> A__U72(a__isNat(N),M,N)
 A__U72(tt,M,N) -> A__PLUS(a__x(mark(N),mark(M)),mark(N))
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__PLUS(N,s(M)) -> A__U51(a__isNat(M),M,N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> A__U51(mark(X1),X2,X3)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> A__U52(mark(X1),X2,X3)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> A__PLUS(mark(X1),mark(X2))
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 A__U52(tt,M,N) -> MARK(M)
 A__U52(tt,M,N) -> MARK(N)
 A__U71(tt,M,N) -> A__U72(a__isNat(N),M,N)
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> A__U52(mark(X1),X2,X3)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
->->-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))

Problem 1.2: 

Reduction Pair Processor:
-> Pairs:
 A__U52(tt,M,N) -> MARK(M)
 A__U52(tt,M,N) -> MARK(N)
 A__U71(tt,M,N) -> A__U72(a__isNat(N),M,N)
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> A__U52(mark(X1),X2,X3)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
-> Usable rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Interpretation type:
 Simple mixed
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[a__U11](X1,X2) = X1
[a__U12](X) = X
[a__U21](X) = X
[a__U31](X1,X2) = X1
[a__U32](X) = X
[a__U41](X1,X2) = 2.X1 + X2 + 2
[a__U51](X1,X2,X3) = X1.X2 + 2.X1 + X3 + 2
[a__U52](X1,X2,X3) = 2.X1 + 2.X2 + X3 + 2
[a__U61](X) = X.X + X
[a__U71](X1,X2,X3) = X1.X2 + X1.X3 + 2.X2.X3 + 2.X1 + 2.X3
[a__U72](X1,X2,X3) = X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2.X3
[a__isNat](X) = 2
[a__plus](X1,X2) = X1 + 2.X2 + 2
[a__x](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2
[mark](X) = X
[0] = 2
[U11](X1,X2) = X1
[U12](X) = X
[U21](X) = X
[U31](X1,X2) = X1
[U32](X) = X
[U41](X1,X2) = 2.X1 + X2 + 2
[U51](X1,X2,X3) = X1.X2 + 2.X1 + X3 + 2
[U52](X1,X2,X3) = 2.X1 + 2.X2 + X3 + 2
[U61](X) = X.X + X
[U71](X1,X2,X3) = X1.X2 + X1.X3 + 2.X2.X3 + 2.X1 + 2.X3
[U72](X1,X2,X3) = X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2.X3
[isNat](X) = 2
[plus](X1,X2) = X1 + 2.X2 + 2
[s](X) = X + 2
[tt] = 2
[x](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2
[A__U52](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3
[A__U71](X1,X2,X3) = X1.X2 + 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X3 + 1
[A__U72](X1,X2,X3) = 2.X1.X3 + 2.X2.X3 + X1 + 2.X2 + X3 + 2
[A__X](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2
[MARK](X) = 2.X + 2

Problem 1.2: 

SCC Processor:
-> Pairs:
 A__U52(tt,M,N) -> MARK(N)
 A__U71(tt,M,N) -> A__U72(a__isNat(N),M,N)
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> A__U52(mark(X1),X2,X3)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 A__U52(tt,M,N) -> MARK(N)
 A__U71(tt,M,N) -> A__U72(a__isNat(N),M,N)
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> A__U52(mark(X1),X2,X3)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
->->-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))

Problem 1.2: 

Reduction Pair Processor:
-> Pairs:
 A__U52(tt,M,N) -> MARK(N)
 A__U71(tt,M,N) -> A__U72(a__isNat(N),M,N)
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> A__U52(mark(X1),X2,X3)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
-> Usable rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Interpretation type:
 Simple mixed
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[a__U11](X1,X2) = X1
[a__U12](X) = X
[a__U21](X) = X
[a__U31](X1,X2) = X1
[a__U32](X) = X
[a__U41](X1,X2) = 2.X1 + X2
[a__U51](X1,X2,X3) = X1.X2 + 2.X1 + X3 + 2
[a__U52](X1,X2,X3) = 2.X1 + 2.X2 + X3 + 2
[a__U61](X) = 2.X + 2
[a__U71](X1,X2,X3) = X1.X2 + 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X3 + 2
[a__U72](X1,X2,X3) = X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2.X3 + 1
[a__isNat](X) = 2
[a__plus](X1,X2) = X1 + 2.X2 + 2
[a__x](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2
[mark](X) = X
[0] = 2
[U11](X1,X2) = X1
[U12](X) = X
[U21](X) = X
[U31](X1,X2) = X1
[U32](X) = X
[U41](X1,X2) = 2.X1 + X2
[U51](X1,X2,X3) = X1.X2 + 2.X1 + X3 + 2
[U52](X1,X2,X3) = 2.X1 + 2.X2 + X3 + 2
[U61](X) = 2.X + 2
[U71](X1,X2,X3) = X1.X2 + 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X3 + 2
[U72](X1,X2,X3) = X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2.X3 + 1
[isNat](X) = 2
[plus](X1,X2) = X1 + 2.X2 + 2
[s](X) = X + 2
[tt] = 2
[x](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2
[A__U52](X1,X2,X3) = 2.X1 + 2.X3 + 2
[A__U71](X1,X2,X3) = X1.X2 + 2.X2.X3 + 2.X1 + 2.X3 + 2
[A__U72](X1,X2,X3) = X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2
[A__X](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2
[MARK](X) = 2.X + 2

Problem 1.2: 

SCC Processor:
-> Pairs:
 A__U71(tt,M,N) -> A__U72(a__isNat(N),M,N)
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> A__U52(mark(X1),X2,X3)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 A__U71(tt,M,N) -> A__U72(a__isNat(N),M,N)
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
->->-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))

Problem 1.2: 

Reduction Pair Processor:
-> Pairs:
 A__U71(tt,M,N) -> A__U72(a__isNat(N),M,N)
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
-> Usable rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Interpretation type:
 Simple mixed
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[a__U11](X1,X2) = X1
[a__U12](X) = X
[a__U21](X) = X
[a__U31](X1,X2) = X1
[a__U32](X) = X
[a__U41](X1,X2) = X1 + X2 + 2
[a__U51](X1,X2,X3) = X1.X2 + 2.X1 + X3 + 2
[a__U52](X1,X2,X3) = 2.X1 + 2.X2 + X3 + 2
[a__U61](X) = 2.X + 2
[a__U71](X1,X2,X3) = 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2.X3 + 2
[a__U72](X1,X2,X3) = X1.X2 + 2.X1.X3 + 2.X2.X3 + 2.X1 + X3 + 2
[a__isNat](X) = 2
[a__plus](X1,X2) = X1 + 2.X2 + 2
[a__x](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2
[mark](X) = X
[0] = 2
[U11](X1,X2) = X1
[U12](X) = X
[U21](X) = X
[U31](X1,X2) = X1
[U32](X) = X
[U41](X1,X2) = X1 + X2 + 2
[U51](X1,X2,X3) = X1.X2 + 2.X1 + X3 + 2
[U52](X1,X2,X3) = 2.X1 + 2.X2 + X3 + 2
[U61](X) = 2.X + 2
[U71](X1,X2,X3) = 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2.X3 + 2
[U72](X1,X2,X3) = X1.X2 + 2.X1.X3 + 2.X2.X3 + 2.X1 + X3 + 2
[isNat](X) = 2
[plus](X1,X2) = X1 + 2.X2 + 2
[s](X) = X + 2
[tt] = 2
[x](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2
[A__U71](X1,X2,X3) = 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 1
[A__U72](X1,X2,X3) = X1.X2 + 2.X1.X3 + 2.X2.X3 + X1 + 2
[A__X](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2
[MARK](X) = 2.X

Problem 1.2: 

SCC Processor:
-> Pairs:
 A__U72(tt,M,N) -> A__X(mark(N),mark(M))
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 A__X(N,s(M)) -> A__U71(a__isNat(M),M,N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> A__U71(mark(X1),X2,X3)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> A__X(mark(X1),mark(X2))
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
->->-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))

Problem 1.2: 

Reduction Pair Processor:
-> Pairs:
 A__U72(tt,M,N) -> MARK(M)
 A__U72(tt,M,N) -> MARK(N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
-> Usable rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Interpretation type:
 Simple mixed
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[a__U11](X1,X2) = 2.X1
[a__U12](X) = 2.X.X + 2.X
[a__U21](X) = 2.X
[a__U31](X1,X2) = X1.X2 + 2.X1
[a__U32](X) = 2.X.X + X
[a__U41](X1,X2) = 2.X1.X2 + 2.X1 + X2 + 1
[a__U51](X1,X2,X3) = X1.X2.X3 + 2.X1.X2 + X1.X3 + 2.X1 + X2 + X3 + 2
[a__U52](X1,X2,X3) = X1.X2.X3 + X1.X2 + 2.X1.X3 + 2.X1 + X2 + X3 + 2
[a__U61](X) = 2.X.X + 2.X + 2
[a__U71](X1,X2,X3) = 2.X1.X2 + 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2.X3 + 2
[a__U72](X1,X2,X3) = X1.X2.X3 + 2.X1.X2 + 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2.X3 + 2
[a__isNat](X) = 0
[a__plus](X1,X2) = X1 + X2
[a__x](X1,X2) = 2.X1.X2 + X1 + 2.X2 + 2
[mark](X) = X
[0] = 2
[U11](X1,X2) = 2.X1
[U12](X) = 2.X.X + 2.X
[U21](X) = 2.X
[U31](X1,X2) = X1.X2 + 2.X1
[U32](X) = 2.X.X + X
[U41](X1,X2) = 2.X1.X2 + 2.X1 + X2 + 1
[U51](X1,X2,X3) = X1.X2.X3 + 2.X1.X2 + X1.X3 + 2.X1 + X2 + X3 + 2
[U52](X1,X2,X3) = X1.X2.X3 + X1.X2 + 2.X1.X3 + 2.X1 + X2 + X3 + 2
[U61](X) = 2.X.X + 2.X + 2
[U71](X1,X2,X3) = 2.X1.X2 + 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2.X3 + 2
[U72](X1,X2,X3) = X1.X2.X3 + 2.X1.X2 + 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2.X3 + 2
[isNat](X) = 0
[plus](X1,X2) = X1 + X2
[s](X) = X + 2
[tt] = 0
[x](X1,X2) = 2.X1.X2 + X1 + 2.X2 + 2
[A__U72](X1,X2,X3) = X1.X2.X3 + 2.X1.X2 + 2.X1 + 2.X2 + 2.X3 + 2
[MARK](X) = X + 1

Problem 1.2: 

SCC Processor:
-> Pairs:
 A__U72(tt,M,N) -> MARK(N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 A__U72(tt,M,N) -> MARK(N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
->->-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))

Problem 1.2: 

Subterm Processor:
-> Pairs:
 A__U72(tt,M,N) -> MARK(N)
 MARK(U11(X1,X2)) -> MARK(X1)
 MARK(U12(X)) -> MARK(X)
 MARK(U21(X)) -> MARK(X)
 MARK(U31(X1,X2)) -> MARK(X1)
 MARK(U32(X)) -> MARK(X)
 MARK(U41(X1,X2)) -> MARK(X1)
 MARK(U51(X1,X2,X3)) -> MARK(X1)
 MARK(U52(X1,X2,X3)) -> MARK(X1)
 MARK(U61(X)) -> MARK(X)
 MARK(U71(X1,X2,X3)) -> MARK(X1)
 MARK(U72(X1,X2,X3)) -> A__U72(mark(X1),X2,X3)
 MARK(U72(X1,X2,X3)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X1)
 MARK(plus(X1,X2)) -> MARK(X2)
 MARK(s(X)) -> MARK(X)
 MARK(x(X1,X2)) -> MARK(X1)
 MARK(x(X1,X2)) -> MARK(X2)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Projection:
 pi(A__U72) = 3
 pi(MARK) = 1

Problem 1.2: 

SCC Processor:
-> Pairs:
 A__U72(tt,M,N) -> MARK(N)
-> Rules:
 a__U11(tt,V2) -> a__U12(a__isNat(V2))
 a__U11(X1,X2) -> U11(X1,X2)
 a__U12(tt) -> tt
 a__U12(X) -> U12(X)
 a__U21(tt) -> tt
 a__U21(X) -> U21(X)
 a__U31(tt,V2) -> a__U32(a__isNat(V2))
 a__U31(X1,X2) -> U31(X1,X2)
 a__U32(tt) -> tt
 a__U32(X) -> U32(X)
 a__U41(tt,N) -> mark(N)
 a__U41(X1,X2) -> U41(X1,X2)
 a__U51(tt,M,N) -> a__U52(a__isNat(N),M,N)
 a__U51(X1,X2,X3) -> U51(X1,X2,X3)
 a__U52(tt,M,N) -> s(a__plus(mark(N),mark(M)))
 a__U52(X1,X2,X3) -> U52(X1,X2,X3)
 a__U61(tt) -> 0
 a__U61(X) -> U61(X)
 a__U71(tt,M,N) -> a__U72(a__isNat(N),M,N)
 a__U71(X1,X2,X3) -> U71(X1,X2,X3)
 a__U72(tt,M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N))
 a__U72(X1,X2,X3) -> U72(X1,X2,X3)
 a__isNat(0) -> tt
 a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2)
 a__isNat(s(V1)) -> a__U21(a__isNat(V1))
 a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2)
 a__isNat(X) -> isNat(X)
 a__plus(N,0) -> a__U41(a__isNat(N),N)
 a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N)
 a__plus(X1,X2) -> plus(X1,X2)
 a__x(N,0) -> a__U61(a__isNat(N))
 a__x(N,s(M)) -> a__U71(a__isNat(M),M,N)
 a__x(X1,X2) -> x(X1,X2)
 mark(0) -> 0
 mark(U11(X1,X2)) -> a__U11(mark(X1),X2)
 mark(U12(X)) -> a__U12(mark(X))
 mark(U21(X)) -> a__U21(mark(X))
 mark(U31(X1,X2)) -> a__U31(mark(X1),X2)
 mark(U32(X)) -> a__U32(mark(X))
 mark(U41(X1,X2)) -> a__U41(mark(X1),X2)
 mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3)
 mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3)
 mark(U61(X)) -> a__U61(mark(X))
 mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3)
 mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3)
 mark(isNat(X)) -> a__isNat(X)
 mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2))
 mark(s(X)) -> s(mark(X))
 mark(tt) -> tt
 mark(x(X1,X2)) -> a__x(mark(X1),mark(X2))
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.