/export/starexec/sandbox2/solver/bin/starexec_run_default /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] (fun app=app) subterm comparison of args w. LR LR (meta Xs)[is acc in cons(X,Xs),Ys] [is positive in cons(X,Xs)] [is acc in Xs] (meta Ys)[is acc in cons(X,Xs),Ys] [is positive in cons(X,Xs)] [is acc in Ys] >>True Checking (5) le(0,Y) => true (fun le>true) >>True Checking (6) le(s(X),0) => false (fun le>false) >>True Checking (7) le(s(X),s(Y)) => le(X,Y) (fun le=le) subterm comparison of args w. LR LR (meta X)[is acc in s(X),s(Y)] [is positive in s(X)] [is acc in X] (meta Y)[is acc in s(X),s(Y)] [is positive in s(X)] [is positive in s(Y)] [is acc in Y] >>True Checking (8) gr(0,Y) => false (fun gr>false) >>True Checking (9) gr(s(X),0) => true (fun gr>true) >>True Checking (10) gr(s(X),s(Y)) => gr(X,Y) (fun gr=gr) subterm comparison of args w. LR LR (meta X)[is acc in s(X),s(Y)] [is positive in s(X)] [is acc in X] (meta Y)[is acc in s(X),s(Y)] [is positive in s(X)] [is positive in s(Y)] [is acc in Y] >>True Checking (11) filter(P,nil) => nil (fun filter>nil) >>True Checking (12) filter(P,cons(X,Xs)) => if(P[X],cons(X,filter(P,Xs)),filter(P,Xs)) (fun filter>if) (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta X)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in X] (fun filter>cons) (meta X)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in X] (fun filter=filter) subterm comparison of args w. Arg [1,2] Arg [1,2] (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta Xs)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in Xs] (fun filter=filter) subterm comparison of args w. Arg [1,2] Arg [1,2] (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta Xs)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in Xs] >>True Checking (13) qsort(nil) => nil (fun qsort>nil) >>True Checking (14) qsort(cons(X,Xs)) => qsort(filter(z.le(z,X),Xs))@(cons(X,nil)@qsort(filter(z.gr(z,X),Xs))) (fun qsort>app) (fun qsort=qsort) subterm comparison of args w. LR LR >>False Try again using status RL 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] (fun app=app) subterm comparison of args w. RL RL (meta Xs)[is acc in cons(X,Xs),Ys] [is positive in cons(X,Xs)] [is acc in Xs] (meta Ys)[is acc in cons(X,Xs),Ys] [is positive in cons(X,Xs)] [is acc in Ys] >>True Checking (5) le(0,Y) => true (fun le>true) >>True Checking (6) le(s(X),0) => false (fun le>false) >>True Checking (7) le(s(X),s(Y)) => le(X,Y) (fun le=le) subterm comparison of args w. RL RL (meta X)[is acc in s(X),s(Y)] [is positive in s(X)] [is acc in X] (meta Y)[is acc in s(X),s(Y)] [is positive in s(X)] [is positive in s(Y)] [is acc in Y] >>True Checking (8) gr(0,Y) => false (fun gr>false) >>True Checking (9) gr(s(X),0) => true (fun gr>true) >>True Checking (10) gr(s(X),s(Y)) => gr(X,Y) (fun gr=gr) subterm comparison of args w. RL RL (meta X)[is acc in s(X),s(Y)] [is positive in s(X)] [is acc in X] (meta Y)[is acc in s(X),s(Y)] [is positive in s(X)] [is positive in s(Y)] [is acc in Y] >>True Checking (11) filter(P,nil) => nil (fun filter>nil) >>True Checking (12) filter(P,cons(X,Xs)) => if(P[X],cons(X,filter(P,Xs)),filter(P,Xs)) (fun filter>if) (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta X)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in X] (fun filter>cons) (meta X)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in X] (fun filter=filter) subterm comparison of args w. Arg [1,2] Arg [1,2] (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta Xs)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in Xs] (fun filter=filter) subterm comparison of args w. Arg [1,2] Arg [1,2] (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta Xs)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in Xs] >>True Checking (13) qsort(nil) => nil (fun qsort>nil) >>True Checking (14) qsort(cons(X,Xs)) => qsort(filter(z.le(z,X),Xs))@(cons(X,nil)@qsort(filter(z.gr(z,X),Xs))) (fun qsort>app) (fun qsort=qsort) subterm comparison of args w. RL RL >>False Try again using status Mul 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] (fun app=app) subterm comparison of args w. Mul Mul (meta Xs)[is acc in cons(X,Xs),Ys] [is positive in cons(X,Xs)] [is acc in Xs] (meta Ys)[is acc in cons(X,Xs),Ys] [is positive in cons(X,Xs)] [is acc in Ys] >>True Checking (5) le(0,Y) => true (fun le>true) >>True Checking (6) le(s(X),0) => false (fun le>false) >>True Checking (7) le(s(X),s(Y)) => le(X,Y) (fun le=le) subterm comparison of args w. Mul Mul (meta X)[is acc in s(X),s(Y)] [is positive in s(X)] [is acc in X] (meta Y)[is acc in s(X),s(Y)] [is positive in s(X)] [is positive in s(Y)] [is acc in Y] >>True Checking (8) gr(0,Y) => false (fun gr>false) >>True Checking (9) gr(s(X),0) => true (fun gr>true) >>True Checking (10) gr(s(X),s(Y)) => gr(X,Y) (fun gr=gr) subterm comparison of args w. Mul Mul (meta X)[is acc in s(X),s(Y)] [is positive in s(X)] [is acc in X] (meta Y)[is acc in s(X),s(Y)] [is positive in s(X)] [is positive in s(Y)] [is acc in Y] >>True Checking (11) filter(P,nil) => nil (fun filter>nil) >>True Checking (12) filter(P,cons(X,Xs)) => if(P[X],cons(X,filter(P,Xs)),filter(P,Xs)) (fun filter>if) (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta X)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in X] (fun filter>cons) (meta X)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in X] (fun filter=filter) subterm comparison of args w. Arg [1,2] Arg [1,2] (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta Xs)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in Xs] (fun filter=filter) subterm comparison of args w. Arg [1,2] Arg [1,2] (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta Xs)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in Xs] >>True Checking (13) qsort(nil) => nil (fun qsort>nil) >>True Checking (14) qsort(cons(X,Xs)) => qsort(filter(z.le(z,X),Xs))@(cons(X,nil)@qsort(filter(z.gr(z,X),Xs))) (fun qsort>app) (fun qsort=qsort) subterm comparison of args w. Mul Mul >>False Found constructors: nil, cons, if, app, le, gr Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>OK Checking (13) qsort(nil) => nil (fun qsort>nil) >>True Checking (11) filter(P,nil) => nil (fun filter>nil) >>True Checking (12) filter(P,cons(X,Xs)) => if(P[X],cons(X,filter(P,Xs)),filter(P,Xs)) (fun filter>if) (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta X)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in X] (fun filter>cons) (meta X)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in X] (fun filter=filter) subterm comparison of args w. Arg [1,2] Arg [1,2] (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta Xs)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in Xs] (fun filter=filter) subterm comparison of args w. Arg [1,2] Arg [1,2] (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta Xs)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in Xs] >>True Checking (14) qsort(cons(X,Xs)) => qsort(filter(z.le(z,X),Xs))@(cons(X,nil)@qsort(filter(z.gr(z,X),Xs))) (fun qsort>app) (fun qsort=qsort) subterm comparison of args w. LR LR >>False Try again using status RL Checking (13) qsort(nil) => nil (fun qsort>nil) >>True Checking (11) filter(P,nil) => nil (fun filter>nil) >>True Checking (12) filter(P,cons(X,Xs)) => if(P[X],cons(X,filter(P,Xs)),filter(P,Xs)) (fun filter>if) (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta X)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in X] (fun filter>cons) (meta X)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in X] (fun filter=filter) subterm comparison of args w. Arg [1,2] Arg [1,2] (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta Xs)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in Xs] (fun filter=filter) subterm comparison of args w. Arg [1,2] Arg [1,2] (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta Xs)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in Xs] >>True Checking (14) qsort(cons(X,Xs)) => qsort(filter(z.le(z,X),Xs))@(cons(X,nil)@qsort(filter(z.gr(z,X),Xs))) (fun qsort>app) (fun qsort=qsort) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (13) qsort(nil) => nil (fun qsort>nil) >>True Checking (11) filter(P,nil) => nil (fun filter>nil) >>True Checking (12) filter(P,cons(X,Xs)) => if(P[X],cons(X,filter(P,Xs)),filter(P,Xs)) (fun filter>if) (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta X)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in X] (fun filter>cons) (meta X)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in X] (fun filter=filter) subterm comparison of args w. Arg [1,2] Arg [1,2] (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta Xs)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in Xs] (fun filter=filter) subterm comparison of args w. Arg [1,2] Arg [1,2] (meta P)[is acc in P,cons(X,Xs)] [is acc in P] (meta Xs)[is acc in P,cons(X,Xs)] [is positive in cons(X,Xs)] [is acc in Xs] >>True Checking (14) qsort(cons(X,Xs)) => qsort(filter(z.le(z,X),Xs))@(cons(X,nil)@qsort(filter(z.gr(z,X),Xs))) (fun qsort>app) (fun qsort=qsort) subterm comparison of args w. Mul Mul >>False #No idea.. ******** Signature ******** 0 : nat s : nat -> nat le : (nat,nat) -> bool gr : (nat,nat) -> bool true : bool false : bool if : (bool,list,list) -> list nil : list cons : (nat,list) -> list app : (list,list) -> list filter : ((nat -> bool),list) -> list qsort : list -> list ******** Computation Rules ******** (1) if(true,Xs,Ys) => Xs (2) if(false,Xs,Ys) => Ys (3) nil@Xs => Xs (4) cons(X,Xs)@Ys => cons(X,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) filter(P,nil) => nil (12) filter(P,cons(X,Xs)) => if(P[X],cons(X,filter(P,Xs)),filter(P,Xs)) (13) qsort(nil) => nil (14) qsort(cons(X,Xs)) => qsort(filter(z.le(z,X),Xs))@(cons(X,nil)@qsort(filter(z.gr(z,X),Xs))) MAYBE