/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE Input TRS: 1: qsort(xs) -> qs(half(length(xs)),xs) 2: qs(n,nil()) -> nil() 3: qs(n,cons(x,xs)) -> append(qs(half(n),filterlow(get(n,cons(x,xs)),cons(x,xs))),cons(get(n,cons(x,xs)),qs(half(n),filterhigh(get(n,cons(x,xs)),cons(x,xs))))) 4: filterlow(n,nil()) -> nil() 5: filterlow(n,cons(x,xs)) -> if1(ge(n,x),n,x,xs) 6: if1(true(),n,x,xs) -> filterlow(n,xs) 7: if1(false(),n,x,xs) -> cons(x,filterlow(n,xs)) 8: filterhigh(n,nil()) -> nil() 9: filterhigh(n,cons(x,xs)) -> if2(ge(x,n),n,x,xs) 10: if2(true(),n,x,xs) -> filterhigh(n,xs) 11: if2(false(),n,x,xs) -> cons(x,filterhigh(n,xs)) 12: ge(x,0()) -> true() 13: ge(0(),s(x)) -> false() 14: ge(s(x),s(y)) -> ge(x,y) 15: append(nil(),ys()) -> ys() 16: append(cons(x,xs),ys()) -> cons(x,append(xs,ys())) 17: length(nil()) -> 0() 18: length(cons(x,xs)) -> s(length(xs)) 19: half(0()) -> 0() 20: half(s(0())) -> 0() 21: half(s(s(x))) -> s(half(x)) 22: get(n,nil()) -> 0() 23: get(n,cons(x,nil())) -> x 24: get(0(),cons(x,cons(y,xs))) -> x 25: get(s(n),cons(x,cons(y,xs))) -> get(n,cons(y,xs)) Number of strict rules: 25 Direct poly ... failed. Freezing ... failed. Dependency Pairs: #1: #if1(true(),n,x,xs) -> #filterlow(n,xs) #2: #filterhigh(n,cons(x,xs)) -> #if2(ge(x,n),n,x,xs) #3: #filterhigh(n,cons(x,xs)) -> #ge(x,n) #4: #if2(false(),n,x,xs) -> #filterhigh(n,xs) #5: #ge(s(x),s(y)) -> #ge(x,y) #6: #get(s(n),cons(x,cons(y,xs))) -> #get(n,cons(y,xs)) #7: #if1(false(),n,x,xs) -> #filterlow(n,xs) #8: #if2(true(),n,x,xs) -> #filterhigh(n,xs) #9: #filterlow(n,cons(x,xs)) -> #if1(ge(n,x),n,x,xs) #10: #filterlow(n,cons(x,xs)) -> #ge(n,x) #11: #half(s(s(x))) -> #half(x) #12: #append(cons(x,xs),ys()) -> #append(xs,ys()) #13: #qs(n,cons(x,xs)) -> #append(qs(half(n),filterlow(get(n,cons(x,xs)),cons(x,xs))),cons(get(n,cons(x,xs)),qs(half(n),filterhigh(get(n,cons(x,xs)),cons(x,xs))))) #14: #qs(n,cons(x,xs)) -> #qs(half(n),filterlow(get(n,cons(x,xs)),cons(x,xs))) #15: #qs(n,cons(x,xs)) -> #half(n) #16: #qs(n,cons(x,xs)) -> #filterlow(get(n,cons(x,xs)),cons(x,xs)) #17: #qs(n,cons(x,xs)) -> #get(n,cons(x,xs)) #18: #qs(n,cons(x,xs)) -> #get(n,cons(x,xs)) #19: #qs(n,cons(x,xs)) -> #qs(half(n),filterhigh(get(n,cons(x,xs)),cons(x,xs))) #20: #qs(n,cons(x,xs)) -> #half(n) #21: #qs(n,cons(x,xs)) -> #filterhigh(get(n,cons(x,xs)),cons(x,xs)) #22: #qs(n,cons(x,xs)) -> #get(n,cons(x,xs)) #23: #qsort(xs) -> #qs(half(length(xs)),xs) #24: #qsort(xs) -> #half(length(xs)) #25: #qsort(xs) -> #length(xs) #26: #length(cons(x,xs)) -> #length(xs) Number of SCCs: 8, DPs: 13 SCC { #26 } Sum... succeeded. #qs(x1,x2) w: (0) s(x1) w: (0) #append(x1,x2) w: (0) if1(x1,x2,x3,x4) w: (0) false() w: (0) #ge(x1,x2) w: (0) filterlow(x1,x2) w: (0) #half(x1) w: (0) qsort(x1) w: (0) true() w: (0) #if1(x1,x2,x3,x4) w: (0) half(x1) w: (0) if2(x1,x2,x3,x4) w: (0) #qsort(x1) w: (0) qs(x1,x2) w: (0) append(x1,x2) w: (0) 0() w: (0) ge(x1,x2) w: (0) nil() w: (0) #filterlow(x1,x2) w: (0) get(x1,x2) w: (0) #get(x1,x2) w: (0) cons(x1,x2) w: (1 + x2) filterhigh(x1,x2) w: (0) ys() w: (0) #filterhigh(x1,x2) w: (0) length(x1) w: (0) #if2(x1,x2,x3,x4) w: (0) #length(x1) w: (x1) USABLE RULES: { } Removed DPs: #26 Number of SCCs: 7, DPs: 12 SCC { #11 } Sum... succeeded. #qs(x1,x2) w: (0) s(x1) w: (1 + x1) #append(x1,x2) w: (0) if1(x1,x2,x3,x4) w: (0) false() w: (0) #ge(x1,x2) w: (0) filterlow(x1,x2) w: (0) #half(x1) w: (x1) qsort(x1) w: (0) true() w: (0) #if1(x1,x2,x3,x4) w: (0) half(x1) w: (0) if2(x1,x2,x3,x4) w: (0) #qsort(x1) w: (0) qs(x1,x2) w: (0) append(x1,x2) w: (0) 0() w: (0) ge(x1,x2) w: (0) nil() w: (0) #filterlow(x1,x2) w: (0) get(x1,x2) w: (0) #get(x1,x2) w: (0) cons(x1,x2) w: (1) filterhigh(x1,x2) w: (0) ys() w: (0) #filterhigh(x1,x2) w: (0) length(x1) w: (0) #if2(x1,x2,x3,x4) w: (0) #length(x1) w: (0) USABLE RULES: { } Removed DPs: #11 Number of SCCs: 6, DPs: 11 SCC { #12 } Sum... succeeded. #qs(x1,x2) w: (0) s(x1) w: (1) #append(x1,x2) w: (x2 + x1) if1(x1,x2,x3,x4) w: (0) false() w: (0) #ge(x1,x2) w: (0) filterlow(x1,x2) w: (0) #half(x1) w: (0) qsort(x1) w: (0) true() w: (0) #if1(x1,x2,x3,x4) w: (0) half(x1) w: (0) if2(x1,x2,x3,x4) w: (0) #qsort(x1) w: (0) qs(x1,x2) w: (0) append(x1,x2) w: (0) 0() w: (0) ge(x1,x2) w: (0) nil() w: (0) #filterlow(x1,x2) w: (0) get(x1,x2) w: (0) #get(x1,x2) w: (0) cons(x1,x2) w: (1 + x2) filterhigh(x1,x2) w: (0) ys() w: (1) #filterhigh(x1,x2) w: (0) length(x1) w: (0) #if2(x1,x2,x3,x4) w: (0) #length(x1) w: (0) USABLE RULES: { } Removed DPs: #12 Number of SCCs: 5, DPs: 10 SCC { #5 } Sum... succeeded. #qs(x1,x2) w: (0) s(x1) w: (1 + x1) #append(x1,x2) w: (0) if1(x1,x2,x3,x4) w: (0) false() w: (0) #ge(x1,x2) w: (x2) filterlow(x1,x2) w: (0) #half(x1) w: (0) qsort(x1) w: (0) true() w: (0) #if1(x1,x2,x3,x4) w: (0) half(x1) w: (0) if2(x1,x2,x3,x4) w: (0) #qsort(x1) w: (0) qs(x1,x2) w: (0) append(x1,x2) w: (0) 0() w: (0) ge(x1,x2) w: (0) nil() w: (0) #filterlow(x1,x2) w: (0) get(x1,x2) w: (0) #get(x1,x2) w: (0) cons(x1,x2) w: (1) filterhigh(x1,x2) w: (0) ys() w: (1) #filterhigh(x1,x2) w: (0) length(x1) w: (0) #if2(x1,x2,x3,x4) w: (0) #length(x1) w: (0) USABLE RULES: { } Removed DPs: #5 Number of SCCs: 4, DPs: 9 SCC { #6 } Sum... succeeded. #qs(x1,x2) w: (0) s(x1) w: (1) #append(x1,x2) w: (0) if1(x1,x2,x3,x4) w: (0) false() w: (0) #ge(x1,x2) w: (0) filterlow(x1,x2) w: (0) #half(x1) w: (0) qsort(x1) w: (0) true() w: (0) #if1(x1,x2,x3,x4) w: (0) half(x1) w: (0) if2(x1,x2,x3,x4) w: (0) #qsort(x1) w: (0) qs(x1,x2) w: (0) append(x1,x2) w: (0) 0() w: (0) ge(x1,x2) w: (0) nil() w: (0) #filterlow(x1,x2) w: (0) get(x1,x2) w: (0) #get(x1,x2) w: (x2) cons(x1,x2) w: (1 + x2 + x1) filterhigh(x1,x2) w: (0) ys() w: (1) #filterhigh(x1,x2) w: (0) length(x1) w: (0) #if2(x1,x2,x3,x4) w: (0) #length(x1) w: (0) USABLE RULES: { } Removed DPs: #6 Number of SCCs: 3, DPs: 8 SCC { #1 #7 #9 } Sum... succeeded. #qs(x1,x2) w: (0) s(x1) w: (1) #append(x1,x2) w: (0) if1(x1,x2,x3,x4) w: (0) false() w: (10453) #ge(x1,x2) w: (0) filterlow(x1,x2) w: (0) #half(x1) w: (0) qsort(x1) w: (0) true() w: (10452) #if1(x1,x2,x3,x4) w: (32286 + x4 + x3 + x2) half(x1) w: (0) if2(x1,x2,x3,x4) w: (0) #qsort(x1) w: (0) qs(x1,x2) w: (0) append(x1,x2) w: (0) 0() w: (1) ge(x1,x2) w: (10451 + x1) nil() w: (0) #filterlow(x1,x2) w: (32285 + x2 + x1) get(x1,x2) w: (0) #get(x1,x2) w: (0) cons(x1,x2) w: (2 + x2 + x1) filterhigh(x1,x2) w: (0) ys() w: (1) #filterhigh(x1,x2) w: (0) length(x1) w: (0) #if2(x1,x2,x3,x4) w: (0) #length(x1) w: (0) USABLE RULES: { } Removed DPs: #1 #7 #9 Number of SCCs: 2, DPs: 5 SCC { #2 #4 #8 } Sum... succeeded. #qs(x1,x2) w: (0) s(x1) w: (1) #append(x1,x2) w: (0) if1(x1,x2,x3,x4) w: (0) false() w: (39695) #ge(x1,x2) w: (0) filterlow(x1,x2) w: (0) #half(x1) w: (0) qsort(x1) w: (0) true() w: (10452) #if1(x1,x2,x3,x4) w: (32286) half(x1) w: (0) if2(x1,x2,x3,x4) w: (0) #qsort(x1) w: (0) qs(x1,x2) w: (0) append(x1,x2) w: (0) 0() w: (29243) ge(x1,x2) w: (10451 + x1) nil() w: (0) #filterlow(x1,x2) w: (32285) get(x1,x2) w: (0) #get(x1,x2) w: (0) cons(x1,x2) w: (2 + x2) filterhigh(x1,x2) w: (0) ys() w: (1) #filterhigh(x1,x2) w: (x2 + x1) length(x1) w: (0) #if2(x1,x2,x3,x4) w: (1 + x4 + x2) #length(x1) w: (0) USABLE RULES: { } Removed DPs: #2 #4 #8 Number of SCCs: 1, DPs: 2 SCC { #14 #19 } Sum... Max... QLPOpS... NegMaxSum... QWPOpSMaxSum... 2D-Mat... sum_sum_int,sum_neg... heuristic_int,sum_neg... failed. Finding a loop... failed.