MAYBE Input TRS: AC symbols: plus union mult 1: union(X,empty()) -> X 2: union(empty(),X) -> X 3: 0(z()) -> z() 4: U11(tt(),X,Y) -> U12(tt(),X,Y) 5: U12(tt(),X,Y) -> 0(mult(X,Y)) 6: U21(tt(),X,Y) -> U22(tt(),X,Y) 7: U22(tt(),X,Y) -> plus(0(mult(X,Y)),Y) 8: U31(tt(),X,Y) -> U32(tt(),X,Y) 9: U32(tt(),X,Y) -> 0(plus(X,Y)) 10: U41(tt(),X,Y) -> U42(tt(),X,Y) 11: U42(tt(),X,Y) -> 1(plus(X,Y)) 12: U51(tt(),X,Y) -> U52(tt(),X,Y) 13: U52(tt(),X,Y) -> 0(plus(plus(X,Y),1(z()))) 14: U61(tt(),A,B) -> U62(tt(),A,B) 15: U62(tt(),A,B) -> mult(prod(A),prod(B)) 16: U71(tt(),A,B) -> U72(tt(),A,B) 17: U72(tt(),A,B) -> plus(sum(A),sum(B)) 18: mult(z(),X) -> z() 19: mult(0(X),Y) -> U11(tt(),X,Y) 20: mult(1(X),Y) -> U21(tt(),X,Y) 21: plus(z(),X) -> X 22: plus(0(X),0(Y)) -> U31(tt(),X,Y) 23: plus(0(X),1(Y)) -> U41(tt(),X,Y) 24: plus(1(X),1(Y)) -> U51(tt(),X,Y) 25: prod(empty()) -> 1(z()) 26: prod(singl(X)) -> X 27: prod(union(A,B)) -> U61(tt(),A,B) 28: sum(empty()) -> 0(z()) 29: sum(singl(X)) -> X 30: sum(union(A,B)) -> U71(tt(),A,B) Number of strict rules: 30 Direct POLO(bPol) ... failed. Uncurrying U71 U41 U42 U32 U12 U51 U22 U62 U72 U11 U21 U31 U61 U52 AC symbols: plus union mult 1: union(X,empty()) -> X 2: union(empty(),X) -> X 3: 0(z()) -> z() 4: U11^1_tt(X,Y) -> U12^1_tt(X,Y) 5: U12^1_tt(X,Y) -> 0(mult(X,Y)) 6: U21^1_tt(X,Y) -> U22^1_tt(X,Y) 7: U22^1_tt(X,Y) -> plus(0(mult(X,Y)),Y) 8: U31^1_tt(X,Y) -> U32^1_tt(X,Y) 9: U32^1_tt(X,Y) -> 0(plus(X,Y)) 10: U41^1_tt(X,Y) -> U42^1_tt(X,Y) 11: U42^1_tt(X,Y) -> 1(plus(X,Y)) 12: U51^1_tt(X,Y) -> U52^1_tt(X,Y) 13: U52^1_tt(X,Y) -> 0(plus(plus(X,Y),1(z()))) 14: U61^1_tt(A,B) -> U62^1_tt(A,B) 15: U62^1_tt(A,B) -> mult(prod(A),prod(B)) 16: U71^1_tt(A,B) -> U72^1_tt(A,B) 17: U72^1_tt(A,B) -> plus(sum(A),sum(B)) 18: mult(z(),X) -> z() 19: mult(0(X),Y) -> U11^1_tt(X,Y) 20: mult(1(X),Y) -> U21^1_tt(X,Y) 21: plus(z(),X) -> X 22: plus(0(X),0(Y)) -> U31^1_tt(X,Y) 23: plus(0(X),1(Y)) -> U41^1_tt(X,Y) 24: plus(1(X),1(Y)) -> U51^1_tt(X,Y) 25: prod(empty()) -> 1(z()) 26: prod(singl(X)) -> X 27: prod(union(A,B)) -> U61^1_tt(A,B) 28: sum(empty()) -> 0(z()) 29: sum(singl(X)) -> X 30: sum(union(A,B)) -> U71^1_tt(A,B) 31: U52(tt(),_2,_3) ->= U52^1_tt(_2,_3) 32: U61(tt(),_2,_3) ->= U61^1_tt(_2,_3) 33: U31(tt(),_2,_3) ->= U31^1_tt(_2,_3) 34: U21(tt(),_2,_3) ->= U21^1_tt(_2,_3) 35: U11(tt(),_2,_3) ->= U11^1_tt(_2,_3) 36: U72(tt(),_2,_3) ->= U72^1_tt(_2,_3) 37: U62(tt(),_2,_3) ->= U62^1_tt(_2,_3) 38: U22(tt(),_2,_3) ->= U22^1_tt(_2,_3) 39: U51(tt(),_2,_3) ->= U51^1_tt(_2,_3) 40: U12(tt(),_2,_3) ->= U12^1_tt(_2,_3) 41: U32(tt(),_2,_3) ->= U32^1_tt(_2,_3) 42: U42(tt(),_2,_3) ->= U42^1_tt(_2,_3) 43: U41(tt(),_2,_3) ->= U41^1_tt(_2,_3) 44: U71(tt(),_2,_3) ->= U71^1_tt(_2,_3) Number of strict rules: 30 Direct POLO(bPol) ... failed. Dependency Pairs: #1: #U41(tt(),_2,_3) ->? #U41^1_tt(_2,_3) #2: #U11(tt(),_2,_3) ->? #U11^1_tt(_2,_3) #3: #union(x,union(y,z)) ->= #union(union(x,y),z) #4: #union(x,union(y,z)) ->= #union(x,y) #5: #U42(tt(),_2,_3) ->? #U42^1_tt(_2,_3) #6: #U32(tt(),_2,_3) ->? #U32^1_tt(_2,_3) #7: #U62(tt(),_2,_3) ->? #U62^1_tt(_2,_3) #8: #mult(x,mult(y,z)) ->= #mult(mult(x,y),z) #9: #mult(x,mult(y,z)) ->= #mult(x,y) #10: #U22(tt(),_2,_3) ->? #U22^1_tt(_2,_3) #11: #U21^1_tt(X,Y) -> #U22^1_tt(X,Y) #12: #U12(tt(),_2,_3) ->? #U12^1_tt(_2,_3) #13: #U52^1_tt(X,Y) -> #0(plus(plus(X,Y),1(z()))) #14: #U52^1_tt(X,Y) -> #plus(plus(X,Y),1(z())) #15: #U52^1_tt(X,Y) -> #plus(X,Y) #16: #U32^1_tt(X,Y) -> #0(plus(X,Y)) #17: #U32^1_tt(X,Y) -> #plus(X,Y) #18: #U42^1_tt(X,Y) -> #plus(X,Y) #19: #plus(1(X),1(Y)) -> #U51^1_tt(X,Y) #20: #plus(0(X),1(Y)) -> #U41^1_tt(X,Y) #21: #plus(x,plus(y,z)) ->= #plus(plus(x,y),z) #22: #plus(x,plus(y,z)) ->= #plus(x,y) #23: #U51^1_tt(X,Y) -> #U52^1_tt(X,Y) #24: #U52(tt(),_2,_3) ->? #U52^1_tt(_2,_3) #25: #U61^1_tt(A,B) -> #U62^1_tt(A,B) #26: #sum(union(A,B)) -> #U71^1_tt(A,B) #27: #mult(1(X),Y) -> #U21^1_tt(X,Y) #28: #U22^1_tt(X,Y) -> #plus(0(mult(X,Y)),Y) #29: #U22^1_tt(X,Y) -> #0(mult(X,Y)) #30: #U22^1_tt(X,Y) -> #mult(X,Y) #31: #U51(tt(),_2,_3) ->? #U51^1_tt(_2,_3) #32: #U41^1_tt(X,Y) -> #U42^1_tt(X,Y) #33: #U31(tt(),_2,_3) ->? #U31^1_tt(_2,_3) #34: #U12^1_tt(X,Y) -> #0(mult(X,Y)) #35: #U12^1_tt(X,Y) -> #mult(X,Y) #36: #U71(tt(),_2,_3) ->? #U71^1_tt(_2,_3) #37: #sum(empty()) -> #0(z()) #38: #plus(0(X),0(Y)) -> #U31^1_tt(X,Y) #39: #U21(tt(),_2,_3) ->? #U21^1_tt(_2,_3) #40: #prod(union(A,B)) -> #U61^1_tt(A,B) #41: #U72^1_tt(A,B) -> #plus(sum(A),sum(B)) #42: #U72^1_tt(A,B) -> #sum(A) #43: #U72^1_tt(A,B) -> #sum(B) #44: #U61(tt(),_2,_3) ->? #U61^1_tt(_2,_3) #45: #mult(0(X),Y) -> #U11^1_tt(X,Y) #46: #U72(tt(),_2,_3) ->? #U72^1_tt(_2,_3) #47: #U71^1_tt(A,B) -> #U72^1_tt(A,B) #48: #U31^1_tt(X,Y) -> #U32^1_tt(X,Y) #49: #U62^1_tt(A,B) -> #mult(prod(A),prod(B)) #50: #U62^1_tt(A,B) -> #prod(A) #51: #U62^1_tt(A,B) -> #prod(B) #52: #U11^1_tt(X,Y) -> #U12^1_tt(X,Y) Number of SCCs: 5, DPs: 30 SCC { #3 #4 } only weak rules. Number of SCCs: 4, DPs: 28 SCC { #25 #40 #50 #51 } POLO(Sum)... succeeded. #0 w: 0 #U72 w: 0 #U32 w: 0 U21 w: 0 1 w: 0 prod w: 0 U71^1_tt w: 0 U11 w: 0 #U72^1_tt w: 0 #U32^1_tt w: 0 #U42^1_tt w: 0 z w: 0 #prod w: x1 #U52^1_tt w: 0 U42 w: 0 #U31^1_tt w: 0 #U22^1_tt w: 0 U61^1_tt w: 0 U71 w: 0 #plus w: 0 U52^1_tt w: 0 U41^1_tt w: 0 U72 w: 0 #U62^1_tt w: x1 + x2 + 1 U62^1_tt w: 0 #U52 w: 0 U12 w: 0 U22^1_tt w: 0 sum w: 0 mult w: 0 #U51^1_tt w: 0 #U42 w: 0 #U12 w: 0 #U62 w: 0 0 w: 0 U21^1_tt w: 0 #U21^1_tt w: 0 U42^1_tt w: 0 union w: x1 + x2 + 3 U11^1_tt w: 0 U62 w: 0 #U71^1_tt w: 0 U31^1_tt w: 0 #U12^1_tt w: 0 U32 w: 0 U51^1_tt w: 0 U12^1_tt w: 0 singl w: 0 U52 w: 0 plus w: 0 U61 w: 0 #U51 w: 0 #U11 w: 0 U31 w: 0 #U41^1_tt w: 0 #U41 w: 0 empty w: 0 #U21 w: 0 #U22 w: 0 tt w: 0 U32^1_tt w: 0 #U71 w: 0 U72^1_tt w: 0 U22 w: 0 U51 w: 0 #sum w: 0 #U61^1_tt w: x1 + x2 + 2 U41 w: 0 #U31 w: 0 #union w: 0 #mult w: 0 #U61 w: 0 #U11^1_tt w: 0 USABLE RULES: { } Removed DPs: #25 #40 #50 #51 Number of SCCs: 3, DPs: 24 SCC { #26 #42 #43 #47 } POLO(Sum)... succeeded. #0 w: 0 #U72 w: 0 #U32 w: 0 U21 w: 0 1 w: 0 prod w: 0 U71^1_tt w: 0 U11 w: 0 #U72^1_tt w: x1 + x2 + 1 #U32^1_tt w: 0 #U42^1_tt w: 0 z w: 0 #prod w: 0 #U52^1_tt w: 0 U42 w: 0 #U31^1_tt w: 0 #U22^1_tt w: 0 U61^1_tt w: 0 U71 w: 0 #plus w: 0 U52^1_tt w: 0 U41^1_tt w: 0 U72 w: 0 #U62^1_tt w: 1 U62^1_tt w: 0 #U52 w: 0 U12 w: 0 U22^1_tt w: 0 sum w: 0 mult w: 0 #U51^1_tt w: 0 #U42 w: 0 #U12 w: 0 #U62 w: 0 0 w: 0 U21^1_tt w: 0 #U21^1_tt w: 0 U42^1_tt w: 0 union w: x1 + x2 + 3 U11^1_tt w: 0 U62 w: 0 #U71^1_tt w: x1 + x2 + 2 U31^1_tt w: 0 #U12^1_tt w: 0 U32 w: 0 U51^1_tt w: 0 U12^1_tt w: 0 singl w: 0 U52 w: 0 plus w: 0 U61 w: 0 #U51 w: 0 #U11 w: 0 U31 w: 0 #U41^1_tt w: 0 #U41 w: 0 empty w: 0 #U21 w: 0 #U22 w: 0 tt w: 0 U32^1_tt w: 0 #U71 w: 0 U72^1_tt w: 0 U22 w: 0 U51 w: 0 #sum w: x1 #U61^1_tt w: 2 U41 w: 0 #U31 w: 0 #union w: 0 #mult w: 0 #U61 w: 0 #U11^1_tt w: 0 USABLE RULES: { } Removed DPs: #26 #42 #43 #47 Number of SCCs: 2, DPs: 20 SCC { #8 #9 #11 #27 #30 #35 #45 #52 } POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... succeeded. #0 w: max(x1 - 1, 0) #U72 w: max(x2 - 1, 0) #U32 w: max(x2 - 1, 0) U21 w: 0 1 w: max(x1, 0) prod w: 0 U71^1_tt w: max(x1 - 1, 0) U11 w: max(x1 - 1, 0) #U72^1_tt w: max(x2 - 1, 0) #U32^1_tt w: 0 #U42^1_tt w: 0 z w: 0 #prod w: 0 #U52^1_tt w: 0 U42 w: max(x3 - 1, 0) #U31^1_tt w: 0 #U22^1_tt w: max(x1 + x2 + 1, 0) U61^1_tt w: max(x2 - 1, 0) U71 w: max(x3 - 1, 0) #plus w: 0 U52^1_tt w: max(x1, x2, 0) U41^1_tt w: max(x1, x2, 0) U72 w: max(x2 - 1, 0) #U62^1_tt w: max(x1 - 1, 0) U62^1_tt w: 0 #U52 w: max(x1 - 1, 0) U12 w: max(x1 - 1, 0) U22^1_tt w: max(x1 + x2 + 1, 0) sum w: 0 mult w: max(x1 + x2 + 1, 0) #U51^1_tt w: 0 #U42 w: 0 #U12 w: max(x1 - 1, 0) #U62 w: max(x2 - 1, 0) 0 w: max(x1, 0) U21^1_tt w: max(x1 + x2 + 1, 0) #U21^1_tt w: max(x1 + x2 + 1, 0) U42^1_tt w: max(x1, x2, 0) union w: max(x1 + x2 - 1, 0) U11^1_tt w: max(x1 + x2 + 1, 0) U62 w: max(x3 - 1, 0) #U71^1_tt w: max(x1 - 1, 0) U31^1_tt w: max(x1, x2, 0) #U12^1_tt w: max(x1 + x2 + 1, 0) U32 w: max(x1 - 1, 0) U51^1_tt w: max(x1, x2, 0) U12^1_tt w: max(x1 + x2 + 1, 0) singl w: max(x1 - 1, 0) U52 w: max(x2 - 1, 0) plus w: max(x1, x2, 0) U61 w: max(x1 - 1, 0) #U51 w: max(x2 - 1, 0) #U11 w: max(x3 - 1, 0) U31 w: max(x1 - 1, 0) #U41^1_tt w: 0 #U41 w: max(x2 - 1, 0) empty w: 0 #U21 w: max(x1 - 1, 0) #U22 w: max(x1 - 1, 0) tt w: 0 U32^1_tt w: max(x1, x2, 0) #U71 w: 0 U72^1_tt w: 0 U22 w: max(x3 - 1, 0) U51 w: max(x2 - 1, 0) #sum w: max(x1 - 1, 0) #U61^1_tt w: max(x1 - 1, 0) U41 w: max(x1 - 1, 0) #U31 w: max(x3 - 1, 0) #union w: max(x1 + x2 - 1, 0) #mult w: max(x1 + x2 + 1, 0) #U61 w: max(x1 - 1, 0) #U11^1_tt w: max(x1 + x2 + 1, 0) USABLE RULES: { 3..13 18..24 45 47 } Removed DPs: #9 Number of SCCs: 2, DPs: 19 SCC { #8 #11 #27 #30 #35 #45 #52 } POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... Mat2b... failed. Finding a loop... failed.