/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/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: app(nil(),L) -> L 2: app(cons(N,L),Y) -> cons(N,app(L,Y)) 3: reverse(nil()) -> nil() 4: reverse(cons(N,L)) -> app(reverse(L),cons(N,nil())) 5: shuffle(nil()) -> nil() 6: shuffle(cons(N,L)) -> cons(N,shuffle(reverse(L))) 7: fst(p(X,Y)) -> X 8: pshuffle(L) -> p(L,shuffle(L)) 9: _(X1,X2) -> X1 10: _(X1,X2) -> X2 Number of strict rules: 10 Direct POLO(bPol) ... removes: 8 5 10 7 9 fst w: 2 * x1 + 1 reverse w: x1 _ w: 2 * x1 + 2 * x2 + 1 shuffle w: x1 + 1641 p w: x1 + x2 + 4214 pshuffle w: 2 * x1 + 5856 nil w: 0 cons w: x1 + x2 + 1889 app w: x1 + x2 Number of strict rules: 5 Direct POLO(bPol) ... removes: 3 6 fst w: 2 * x1 + 1 reverse w: x1 + 9726 _ w: 2 * x1 + 2 * x2 + 1 shuffle w: 2 * x1 + 1641 p w: x1 + x2 + 4214 pshuffle w: 2 * x1 + 5856 nil w: 0 cons w: x1 + x2 + 20293 app w: x1 + x2 Number of strict rules: 3 Direct POLO(bPol) ... removes: 4 1 fst w: 2 * x1 + 1 reverse w: 2 * x1 + 1 _ w: 2 * x1 + 2 * x2 + 1 shuffle w: 2 * x1 + 1641 p w: x1 + x2 + 4214 pshuffle w: 2 * x1 + 5856 nil w: 1 cons w: x1 + x2 + 3 app w: x1 + x2 + 1 Number of strict rules: 1 Direct POLO(bPol) ... removes: 2 fst w: 2 * x1 + 1 reverse w: 2 * x1 + 419 _ w: 2 * x1 + 2 * x2 + 1 shuffle w: 2 * x1 + 1641 p w: x1 + x2 + 4214 pshuffle w: 2 * x1 + 5856 nil w: 2332 cons w: x1 + x2 + 1912 app w: 2 * x1 + 2 * x2 + 1651 Number of strict rules: 0 ... Input TRS: 1: app(nil(),L) -> L 2: app(cons(N,L),Y) -> cons(N,app(L,Y)) 3: reverse(nil()) -> nil() 4: reverse(cons(N,L)) -> app(reverse(L),cons(N,nil())) 5: shuffle(nil()) -> nil() 6: shuffle(cons(N,L)) -> cons(N,shuffle(reverse(L))) 7: fst(p(X,Y)) -> X 8: pshuffle(L) -> p(L,shuffle(L)) 9: _(X1,X2) -> X1 10: _(X1,X2) -> X2 Number of strict rules: 10 Direct POLO(bPol) ... removes: 8 5 10 7 9 fst w: 2 * x1 + 1 reverse w: x1 _ w: 2 * x1 + 2 * x2 + 1 shuffle w: x1 + 1641 p w: x1 + x2 + 4214 pshuffle w: 2 * x1 + 5856 nil w: 0 cons w: x1 + x2 + 1889 app w: x1 + x2 Number of strict rules: 5 Direct POLO(bPol) ... removes: 3 6 fst w: 2 * x1 + 1 reverse w: x1 + 9726 _ w: 2 * x1 + 2 * x2 + 1 shuffle w: 2 * x1 + 1641 p w: x1 + x2 + 4214 pshuffle w: 2 * x1 + 5856 nil w: 0 cons w: x1 + x2 + 20293 app w: x1 + x2 Number of strict rules: 3 Direct POLO(bPol) ... removes: 4 1 fst w: 2 * x1 + 1 reverse w: 2 * x1 + 1 _ w: 2 * x1 + 2 * x2 + 1 shuffle w: 2 * x1 + 1641 p w: x1 + x2 + 4214 pshuffle w: 2 * x1 + 5856 nil w: 1 cons w: x1 + x2 + 3 app w: x1 + x2 + 1 Number of strict rules: 1 Direct POLO(bPol) ... removes: 2 fst w: 2 * x1 + 1 reverse w: 2 * x1 + 419 _ w: 2 * x1 + 2 * x2 + 1 shuffle w: 2 * x1 + 1641 p w: x1 + x2 + 4214 pshuffle w: 2 * x1 + 5856 nil w: 2332 cons w: x1 + x2 + 1912 app w: 2 * x1 + 2 * x2 + 1651 Number of strict rules: 0 >>YES ******** Signature ******** pps : natlist -> plist prefixshuffle : (pair,natlist) -> plist p : (natlist,natlist) -> pair nil : natlist pcons : (pair,plist) -> plist pnil : plist cons : (nat,natlist) -> natlist apply2 : (((pair,nat) -> pair),pair,nat) -> pair pshuffle : natlist -> pair app : (natlist,natlist) -> natlist fst : pair -> natlist reverse : natlist -> natlist 0 : nat s : nat -> nat ******** Computation rules ******** (13) pps(L) => prefixshuffle(p(nil,nil),L) (9) prefixshuffle(Z,nil) => pcons(Z,pnil) (10) prefixshuffle(Z,cons(N,L)) => pcons(Z,prefixshuffle(apply2(x.y.pshuffle(fst(x)@cons(y,nil)),Z,N),reverse(L))) (11) apply2(F,Z,0) => Z (12) apply2(F,Z,s(N)) => F[Z,s(N)] ******** General Schema criterion ******** Found constructors: nil, pnil, cons, p, pcons, s, 0 Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>OK Checking (1) nil@L => L (meta L)[is acc in nil,L] [is positive in nil] [is acc in L] >>True Checking (2) cons(N,L)@Y => cons(N,L@Y) (fun app>cons) (meta N)[is acc in cons(N,L),Y] [is positive in cons(N,L)] [is acc in N] (fun app=app) subterm comparison of args w. LR LR (meta L)[is acc in cons(N,L),Y] [is positive in cons(N,L)] [is acc in L] (meta Y)[is acc in cons(N,L),Y] [is positive in cons(N,L)] [is acc in Y] >>True Checking (3) reverse(nil) => nil (fun reverse>nil) >>True Checking (4) reverse(cons(N,L)) => reverse(L)@cons(N,nil) (fun reverse>app) (fun reverse=reverse) subterm comparison of args w. LR LR (meta L)[is acc in cons(N,L)] [is positive in cons(N,L)] [is acc in L] (fun reverse>cons) (meta N)[is acc in cons(N,L)] [is positive in cons(N,L)] [is acc in N] (fun reverse>nil) >>True Checking (5) shuffle(nil) => nil (fun shuffle>nil) >>True Checking (6) shuffle(cons(N,L)) => cons(N,shuffle(reverse(L))) (fun shuffle>cons) (meta N)[is acc in cons(N,L)] [is positive in cons(N,L)] [is acc in N] (fun shuffle=shuffle) subterm comparison of args w. LR LR >>False Try again using status RL Checking (1) nil@L => L (meta L)[is acc in nil,L] [is positive in nil] [is acc in L] >>True Checking (2) cons(N,L)@Y => cons(N,L@Y) (fun app>cons) (meta N)[is acc in cons(N,L),Y] [is positive in cons(N,L)] [is acc in N] (fun app=app) subterm comparison of args w. RL RL (meta L)[is acc in cons(N,L),Y] [is positive in cons(N,L)] [is acc in L] (meta Y)[is acc in cons(N,L),Y] [is positive in cons(N,L)] [is acc in Y] >>True Checking (3) reverse(nil) => nil (fun reverse>nil) >>True Checking (4) reverse(cons(N,L)) => reverse(L)@cons(N,nil) (fun reverse>app) (fun reverse=reverse) subterm comparison of args w. RL RL (meta L)[is acc in cons(N,L)] [is positive in cons(N,L)] [is acc in L] (fun reverse>cons) (meta N)[is acc in cons(N,L)] [is positive in cons(N,L)] [is acc in N] (fun reverse>nil) >>True Checking (5) shuffle(nil) => nil (fun shuffle>nil) >>True Checking (6) shuffle(cons(N,L)) => cons(N,shuffle(reverse(L))) (fun shuffle>cons) (meta N)[is acc in cons(N,L)] [is positive in cons(N,L)] [is acc in N] (fun shuffle=shuffle) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (1) nil@L => L (meta L)[is acc in nil,L] [is positive in nil] [is acc in L] >>True Checking (2) cons(N,L)@Y => cons(N,L@Y) (fun app>cons) (meta N)[is acc in cons(N,L),Y] [is positive in cons(N,L)] [is acc in N] (fun app=app) subterm comparison of args w. Mul Mul (meta L)[is acc in cons(N,L),Y] [is positive in cons(N,L)] [is acc in L] (meta Y)[is acc in cons(N,L),Y] [is positive in cons(N,L)] [is acc in Y] >>True Checking (3) reverse(nil) => nil (fun reverse>nil) >>True Checking (4) reverse(cons(N,L)) => reverse(L)@cons(N,nil) (fun reverse>app) (fun reverse=reverse) subterm comparison of args w. Mul Mul (meta L)[is acc in cons(N,L)] [is positive in cons(N,L)] [is acc in L] (fun reverse>cons) (meta N)[is acc in cons(N,L)] [is positive in cons(N,L)] [is acc in N] (fun reverse>nil) >>True Checking (5) shuffle(nil) => nil (fun shuffle>nil) >>True Checking (6) shuffle(cons(N,L)) => cons(N,shuffle(reverse(L))) (fun shuffle>cons) (meta N)[is acc in cons(N,L)] [is positive in cons(N,L)] [is acc in N] (fun shuffle=shuffle) subterm comparison of args w. Mul Mul >>False Found constructors: p, nil, pcons, pnil, cons, pshuffle, app, fst, reverse, 0, s Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>OK Checking (13) pps(L) => prefixshuffle(p(nil,nil),L) (fun pps>prefixshuffle) (fun pps>p) (fun pps>nil) (fun pps>nil) (meta L)[is acc in L] [is acc in L] >>True Checking (9) prefixshuffle(Z,nil) => pcons(Z,pnil) (fun prefixshuffle>pcons) (meta Z)[is acc in Z,nil] [is acc in Z] (fun prefixshuffle>pnil) >>True Checking (10) prefixshuffle(Z,cons(N,L)) => pcons(Z,prefixshuffle(apply2(x.y.pshuffle(fst(x)@cons(y,nil)),Z,N),reverse(L))) (fun prefixshuffle>pcons) (meta Z)[is acc in Z,cons(N,L)] [is acc in Z] (fun prefixshuffle=prefixshuffle) subterm comparison of args w. LR LR >>False Try again using status RL Checking (13) pps(L) => prefixshuffle(p(nil,nil),L) (fun pps>prefixshuffle) (fun pps>p) (fun pps>nil) (fun pps>nil) (meta L)[is acc in L] [is acc in L] >>True Checking (9) prefixshuffle(Z,nil) => pcons(Z,pnil) (fun prefixshuffle>pcons) (meta Z)[is acc in Z,nil] [is acc in Z] (fun prefixshuffle>pnil) >>True Checking (10) prefixshuffle(Z,cons(N,L)) => pcons(Z,prefixshuffle(apply2(x.y.pshuffle(fst(x)@cons(y,nil)),Z,N),reverse(L))) (fun prefixshuffle>pcons) (meta Z)[is acc in Z,cons(N,L)] [is acc in Z] (fun prefixshuffle=prefixshuffle) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (13) pps(L) => prefixshuffle(p(nil,nil),L) (fun pps>prefixshuffle) (fun pps>p) (fun pps>nil) (fun pps>nil) (meta L)[is acc in L] [is acc in L] >>True Checking (9) prefixshuffle(Z,nil) => pcons(Z,pnil) (fun prefixshuffle>pcons) (meta Z)[is acc in Z,nil] [is acc in Z] (fun prefixshuffle>pnil) >>True Checking (10) prefixshuffle(Z,cons(N,L)) => pcons(Z,prefixshuffle(apply2(x.y.pshuffle(fst(x)@cons(y,nil)),Z,N),reverse(L))) (fun prefixshuffle>pcons) (meta Z)[is acc in Z,cons(N,L)] [is acc in Z] (fun prefixshuffle=prefixshuffle) subterm comparison of args w. Mul Mul >>False #No idea.. ******** Signature ******** nil : natlist pnil : plist app : (natlist,natlist) -> natlist cons : (nat,natlist) -> natlist p : (natlist,natlist) -> pair pcons : (pair,plist) -> plist fst : pair -> natlist shuffle : natlist -> natlist reverse : natlist -> natlist pshuffle : natlist -> pair prefixshuffle : (pair,natlist) -> plist apply2 : (((pair,nat) -> pair),pair,nat) -> pair pps : natlist -> plist s : nat -> nat 0 : nat ******** Computation Rules ******** (1) nil@L => L (2) cons(N,L)@Y => cons(N,L@Y) (3) reverse(nil) => nil (4) reverse(cons(N,L)) => reverse(L)@cons(N,nil) (5) shuffle(nil) => nil (6) shuffle(cons(N,L)) => cons(N,shuffle(reverse(L))) (7) fst(p(X,Y)) => X (8) pshuffle(L) => p(L,shuffle(L)) (9) prefixshuffle(Z,nil) => pcons(Z,pnil) (10) prefixshuffle(Z,cons(N,L)) => pcons(Z,prefixshuffle(apply2(x.y.pshuffle(fst(x)@cons(y,nil)),Z,N),reverse(L))) (11) apply2(F,Z,0) => Z (12) apply2(F,Z,s(N)) => F[Z,s(N)] (13) pps(L) => prefixshuffle(p(nil,nil),L) MAYBE