/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES Input TRS: 1: active(fib(N)) -> mark(sel(N,fib1(s(0()),s(0())))) 2: active(fib1(X,Y)) -> mark(cons(X,fib1(Y,add(X,Y)))) 3: active(add(0(),X)) -> mark(X) 4: active(add(s(X),Y)) -> mark(s(add(X,Y))) 5: active(sel(0(),cons(X,XS))) -> mark(X) 6: active(sel(s(N),cons(X,XS))) -> mark(sel(N,XS)) 7: mark(fib(X)) -> active(fib(mark(X))) 8: mark(sel(X1,X2)) -> active(sel(mark(X1),mark(X2))) 9: mark(fib1(X1,X2)) -> active(fib1(mark(X1),mark(X2))) 10: mark(s(X)) -> active(s(mark(X))) 11: mark(0()) -> active(0()) 12: mark(cons(X1,X2)) -> active(cons(mark(X1),X2)) 13: mark(add(X1,X2)) -> active(add(mark(X1),mark(X2))) 14: fib(mark(X)) -> fib(X) 15: fib(active(X)) -> fib(X) 16: sel(mark(X1),X2) -> sel(X1,X2) 17: sel(X1,mark(X2)) -> sel(X1,X2) 18: sel(active(X1),X2) -> sel(X1,X2) 19: sel(X1,active(X2)) -> sel(X1,X2) 20: fib1(mark(X1),X2) -> fib1(X1,X2) 21: fib1(X1,mark(X2)) -> fib1(X1,X2) 22: fib1(active(X1),X2) -> fib1(X1,X2) 23: fib1(X1,active(X2)) -> fib1(X1,X2) 24: s(mark(X)) -> s(X) 25: s(active(X)) -> s(X) 26: cons(mark(X1),X2) -> cons(X1,X2) 27: cons(X1,mark(X2)) -> cons(X1,X2) 28: cons(active(X1),X2) -> cons(X1,X2) 29: cons(X1,active(X2)) -> cons(X1,X2) 30: add(mark(X1),X2) -> add(X1,X2) 31: add(X1,mark(X2)) -> add(X1,X2) 32: add(active(X1),X2) -> add(X1,X2) 33: add(X1,active(X2)) -> add(X1,X2) Number of strict rules: 33 Direct poly ... failed. Freezing ... failed. Dependency Pairs: #1: #active(fib1(X,Y)) -> #mark(cons(X,fib1(Y,add(X,Y)))) #2: #active(fib1(X,Y)) -> #cons(X,fib1(Y,add(X,Y))) #3: #active(fib1(X,Y)) -> #fib1(Y,add(X,Y)) #4: #active(fib1(X,Y)) -> #add(X,Y) #5: #cons(X1,active(X2)) -> #cons(X1,X2) #6: #active(sel(s(N),cons(X,XS))) -> #mark(sel(N,XS)) #7: #active(sel(s(N),cons(X,XS))) -> #sel(N,XS) #8: #mark(add(X1,X2)) -> #active(add(mark(X1),mark(X2))) #9: #mark(add(X1,X2)) -> #add(mark(X1),mark(X2)) #10: #mark(add(X1,X2)) -> #mark(X1) #11: #mark(add(X1,X2)) -> #mark(X2) #12: #mark(fib1(X1,X2)) -> #active(fib1(mark(X1),mark(X2))) #13: #mark(fib1(X1,X2)) -> #fib1(mark(X1),mark(X2)) #14: #mark(fib1(X1,X2)) -> #mark(X1) #15: #mark(fib1(X1,X2)) -> #mark(X2) #16: #mark(0()) -> #active(0()) #17: #s(mark(X)) -> #s(X) #18: #fib1(X1,active(X2)) -> #fib1(X1,X2) #19: #mark(cons(X1,X2)) -> #active(cons(mark(X1),X2)) #20: #mark(cons(X1,X2)) -> #cons(mark(X1),X2) #21: #mark(cons(X1,X2)) -> #mark(X1) #22: #add(X1,mark(X2)) -> #add(X1,X2) #23: #fib(mark(X)) -> #fib(X) #24: #add(mark(X1),X2) -> #add(X1,X2) #25: #s(active(X)) -> #s(X) #26: #fib1(mark(X1),X2) -> #fib1(X1,X2) #27: #mark(fib(X)) -> #active(fib(mark(X))) #28: #mark(fib(X)) -> #fib(mark(X)) #29: #mark(fib(X)) -> #mark(X) #30: #mark(s(X)) -> #active(s(mark(X))) #31: #mark(s(X)) -> #s(mark(X)) #32: #mark(s(X)) -> #mark(X) #33: #add(X1,active(X2)) -> #add(X1,X2) #34: #active(sel(0(),cons(X,XS))) -> #mark(X) #35: #cons(active(X1),X2) -> #cons(X1,X2) #36: #fib1(active(X1),X2) -> #fib1(X1,X2) #37: #cons(X1,mark(X2)) -> #cons(X1,X2) #38: #sel(X1,mark(X2)) -> #sel(X1,X2) #39: #add(active(X1),X2) -> #add(X1,X2) #40: #sel(X1,active(X2)) -> #sel(X1,X2) #41: #cons(mark(X1),X2) -> #cons(X1,X2) #42: #fib1(X1,mark(X2)) -> #fib1(X1,X2) #43: #sel(mark(X1),X2) -> #sel(X1,X2) #44: #active(add(0(),X)) -> #mark(X) #45: #active(fib(N)) -> #mark(sel(N,fib1(s(0()),s(0())))) #46: #active(fib(N)) -> #sel(N,fib1(s(0()),s(0()))) #47: #active(fib(N)) -> #fib1(s(0()),s(0())) #48: #active(fib(N)) -> #s(0()) #49: #active(fib(N)) -> #s(0()) #50: #mark(sel(X1,X2)) -> #active(sel(mark(X1),mark(X2))) #51: #mark(sel(X1,X2)) -> #sel(mark(X1),mark(X2)) #52: #mark(sel(X1,X2)) -> #mark(X1) #53: #mark(sel(X1,X2)) -> #mark(X2) #54: #fib(active(X)) -> #fib(X) #55: #active(add(s(X),Y)) -> #mark(s(add(X,Y))) #56: #active(add(s(X),Y)) -> #s(add(X,Y)) #57: #active(add(s(X),Y)) -> #add(X,Y) #58: #sel(active(X1),X2) -> #sel(X1,X2) Number of SCCs: 7, DPs: 39 SCC { #23 #54 } Sum... succeeded. #cons(x1,x2) w: (0) s(x1) w: (0) #fib1(x1,x2) w: (0) fib1(x1,x2) w: (0) fib(x1) w: (0) #mark(x1) w: (0) 0() w: (0) #sel(x1,x2) w: (0) sel(x1,x2) w: (0) #s(x1) w: (0) mark(x1) w: (1 + x1) active(x1) w: (1 + x1) cons(x1,x2) w: (0) #active(x1) w: (0) #add(x1,x2) w: (0) add(x1,x2) w: (0) #fib(x1) w: (x1) USABLE RULES: { } Removed DPs: #23 #54 Number of SCCs: 6, DPs: 37 SCC { #17 #25 } Sum... succeeded. #cons(x1,x2) w: (0) s(x1) w: (0) #fib1(x1,x2) w: (0) fib1(x1,x2) w: (0) fib(x1) w: (0) #mark(x1) w: (0) 0() w: (0) #sel(x1,x2) w: (0) sel(x1,x2) w: (0) #s(x1) w: (x1) mark(x1) w: (1 + x1) active(x1) w: (1 + x1) cons(x1,x2) w: (0) #active(x1) w: (0) #add(x1,x2) w: (0) add(x1,x2) w: (0) #fib(x1) w: (0) USABLE RULES: { } Removed DPs: #17 #25 Number of SCCs: 5, DPs: 35 SCC { #22 #24 #33 #39 } Sum... succeeded. #cons(x1,x2) w: (0) s(x1) w: (0) #fib1(x1,x2) w: (0) fib1(x1,x2) w: (0) fib(x1) w: (0) #mark(x1) w: (0) 0() w: (0) #sel(x1,x2) w: (0) sel(x1,x2) w: (0) #s(x1) w: (0) mark(x1) w: (1 + x1) active(x1) w: (1 + x1) cons(x1,x2) w: (0) #active(x1) w: (0) #add(x1,x2) w: (x2) add(x1,x2) w: (0) #fib(x1) w: (0) USABLE RULES: { } Removed DPs: #22 #33 Number of SCCs: 5, DPs: 33 SCC { #24 #39 } Sum... succeeded. #cons(x1,x2) w: (0) s(x1) w: (0) #fib1(x1,x2) w: (0) fib1(x1,x2) w: (0) fib(x1) w: (0) #mark(x1) w: (0) 0() w: (0) #sel(x1,x2) w: (0) sel(x1,x2) w: (0) #s(x1) w: (0) mark(x1) w: (1 + x1) active(x1) w: (1 + x1) cons(x1,x2) w: (0) #active(x1) w: (0) #add(x1,x2) w: (x1) add(x1,x2) w: (0) #fib(x1) w: (0) USABLE RULES: { } Removed DPs: #24 #39 Number of SCCs: 4, DPs: 31 SCC { #18 #26 #36 #42 } Sum... succeeded. #cons(x1,x2) w: (0) s(x1) w: (0) #fib1(x1,x2) w: (x1) fib1(x1,x2) w: (0) fib(x1) w: (0) #mark(x1) w: (0) 0() w: (0) #sel(x1,x2) w: (0) sel(x1,x2) w: (0) #s(x1) w: (0) mark(x1) w: (1 + x1) active(x1) w: (1 + x1) cons(x1,x2) w: (0) #active(x1) w: (0) #add(x1,x2) w: (0) add(x1,x2) w: (0) #fib(x1) w: (0) USABLE RULES: { } Removed DPs: #26 #36 Number of SCCs: 4, DPs: 29 SCC { #18 #42 } Sum... succeeded. #cons(x1,x2) w: (0) s(x1) w: (0) #fib1(x1,x2) w: (x2) fib1(x1,x2) w: (0) fib(x1) w: (0) #mark(x1) w: (0) 0() w: (0) #sel(x1,x2) w: (0) sel(x1,x2) w: (0) #s(x1) w: (0) mark(x1) w: (1 + x1) active(x1) w: (1 + x1) cons(x1,x2) w: (0) #active(x1) w: (0) #add(x1,x2) w: (0) add(x1,x2) w: (0) #fib(x1) w: (0) USABLE RULES: { } Removed DPs: #18 #42 Number of SCCs: 3, DPs: 27 SCC { #38 #40 #43 #58 } Sum... succeeded. #cons(x1,x2) w: (0) s(x1) w: (0) #fib1(x1,x2) w: (0) fib1(x1,x2) w: (0) fib(x1) w: (0) #mark(x1) w: (0) 0() w: (0) #sel(x1,x2) w: (x2) sel(x1,x2) w: (0) #s(x1) w: (0) mark(x1) w: (1 + x1) active(x1) w: (1 + x1) cons(x1,x2) w: (0) #active(x1) w: (0) #add(x1,x2) w: (0) add(x1,x2) w: (0) #fib(x1) w: (0) USABLE RULES: { } Removed DPs: #38 #40 Number of SCCs: 3, DPs: 25 SCC { #43 #58 } Sum... succeeded. #cons(x1,x2) w: (0) s(x1) w: (0) #fib1(x1,x2) w: (0) fib1(x1,x2) w: (0) fib(x1) w: (0) #mark(x1) w: (0) 0() w: (0) #sel(x1,x2) w: (x1) sel(x1,x2) w: (0) #s(x1) w: (0) mark(x1) w: (1 + x1) active(x1) w: (1 + x1) cons(x1,x2) w: (0) #active(x1) w: (0) #add(x1,x2) w: (0) add(x1,x2) w: (0) #fib(x1) w: (0) USABLE RULES: { } Removed DPs: #43 #58 Number of SCCs: 2, DPs: 23 SCC { #5 #35 #37 #41 } Sum... succeeded. #cons(x1,x2) w: (x2) s(x1) w: (0) #fib1(x1,x2) w: (0) fib1(x1,x2) w: (0) fib(x1) w: (0) #mark(x1) w: (0) 0() w: (0) #sel(x1,x2) w: (0) sel(x1,x2) w: (0) #s(x1) w: (0) mark(x1) w: (1 + x1) active(x1) w: (1 + x1) cons(x1,x2) w: (0) #active(x1) w: (0) #add(x1,x2) w: (0) add(x1,x2) w: (0) #fib(x1) w: (0) USABLE RULES: { } Removed DPs: #5 #37 Number of SCCs: 2, DPs: 21 SCC { #35 #41 } Sum... succeeded. #cons(x1,x2) w: (x1) s(x1) w: (0) #fib1(x1,x2) w: (0) fib1(x1,x2) w: (0) fib(x1) w: (0) #mark(x1) w: (0) 0() w: (0) #sel(x1,x2) w: (0) sel(x1,x2) w: (0) #s(x1) w: (0) mark(x1) w: (1 + x1) active(x1) w: (1 + x1) cons(x1,x2) w: (0) #active(x1) w: (0) #add(x1,x2) w: (0) add(x1,x2) w: (0) #fib(x1) w: (0) USABLE RULES: { } Removed DPs: #35 #41 Number of SCCs: 1, DPs: 19 SCC { #1 #6 #8 #10..12 #14 #15 #21 #27 #29 #32 #34 #44 #45 #50 #52 #53 #55 } Sum... Max... succeeded. #cons(x1,x2) w: (0) s(x1) w: (x1) #fib1(x1,x2) w: (0) fib1(x1,x2) w: (max{8366 + x2, 8366 + x1}) fib(x1) w: (49432 + x1) #mark(x1) w: (32285 + x1) 0() w: (30613) #sel(x1,x2) w: (0) sel(x1,x2) w: (max{10452 + x2, 10451 + x1}) #s(x1) w: (0) mark(x1) w: (x1) active(x1) w: (x1) cons(x1,x2) w: (max{x2, 8366 + x1}) #active(x1) w: (32285 + x1) #add(x1,x2) w: (0) add(x1,x2) w: (max{x2, x1}) #fib(x1) w: (0) USABLE RULES: { 1..33 } Removed DPs: #14 #15 #21 #29 #34 #45 #52 #53 Number of SCCs: 2, DPs: 8 SCC { #6 #50 } Sum... Max... QLPOpS... NegMaxSum... QWPOpSMaxSum... succeeded. #cons(x1,x2) 0[x2] w: (max{1 + x2, 0}) s(x1) 2[x1] w: (x1) #fib1(x1,x2) 0[] w: (0) fib1(x1,x2) 4[] w: (max{11945 + x2, 11945 + x1}) fib(x1) 0[x1] w: (38233 + x1) #mark(x1) 0[x1] w: (3000 + x1) 0() 4 w: (26286) #sel(x1,x2) 0[x2,x1] w: (1 + x2 + x1) sel(x1,x2) 1[x1] w: (1 + x2 + x1) #s(x1) 0[] w: (1) mark(x1) x1 w: (x1) active(x1) x1 w: (x1) cons(x1,x2) 0[] w: (max{x2, 2999 + x1}) #active(x1) 0[x1] w: (3000 + x1) #add(x1,x2) 0[] w: (0) add(x1,x2) 3[x1,x2] w: (max{x2, x1}) #fib(x1) 0[] w: (x1) USABLE RULES: { 1..33 } Removed DPs: #6 Number of SCCs: 1, DPs: 6 SCC { #8 #10 #11 #32 #44 #55 } Sum... Max... QLPOpS... NegMaxSum... QWPOpSMaxSum... succeeded. #cons(x1,x2) 0[x2] w: (max{x2, 0}) s(x1) 1[x1] w: (x1) #fib1(x1,x2) 0[] w: (0) fib1(x1,x2) 3[] w: (max{2 + x2, 2 + x1}) fib(x1) 0[x1] w: (21462 + x1) #mark(x1) 2[x1] w: (3000 + x1) 0() 3 w: (3001) #sel(x1,x2) 0[x2,x1] w: (1 + x2 + x1) sel(x1,x2) 4[x1] w: (1 + x2 + x1) #s(x1) 0[] w: (1) mark(x1) x1 w: (x1) active(x1) x1 w: (x1) cons(x1,x2) 3[] w: (max{x2, 2 + x1}) #active(x1) 2[x1] w: (3000 + x1) #add(x1,x2) 0[] w: (0) add(x1,x2) 2[x1,x2] w: (max{x2, x1}) #fib(x1) 0[] w: (x1) USABLE RULES: { 1..33 } Removed DPs: #10 #11 #32 #44 #55 Number of SCCs: 0, DPs: 0