MAYBE Input TRS: AC symbols: plus union mult 1: union(X,empty()) -> X 2: union(empty(),X) -> X 3: 0(z()) -> z() 4: U101(tt(),X,Y) -> 0(mult(X,Y)) 5: U11(tt(),V1) -> U12(isBin(V1)) 6: U111(tt(),X,Y) -> plus(0(mult(X,Y)),Y) 7: U12(tt()) -> tt() 8: U121(tt(),X) -> X 9: U131(tt(),X,Y) -> 0(plus(X,Y)) 10: U141(tt(),X,Y) -> 1(plus(X,Y)) 11: U151(tt(),X,Y) -> 0(plus(plus(X,Y),1(z()))) 12: U161(tt(),X) -> X 13: U171(tt(),A,B) -> mult(prod(A),prod(B)) 14: U181(tt(),X) -> X 15: U191(tt(),A,B) -> plus(sum(A),sum(B)) 16: U21(tt(),V1,V2) -> U22(isBag(V1),V2) 17: U22(tt(),V2) -> U23(isBag(V2)) 18: U23(tt()) -> tt() 19: U31(tt(),V1) -> U32(isBin(V1)) 20: U32(tt()) -> tt() 21: U41(tt(),V1) -> U42(isBin(V1)) 22: U42(tt()) -> tt() 23: U51(tt(),V1,V2) -> U52(isBin(V1),V2) 24: U52(tt(),V2) -> U53(isBin(V2)) 25: U53(tt()) -> tt() 26: U61(tt(),V1,V2) -> U62(isBin(V1),V2) 27: U62(tt(),V2) -> U63(isBin(V2)) 28: U63(tt()) -> tt() 29: U71(tt(),V1) -> U72(isBag(V1)) 30: U72(tt()) -> tt() 31: U81(tt(),V1) -> U82(isBag(V1)) 32: U82(tt()) -> tt() 33: U91(tt()) -> z() 34: and(tt(),X) -> X 35: isBag(empty()) -> tt() 36: isBag(singl(V1)) -> U11(isBinKind(V1),V1) 37: isBag(union(V1,V2)) -> U21(and(isBagKind(V1),isBagKind(V2)),V1,V2) 38: isBagKind(empty()) -> tt() 39: isBagKind(singl(V1)) -> isBinKind(V1) 40: isBagKind(union(V1,V2)) -> and(isBagKind(V1),isBagKind(V2)) 41: isBin(z()) -> tt() 42: isBin(0(V1)) -> U31(isBinKind(V1),V1) 43: isBin(1(V1)) -> U41(isBinKind(V1),V1) 44: isBin(mult(V1,V2)) -> U51(and(isBinKind(V1),isBinKind(V2)),V1,V2) 45: isBin(plus(V1,V2)) -> U61(and(isBinKind(V1),isBinKind(V2)),V1,V2) 46: isBin(prod(V1)) -> U71(isBagKind(V1),V1) 47: isBin(sum(V1)) -> U81(isBagKind(V1),V1) 48: isBinKind(z()) -> tt() 49: isBinKind(0(V1)) -> isBinKind(V1) 50: isBinKind(1(V1)) -> isBinKind(V1) 51: isBinKind(mult(V1,V2)) -> and(isBinKind(V1),isBinKind(V2)) 52: isBinKind(plus(V1,V2)) -> and(isBinKind(V1),isBinKind(V2)) 53: isBinKind(prod(V1)) -> isBagKind(V1) 54: isBinKind(sum(V1)) -> isBagKind(V1) 55: mult(z(),X) -> U91(and(isBin(X),isBinKind(X))) 56: mult(0(X),Y) -> U101(and(and(isBin(X),isBinKind(X)),and(isBin(Y),isBinKind(Y))),X,Y) 57: mult(1(X),Y) -> U111(and(and(isBin(X),isBinKind(X)),and(isBin(Y),isBinKind(Y))),X,Y) 58: plus(z(),X) -> U121(and(isBin(X),isBinKind(X)),X) 59: plus(0(X),0(Y)) -> U131(and(and(isBin(X),isBinKind(X)),and(isBin(Y),isBinKind(Y))),X,Y) 60: plus(0(X),1(Y)) -> U141(and(and(isBin(X),isBinKind(X)),and(isBin(Y),isBinKind(Y))),X,Y) 61: plus(1(X),1(Y)) -> U151(and(and(isBin(X),isBinKind(X)),and(isBin(Y),isBinKind(Y))),X,Y) 62: prod(empty()) -> 1(z()) 63: prod(singl(X)) -> U161(and(isBin(X),isBinKind(X)),X) 64: prod(union(A,B)) -> U171(and(and(isBag(A),isBagKind(A)),and(isBag(B),isBagKind(B))),A,B) 65: sum(empty()) -> 0(z()) 66: sum(singl(X)) -> U181(and(isBin(X),isBinKind(X)),X) 67: sum(union(A,B)) -> U191(and(and(isBag(A),isBagKind(A)),and(isBag(B),isBagKind(B))),A,B) Number of strict rules: 67 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #isBin(1(V1)) -> #U41(isBinKind(V1),V1) #2: #isBin(1(V1)) -> #isBinKind(V1) #3: #U71(tt(),V1) -> #U72(isBag(V1)) #4: #U71(tt(),V1) -> #isBag(V1) #5: #sum(singl(X)) -> #U181(and(isBin(X),isBinKind(X)),X) #6: #sum(singl(X)) -> #and(isBin(X),isBinKind(X)) #7: #sum(singl(X)) -> #isBin(X) #8: #sum(singl(X)) -> #isBinKind(X) #9: #isBin(prod(V1)) -> #U71(isBagKind(V1),V1) #10: #isBin(prod(V1)) -> #isBagKind(V1) #11: #isBin(0(V1)) -> #U31(isBinKind(V1),V1) #12: #isBin(0(V1)) -> #isBinKind(V1) #13: #isBag(union(V1,V2)) -> #U21(and(isBagKind(V1),isBagKind(V2)),V1,V2) #14: #isBag(union(V1,V2)) -> #and(isBagKind(V1),isBagKind(V2)) #15: #isBag(union(V1,V2)) -> #isBagKind(V1) #16: #isBag(union(V1,V2)) -> #isBagKind(V2) #17: #isBin(sum(V1)) -> #U81(isBagKind(V1),V1) #18: #isBin(sum(V1)) -> #isBagKind(V1) #19: #isBinKind(prod(V1)) -> #isBagKind(V1) #20: #plus(z(),X) -> #U121(and(isBin(X),isBinKind(X)),X) #21: #plus(z(),X) -> #and(isBin(X),isBinKind(X)) #22: #plus(z(),X) -> #isBin(X) #23: #plus(z(),X) -> #isBinKind(X) #24: #plus(1(X),1(Y)) -> #U151(and(and(isBin(X),isBinKind(X)),and(isBin(Y),isBinKind(Y))),X,Y) #25: #plus(1(X),1(Y)) -> #and(and(isBin(X),isBinKind(X)),and(isBin(Y),isBinKind(Y))) #26: #plus(1(X),1(Y)) -> #and(isBin(X),isBinKind(X)) #27: #plus(1(X),1(Y)) -> #isBin(X) #28: #plus(1(X),1(Y)) -> #isBinKind(X) #29: #plus(1(X),1(Y)) -> #and(isBin(Y),isBinKind(Y)) #30: #plus(1(X),1(Y)) -> #isBin(Y) #31: #plus(1(X),1(Y)) -> #isBinKind(Y) #32: #U111(tt(),X,Y) -> #plus(0(mult(X,Y)),Y) #33: #U111(tt(),X,Y) -> #0(mult(X,Y)) #34: #U111(tt(),X,Y) -> #mult(X,Y) #35: #plus(0(X),0(Y)) -> #U131(and(and(isBin(X),isBinKind(X)),and(isBin(Y),isBinKind(Y))),X,Y) #36: #plus(0(X),0(Y)) -> #and(and(isBin(X),isBinKind(X)),and(isBin(Y),isBinKind(Y))) #37: #plus(0(X),0(Y)) -> #and(isBin(X),isBinKind(X)) #38: #plus(0(X),0(Y)) -> #isBin(X) #39: #plus(0(X),0(Y)) -> #isBinKind(X) #40: #plus(0(X),0(Y)) -> #and(isBin(Y),isBinKind(Y)) #41: #plus(0(X),0(Y)) -> #isBin(Y) #42: #plus(0(X),0(Y)) -> #isBinKind(Y) #43: #mult(z(),X) -> #U91(and(isBin(X),isBinKind(X))) #44: #mult(z(),X) -> #and(isBin(X),isBinKind(X)) #45: #mult(z(),X) -> #isBin(X) #46: #mult(z(),X) -> #isBinKind(X) #47: #sum(union(A,B)) -> #U191(and(and(isBag(A),isBagKind(A)),and(isBag(B),isBagKind(B))),A,B) #48: #sum(union(A,B)) -> #and(and(isBag(A),isBagKind(A)),and(isBag(B),isBagKind(B))) #49: #sum(union(A,B)) -> #and(isBag(A),isBagKind(A)) #50: #sum(union(A,B)) -> #isBag(A) #51: #sum(union(A,B)) -> #isBagKind(A) #52: #sum(union(A,B)) -> #and(isBag(B),isBagKind(B)) #53: #sum(union(A,B)) -> #isBag(B) #54: #sum(union(A,B)) -> #isBagKind(B) #55: #isBagKind(union(V1,V2)) -> #and(isBagKind(V1),isBagKind(V2)) #56: #isBagKind(union(V1,V2)) -> #isBagKind(V1) #57: #isBagKind(union(V1,V2)) -> #isBagKind(V2) #58: #isBinKind(mult(V1,V2)) -> #and(isBinKind(V1),isBinKind(V2)) #59: #isBinKind(mult(V1,V2)) -> #isBinKind(V1) #60: #isBinKind(mult(V1,V2)) -> #isBinKind(V2) #61: #U171(tt(),A,B) -> #mult(prod(A),prod(B)) #62: #U171(tt(),A,B) -> #prod(A) #63: #U171(tt(),A,B) -> #prod(B) #64: #U131(tt(),X,Y) -> #0(plus(X,Y)) #65: #U131(tt(),X,Y) -> #plus(X,Y) #66: #U151(tt(),X,Y) -> #0(plus(plus(X,Y),1(z()))) #67: #U151(tt(),X,Y) -> #plus(plus(X,Y),1(z())) #68: #U151(tt(),X,Y) -> #plus(X,Y) #69: #mult(1(X),Y) -> #U111(and(and(isBin(X),isBinKind(X)),and(isBin(Y),isBinKind(Y))),X,Y) #70: #mult(1(X),Y) -> #and(and(isBin(X),isBinKind(X)),and(isBin(Y),isBinKind(Y))) #71: #mult(1(X),Y) -> #and(isBin(X),isBinKind(X)) #72: #mult(1(X),Y) -> #isBin(X) #73: #mult(1(X),Y) -> #isBinKind(X) #74: #mult(1(X),Y) -> #and(isBin(Y),isBinKind(Y)) #75: #mult(1(X),Y) -> #isBin(Y) #76: #mult(1(X),Y) -> #isBinKind(Y) #77: #U52(tt(),V2) -> #U53(isBin(V2)) #78: #U52(tt(),V2) -> #isBin(V2) #79: #mult(x,mult(y,z)) ->= #mult(mult(x,y),z) #80: #mult(x,mult(y,z)) ->= #mult(x,y) #81: #U51(tt(),V1,V2) -> #U52(isBin(V1),V2) #82: #U51(tt(),V1,V2) -> #isBin(V1) #83: #isBin(plus(V1,V2)) -> #U61(and(isBinKind(V1),isBinKind(V2)),V1,V2) #84: #isBin(plus(V1,V2)) -> #and(isBinKind(V1),isBinKind(V2)) #85: #isBin(plus(V1,V2)) -> #isBinKind(V1) #86: #isBin(plus(V1,V2)) -> #isBinKind(V2) #87: #union(x,union(y,z)) ->= #union(union(x,y),z) #88: #union(x,union(y,z)) ->= #union(x,y) #89: #U81(tt(),V1) -> #U82(isBag(V1)) #90: #U81(tt(),V1) -> #isBag(V1) #91: #mult(0(X),Y) -> #U101(and(and(isBin(X),isBinKind(X)),and(isBin(Y),isBinKind(Y))),X,Y) #92: #mult(0(X),Y) -> #and(and(isBin(X),isBinKind(X)),and(isBin(Y),isBinKind(Y))) #93: #mult(0(X),Y) -> #and(isBin(X),isBinKind(X)) #94: #mult(0(X),Y) -> #isBin(X) #95: #mult(0(X),Y) -> #isBinKind(X) #96: #mult(0(X),Y) -> #and(isBin(Y),isBinKind(Y)) #97: #mult(0(X),Y) -> #isBin(Y) #98: #mult(0(X),Y) -> #isBinKind(Y) #99: #isBinKind(plus(V1,V2)) -> #and(isBinKind(V1),isBinKind(V2)) #100: #isBinKind(plus(V1,V2)) -> #isBinKind(V1) #101: #isBinKind(plus(V1,V2)) -> #isBinKind(V2) #102: #isBinKind(0(V1)) -> #isBinKind(V1) #103: #isBagKind(singl(V1)) -> #isBinKind(V1) #104: #U141(tt(),X,Y) -> #plus(X,Y) #105: #prod(union(A,B)) -> #U171(and(and(isBag(A),isBagKind(A)),and(isBag(B),isBagKind(B))),A,B) #106: #prod(union(A,B)) -> #and(and(isBag(A),isBagKind(A)),and(isBag(B),isBagKind(B))) #107: #prod(union(A,B)) -> #and(isBag(A),isBagKind(A)) #108: #prod(union(A,B)) -> #isBag(A) #109: #prod(union(A,B)) -> #isBagKind(A) #110: #prod(union(A,B)) -> #and(isBag(B),isBagKind(B)) #111: #prod(union(A,B)) -> #isBag(B) #112: #prod(union(A,B)) -> #isBagKind(B) #113: #U11(tt(),V1) -> #U12(isBin(V1)) #114: #U11(tt(),V1) -> #isBin(V1) #115: #isBin(mult(V1,V2)) -> #U51(and(isBinKind(V1),isBinKind(V2)),V1,V2) #116: #isBin(mult(V1,V2)) -> #and(isBinKind(V1),isBinKind(V2)) #117: #isBin(mult(V1,V2)) -> #isBinKind(V1) #118: #isBin(mult(V1,V2)) -> #isBinKind(V2) #119: #sum(empty()) -> #0(z()) #120: #U62(tt(),V2) -> #U63(isBin(V2)) #121: #U62(tt(),V2) -> #isBin(V2) #122: #plus(0(X),1(Y)) -> #U141(and(and(isBin(X),isBinKind(X)),and(isBin(Y),isBinKind(Y))),X,Y) #123: #plus(0(X),1(Y)) -> #and(and(isBin(X),isBinKind(X)),and(isBin(Y),isBinKind(Y))) #124: #plus(0(X),1(Y)) -> #and(isBin(X),isBinKind(X)) #125: #plus(0(X),1(Y)) -> #isBin(X) #126: #plus(0(X),1(Y)) -> #isBinKind(X) #127: #plus(0(X),1(Y)) -> #and(isBin(Y),isBinKind(Y)) #128: #plus(0(X),1(Y)) -> #isBin(Y) #129: #plus(0(X),1(Y)) -> #isBinKind(Y) #130: #U22(tt(),V2) -> #U23(isBag(V2)) #131: #U22(tt(),V2) -> #isBag(V2) #132: #U31(tt(),V1) -> #U32(isBin(V1)) #133: #U31(tt(),V1) -> #isBin(V1) #134: #prod(singl(X)) -> #U161(and(isBin(X),isBinKind(X)),X) #135: #prod(singl(X)) -> #and(isBin(X),isBinKind(X)) #136: #prod(singl(X)) -> #isBin(X) #137: #prod(singl(X)) -> #isBinKind(X) #138: #U61(tt(),V1,V2) -> #U62(isBin(V1),V2) #139: #U61(tt(),V1,V2) -> #isBin(V1) #140: #plus(x,plus(y,z)) ->= #plus(plus(x,y),z) #141: #plus(x,plus(y,z)) ->= #plus(x,y) #142: #isBag(singl(V1)) -> #U11(isBinKind(V1),V1) #143: #isBag(singl(V1)) -> #isBinKind(V1) #144: #U41(tt(),V1) -> #U42(isBin(V1)) #145: #U41(tt(),V1) -> #isBin(V1) #146: #U21(tt(),V1,V2) -> #U22(isBag(V1),V2) #147: #U21(tt(),V1,V2) -> #isBag(V1) #148: #isBinKind(sum(V1)) -> #isBagKind(V1) #149: #U191(tt(),A,B) -> #plus(sum(A),sum(B)) #150: #U191(tt(),A,B) -> #sum(A) #151: #U191(tt(),A,B) -> #sum(B) #152: #U101(tt(),X,Y) -> #0(mult(X,Y)) #153: #U101(tt(),X,Y) -> #mult(X,Y) #154: #isBinKind(1(V1)) -> #isBinKind(V1) Number of SCCs: 7, DPs: 56 SCC { #87 #88 } only weak rules. Number of SCCs: 6, DPs: 54 SCC { #62 #63 #105 } POLO(Sum)... succeeded. #0 w: 0 #U72 w: 0 #U32 w: 0 #isBag w: 0 U21 w: x2 + x3 + 3 1 w: x1 + 1 prod w: x1 + 1 U161 w: 0 U11 w: x2 + 3 z w: 1 #U181 w: 0 #prod w: x1 U42 w: 2 U91 w: 0 #U101 w: 0 #U82 w: 0 U71 w: x1 + x2 #isBagKind w: 0 #U81 w: 0 and w: x1 + x2 U131 w: 0 #plus w: 0 U101 w: 0 U111 w: 0 #U23 w: 0 #U53 w: 0 #U121 w: 0 U23 w: x1 U63 w: 2 #U131 w: 0 U72 w: 4 #U52 w: 0 U12 w: 3 sum w: x1 + 1 mult w: x1 + x2 + 2 isBagKind w: 3 isBinKind w: x1 + 2 #U42 w: 0 isBin w: x1 + 1 #U141 w: 0 #U12 w: 0 U141 w: 0 #U171 w: x2 + x3 + 1 #U62 w: 0 #isBinKind w: 0 0 w: x1 + 28382 U191 w: 0 #isBin w: 0 U171 w: 0 union w: x1 + x2 + 5 U62 w: x1 + 3 #U63 w: 0 U151 w: 0 #U111 w: 0 U32 w: x1 + 28385 singl w: x1 U52 w: x1 + 3 plus w: x1 + x2 + 2 U61 w: x1 + x2 + x3 #U51 w: 0 #U11 w: 0 U31 w: x1 + x2 + 28382 #U41 w: 0 #U191 w: 0 empty w: 1143 #U21 w: 0 U81 w: x1 + x2 U82 w: x1 + 1 #U22 w: 0 tt w: 3 #U71 w: 0 #U151 w: 0 isBag w: x1 + 3 U22 w: x1 + x2 U51 w: x1 + x3 #U161 w: 0 #sum w: 0 U53 w: x1 + 6 U41 w: x1 + x2 + 1 #U31 w: 0 #and w: 0 #union w: 0 #U91 w: 0 #mult w: 0 U121 w: 0 #U61 w: 0 U181 w: 0 USABLE RULES: { 5 7 16..18 34..38 48 } Removed DPs: #62 #63 #105 Number of SCCs: 5, DPs: 51 SCC { #47 #150 #151 } POLO(Sum)... succeeded. #0 w: 0 #U72 w: 0 #U32 w: 0 #isBag w: 0 U21 w: x2 + 7 1 w: 1 prod w: x1 + 1 U161 w: 0 U11 w: x2 + 2 z w: 1 #U181 w: 0 #prod w: 0 U42 w: 0 U91 w: 0 #U101 w: 0 #U82 w: 0 U71 w: x1 + x2 #isBagKind w: 0 #U81 w: 0 and w: x2 U131 w: 0 #plus w: 0 U101 w: 0 U111 w: 0 #U23 w: 0 #U53 w: 0 #U121 w: 0 U23 w: x1 + 13 U63 w: 0 #U131 w: 0 U72 w: x1 + 5 #U52 w: 0 U12 w: 3 sum w: x1 + 1 mult w: 1 isBagKind w: 4 isBinKind w: 4 #U42 w: 0 isBin w: x1 + 1 #U141 w: 0 #U12 w: 0 U141 w: 0 #U171 w: 1 #U62 w: 0 #isBinKind w: 0 0 w: x1 + 2 U191 w: 0 #isBin w: 0 U171 w: 0 union w: x1 + x2 + 6 U62 w: x1 + 4 #U63 w: 0 U151 w: 0 #U111 w: 0 U32 w: x1 + 4 singl w: x1 + 1 U52 w: x1 + 4 plus w: 1 U61 w: x1 + x2 + x3 #U51 w: 0 #U11 w: 0 U31 w: x1 + x2 #U41 w: 0 #U191 w: x1 + x2 + x3 empty w: 3 #U21 w: 0 U81 w: x1 + x2 U82 w: x1 + 5 #U22 w: 0 tt w: 4 #U71 w: 0 #U151 w: 0 isBag w: x1 U22 w: x1 + 8 U51 w: x1 + x3 #U161 w: 0 #sum w: x1 + 3 U53 w: x1 + 8 U41 w: x2 + 3 #U31 w: 0 #and w: 0 #union w: 0 #U91 w: 0 #mult w: 0 U121 w: 0 #U61 w: 0 U181 w: 0 USABLE RULES: { 34 38..40 48..54 } Removed DPs: #47 #150 #151 Number of SCCs: 4, DPs: 48 SCC { #19 #56 #57 #59 #60 #100..103 #148 #154 } POLO(Sum)... succeeded. #0 w: 0 #U72 w: 0 #U32 w: 0 #isBag w: 0 U21 w: x2 + 8 1 w: x1 + 1 prod w: x1 + 5 U161 w: 0 U11 w: x2 + 3 z w: 7583 #U181 w: 0 #prod w: 0 U42 w: x1 U91 w: 0 #U101 w: 0 #U82 w: 0 U71 w: x2 + 12 #isBagKind w: x1 #U81 w: 0 and w: x1 + 1 U131 w: 0 #plus w: 0 U101 w: 0 U111 w: 0 #U23 w: 0 #U53 w: 0 #U121 w: 0 U23 w: 14 U63 w: x1 #U131 w: 0 U72 w: x1 + 12 #U52 w: 0 U12 w: 4 sum w: x1 + 17071 mult w: x1 + x2 + 32018 isBagKind w: 5 isBinKind w: x1 #U42 w: 0 isBin w: x1 + 6 #U141 w: 0 #U12 w: 0 U141 w: 0 #U171 w: 1 #U62 w: 0 #isBinKind w: x1 0 w: x1 + 12280 U191 w: 0 #isBin w: 0 U171 w: 0 union w: x1 + x2 + 6 U62 w: x1 + x2 + 7 #U63 w: 0 U151 w: 0 #U111 w: 0 U32 w: x1 + 12287 singl w: x1 + 1 U52 w: 32030 plus w: x1 + x2 + 1 U61 w: x1 + x2 + x3 + 7 #U51 w: 0 #U11 w: 0 U31 w: x1 + 12287 #U41 w: 0 #U191 w: 0 empty w: 3 #U21 w: 0 U81 w: x1 + x2 + 17073 U82 w: x1 + 17078 #U22 w: 0 tt w: 5 #U71 w: 0 #U151 w: 0 isBag w: x1 + 1 U22 w: x1 + 8 U51 w: x1 + x3 + 32024 #U161 w: 0 #sum w: 3 U53 w: x1 + 32025 U41 w: x2 + 8 #U31 w: 0 #and w: 0 #union w: 0 #U91 w: 0 #mult w: 0 U121 w: 0 #U61 w: 0 U181 w: 0 USABLE RULES: { 38 48 } Removed DPs: #19 #56 #57 #59 #60 #100..103 #148 #154 Number of SCCs: 3, DPs: 37 SCC { #34 #69 #79 #80 #91 #153 } POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... Mat2b... failed. Finding a loop... failed.