/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES 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: p(s(X)) -> X 2: fact(0()) -> s(0()) 3: fact(s(Y)) -> xbtimes(s(Y),fact(p(s(Y)))) 4: xbtimes(0(),U) -> 0() 5: xbtimes(s(V),W) -> xbplus(xbtimes(V,W),W) 6: xbplus(P,0()) -> P 7: xbplus(X1,s(Y1)) -> s(xbplus(X1,Y1)) 8: _(X1,X2) -> X1 9: _(X1,X2) -> X2 Number of strict rules: 9 Direct POLO(bPol) ... failed. Uncurrying xbtimes p 1: p^1_s(X) -> X 2: fact(0()) -> s(0()) 3: fact(s(Y)) -> xbtimes^1_s(Y,fact(p^1_s(Y))) 4: xbtimes^1_0(U) -> 0() 5: xbtimes^1_s(V,W) -> xbplus(xbtimes(V,W),W) 6: xbplus(P,0()) -> P 7: xbplus(X1,s(Y1)) -> s(xbplus(X1,Y1)) 8: _(X1,X2) -> X1 9: _(X1,X2) -> X2 10: p(s(_1)) ->= p^1_s(_1) 11: xbtimes(0(),_1) ->= xbtimes^1_0(_1) 12: xbtimes(s(_1),_2) ->= xbtimes^1_s(_1,_2) Number of strict rules: 9 Direct POLO(bPol) ... failed. Dependency Pairs: #1: #xbtimes(0(),_1) ->? #xbtimes^1_0(_1) #2: #xbtimes(s(_1),_2) ->? #xbtimes^1_s(_1,_2) #3: #xbplus(X1,s(Y1)) -> #xbplus(X1,Y1) #4: #p(s(_1)) ->? #p^1_s(_1) #5: #xbtimes^1_s(V,W) -> #xbplus(xbtimes(V,W),W) #6: #xbtimes^1_s(V,W) -> #xbtimes(V,W) #7: #fact(s(Y)) -> #xbtimes^1_s(Y,fact(p^1_s(Y))) #8: #fact(s(Y)) -> #fact(p^1_s(Y)) #9: #fact(s(Y)) -> #p^1_s(Y) Number of SCCs: 3, DPs: 4 SCC { #8 } POLO(Sum)... succeeded. xbtimes w: 0 s w: x1 + 2 #xbtimes^1_s w: 0 #p^1_s w: 0 #xbtimes w: 0 #xbplus w: 0 p^1_s w: x1 + 1 #fact w: x1 #p w: 0 _ w: 0 p w: 0 #xbtimes^1_0 w: 0 0 w: 0 xbtimes^1_0 w: 0 xbplus w: 0 fact w: 0 #_ w: 0 xbtimes^1_s w: 0 USABLE RULES: { 1 } Removed DPs: #8 Number of SCCs: 2, DPs: 3 SCC { #3 } POLO(Sum)... succeeded. xbtimes w: 0 s w: x1 + 1 #xbtimes^1_s w: 0 #p^1_s w: 0 #xbtimes w: 0 #xbplus w: x2 p^1_s w: x1 + 1 #fact w: x1 #p w: 0 _ w: 0 p w: 0 #xbtimes^1_0 w: 0 0 w: 0 xbtimes^1_0 w: 0 xbplus w: 0 fact w: 0 #_ w: 0 xbtimes^1_s w: 0 USABLE RULES: { 1 } Removed DPs: #3 Number of SCCs: 1, DPs: 2 SCC { #2 #6 } POLO(Sum)... succeeded. xbtimes w: 0 s w: x1 + 2 #xbtimes^1_s w: x1 + 1 #p^1_s w: 0 #xbtimes w: x1 #xbplus w: 0 p^1_s w: x1 + 1 #fact w: x1 #p w: 0 _ w: 0 p w: 0 #xbtimes^1_0 w: 0 0 w: 0 xbtimes^1_0 w: 0 xbplus w: 0 fact w: 0 #_ w: 0 xbtimes^1_s w: 0 USABLE RULES: { 1 } Removed DPs: #2 #6 Number of SCCs: 0, DPs: 0 ... Input TRS: 1: p(s(X)) -> X 2: fact(0()) -> s(0()) 3: fact(s(Y)) -> xbtimes(s(Y),fact(p(s(Y)))) 4: xbtimes(0(),U) -> 0() 5: xbtimes(s(V),W) -> xbplus(xbtimes(V,W),W) 6: xbplus(P,0()) -> P 7: xbplus(X1,s(Y1)) -> s(xbplus(X1,Y1)) 8: _(X1,X2) -> X1 9: _(X1,X2) -> X2 Number of strict rules: 9 Direct POLO(bPol) ... failed. Uncurrying xbtimes p 1: p^1_s(X) -> X 2: fact(0()) -> s(0()) 3: fact(s(Y)) -> xbtimes^1_s(Y,fact(p^1_s(Y))) 4: xbtimes^1_0(U) -> 0() 5: xbtimes^1_s(V,W) -> xbplus(xbtimes(V,W),W) 6: xbplus(P,0()) -> P 7: xbplus(X1,s(Y1)) -> s(xbplus(X1,Y1)) 8: _(X1,X2) -> X1 9: _(X1,X2) -> X2 10: p(s(_1)) ->= p^1_s(_1) 11: xbtimes(0(),_1) ->= xbtimes^1_0(_1) 12: xbtimes(s(_1),_2) ->= xbtimes^1_s(_1,_2) Number of strict rules: 9 Direct POLO(bPol) ... failed. Dependency Pairs: #1: #xbtimes(0(),_1) ->? #xbtimes^1_0(_1) #2: #xbtimes(s(_1),_2) ->? #xbtimes^1_s(_1,_2) #3: #xbplus(X1,s(Y1)) -> #xbplus(X1,Y1) #4: #p(s(_1)) ->? #p^1_s(_1) #5: #xbtimes^1_s(V,W) -> #xbplus(xbtimes(V,W),W) #6: #xbtimes^1_s(V,W) -> #xbtimes(V,W) #7: #fact(s(Y)) -> #xbtimes^1_s(Y,fact(p^1_s(Y))) #8: #fact(s(Y)) -> #fact(p^1_s(Y)) #9: #fact(s(Y)) -> #p^1_s(Y) Number of SCCs: 3, DPs: 4 SCC { #8 } POLO(Sum)... succeeded. xbtimes w: 0 s w: x1 + 2 #xbtimes^1_s w: 0 #p^1_s w: 0 #xbtimes w: 0 #xbplus w: 0 p^1_s w: x1 + 1 #fact w: x1 #p w: 0 _ w: 0 p w: 0 #xbtimes^1_0 w: 0 0 w: 0 xbtimes^1_0 w: 0 xbplus w: 0 fact w: 0 #_ w: 0 xbtimes^1_s w: 0 USABLE RULES: { 1 } Removed DPs: #8 Number of SCCs: 2, DPs: 3 SCC { #3 } POLO(Sum)... succeeded. xbtimes w: 0 s w: x1 + 1 #xbtimes^1_s w: 0 #p^1_s w: 0 #xbtimes w: 0 #xbplus w: x2 p^1_s w: x1 + 1 #fact w: x1 #p w: 0 _ w: 0 p w: 0 #xbtimes^1_0 w: 0 0 w: 0 xbtimes^1_0 w: 0 xbplus w: 0 fact w: 0 #_ w: 0 xbtimes^1_s w: 0 USABLE RULES: { 1 } Removed DPs: #3 Number of SCCs: 1, DPs: 2 SCC { #2 #6 } POLO(Sum)... succeeded. xbtimes w: 0 s w: x1 + 2 #xbtimes^1_s w: x1 + 1 #p^1_s w: 0 #xbtimes w: x1 #xbplus w: 0 p^1_s w: x1 + 1 #fact w: x1 #p w: 0 _ w: 0 p w: 0 #xbtimes^1_0 w: 0 0 w: 0 xbtimes^1_0 w: 0 xbplus w: 0 fact w: 0 #_ w: 0 xbtimes^1_s w: 0 USABLE RULES: { 1 } Removed DPs: #2 #6 Number of SCCs: 0, DPs: 0 >>YES ******** Signature ******** map : ((c -> c),d) -> d nil : d cons : (c,d) -> d filter : ((c -> b),d) -> d filter2 : (b,(c -> b),c,d) -> d true : b false : b ******** Computation rules ******** (8) map(G1,nil) => nil (9) map(H1,cons(W1,P1)) => cons(H1[W1],map(H1,P1)) (10) filter(F2,nil) => nil (11) filter(Z2,cons(U2,V2)) => filter2(Z2[U2],Z2,U2,V2) (12) filter2(true,I2,P2,X3) => cons(P2,filter(I2,X3)) (13) filter2(false,Z3,U3,V3) => filter(Z3,V3) ******** General Schema criterion ******** Found constructors: 0, cons, false, nil, s, true Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>Regared as equal: filter2, filter Checking (1) p(s(X)) => X (meta X)[is acc in s(X)] [is positive in s(X)] [is acc in X] >>True Checking (2) fact(0) => s(0) (fun fact>s) (fun fact>0) >>True Checking (3) fact(s(Y)) => xbtimes(s(Y),fact(p(s(Y)))) (fun fact>xbtimes) (fun fact>s) (meta Y)[is acc in s(Y)] [is positive in s(Y)] [is acc in Y] (fun fact=fact) subterm comparison of args w. LR LR >>False Try again using status RL Checking (1) p(s(X)) => X (meta X)[is acc in s(X)] [is positive in s(X)] [is acc in X] >>True Checking (2) fact(0) => s(0) (fun fact>s) (fun fact>0) >>True Checking (3) fact(s(Y)) => xbtimes(s(Y),fact(p(s(Y)))) (fun fact>xbtimes) (fun fact>s) (meta Y)[is acc in s(Y)] [is positive in s(Y)] [is acc in Y] (fun fact=fact) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (1) p(s(X)) => X (meta X)[is acc in s(X)] [is positive in s(X)] [is acc in X] >>True Checking (2) fact(0) => s(0) (fun fact>s) (fun fact>0) >>True Checking (3) fact(s(Y)) => xbtimes(s(Y),fact(p(s(Y)))) (fun fact>xbtimes) (fun fact>s) (meta Y)[is acc in s(Y)] [is positive in s(Y)] [is acc in Y] (fun fact=fact) subterm comparison of args w. Mul Mul >>False Found constructors: nil, cons, true, false Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>Regared as equal: filter2, filter Checking (8) map(G1,nil) => nil (fun map>nil) >>True Checking (9) map(H1,cons(W1,P1)) => cons(H1[W1],map(H1,P1)) (fun map>cons) (meta H1)[is acc in H1,cons(W1,P1)] [is acc in H1] (meta W1)[is acc in H1,cons(W1,P1)] [is positive in cons(W1,P1)] [is acc in W1] (fun map=map) subterm comparison of args w. LR LR (meta H1)[is acc in H1,cons(W1,P1)] [is acc in H1] (meta P1)[is acc in H1,cons(W1,P1)] [is positive in cons(W1,P1)] [is acc in P1] >>True Checking (10) filter(F2,nil) => nil (fun filter>nil) >>True Checking (11) filter(Z2,cons(U2,V2)) => filter2(Z2[U2],Z2,U2,V2) (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1] (meta Z2)[is acc in Z2,cons(U2,V2)] [is acc in Z2] (meta U2)[is acc in Z2,cons(U2,V2)] [is positive in cons(U2,V2)] [is acc in U2] (meta Z2)[is acc in Z2,cons(U2,V2)] [is acc in Z2] (meta U2)[is acc in Z2,cons(U2,V2)] [is positive in cons(U2,V2)] [is acc in U2] (meta V2)[is acc in Z2,cons(U2,V2)] [is positive in cons(U2,V2)] [is acc in V2] >>True Checking (12) filter2(true,I2,P2,X3) => cons(P2,filter(I2,X3)) (fun filter2>cons) (meta P2)[is acc in true,I2,P2,X3] [is positive in true] [is acc in P2] (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta I2)[is acc in true,I2,P2,X3] [is positive in true] [is acc in I2] (meta X3)[is acc in true,I2,P2,X3] [is positive in true] [is acc in X3] >>True Checking (13) filter2(false,Z3,U3,V3) => filter(Z3,V3) (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta Z3)[is acc in false,Z3,U3,V3] [is positive in false] [is acc in Z3] (meta V3)[is acc in false,Z3,U3,V3] [is positive in false] [is acc in V3] >>True #SN! ******** Signature ******** xbplus : (a,a) -> a xbtimes : (a,a) -> a 0 : a cons : (c,d) -> d fact : a -> a false : b filter : ((c -> b),d) -> d filter2 : (b,(c -> b),c,d) -> d map : ((c -> c),d) -> d nil : d p : a -> a s : a -> a true : b ******** Computation Rules ******** (1) p(s(X)) => X (2) fact(0) => s(0) (3) fact(s(Y)) => xbtimes(s(Y),fact(p(s(Y)))) (4) xbtimes(0,U) => 0 (5) xbtimes(s(V),W) => xbplus(xbtimes(V,W),W) (6) xbplus(P,0) => P (7) xbplus(X1,s(Y1)) => s(xbplus(X1,Y1)) (8) map(G1,nil) => nil (9) map(H1,cons(W1,P1)) => cons(H1[W1],map(H1,P1)) (10) filter(F2,nil) => nil (11) filter(Z2,cons(U2,V2)) => filter2(Z2[U2],Z2,U2,V2) (12) filter2(true,I2,P2,X3) => cons(P2,filter(I2,X3)) (13) filter2(false,Z3,U3,V3) => filter(Z3,V3) YES