/export/starexec/sandbox/solver/bin/starexec_run_Default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES Input TRS: 1: 0(\#()) -> \#() 2: +(x,\#()) -> x 3: +(\#(),x) -> x 4: +(0(x),0(y)) -> 0(+(x,y)) 5: +(0(x),1(y)) -> 1(+(x,y)) 6: +(1(x),0(y)) -> 1(+(x,y)) 7: +(1(x),1(y)) -> 0(+(+(x,y),1(\#()))) 8: +(+(x,y),z) -> +(x,+(y,z)) 9: -(\#(),x) -> \#() 10: -(x,\#()) -> x 11: -(0(x),0(y)) -> 0(-(x,y)) 12: -(0(x),1(y)) -> 1(-(-(x,y),1(\#()))) 13: -(1(x),0(y)) -> 1(-(x,y)) 14: -(1(x),1(y)) -> 0(-(x,y)) 15: not(true()) -> false() 16: not(false()) -> true() 17: if(true(),x,y) -> x 18: if(false(),x,y) -> y 19: eq(\#(),\#()) -> true() 20: eq(\#(),1(y)) -> false() 21: eq(1(x),\#()) -> false() 22: eq(\#(),0(y)) -> eq(\#(),y) 23: eq(0(x),\#()) -> eq(x,\#()) 24: eq(1(x),1(y)) -> eq(x,y) 25: eq(0(x),1(y)) -> false() 26: eq(1(x),0(y)) -> false() 27: eq(0(x),0(y)) -> eq(x,y) 28: ge(0(x),0(y)) -> ge(x,y) 29: ge(0(x),1(y)) -> not(ge(y,x)) 30: ge(1(x),0(y)) -> ge(x,y) 31: ge(1(x),1(y)) -> ge(x,y) 32: ge(x,\#()) -> true() 33: ge(\#(),0(x)) -> ge(\#(),x) 34: ge(\#(),1(x)) -> false() 35: log(x) -> -(log'(x),1(\#())) 36: log'(\#()) -> \#() 37: log'(1(x)) -> +(log'(x),1(\#())) 38: log'(0(x)) -> if(ge(x,1(\#())),+(log'(x),1(\#())),\#()) 39: *(\#(),x) -> \#() 40: *(0(x),y) -> 0(*(x,y)) 41: *(1(x),y) -> +(0(*(x,y)),y) 42: *(*(x,y),z) -> *(x,*(y,z)) 43: *(x,+(y,z)) -> +(*(x,y),*(x,z)) 44: app(nil(),l) -> l 45: app(cons(x,l1),l2) -> cons(x,app(l1,l2)) 46: sum(nil()) -> 0(\#()) 47: sum(cons(x,l)) -> +(x,sum(l)) 48: sum(app(l1,l2)) -> +(sum(l1),sum(l2)) 49: prod(nil()) -> 1(\#()) 50: prod(cons(x,l)) -> *(x,prod(l)) 51: prod(app(l1,l2)) -> *(prod(l1),prod(l2)) 52: mem(x,nil()) -> false() 53: mem(x,cons(y,l)) -> if(eq(x,y),true(),mem(x,l)) 54: inter(x,nil()) -> nil() 55: inter(nil(),x) -> nil() 56: inter(app(l1,l2),l3) -> app(inter(l1,l3),inter(l2,l3)) 57: inter(l1,app(l2,l3)) -> app(inter(l1,l2),inter(l1,l3)) 58: inter(cons(x,l1),l2) -> ifinter(mem(x,l2),x,l1,l2) 59: inter(l1,cons(x,l2)) -> ifinter(mem(x,l1),x,l2,l1) 60: ifinter(true(),x,l1,l2) -> cons(x,inter(l1,l2)) 61: ifinter(false(),x,l1,l2) -> inter(l1,l2) Number of strict rules: 61 Direct POLO(bPol) ... failed. Uncurrying ... failed. Dependency Pairs: #1: #*(x,+(y,z)) -> #+(*(x,y),*(x,z)) #2: #*(x,+(y,z)) -> #*(x,y) #3: #*(x,+(y,z)) -> #*(x,z) #4: #ge(0(x),1(y)) -> #not(ge(y,x)) #5: #ge(0(x),1(y)) -> #ge(y,x) #6: #log(x) -> #-(log'(x),1(\#())) #7: #log(x) -> #log'(x) #8: #sum(nil()) -> #0(\#()) #9: #*(*(x,y),z) -> #*(x,*(y,z)) #10: #*(*(x,y),z) -> #*(y,z) #11: #*(1(x),y) -> #+(0(*(x,y)),y) #12: #*(1(x),y) -> #0(*(x,y)) #13: #*(1(x),y) -> #*(x,y) #14: #log'(1(x)) -> #+(log'(x),1(\#())) #15: #log'(1(x)) -> #log'(x) #16: #sum(cons(x,l)) -> #+(x,sum(l)) #17: #sum(cons(x,l)) -> #sum(l) #18: #mem(x,cons(y,l)) -> #if(eq(x,y),true(),mem(x,l)) #19: #mem(x,cons(y,l)) -> #eq(x,y) #20: #mem(x,cons(y,l)) -> #mem(x,l) #21: #sum(app(l1,l2)) -> #+(sum(l1),sum(l2)) #22: #sum(app(l1,l2)) -> #sum(l1) #23: #sum(app(l1,l2)) -> #sum(l2) #24: #inter(cons(x,l1),l2) -> #ifinter(mem(x,l2),x,l1,l2) #25: #inter(cons(x,l1),l2) -> #mem(x,l2) #26: #ifinter(false(),x,l1,l2) -> #inter(l1,l2) #27: #log'(0(x)) -> #if(ge(x,1(\#())),+(log'(x),1(\#())),\#()) #28: #log'(0(x)) -> #ge(x,1(\#())) #29: #log'(0(x)) -> #+(log'(x),1(\#())) #30: #log'(0(x)) -> #log'(x) #31: #+(1(x),0(y)) -> #+(x,y) #32: #inter(l1,cons(x,l2)) -> #ifinter(mem(x,l1),x,l2,l1) #33: #inter(l1,cons(x,l2)) -> #mem(x,l1) #34: #*(0(x),y) -> #0(*(x,y)) #35: #*(0(x),y) -> #*(x,y) #36: #prod(app(l1,l2)) -> #*(prod(l1),prod(l2)) #37: #prod(app(l1,l2)) -> #prod(l1) #38: #prod(app(l1,l2)) -> #prod(l2) #39: #-(1(x),0(y)) -> #-(x,y) #40: #-(0(x),0(y)) -> #0(-(x,y)) #41: #-(0(x),0(y)) -> #-(x,y) #42: #inter(l1,app(l2,l3)) -> #app(inter(l1,l2),inter(l1,l3)) #43: #inter(l1,app(l2,l3)) -> #inter(l1,l2) #44: #inter(l1,app(l2,l3)) -> #inter(l1,l3) #45: #eq(1(x),1(y)) -> #eq(x,y) #46: #eq(0(x),\#()) -> #eq(x,\#()) #47: #app(cons(x,l1),l2) -> #app(l1,l2) #48: #-(0(x),1(y)) -> #-(-(x,y),1(\#())) #49: #-(0(x),1(y)) -> #-(x,y) #50: #ge(1(x),1(y)) -> #ge(x,y) #51: #inter(app(l1,l2),l3) -> #app(inter(l1,l3),inter(l2,l3)) #52: #inter(app(l1,l2),l3) -> #inter(l1,l3) #53: #inter(app(l1,l2),l3) -> #inter(l2,l3) #54: #-(1(x),1(y)) -> #0(-(x,y)) #55: #-(1(x),1(y)) -> #-(x,y) #56: #ge(1(x),0(y)) -> #ge(x,y) #57: #+(1(x),1(y)) -> #0(+(+(x,y),1(\#()))) #58: #+(1(x),1(y)) -> #+(+(x,y),1(\#())) #59: #+(1(x),1(y)) -> #+(x,y) #60: #ge(\#(),0(x)) -> #ge(\#(),x) #61: #+(0(x),1(y)) -> #+(x,y) #62: #ge(0(x),0(y)) -> #ge(x,y) #63: #eq(\#(),0(y)) -> #eq(\#(),y) #64: #eq(0(x),0(y)) -> #eq(x,y) #65: #ifinter(true(),x,l1,l2) -> #inter(l1,l2) #66: #+(+(x,y),z) -> #+(x,+(y,z)) #67: #+(+(x,y),z) -> #+(y,z) #68: #+(0(x),0(y)) -> #0(+(x,y)) #69: #+(0(x),0(y)) -> #+(x,y) #70: #prod(cons(x,l)) -> #*(x,prod(l)) #71: #prod(cons(x,l)) -> #prod(l) Number of SCCs: 14, DPs: 45 SCC { #60 } POLO(Sum)... succeeded. #0 w: 0 1 w: 0 mem w: 0 prod w: 0 #prod w: 0 ifinter w: 0 eq w: 0 false w: 0 #ge w: x2 #mem w: 0 #* w: 0 #log w: 0 \# w: 0 #ifinter w: 0 true w: 0 #eq w: 0 sum w: 0 #not w: 0 log w: 0 0 w: x1 + 1 if w: 0 ge w: 0 nil w: 0 #log' w: 0 - w: 0 #app w: 0 #- w: 0 cons w: 0 #if w: 0 inter w: 0 #inter w: 0 + w: 0 log' w: 0 #sum w: 0 #+ w: 0 not w: 0 * w: 0 app w: 0 USABLE RULES: { } Removed DPs: #60 Number of SCCs: 13, DPs: 44 SCC { #46 } POLO(Sum)... succeeded. #0 w: 0 1 w: 0 mem w: 0 prod w: 0 #prod w: 0 ifinter w: 0 eq w: 0 false w: 0 #ge w: 0 #mem w: 0 #* w: 0 #log w: 0 \# w: 0 #ifinter w: 0 true w: 0 #eq w: x1 sum w: 0 #not w: 0 log w: 0 0 w: x1 + 1 if w: 0 ge w: 0 nil w: 0 #log' w: 0 - w: 0 #app w: 0 #- w: 0 cons w: 0 #if w: 0 inter w: 0 #inter w: 0 + w: 0 log' w: 0 #sum w: 0 #+ w: 0 not w: 0 * w: 0 app w: 0 USABLE RULES: { } Removed DPs: #46 Number of SCCs: 12, DPs: 43 SCC { #63 } POLO(Sum)... succeeded. #0 w: 0 1 w: 0 mem w: 0 prod w: 0 #prod w: 0 ifinter w: 0 eq w: 0 false w: 0 #ge w: 0 #mem w: 0 #* w: 0 #log w: 0 \# w: 0 #ifinter w: 0 true w: 0 #eq w: x2 sum w: 0 #not w: 0 log w: 0 0 w: x1 + 1 if w: 0 ge w: 0 nil w: 0 #log' w: 0 - w: 0 #app w: 0 #- w: 0 cons w: 0 #if w: 0 inter w: 0 #inter w: 0 + w: 0 log' w: 0 #sum w: 0 #+ w: 0 not w: 0 * w: 0 app w: 0 USABLE RULES: { } Removed DPs: #63 Number of SCCs: 11, DPs: 42 SCC { #47 } POLO(Sum)... succeeded. #0 w: 0 1 w: 0 mem w: 0 prod w: 0 #prod w: 0 ifinter w: 0 eq w: 0 false w: 0 #ge w: 0 #mem w: 0 #* w: 0 #log w: 0 \# w: 0 #ifinter w: 0 true w: 0 #eq w: 0 sum w: 0 #not w: 0 log w: 0 0 w: 1 if w: 0 ge w: 0 nil w: 0 #log' w: 0 - w: 0 #app w: x1 #- w: 0 cons w: x2 + 1 #if w: 0 inter w: 0 #inter w: 0 + w: 0 log' w: 0 #sum w: 0 #+ w: 0 not w: 0 * w: 0 app w: 0 USABLE RULES: { } Removed DPs: #47 Number of SCCs: 10, DPs: 41 SCC { #20 } POLO(Sum)... succeeded. #0 w: 0 1 w: 0 mem w: 0 prod w: 0 #prod w: 0 ifinter w: 0 eq w: 0 false w: 0 #ge w: 0 #mem w: x2 #* w: 0 #log w: 0 \# w: 0 #ifinter w: 0 true w: 0 #eq w: 0 sum w: 0 #not w: 0 log w: 0 0 w: 1 if w: 0 ge w: 0 nil w: 0 #log' w: 0 - w: 0 #app w: 0 #- w: 0 cons w: x2 + 1 #if w: 0 inter w: 0 #inter w: 0 + w: 0 log' w: 0 #sum w: 0 #+ w: 0 not w: 0 * w: 0 app w: 0 USABLE RULES: { } Removed DPs: #20 Number of SCCs: 9, DPs: 40 SCC { #15 #30 } POLO(Sum)... succeeded. #0 w: 0 1 w: x1 + 1 mem w: 0 prod w: 0 #prod w: 0 ifinter w: 0 eq w: 0 false w: 0 #ge w: 0 #mem w: 0 #* w: 0 #log w: 0 \# w: 0 #ifinter w: 0 true w: 0 #eq w: 0 sum w: 0 #not w: 0 log w: 0 0 w: x1 + 1 if w: 0 ge w: 0 nil w: 0 #log' w: x1 - w: 0 #app w: 0 #- w: 0 cons w: 1 #if w: 0 inter w: 0 #inter w: 0 + w: 0 log' w: 0 #sum w: 0 #+ w: 0 not w: 0 * w: 0 app w: 0 USABLE RULES: { } Removed DPs: #15 #30 Number of SCCs: 8, DPs: 38 SCC { #45 #64 } POLO(Sum)... succeeded. #0 w: 0 1 w: x1 + 1 mem w: 0 prod w: 0 #prod w: 0 ifinter w: 0 eq w: 0 false w: 0 #ge w: 0 #mem w: 0 #* w: 0 #log w: 0 \# w: 0 #ifinter w: 0 true w: 0 #eq w: x2 sum w: 0 #not w: 0 log w: 0 0 w: x1 + 1 if w: 0 ge w: 0 nil w: 0 #log' w: 0 - w: 0 #app w: 0 #- w: 0 cons w: 1 #if w: 0 inter w: 0 #inter w: 0 + w: 0 log' w: 0 #sum w: 0 #+ w: 0 not w: 0 * w: 0 app w: 0 USABLE RULES: { } Removed DPs: #45 #64 Number of SCCs: 7, DPs: 36 SCC { #17 #22 #23 } POLO(Sum)... succeeded. #0 w: 0 1 w: 1 mem w: 0 prod w: 0 #prod w: 0 ifinter w: 0 eq w: 0 false w: 0 #ge w: 0 #mem w: 0 #* w: 0 #log w: 0 \# w: 0 #ifinter w: 0 true w: 0 #eq w: 0 sum w: 0 #not w: 0 log w: 0 0 w: 1 if w: 0 ge w: 0 nil w: 0 #log' w: 0 - w: 0 #app w: 0 #- w: 0 cons w: x2 + 1 #if w: 0 inter w: 0 #inter w: 0 + w: 0 log' w: 0 #sum w: x1 #+ w: 0 not w: 0 * w: 0 app w: x1 + x2 + 1 USABLE RULES: { } Removed DPs: #17 #22 #23 Number of SCCs: 6, DPs: 33 SCC { #37 #38 #71 } POLO(Sum)... succeeded. #0 w: 0 1 w: 1 mem w: 0 prod w: 0 #prod w: x1 ifinter w: 0 eq w: 0 false w: 0 #ge w: 0 #mem w: 0 #* w: 0 #log w: 0 \# w: 0 #ifinter w: 0 true w: 0 #eq w: 0 sum w: 0 #not w: 0 log w: 0 0 w: 1 if w: 0 ge w: 0 nil w: 0 #log' w: 0 - w: 0 #app w: 0 #- w: 0 cons w: x2 + 1 #if w: 0 inter w: 0 #inter w: 0 + w: 0 log' w: 0 #sum w: 0 #+ w: 0 not w: 0 * w: 0 app w: x1 + x2 + 1 USABLE RULES: { } Removed DPs: #37 #38 #71 Number of SCCs: 5, DPs: 30 SCC { #5 #50 #56 #62 } POLO(Sum)... succeeded. #0 w: 0 1 w: x1 + 1 mem w: 0 prod w: 0 #prod w: 0 ifinter w: 0 eq w: 0 false w: 0 #ge w: x1 + x2 #mem w: 0 #* w: 0 #log w: 0 \# w: 0 #ifinter w: 0 true w: 0 #eq w: 0 sum w: 0 #not w: 0 log w: 0 0 w: x1 + 1 if w: 0 ge w: 0 nil w: 0 #log' w: 0 - w: 0 #app w: 0 #- w: 0 cons w: 1 #if w: 0 inter w: 0 #inter w: 0 + w: 0 log' w: 0 #sum w: 0 #+ w: 0 not w: 0 * w: 0 app w: 1 USABLE RULES: { } Removed DPs: #5 #50 #56 #62 Number of SCCs: 4, DPs: 26 SCC { #39 #41 #48 #49 #55 } POLO(Sum)... succeeded. #0 w: 0 1 w: x1 + 1 mem w: 0 prod w: 0 #prod w: 0 ifinter w: 0 eq w: 0 false w: 0 #ge w: 0 #mem w: 0 #* w: 0 #log w: 0 \# w: 0 #ifinter w: 0 true w: 0 #eq w: 0 sum w: 0 #not w: 0 log w: 0 0 w: x1 + 2 if w: 0 ge w: 0 nil w: 0 #log' w: 0 - w: x1 + x2 + 1 #app w: 0 #- w: x2 cons w: 1 #if w: 0 inter w: 0 #inter w: 0 + w: 0 log' w: 0 #sum w: 0 #+ w: 0 not w: 0 * w: 0 app w: 1 USABLE RULES: { } Removed DPs: #39 #41 #49 #55 Number of SCCs: 4, DPs: 22 SCC { #48 } POLO(Sum)... succeeded. #0 w: 0 1 w: x1 + 1 mem w: 0 prod w: 0 #prod w: 0 ifinter w: 0 eq w: 0 false w: 0 #ge w: 0 #mem w: 0 #* w: 0 #log w: 0 \# w: 0 #ifinter w: 0 true w: 0 #eq w: 0 sum w: 0 #not w: 0 log w: 0 0 w: x1 + 2 if w: 0 ge w: 0 nil w: 0 #log' w: 0 - w: x1 + x2 + 1 #app w: 0 #- w: x1 + x2 cons w: 1 #if w: 0 inter w: 0 #inter w: 0 + w: 0 log' w: 0 #sum w: 0 #+ w: 0 not w: 0 * w: 0 app w: 1 USABLE RULES: { 1 9..14 } Removed DPs: #48 Number of SCCs: 3, DPs: 21 SCC { #2 #3 #9 #10 #13 #35 } POLO(Sum)... succeeded. #0 w: 0 1 w: x1 + 1 mem w: 0 prod w: 0 #prod w: 0 ifinter w: 0 eq w: 0 false w: 0 #ge w: 0 #mem w: 0 #* w: x1 #log w: 0 \# w: 0 #ifinter w: 0 true w: 0 #eq w: 0 sum w: 0 #not w: 0 log w: 0 0 w: x1 + 1 if w: 0 ge w: 0 nil w: 0 #log' w: 0 - w: x1 #app w: 0 #- w: x1 cons w: 1 #if w: 0 inter w: 0 #inter w: 0 + w: x1 log' w: 0 #sum w: 0 #+ w: 0 not w: 0 * w: x1 + x2 + 1 app w: 1 USABLE RULES: { 1 9..14 } Removed DPs: #9 #10 #13 #35 Number of SCCs: 3, DPs: 17 SCC { #2 #3 } POLO(Sum)... POLO(max)... succeeded. #0 w: 0 1 w: 0 mem w: 0 prod w: 0 #prod w: 0 ifinter w: 0 eq w: 0 false w: 0 #ge w: 0 #mem w: 0 #* w: max(x2 + 1) #log w: 0 \# w: 0 #ifinter w: 0 true w: 0 #eq w: 0 sum w: 0 #not w: 0 log w: 0 0 w: 0 if w: 0 ge w: 0 nil w: 0 #log' w: 0 - w: 0 #app w: 0 #- w: 0 cons w: 0 #if w: 0 inter w: 0 #inter w: 0 + w: max(x1 + 1, x2 + 1) log' w: 0 #sum w: 0 #+ w: 0 not w: 0 * w: 0 app w: 0 USABLE RULES: { } Removed DPs: #2 #3 Number of SCCs: 2, DPs: 15 SCC { #31 #58 #59 #61 #66 #67 #69 } POLO(Sum)... succeeded. #0 w: 0 1 w: x1 + 7 mem w: 0 prod w: 0 #prod w: 0 ifinter w: 0 eq w: 0 false w: 0 #ge w: 0 #mem w: 0 #* w: 0 #log w: 0 \# w: 5 #ifinter w: 0 true w: 0 #eq w: 0 sum w: 0 #not w: 0 log w: 0 0 w: x1 + 1 if w: 0 ge w: 0 nil w: 0 #log' w: 0 - w: 5 #app w: 0 #- w: 0 cons w: 1 #if w: 0 inter w: 0 #inter w: 0 + w: x1 + x2 + 1 log' w: 0 #sum w: 0 #+ w: x1 + x2 not w: 0 * w: 1 app w: 1 USABLE RULES: { 1..8 } Removed DPs: #31 #58 #59 #61 #67 #69 Number of SCCs: 2, DPs: 9 SCC { #66 } POLO(Sum)... succeeded. #0 w: 0 1 w: x1 + 7 mem w: 0 prod w: 0 #prod w: 0 ifinter w: 0 eq w: 0 false w: 0 #ge w: 0 #mem w: 0 #* w: 0 #log w: 0 \# w: 5 #ifinter w: 0 true w: 0 #eq w: 0 sum w: 0 #not w: 0 log w: 0 0 w: x1 + 1 if w: 0 ge w: 0 nil w: 0 #log' w: 0 - w: 5 #app w: 0 #- w: 0 cons w: 1 #if w: 0 inter w: 0 #inter w: 0 + w: x1 + x2 + 1 log' w: 0 #sum w: 0 #+ w: x1 not w: 0 * w: 1 app w: 1 USABLE RULES: { 1..8 } Removed DPs: #66 Number of SCCs: 1, DPs: 8 SCC { #24 #26 #32 #43 #44 #52 #53 #65 } POLO(Sum)... succeeded. #0 w: 0 1 w: x1 + 7 mem w: x1 + 9 prod w: 0 #prod w: 0 ifinter w: 0 eq w: x2 + 1 false w: 9 #ge w: 0 #mem w: 0 #* w: 0 #log w: 0 \# w: 5 #ifinter w: x3 + x4 + 1 true w: 7 #eq w: 0 sum w: 0 #not w: 0 log w: 0 0 w: x1 + 1 if w: x2 ge w: 0 nil w: 1 #log' w: 0 - w: 5 #app w: 0 #- w: 0 cons w: x1 + x2 + 2 #if w: 0 inter w: 0 #inter w: x1 + x2 + w: x1 + x2 + 1 log' w: 0 #sum w: 0 #+ w: x1 not w: 0 * w: 1 app w: x1 + x2 + 1 USABLE RULES: { 1..8 17 52 } Removed DPs: #24 #26 #32 #43 #44 #52 #53 #65 Number of SCCs: 0, DPs: 0