details

property	value
status	complete
benchmark	qsortmiddle.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n035.star.cs.uiowa.edu
space	AProVE_09_Inductive

run statistics

property	value
solver	NaTT 2.3.3
configuration	default
runtime (wallclock)	4.12413716316 seconds
cpu usage	4.730830552
max memory	2.62787072E8

stage attributes

key	value
output-size	9284
starexec-result	"MAYBE"

output

/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 Order(PosReal,>,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, edges: 17 SCC { #11 } Removing DPs: Order(PosReal,>,Sum)... succeeded. #qs(x1,x2) weight: 0 s(x1) weight: (/ 1 4) + x1 #append(x1,x2) weight: 0 if1(x1,x2,x3,x4) weight: 0 false() weight: 0 #ge(x1,x2) weight: 0 filterlow(x1,x2) weight: 0 #half(x1) weight: x1 qsort(x1) weight: 0 true() weight: 0 #if1(x1,x2,x3,x4) weight: 0 half(x1) weight: 0 if2(x1,x2,x3,x4) weight: 0 #qsort(x1) weight: 0 qs(x1,x2) weight: 0 append(x1,x2) weight: 0 0() weight: 0 ge(x1,x2) weight: 0 nil() weight: 0 #filterlow(x1,x2) weight: 0 get(x1,x2) weight: 0 #get(x1,x2) weight: 0 cons(x1,x2) weight: 0 filterhigh(x1,x2) weight: 0 ys() weight: 0 #filterhigh(x1,x2) weight: 0 length(x1) weight: 0 #if2(x1,x2,x3,x4) weight: 0 #length(x1) weight: 0 Usable rules: { } Removed DPs: #11 Number of SCCs: 7, DPs: 12, edges: 16 SCC { #26 } Removing DPs: Order(PosReal,>,Sum)... succeeded. popout

output may be truncated. 'popout' for the full output.

job log

popout

actions

all output return to TRS Standard