/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES Input TRS: 1: U101(tt(),M,N) -> U102(isNatKind(activate(M)),activate(M),activate(N)) 2: U102(tt(),M,N) -> U103(isNat(activate(N)),activate(M),activate(N)) 3: U103(tt(),M,N) -> U104(isNatKind(activate(N)),activate(M),activate(N)) 4: U104(tt(),M,N) -> plus(x(activate(N),activate(M)),activate(N)) 5: U11(tt(),V1,V2) -> U12(isNatKind(activate(V1)),activate(V1),activate(V2)) 6: U12(tt(),V1,V2) -> U13(isNatKind(activate(V2)),activate(V1),activate(V2)) 7: U13(tt(),V1,V2) -> U14(isNatKind(activate(V2)),activate(V1),activate(V2)) 8: U14(tt(),V1,V2) -> U15(isNat(activate(V1)),activate(V2)) 9: U15(tt(),V2) -> U16(isNat(activate(V2))) 10: U16(tt()) -> tt() 11: U21(tt(),V1) -> U22(isNatKind(activate(V1)),activate(V1)) 12: U22(tt(),V1) -> U23(isNat(activate(V1))) 13: U23(tt()) -> tt() 14: U31(tt(),V1,V2) -> U32(isNatKind(activate(V1)),activate(V1),activate(V2)) 15: U32(tt(),V1,V2) -> U33(isNatKind(activate(V2)),activate(V1),activate(V2)) 16: U33(tt(),V1,V2) -> U34(isNatKind(activate(V2)),activate(V1),activate(V2)) 17: U34(tt(),V1,V2) -> U35(isNat(activate(V1)),activate(V2)) 18: U35(tt(),V2) -> U36(isNat(activate(V2))) 19: U36(tt()) -> tt() 20: U41(tt(),V2) -> U42(isNatKind(activate(V2))) 21: U42(tt()) -> tt() 22: U51(tt()) -> tt() 23: U61(tt(),V2) -> U62(isNatKind(activate(V2))) 24: U62(tt()) -> tt() 25: U71(tt(),N) -> U72(isNatKind(activate(N)),activate(N)) 26: U72(tt(),N) -> activate(N) 27: U81(tt(),M,N) -> U82(isNatKind(activate(M)),activate(M),activate(N)) 28: U82(tt(),M,N) -> U83(isNat(activate(N)),activate(M),activate(N)) 29: U83(tt(),M,N) -> U84(isNatKind(activate(N)),activate(M),activate(N)) 30: U84(tt(),M,N) -> s(plus(activate(N),activate(M))) 31: U91(tt(),N) -> U92(isNatKind(activate(N))) 32: U92(tt()) -> 0() 33: isNat(n__0()) -> tt() 34: isNat(n__plus(V1,V2)) -> U11(isNatKind(activate(V1)),activate(V1),activate(V2)) 35: isNat(n__s(V1)) -> U21(isNatKind(activate(V1)),activate(V1)) 36: isNat(n__x(V1,V2)) -> U31(isNatKind(activate(V1)),activate(V1),activate(V2)) 37: isNatKind(n__0()) -> tt() 38: isNatKind(n__plus(V1,V2)) -> U41(isNatKind(activate(V1)),activate(V2)) 39: isNatKind(n__s(V1)) -> U51(isNatKind(activate(V1))) 40: isNatKind(n__x(V1,V2)) -> U61(isNatKind(activate(V1)),activate(V2)) 41: plus(N,0()) -> U71(isNat(N),N) 42: plus(N,s(M)) -> U81(isNat(M),M,N) 43: x(N,0()) -> U91(isNat(N),N) 44: x(N,s(M)) -> U101(isNat(M),M,N) 45: 0() -> n__0() 46: plus(X1,X2) -> n__plus(X1,X2) 47: s(X) -> n__s(X) 48: x(X1,X2) -> n__x(X1,X2) 49: activate(n__0()) -> 0() 50: activate(n__plus(X1,X2)) -> plus(activate(X1),activate(X2)) 51: activate(n__s(X)) -> s(activate(X)) 52: activate(n__x(X1,X2)) -> x(activate(X1),activate(X2)) 53: activate(X) -> X Number of strict rules: 53 Direct poly ... failed. Freezing ... failed. Dependency Pairs: #1: #U102(tt(),M,N) -> #U103(isNat(activate(N)),activate(M),activate(N)) #2: #U102(tt(),M,N) -> #isNat(activate(N)) #3: #U102(tt(),M,N) -> #activate(N) #4: #U102(tt(),M,N) -> #activate(M) #5: #U102(tt(),M,N) -> #activate(N) #6: #x(N,0()) -> #U91(isNat(N),N) #7: #x(N,0()) -> #isNat(N) #8: #U83(tt(),M,N) -> #U84(isNatKind(activate(N)),activate(M),activate(N)) #9: #U83(tt(),M,N) -> #isNatKind(activate(N)) #10: #U83(tt(),M,N) -> #activate(N) #11: #U83(tt(),M,N) -> #activate(M) #12: #U83(tt(),M,N) -> #activate(N) #13: #isNat(n__s(V1)) -> #U21(isNatKind(activate(V1)),activate(V1)) #14: #isNat(n__s(V1)) -> #isNatKind(activate(V1)) #15: #isNat(n__s(V1)) -> #activate(V1) #16: #isNat(n__s(V1)) -> #activate(V1) #17: #plus(N,s(M)) -> #U81(isNat(M),M,N) #18: #plus(N,s(M)) -> #isNat(M) #19: #plus(N,0()) -> #U71(isNat(N),N) #20: #plus(N,0()) -> #isNat(N) #21: #isNatKind(n__plus(V1,V2)) -> #U41(isNatKind(activate(V1)),activate(V2)) #22: #isNatKind(n__plus(V1,V2)) -> #isNatKind(activate(V1)) #23: #isNatKind(n__plus(V1,V2)) -> #activate(V1) #24: #isNatKind(n__plus(V1,V2)) -> #activate(V2) #25: #U12(tt(),V1,V2) -> #U13(isNatKind(activate(V2)),activate(V1),activate(V2)) #26: #U12(tt(),V1,V2) -> #isNatKind(activate(V2)) #27: #U12(tt(),V1,V2) -> #activate(V2) #28: #U12(tt(),V1,V2) -> #activate(V1) #29: #U12(tt(),V1,V2) -> #activate(V2) #30: #isNatKind(n__x(V1,V2)) -> #U61(isNatKind(activate(V1)),activate(V2)) #31: #isNatKind(n__x(V1,V2)) -> #isNatKind(activate(V1)) #32: #isNatKind(n__x(V1,V2)) -> #activate(V1) #33: #isNatKind(n__x(V1,V2)) -> #activate(V2) #34: #activate(n__s(X)) -> #s(activate(X)) #35: #activate(n__s(X)) -> #activate(X) #36: #U15(tt(),V2) -> #U16(isNat(activate(V2))) #37: #U15(tt(),V2) -> #isNat(activate(V2)) #38: #U15(tt(),V2) -> #activate(V2) #39: #U21(tt(),V1) -> #U22(isNatKind(activate(V1)),activate(V1)) #40: #U21(tt(),V1) -> #isNatKind(activate(V1)) #41: #U21(tt(),V1) -> #activate(V1) #42: #U21(tt(),V1) -> #activate(V1) #43: #U61(tt(),V2) -> #U62(isNatKind(activate(V2))) #44: #U61(tt(),V2) -> #isNatKind(activate(V2)) #45: #U61(tt(),V2) -> #activate(V2) #46: #U22(tt(),V1) -> #U23(isNat(activate(V1))) #47: #U22(tt(),V1) -> #isNat(activate(V1)) #48: #U22(tt(),V1) -> #activate(V1) #49: #U91(tt(),N) -> #U92(isNatKind(activate(N))) #50: #U91(tt(),N) -> #isNatKind(activate(N)) #51: #U91(tt(),N) -> #activate(N) #52: #U31(tt(),V1,V2) -> #U32(isNatKind(activate(V1)),activate(V1),activate(V2)) #53: #U31(tt(),V1,V2) -> #isNatKind(activate(V1)) #54: #U31(tt(),V1,V2) -> #activate(V1) #55: #U31(tt(),V1,V2) -> #activate(V1) #56: #U31(tt(),V1,V2) -> #activate(V2) #57: #U84(tt(),M,N) -> #s(plus(activate(N),activate(M))) #58: #U84(tt(),M,N) -> #plus(activate(N),activate(M)) #59: #U84(tt(),M,N) -> #activate(N) #60: #U84(tt(),M,N) -> #activate(M) #61: #activate(n__x(X1,X2)) -> #x(activate(X1),activate(X2)) #62: #activate(n__x(X1,X2)) -> #activate(X1) #63: #activate(n__x(X1,X2)) -> #activate(X2) #64: #activate(n__0()) -> #0() #65: #U71(tt(),N) -> #U72(isNatKind(activate(N)),activate(N)) #66: #U71(tt(),N) -> #isNatKind(activate(N)) #67: #U71(tt(),N) -> #activate(N) #68: #U71(tt(),N) -> #activate(N) #69: #U41(tt(),V2) -> #U42(isNatKind(activate(V2))) #70: #U41(tt(),V2) -> #isNatKind(activate(V2)) #71: #U41(tt(),V2) -> #activate(V2) #72: #U13(tt(),V1,V2) -> #U14(isNatKind(activate(V2)),activate(V1),activate(V2)) #73: #U13(tt(),V1,V2) -> #isNatKind(activate(V2)) #74: #U13(tt(),V1,V2) -> #activate(V2) #75: #U13(tt(),V1,V2) -> #activate(V1) #76: #U13(tt(),V1,V2) -> #activate(V2) #77: #isNatKind(n__s(V1)) -> #U51(isNatKind(activate(V1))) #78: #isNatKind(n__s(V1)) -> #isNatKind(activate(V1)) #79: #isNatKind(n__s(V1)) -> #activate(V1) #80: #U11(tt(),V1,V2) -> #U12(isNatKind(activate(V1)),activate(V1),activate(V2)) #81: #U11(tt(),V1,V2) -> #isNatKind(activate(V1)) #82: #U11(tt(),V1,V2) -> #activate(V1) #83: #U11(tt(),V1,V2) -> #activate(V1) #84: #U11(tt(),V1,V2) -> #activate(V2) #85: #x(N,s(M)) -> #U101(isNat(M),M,N) #86: #x(N,s(M)) -> #isNat(M) #87: #U82(tt(),M,N) -> #U83(isNat(activate(N)),activate(M),activate(N)) #88: #U82(tt(),M,N) -> #isNat(activate(N)) #89: #U82(tt(),M,N) -> #activate(N) #90: #U82(tt(),M,N) -> #activate(M) #91: #U82(tt(),M,N) -> #activate(N) #92: #isNat(n__plus(V1,V2)) -> #U11(isNatKind(activate(V1)),activate(V1),activate(V2)) #93: #isNat(n__plus(V1,V2)) -> #isNatKind(activate(V1)) #94: #isNat(n__plus(V1,V2)) -> #activate(V1) #95: #isNat(n__plus(V1,V2)) -> #activate(V1) #96: #isNat(n__plus(V1,V2)) -> #activate(V2) #97: #U81(tt(),M,N) -> #U82(isNatKind(activate(M)),activate(M),activate(N)) #98: #U81(tt(),M,N) -> #isNatKind(activate(M)) #99: #U81(tt(),M,N) -> #activate(M) #100: #U81(tt(),M,N) -> #activate(M) #101: #U81(tt(),M,N) -> #activate(N) #102: #U34(tt(),V1,V2) -> #U35(isNat(activate(V1)),activate(V2)) #103: #U34(tt(),V1,V2) -> #isNat(activate(V1)) #104: #U34(tt(),V1,V2) -> #activate(V1) #105: #U34(tt(),V1,V2) -> #activate(V2) #106: #U92(tt()) -> #0() #107: #U72(tt(),N) -> #activate(N) #108: #isNat(n__x(V1,V2)) -> #U31(isNatKind(activate(V1)),activate(V1),activate(V2)) #109: #isNat(n__x(V1,V2)) -> #isNatKind(activate(V1)) #110: #isNat(n__x(V1,V2)) -> #activate(V1) #111: #isNat(n__x(V1,V2)) -> #activate(V1) #112: #isNat(n__x(V1,V2)) -> #activate(V2) #113: #U33(tt(),V1,V2) -> #U34(isNatKind(activate(V2)),activate(V1),activate(V2)) #114: #U33(tt(),V1,V2) -> #isNatKind(activate(V2)) #115: #U33(tt(),V1,V2) -> #activate(V2) #116: #U33(tt(),V1,V2) -> #activate(V1) #117: #U33(tt(),V1,V2) -> #activate(V2) #118: #U103(tt(),M,N) -> #U104(isNatKind(activate(N)),activate(M),activate(N)) #119: #U103(tt(),M,N) -> #isNatKind(activate(N)) #120: #U103(tt(),M,N) -> #activate(N) #121: #U103(tt(),M,N) -> #activate(M) #122: #U103(tt(),M,N) -> #activate(N) #123: #U101(tt(),M,N) -> #U102(isNatKind(activate(M)),activate(M),activate(N)) #124: #U101(tt(),M,N) -> #isNatKind(activate(M)) #125: #U101(tt(),M,N) -> #activate(M) #126: #U101(tt(),M,N) -> #activate(M) #127: #U101(tt(),M,N) -> #activate(N) #128: #U14(tt(),V1,V2) -> #U15(isNat(activate(V1)),activate(V2)) #129: #U14(tt(),V1,V2) -> #isNat(activate(V1)) #130: #U14(tt(),V1,V2) -> #activate(V1) #131: #U14(tt(),V1,V2) -> #activate(V2) #132: #U32(tt(),V1,V2) -> #U33(isNatKind(activate(V2)),activate(V1),activate(V2)) #133: #U32(tt(),V1,V2) -> #isNatKind(activate(V2)) #134: #U32(tt(),V1,V2) -> #activate(V2) #135: #U32(tt(),V1,V2) -> #activate(V1) #136: #U32(tt(),V1,V2) -> #activate(V2) #137: #U104(tt(),M,N) -> #plus(x(activate(N),activate(M)),activate(N)) #138: #U104(tt(),M,N) -> #x(activate(N),activate(M)) #139: #U104(tt(),M,N) -> #activate(N) #140: #U104(tt(),M,N) -> #activate(M) #141: #U104(tt(),M,N) -> #activate(N) #142: #activate(n__plus(X1,X2)) -> #plus(activate(X1),activate(X2)) #143: #activate(n__plus(X1,X2)) -> #activate(X1) #144: #activate(n__plus(X1,X2)) -> #activate(X2) #145: #U35(tt(),V2) -> #U36(isNat(activate(V2))) #146: #U35(tt(),V2) -> #isNat(activate(V2)) #147: #U35(tt(),V2) -> #activate(V2) Number of SCCs: 1, DPs: 136 SCC { #1..33 #35 #37..42 #44 #45 #47 #48 #50..56 #58..63 #65..68 #70..76 #78..105 #107..144 #146 #147 } Sum... Max... succeeded. #0() w: (0) #U72(x1,x2) w: (max{2 + x2, 0}) #U32(x1,x2,x3) w: (max{8 + x3, 6 + x2, 0}) isNatKind(x1) w: (x1) U16(x1) w: (0) U21(x1,x2) w: (max{2 + x2, 0}) #U83(x1,x2,x3) w: (max{2 + x3, 23 + x2, 0}) U11(x1,x2,x3) w: (max{0, 27571 + x2}) s(x1) w: (x1) #isNat(x1) w: (2 + x1) U42(x1) w: (11) U91(x1,x2) w: (max{16 + x2, 0}) #U35(x1,x2) w: (max{3 + x2, 0}) #U101(x1,x2,x3) w: (max{23 + x3, 10 + x2, 0}) activate(x1) w: (x1) #U82(x1,x2,x3) w: (max{2 + x3, 23 + x2, 23 + x1}) #U104(x1,x2,x3) w: (max{23 + x3, 10 + x2, 0}) U71(x1,x2) w: (max{x2, 0}) #U81(x1,x2,x3) w: (max{2 + x3, 23 + x2, 0}) #U92(x1) w: (0) #plus(x1,x2) w: (max{23 + x2, 2 + x1}) U101(x1,x2,x3) w: (max{21 + x3, 8 + x2, 0}) #activate(x1) w: (2 + x1) U103(x1,x2,x3) w: (max{21 + x3, 8 + x2, 0}) #U23(x1) w: (0) U84(x1,x2,x3) w: (max{x3, 21 + x2, x1}) U23(x1) w: (0) U35(x1,x2) w: (max{31262 + x2, 6 + x1}) U72(x1,x2) w: (max{x2, 0}) #U13(x1,x2,x3) w: (max{11 + x3, 2 + x2, 0}) U34(x1,x2,x3) w: (max{11 + x3, 31261 + x2, 0}) #U103(x1,x2,x3) w: (max{23 + x3, 10 + x2, 0}) U12(x1,x2,x3) w: (max{27572 + x3, 0, 27574 + x1}) #U33(x1,x2,x3) w: (max{5 + x3, 5 + x2, 7 + x1}) x(x1,x2) w: (max{8 + x2, 21 + x1}) #U16(x1) w: (0) n__s(x1) w: (x1) U104(x1,x2,x3) w: (max{21 + x3, 8 + x2, 3 + x1}) #U42(x1) w: (0) #U12(x1,x2,x3) w: (max{11 + x3, 2 + x2, 2 + x1}) #U62(x1) w: (0) U83(x1,x2,x3) w: (max{x3, 21 + x2, 0}) 0() w: (11) #U14(x1,x2,x3) w: (max{11 + x3, 2 + x2, 11 + x1}) #U36(x1) w: (0) U36(x1) w: (7) #U102(x1,x2,x3) w: (max{23 + x3, 10 + x2, x1}) #x(x1,x2) w: (max{10 + x2, 23 + x1}) #s(x1) w: (0) U62(x1) w: (20) n__plus(x1,x2) w: (max{21 + x2, x1}) #U15(x1,x2) w: (max{10 + x2, 0}) U32(x1,x2,x3) w: (max{9 + x3, 0}) U33(x1,x2,x3) w: (max{10 + x3, 31261 + x2, x1}) n__0() w: (11) #U34(x1,x2,x3) w: (max{4 + x3, 4 + x2, 0}) U14(x1,x2,x3) w: (max{0, 27574 + x2}) isNat(x1) w: (1) n__x(x1,x2) w: (max{8 + x2, 21 + x1}) plus(x1,x2) w: (max{21 + x2, x1}) U15(x1,x2) w: (max{27575 + x2, 0}) U61(x1,x2) w: (max{8 + x2, 19 + x1}) #U51(x1) w: (0) #U11(x1,x2,x3) w: (max{11 + x3, 2 + x2, 1 + x1}) U31(x1,x2,x3) w: (max{0, 1 + x2, 6813 + x1}) U92(x1) w: (11) #U41(x1,x2) w: (max{8 + x2, x1}) U102(x1,x2,x3) w: (max{21 + x3, 8 + x2, 4 + x1}) #U21(x1,x2) w: (max{2 + x2, 1 + x1}) U81(x1,x2,x3) w: (max{x3, 21 + x2, 0}) U82(x1,x2,x3) w: (max{x3, 21 + x2, 7 + x1}) #U22(x1,x2) w: (max{2 + x2, 1 + x1}) tt() w: (11) #U84(x1,x2,x3) w: (max{2 + x3, 23 + x2, 2 + x1}) #U71(x1,x2) w: (max{2 + x2, 0}) U13(x1,x2,x3) w: (max{27573 + x3, 0}) U22(x1,x2) w: (max{1 + x2, 0}) U51(x1) w: (x1) #isNatKind(x1) w: (2 + x1) U41(x1,x2) w: (max{21 + x2, x1}) #U31(x1,x2,x3) w: (max{9 + x3, 19 + x2, 11 + x1}) #U91(x1,x2) w: (max{22 + x2, 0}) #U61(x1,x2) w: (max{7 + x2, 21 + x1}) USABLE RULES: { 1..4 20..32 37..53 } Removed DPs: #2..7 #11 #18 #21 #24 #26 #27 #29..33 #37 #38 #44 #45 #50..56 #60 #62 #63 #70 #71 #73 #74 #76 #84 #86 #90 #96 #98..100 #102..105 #108..117 #119..122 #124..128 #131..136 #139..141 #144 #146 #147 Number of SCCs: 1, DPs: 58 SCC { #1 #8..10 #12..17 #19 #20 #22 #23 #25 #28 #35 #39..42 #47 #48 #58 #59 #61 #65..68 #72 #75 #78..83 #85 #87..89 #91..95 #97 #101 #107 #118 #123 #129 #130 #137 #138 #142 #143 } Sum... Max... QLPOpS... succeeded. #0() 0 #U72(x1,x2) 3[x2] #U32(x1,x2,x3) 0[x3,x2] isNatKind(x1) 4[] U16(x1) 4[] U21(x1,x2) x1 #U83(x1,x2,x3) 7[x2,x3,x1] U11(x1,x2,x3) x1 s(x1) 4[x1] #isNat(x1) 4[x1] U42(x1) x1 U91(x1,x2) 5[] #U35(x1,x2) 0[] #U101(x1,x2,x3) 9[x3,x2,x1] activate(x1) x1 #U82(x1,x2,x3) 7[x2,x3,x1] #U104(x1,x2,x3) 9[x3,x2,x1] U71(x1,x2) 0[x1,x2] #U81(x1,x2,x3) 7[x2,x3,x1] #U92(x1) 0[] #plus(x1,x2) 7[x2,x1] U101(x1,x2,x3) 9[x3,x2,x1] #activate(x1) 2[x1] U103(x1,x2,x3) 9[x3,x2,x1] #U23(x1) 0[] U84(x1,x2,x3) 8[x3,x2,x1] U23(x1) 4[] U35(x1,x2) 4[] U72(x1,x2) 0[x1,x2] #U13(x1,x2,x3) 4[x2] U34(x1,x2,x3) x1 #U103(x1,x2,x3) 9[x3,x2,x1] U12(x1,x2,x3) x1 #U33(x1,x2,x3) 0[x3,x1] x(x1,x2) 9[x1,x2] #U16(x1) 0[] n__s(x1) 4[x1] U104(x1,x2,x3) 9[x3,x2,x1] #U42(x1) 0[] #U12(x1,x2,x3) 4[x2,x3] #U62(x1) 0[] U83(x1,x2,x3) 8[x3,x2,x1] 0() 5 #U14(x1,x2,x3) 4[x2] #U36(x1) 0[] U36(x1) x1 #U102(x1,x2,x3) 9[x3,x2,x1] #x(x1,x2) 9[x1,x2] #s(x1) 0[] U62(x1) 4[] n__plus(x1,x2) 8[x1,x2] #U15(x1,x2) 0[] U32(x1,x2,x3) 4[] U33(x1,x2,x3) 4[] n__0() 5 #U34(x1,x2,x3) 0[x3,x1] U14(x1,x2,x3) x1 isNat(x1) 4[] n__x(x1,x2) 9[x1,x2] plus(x1,x2) 8[x1,x2] U15(x1,x2) 4[] U61(x1,x2) 4[] #U51(x1) 0[] #U11(x1,x2,x3) 4[x2,x3] U31(x1,x2,x3) 4[] U92(x1) 5[] #U41(x1,x2) 0[x2] U102(x1,x2,x3) 9[x3,x2,x1] #U21(x1,x2) 4[x2] U81(x1,x2,x3) 8[x3,x2,x1] U82(x1,x2,x3) 8[x3,x2,x1] #U22(x1,x2) 4[x2] tt() 4 #U84(x1,x2,x3) 7[x2,x3] #U71(x1,x2) 6[x2] U13(x1,x2,x3) x1 U22(x1,x2) x1 U51(x1) x1 #isNatKind(x1) 4[x1] U41(x1,x2) 4[] #U31(x1,x2,x3) 0[x3,x2,x1] #U91(x1,x2) 0[x1] #U61(x1,x2) 0[x1,x2] USABLE RULES: { 1..53 } Removed DPs: #8..10 #12..17 #19 #20 #22 #23 #25 #28 #35 #41 #42 #48 #59 #61 #65..68 #75 #78 #79 #81..83 #85 #88 #89 #91..95 #101 #107 #130 #137 #138 #142 #143 Number of SCCs: 0, DPs: 0