YES Input TRS: 1: a__U11(tt(),V2) -> a__U12(a__isNat(V2)) 2: a__U12(tt()) -> tt() 3: a__U21(tt()) -> tt() 4: a__U31(tt(),V2) -> a__U32(a__isNat(V2)) 5: a__U32(tt()) -> tt() 6: a__U41(tt(),N) -> mark(N) 7: a__U51(tt(),M,N) -> a__U52(a__isNat(N),M,N) 8: a__U52(tt(),M,N) -> s(a__plus(mark(N),mark(M))) 9: a__U61(tt()) -> 0() 10: a__U71(tt(),M,N) -> a__U72(a__isNat(N),M,N) 11: a__U72(tt(),M,N) -> a__plus(a__x(mark(N),mark(M)),mark(N)) 12: a__isNat(0()) -> tt() 13: a__isNat(plus(V1,V2)) -> a__U11(a__isNat(V1),V2) 14: a__isNat(s(V1)) -> a__U21(a__isNat(V1)) 15: a__isNat(x(V1,V2)) -> a__U31(a__isNat(V1),V2) 16: a__plus(N,0()) -> a__U41(a__isNat(N),N) 17: a__plus(N,s(M)) -> a__U51(a__isNat(M),M,N) 18: a__x(N,0()) -> a__U61(a__isNat(N)) 19: a__x(N,s(M)) -> a__U71(a__isNat(M),M,N) 20: mark(U11(X1,X2)) -> a__U11(mark(X1),X2) 21: mark(U12(X)) -> a__U12(mark(X)) 22: mark(isNat(X)) -> a__isNat(X) 23: mark(U21(X)) -> a__U21(mark(X)) 24: mark(U31(X1,X2)) -> a__U31(mark(X1),X2) 25: mark(U32(X)) -> a__U32(mark(X)) 26: mark(U41(X1,X2)) -> a__U41(mark(X1),X2) 27: mark(U51(X1,X2,X3)) -> a__U51(mark(X1),X2,X3) 28: mark(U52(X1,X2,X3)) -> a__U52(mark(X1),X2,X3) 29: mark(plus(X1,X2)) -> a__plus(mark(X1),mark(X2)) 30: mark(U61(X)) -> a__U61(mark(X)) 31: mark(U71(X1,X2,X3)) -> a__U71(mark(X1),X2,X3) 32: mark(U72(X1,X2,X3)) -> a__U72(mark(X1),X2,X3) 33: mark(x(X1,X2)) -> a__x(mark(X1),mark(X2)) 34: mark(tt()) -> tt() 35: mark(s(X)) -> s(mark(X)) 36: mark(0()) -> 0() 37: a__U11(X1,X2) -> U11(X1,X2) 38: a__U12(X) -> U12(X) 39: a__isNat(X) -> isNat(X) 40: a__U21(X) -> U21(X) 41: a__U31(X1,X2) -> U31(X1,X2) 42: a__U32(X) -> U32(X) 43: a__U41(X1,X2) -> U41(X1,X2) 44: a__U51(X1,X2,X3) -> U51(X1,X2,X3) 45: a__U52(X1,X2,X3) -> U52(X1,X2,X3) 46: a__plus(X1,X2) -> plus(X1,X2) 47: a__U61(X) -> U61(X) 48: a__U71(X1,X2,X3) -> U71(X1,X2,X3) 49: a__U72(X1,X2,X3) -> U72(X1,X2,X3) 50: a__x(X1,X2) -> x(X1,X2) Number of strict rules: 50 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #mark(plus(X1,X2)) -> #a__plus(mark(X1),mark(X2)) #2: #mark(plus(X1,X2)) -> #mark(X1) #3: #mark(plus(X1,X2)) -> #mark(X2) #4: #mark(s(X)) -> #mark(X) #5: #a__U41(tt(),N) -> #mark(N) #6: #a__isNat(plus(V1,V2)) -> #a__U11(a__isNat(V1),V2) #7: #a__isNat(plus(V1,V2)) -> #a__isNat(V1) #8: #a__U72(tt(),M,N) -> #a__plus(a__x(mark(N),mark(M)),mark(N)) #9: #a__U72(tt(),M,N) -> #a__x(mark(N),mark(M)) #10: #a__U72(tt(),M,N) -> #mark(N) #11: #a__U72(tt(),M,N) -> #mark(M) #12: #a__U72(tt(),M,N) -> #mark(N) #13: #mark(U31(X1,X2)) -> #a__U31(mark(X1),X2) #14: #mark(U31(X1,X2)) -> #mark(X1) #15: #mark(U21(X)) -> #a__U21(mark(X)) #16: #mark(U21(X)) -> #mark(X) #17: #mark(U71(X1,X2,X3)) -> #a__U71(mark(X1),X2,X3) #18: #mark(U71(X1,X2,X3)) -> #mark(X1) #19: #a__isNat(s(V1)) -> #a__U21(a__isNat(V1)) #20: #a__isNat(s(V1)) -> #a__isNat(V1) #21: #mark(U61(X)) -> #a__U61(mark(X)) #22: #mark(U61(X)) -> #mark(X) #23: #mark(U32(X)) -> #a__U32(mark(X)) #24: #mark(U32(X)) -> #mark(X) #25: #mark(U11(X1,X2)) -> #a__U11(mark(X1),X2) #26: #mark(U11(X1,X2)) -> #mark(X1) #27: #a__U51(tt(),M,N) -> #a__U52(a__isNat(N),M,N) #28: #a__U51(tt(),M,N) -> #a__isNat(N) #29: #a__U71(tt(),M,N) -> #a__U72(a__isNat(N),M,N) #30: #a__U71(tt(),M,N) -> #a__isNat(N) #31: #mark(x(X1,X2)) -> #a__x(mark(X1),mark(X2)) #32: #mark(x(X1,X2)) -> #mark(X1) #33: #mark(x(X1,X2)) -> #mark(X2) #34: #mark(U52(X1,X2,X3)) -> #a__U52(mark(X1),X2,X3) #35: #mark(U52(X1,X2,X3)) -> #mark(X1) #36: #mark(isNat(X)) -> #a__isNat(X) #37: #mark(U51(X1,X2,X3)) -> #a__U51(mark(X1),X2,X3) #38: #mark(U51(X1,X2,X3)) -> #mark(X1) #39: #a__plus(N,s(M)) -> #a__U51(a__isNat(M),M,N) #40: #a__plus(N,s(M)) -> #a__isNat(M) #41: #mark(U72(X1,X2,X3)) -> #a__U72(mark(X1),X2,X3) #42: #mark(U72(X1,X2,X3)) -> #mark(X1) #43: #a__x(N,s(M)) -> #a__U71(a__isNat(M),M,N) #44: #a__x(N,s(M)) -> #a__isNat(M) #45: #mark(U41(X1,X2)) -> #a__U41(mark(X1),X2) #46: #mark(U41(X1,X2)) -> #mark(X1) #47: #mark(U12(X)) -> #a__U12(mark(X)) #48: #mark(U12(X)) -> #mark(X) #49: #a__plus(N,0()) -> #a__U41(a__isNat(N),N) #50: #a__plus(N,0()) -> #a__isNat(N) #51: #a__U11(tt(),V2) -> #a__U12(a__isNat(V2)) #52: #a__U11(tt(),V2) -> #a__isNat(V2) #53: #a__U52(tt(),M,N) -> #a__plus(mark(N),mark(M)) #54: #a__U52(tt(),M,N) -> #mark(N) #55: #a__U52(tt(),M,N) -> #mark(M) #56: #a__isNat(x(V1,V2)) -> #a__U31(a__isNat(V1),V2) #57: #a__isNat(x(V1,V2)) -> #a__isNat(V1) #58: #a__U31(tt(),V2) -> #a__U32(a__isNat(V2)) #59: #a__U31(tt(),V2) -> #a__isNat(V2) #60: #a__x(N,0()) -> #a__U61(a__isNat(N)) #61: #a__x(N,0()) -> #a__isNat(N) Number of SCCs: 2, DPs: 44 SCC { #6 #7 #20 #52 #56 #57 #59 } POLO(Sum)... succeeded. a__plus w: 0 U21 w: 0 #a__U72 w: 0 #a__U71 w: 0 U11 w: 0 s w: x1 + 1 #a__U31 w: x1 + x2 + 3 #a__isNat w: x1 + 3 U71 w: 0 #a__U51 w: 0 #a__x w: 0 U72 w: 0 #a__U11 w: x1 + x2 + 3 a__U31 w: x1 + x2 a__U51 w: 0 a__x w: 0 U12 w: 0 a__U41 w: 0 x w: x1 + x2 + 2 #a__U12 w: 0 #a__U21 w: 0 #a__U61 w: 0 #a__plus w: 0 #mark w: 0 0 w: 1 a__U21 w: x1 a__U32 w: x1 #a__U52 w: 0 mark w: 0 a__U72 w: 0 a__U11 w: x1 + x2 U32 w: 0 a__U52 w: 0 a__U12 w: x1 isNat w: 0 U52 w: 0 plus w: x1 + x2 + 2439 U61 w: 0 U31 w: 0 a__U71 w: 0 a__U61 w: 0 #a__U41 w: 0 tt w: 1 a__isNat w: x1 + 1 U51 w: 0 U41 w: 0 #a__U32 w: 0 USABLE RULES: { 1..5 12..15 37..42 } Removed DPs: #6 #7 #20 #52 #56 #57 #59 Number of SCCs: 1, DPs: 37 SCC { #1..5 #8..12 #14 #16..18 #22 #24 #26 #27 #29 #31..35 #37..39 #41..43 #45 #46 #48 #49 #53..55 } POLO(Sum)... POLO(max)... succeeded. a__plus w: max(x1, x2) U21 w: x1 #a__U72 w: max(x2 + 19266, x3) #a__U71 w: max(x2 + 19266, x3) U11 w: max(x1) s w: x1 #a__U31 w: 0 #a__isNat w: 0 U71 w: max(x1 + 19265, x2 + 19266, x3) #a__U51 w: max(x2, x3) #a__x w: max(x1, x2 + 19266) U72 w: max(x1, x2 + 19266, x3) #a__U11 w: 0 a__U31 w: max(x1) a__U51 w: max(x1, x2, x3) a__x w: max(x1, x2 + 19266) U12 w: x1 a__U41 w: max(x1 + 4814, x2) x w: max(x1, x2 + 19266) #a__U12 w: 0 #a__U21 w: 0 #a__U61 w: 0 #a__plus w: max(x1, x2) #mark w: x1 0 w: 22115 a__U21 w: x1 a__U32 w: x1 #a__U52 w: max(x2, x3) mark w: x1 a__U72 w: max(x1, x2 + 19266, x3) a__U11 w: max(x1) U32 w: x1 a__U52 w: max(x1, x2, x3) a__U12 w: x1 isNat w: 0 U52 w: max(x1, x2, x3) plus w: max(x1, x2) U61 w: x1 + 22115 U31 w: max(x1) a__U71 w: max(x1 + 19265, x2 + 19266, x3) a__U61 w: x1 + 22115 #a__U41 w: max(x2) tt w: 0 a__isNat w: 0 U51 w: max(x1, x2, x3) U41 w: max(x1 + 4814, x2) #a__U32 w: 0 USABLE RULES: { 1..50 } Removed DPs: #11 #18 #22 #33 #46 Number of SCCs: 1, DPs: 32 SCC { #1..5 #8..10 #12 #14 #16 #17 #24 #26 #27 #29 #31 #32 #34 #35 #37..39 #41..43 #45 #48 #49 #53..55 } POLO(Sum)... POLO(max)... succeeded. a__plus w: max(x1, x2) U21 w: x1 #a__U72 w: max(x2 + 4, x3 + 2) #a__U71 w: max(x2 + 4, x3 + 2) U11 w: max(x1) s w: x1 #a__U31 w: 0 #a__isNat w: 0 U71 w: max(x1 + 2, x2 + 3, x3 + 1) #a__U51 w: max(x2 + 1, x3 + 1) #a__x w: max(x1 + 2, x2 + 4) U72 w: max(x1 + 1, x2 + 3, x3 + 1) #a__U11 w: 0 a__U31 w: max(x1) a__U51 w: max(x1, x2, x3) a__x w: max(x1 + 1, x2 + 3) U12 w: x1 a__U41 w: max(x1 + 1, x2) x w: max(x1 + 1, x2 + 3) #a__U12 w: 0 #a__U21 w: 0 #a__U61 w: 0 #a__plus w: max(x1 + 1, x2 + 1) #mark w: x1 + 1 0 w: 1 a__U21 w: x1 a__U32 w: x1 #a__U52 w: max(x2 + 1, x3 + 1) mark w: x1 a__U72 w: max(x1 + 1, x2 + 3, x3 + 1) a__U11 w: max(x1) U32 w: x1 a__U52 w: max(x1, x2, x3) a__U12 w: x1 isNat w: 0 U52 w: max(x1, x2, x3) plus w: max(x1, x2) U61 w: x1 + 2 U31 w: max(x1) a__U71 w: max(x1 + 2, x2 + 3, x3 + 1) a__U61 w: x1 + 2 #a__U41 w: max(x2 + 1) tt w: 0 a__isNat w: 0 U51 w: max(x1, x2, x3) U41 w: max(x1 + 1, x2) #a__U32 w: 0 USABLE RULES: { 1..50 } Removed DPs: #10 #12 #32 #42 Number of SCCs: 1, DPs: 28 SCC { #1..5 #8 #9 #14 #16 #17 #24 #26 #27 #29 #31 #34 #35 #37..39 #41 #43 #45 #48 #49 #53..55 } POLO(Sum)... POLO(max)... succeeded. a__plus w: max(x1, x2 + 9282) U21 w: x1 #a__U72 w: max(x3 + 39844) #a__U71 w: max(x3 + 39844) U11 w: max(x1) s w: x1 #a__U31 w: 0 #a__isNat w: 0 U71 w: max(x1 + 5830, x3 + 9282) #a__U51 w: max(x2 + 31269, x3 + 30562) #a__x w: max(x1 + 39844) U72 w: max(x1 + 655, x3 + 9282) #a__U11 w: 0 a__U31 w: max(x1) a__U51 w: max(x1 + 9280, x2 + 9282, x3) a__x w: max(x1 + 9282) U12 w: x1 a__U41 w: max(x1 + 1, x2) x w: max(x1 + 9282) #a__U12 w: 0 #a__U21 w: 0 #a__U61 w: 0 #a__plus w: max(x1 + 30562, x2 + 31269) #mark w: x1 + 30562 0 w: 1324 a__U21 w: x1 a__U32 w: x1 #a__U52 w: max(x2 + 31269, x3 + 30562) mark w: x1 a__U72 w: max(x1 + 655, x3 + 9282) a__U11 w: max(x1) U32 w: x1 a__U52 w: max(x1 + 706, x2 + 9282, x3) a__U12 w: x1 isNat w: 1 U52 w: max(x1 + 706, x2 + 9282, x3) plus w: max(x1, x2 + 9282) U61 w: 6228 U31 w: max(x1) a__U71 w: max(x1 + 5830, x3 + 9282) a__U61 w: 6228 #a__U41 w: max(x1 + 30563, x2 + 30562) tt w: 1 a__isNat w: 1 U51 w: max(x1 + 9280, x2 + 9282, x3) U41 w: max(x1 + 1, x2) #a__U32 w: 0 USABLE RULES: { 1..50 } Removed DPs: #3 #35 #38 #55 Number of SCCs: 1, DPs: 24 SCC { #1 #2 #4 #5 #8 #9 #14 #16 #17 #24 #26 #27 #29 #31 #34 #37 #39 #41 #43 #45 #48 #49 #53 #54 } POLO(Sum)... POLO(max)... succeeded. a__plus w: max(x1, x2 + 3) U21 w: x1 #a__U72 w: max(x1 + 56368, x2 + 56365, x3 + 56368) #a__U71 w: max(x1 + 27201, x2 + 56365, x3 + 56368) U11 w: max(x1, x2 + 2) s w: x1 #a__U31 w: 0 #a__isNat w: 0 U71 w: max(x1, x2, x3 + 3) #a__U51 w: max(x3 + 56365) #a__x w: max(x1 + 56368, x2 + 56365) U72 w: max(x1 + 3, x2, x3 + 3) #a__U11 w: 0 a__U31 w: max(x1 + 1, x2) a__U51 w: max(x1 + 1, x2 + 3, x3) a__x w: max(x1 + 3, x2) U12 w: x1 + 2 a__U41 w: max(x2) x w: max(x1 + 3, x2) #a__U12 w: 0 #a__U21 w: 0 #a__U61 w: 0 #a__plus w: max(x1 + 56365) #mark w: x1 + 56365 0 w: 1 a__U21 w: x1 a__U32 w: x1 #a__U52 w: max(x3 + 56365) mark w: x1 a__U72 w: max(x1 + 3, x2, x3 + 3) a__U11 w: max(x1, x2 + 2) U32 w: x1 a__U52 w: max(x2 + 3, x3) a__U12 w: x1 + 2 isNat w: x1 U52 w: max(x2 + 3, x3) plus w: max(x1, x2 + 3) U61 w: 3 U31 w: max(x1 + 1, x2) a__U71 w: max(x1, x2, x3 + 3) a__U61 w: 3 #a__U41 w: max(x2 + 56365) tt w: 1 a__isNat w: x1 U51 w: max(x1 + 1, x2 + 3, x3) U41 w: max(x2) #a__U32 w: 0 USABLE RULES: { 1..50 } Removed DPs: #14 #48 Number of SCCs: 1, DPs: 22 SCC { #1 #2 #4 #5 #8 #9 #16 #17 #24 #26 #27 #29 #31 #34 #37 #39 #41 #43 #45 #49 #53 #54 } POLO(Sum)... succeeded. a__plus w: x1 U21 w: x1 #a__U72 w: x2 + 1 #a__U71 w: x2 + 1 U11 w: x1 s w: x1 #a__U31 w: 3 #a__isNat w: 3 U71 w: x2 + 1 #a__U51 w: x3 #a__x w: x2 + 1 U72 w: x2 + 1 #a__U11 w: 3 a__U31 w: x2 + 30820 a__U51 w: x3 a__x w: x2 + 1 U12 w: 0 a__U41 w: x2 x w: x2 + 1 #a__U12 w: 0 #a__U21 w: 0 #a__U61 w: 0 #a__plus w: x1 #mark w: x1 0 w: 1 a__U21 w: x1 a__U32 w: x1 + 1 #a__U52 w: x3 mark w: x1 a__U72 w: x2 + 1 a__U11 w: x1 U32 w: x1 + 1 a__U52 w: x3 a__U12 w: 0 isNat w: x1 + 30819 U52 w: x3 plus w: x1 U61 w: 2 U31 w: x2 + 30820 a__U71 w: x2 + 1 a__U61 w: 2 #a__U41 w: x2 tt w: 0 a__isNat w: x1 + 30819 U51 w: x3 U41 w: x2 #a__U32 w: 0 USABLE RULES: { 1..50 } Removed DPs: #24 Number of SCCs: 1, DPs: 21 SCC { #1 #2 #4 #5 #8 #9 #16 #17 #26 #27 #29 #31 #34 #37 #39 #41 #43 #45 #49 #53 #54 } POLO(Sum)... POLO(max)... QLPOS... succeeded. a__plus s: [1,2] p: 5 U21 s: 1 #a__U72 s: [2,3,1] p: 6 #a__U71 s: [2,3,1] p: 6 U11 s: 1 s s: [1] p: 4 #a__U31 s: 2 #a__isNat s: [] p: 0 U71 s: [2,3,1] p: 6 #a__U51 s: [3] p: 3 #a__x s: [2,1] p: 6 U72 s: [2,3,1] p: 6 #a__U11 s: 2 a__U31 s: [] p: 1 a__U51 s: [3,2,1] p: 5 a__x s: [2,1] p: 6 U12 s: [] p: 1 a__U41 s: [2,1] p: 2 x s: [2,1] p: 6 #a__U12 s: [] p: 0 #a__U21 s: 1 #a__U61 s: [] p: 0 #a__plus s: [1] p: 3 #mark s: 1 0 s: [] p: 6 a__U21 s: 1 a__U32 s: [] p: 1 #a__U52 s: [3] p: 3 mark s: 1 a__U72 s: [2,3,1] p: 6 a__U11 s: 1 U32 s: [] p: 1 a__U52 s: [3,2,1] p: 5 a__U12 s: [] p: 1 isNat s: [] p: 1 U52 s: [3,2,1] p: 5 plus s: [1,2] p: 5 U61 s: [] p: 6 U31 s: [] p: 1 a__U71 s: [2,3,1] p: 6 a__U61 s: [] p: 6 #a__U41 s: [2] p: 2 tt s: [] p: 1 a__isNat s: [] p: 1 U51 s: [3,2,1] p: 5 U41 s: [2,1] p: 2 #a__U32 s: [] p: 0 USABLE RULES: { 1..50 } Removed DPs: #1 #2 #4 #5 #8 #9 #34 #37 #43 #45 #49 #54 Number of SCCs: 2, DPs: 5 SCC { #16 #26 } POLO(Sum)... succeeded. a__plus w: 5 U21 w: x1 + 9920 #a__U72 w: 0 #a__U71 w: 0 U11 w: x1 + x2 + 9924 s w: 2 #a__U31 w: 3 #a__isNat w: 3 U71 w: x1 + x3 + 4 #a__U51 w: 0 #a__x w: 0 U72 w: x1 + x2 + x3 + 5 #a__U11 w: 3 a__U31 w: x2 + 9918 a__U51 w: x2 + 6 a__x w: x1 + x2 U12 w: 9 a__U41 w: 6 x w: 1 #a__U12 w: 0 #a__U21 w: 0 #a__U61 w: 0 #a__plus w: 0 #mark w: x1 0 w: 3 a__U21 w: 9919 a__U32 w: 9919 #a__U52 w: 0 mark w: 1 a__U72 w: 4 a__U11 w: 9923 U32 w: 9920 a__U52 w: x1 + 1 a__U12 w: x1 + 8 isNat w: 9917 U52 w: x2 + 2 plus w: x1 + x2 + 6 U61 w: x1 + 3 U31 w: x1 + 9919 a__U71 w: x2 + 3 a__U61 w: 2 #a__U41 w: 0 tt w: 9920 a__isNat w: x1 + 9916 U51 w: 7 U41 w: x1 + 7 #a__U32 w: 0 USABLE RULES: { } Removed DPs: #16 #26 Number of SCCs: 1, DPs: 3 SCC { #27 #39 #53 } POLO(Sum)... POLO(max)... QLPOS... succeeded. a__plus s: [1,2] p: 5 U21 s: 1 #a__U72 s: [2,3,1] p: 6 #a__U71 s: [2,3,1] p: 6 U11 s: 1 s s: [1] p: 3 #a__U31 s: 2 #a__isNat s: [] p: 0 U71 s: [2,3,1] p: 6 #a__U51 s: [3,2] p: 4 #a__x s: [2,1] p: 6 U72 s: [2,3,1] p: 6 #a__U11 s: 2 a__U31 s: [] p: 1 a__U51 s: [3,2,1] p: 5 a__x s: [2,1] p: 6 U12 s: [] p: 1 a__U41 s: [2,1] p: 2 x s: [2,1] p: 6 #a__U12 s: [] p: 0 #a__U21 s: 1 #a__U61 s: [] p: 0 #a__plus s: [1,2] p: 4 #mark s: 1 0 s: [] p: 6 a__U21 s: 1 a__U32 s: [] p: 1 #a__U52 s: [3,2] p: 4 mark s: 1 a__U72 s: [2,3,1] p: 6 a__U11 s: 1 U32 s: [] p: 1 a__U52 s: [3,2,1] p: 5 a__U12 s: [] p: 1 isNat s: [] p: 1 U52 s: [3,2,1] p: 5 plus s: [1,2] p: 5 U61 s: [] p: 6 U31 s: [] p: 1 a__U71 s: [2,3,1] p: 6 a__U61 s: [] p: 6 #a__U41 s: [2] p: 2 tt s: [] p: 1 a__isNat s: [] p: 1 U51 s: [3,2,1] p: 5 U41 s: [2,1] p: 2 #a__U32 s: [] p: 0 USABLE RULES: { 1..50 } Removed DPs: #39 Number of SCCs: 0, DPs: 0