Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
HRS 58631 pair #381919052
details
property
value
status
complete
benchmark
qsort.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n049.star.cs.uiowa.edu
space
Mixed_HO_10
run statistics
property
value
solver
sol 37957
configuration
hrs
runtime (wallclock)
0.0530989170074 seconds
cpu usage
0.053082263
max memory
7397376.0
stage attributes
key
value
output-size
14211
starexec-result
MAYBE
output
/export/starexec/sandbox2/solver/bin/starexec_run_hrs /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE We split firstr-order part and higher-order part, and do modular checking by a general modularity. ******** FO SN check ******** Check SN using NaTT (Nagoya Termination Tool) Input TRS: 1: if(true(),Xs,Ys) -> Xs 2: if(false(),Xs,Ys) -> Ys 3: app(nil(),Xs) -> Xs 4: app(cons(X,Xs),Ys) -> cons(X,app(Xs,Ys)) 5: le(0(),Y) -> true() 6: le(s(X),0()) -> false() 7: le(s(X),s(Y)) -> le(X,Y) 8: gr(0(),Y) -> false() 9: gr(s(X),0()) -> true() 10: gr(s(X),s(Y)) -> gr(X,Y) 11: _(X1,X2) -> X1 12: _(X1,X2) -> X2 Number of strict rules: 12 Direct POLO(bPol) ... removes: 4 8 1 3 5 10 7 12 11 9 6 2 le w: 2 * x1 + x2 + 535 s w: 2 * x1 + 2998 false w: 8176 _ w: 2 * x1 + 2 * x2 + 1 true w: 11858 if w: 2 * x1 + 2 * x2 + 2 * x3 + 609 0 w: 7550 nil w: 1 cons w: x1 + x2 + 1797 gr w: 2 * x1 + 2 * x2 + 449 app w: 2 * x1 + 2 * x2 + 1143 Number of strict rules: 0 ... Input TRS: 1: if(true(),Xs,Ys) -> Xs 2: if(false(),Xs,Ys) -> Ys 3: app(nil(),Xs) -> Xs 4: app(cons(X,Xs),Ys) -> cons(X,app(Xs,Ys)) 5: le(0(),Y) -> true() 6: le(s(X),0()) -> false() 7: le(s(X),s(Y)) -> le(X,Y) 8: gr(0(),Y) -> false() 9: gr(s(X),0()) -> true() 10: gr(s(X),s(Y)) -> gr(X,Y) 11: _(X1,X2) -> X1 12: _(X1,X2) -> X2 Number of strict rules: 12 Direct POLO(bPol) ... removes: 4 8 1 3 5 10 7 12 11 9 6 2 le w: 2 * x1 + x2 + 535 s w: 2 * x1 + 2998 false w: 8176 _ w: 2 * x1 + 2 * x2 + 1 true w: 11858 if w: 2 * x1 + 2 * x2 + 2 * x3 + 609 0 w: 7550 nil w: 1 cons w: x1 + x2 + 1797 gr w: 2 * x1 + 2 * x2 + 449 app w: 2 * x1 + 2 * x2 + 1143 Number of strict rules: 0 >>YES ******** Signature ******** qsort : list -> list nil : list filter : ((nat -> bool),list) -> list cons : (nat,list) -> list if : (bool,list,list) -> list app : (list,list) -> list le : (nat,nat) -> bool gr : (nat,nat) -> bool ******** Computation rules ******** (13) qsort(nil) => nil (11) filter(P,nil) => nil (12) filter(P,cons(X,Xs)) => if(P[X],cons(X,filter(P,Xs)),filter(P,Xs)) (14) qsort(cons(X,Xs)) => qsort(filter(z.le(z,X),Xs))@(cons(X,nil)@qsort(filter(z.gr(z,X),Xs))) ******** General Schema criterion ******** Found constructors: 0, s, true, false, nil, cons Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>OK Checking (1) if(true,Xs,Ys) => Xs (meta Xs)[is acc in true,Xs,Ys] [is positive in true] [is acc in Xs] >>True Checking (2) if(false,Xs,Ys) => Ys (meta Ys)[is acc in false,Xs,Ys] [is positive in false] [is acc in Ys] >>True Checking (3) nil@Xs => Xs (meta Xs)[is acc in nil,Xs] [is positive in nil] [is acc in Xs] >>True Checking (4) cons(X,Xs)@Ys => cons(X,Xs@Ys) (fun app>cons) (meta X)[is acc in cons(X,Xs),Ys] [is positive in cons(X,Xs)] [is acc in X]
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to HRS 58631