/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: dec(0(),D) -> 0() 2: dec(X,0()) -> X 3: dec(s(X),s(D)) -> dec(X,D) 4: xpls(0(),X) -> X 5: xpls(s(X),Y) -> s(xpls(X,Y)) 6: quad(0()) -> 0() 7: quad(s(X)) -> s(s(s(s(quad(X))))) 8: sqr(p(0(),0())) -> 0() 9: sqr(p(s(s(X)),Y)) -> sqr(p(X,s(Y))) 10: sqr(p(s(0()),Y)) -> xpls(quad(sqr(p(Y,0()))),s(quad(Y))) 11: sqr(p(0(),s(Y))) -> quad(sqr(p(s(Y),0()))) 12: _(X1,X2) -> X1 13: _(X1,X2) -> X2 Number of strict rules: 13 Direct POLO(bPol) ... removes: 8 1 12 13 2 dec w: 2 * x1 + x2 + 1651 s w: x1 _ w: 2 * x1 + 2 * x2 + 1 p w: x1 + 2 * x2 + 112 0 w: 0 quad w: x1 sqr w: x1 + 1102 xpls w: x1 + x2 Number of strict rules: 8 Direct POLO(bPol) ... failed. Uncurrying sqr^1_p sqr 3: dec(s(X),s(D)) -> dec(X,D) 4: xpls(0(),X) -> X 5: xpls(s(X),Y) -> s(xpls(X,Y)) 6: quad(0()) -> 0() 7: quad(s(X)) -> s(s(s(s(quad(X))))) 9: sqr^1_p^1_s(s(X),Y) -> sqr^1_p(X,s(Y)) 10: sqr^1_p^1_s(0(),Y) -> xpls(quad(sqr^1_p(Y,0())),s(quad(Y))) 11: sqr^1_p^1_0(s(Y)) -> quad(sqr^1_p^1_s(Y,0())) 14: sqr(p(_1,_2)) ->= sqr^1_p(_1,_2) 15: sqr^1_p(0(),_1) ->= sqr^1_p^1_0(_1) 16: sqr^1_p(s(_1),_2) ->= sqr^1_p^1_s(_1,_2) Number of strict rules: 8 Direct POLO(bPol) ... removes: 14 sqr^1_p^1_s w: x1 + 2 * x2 + 3415 dec w: x1 + x2 s w: x1 sqr^1_p w: x1 + 2 * x2 + 3415 sqr^1_p^1_0 w: x1 + 3415 _ w: x1 + x2 p w: 2 * x1 + 2 * x2 + 1 0 w: 0 quad w: x1 sqr w: 2 * x1 + 5853 xpls w: x1 + x2 Number of strict rules: 8 Direct POLO(bPol) ... failed. Dependency Pairs: #1: #sqr^1_p^1_s(s(X),Y) -> #sqr^1_p(X,s(Y)) #2: #sqr^1_p^1_0(s(Y)) -> #quad(sqr^1_p^1_s(Y,0())) #3: #sqr^1_p^1_0(s(Y)) -> #sqr^1_p^1_s(Y,0()) #4: #quad(s(X)) -> #quad(X) #5: #sqr^1_p^1_s(0(),Y) -> #xpls(quad(sqr^1_p(Y,0())),s(quad(Y))) #6: #sqr^1_p^1_s(0(),Y) -> #quad(sqr^1_p(Y,0())) #7: #sqr^1_p^1_s(0(),Y) -> #sqr^1_p(Y,0()) #8: #sqr^1_p^1_s(0(),Y) -> #quad(Y) #9: #xpls(s(X),Y) -> #xpls(X,Y) #10: #sqr^1_p(s(_1),_2) ->? #sqr^1_p^1_s(_1,_2) #11: #dec(s(X),s(D)) -> #dec(X,D) #12: #sqr^1_p(0(),_1) ->? #sqr^1_p^1_0(_1) Number of SCCs: 4, DPs: 8 SCC { #4 } POLO(Sum)... succeeded. sqr^1_p^1_s w: 0 dec w: 0 s w: x1 + 1 sqr^1_p w: 0 #xpls w: 0 #sqr^1_p^1_0 w: 0 sqr^1_p^1_0 w: 0 #dec w: 0 _ w: 0 p w: 0 #sqr^1_p^1_s w: 0 0 w: 0 #quad w: x1 quad w: 0 #sqr^1_p w: 0 sqr w: 0 xpls w: 0 USABLE RULES: { } Removed DPs: #4 Number of SCCs: 3, DPs: 7 SCC { #9 } POLO(Sum)... succeeded. sqr^1_p^1_s w: 0 dec w: 0 s w: x1 + 1 sqr^1_p w: 0 #xpls w: x1 #sqr^1_p^1_0 w: 0 sqr^1_p^1_0 w: 0 #dec w: 0 _ w: 0 p w: 0 #sqr^1_p^1_s w: 0 0 w: 0 #quad w: 0 quad w: 0 #sqr^1_p w: 0 sqr w: 0 xpls w: 0 USABLE RULES: { } Removed DPs: #9 Number of SCCs: 2, DPs: 6 SCC { #11 } POLO(Sum)... succeeded. sqr^1_p^1_s w: 0 dec w: 0 s w: x1 + 1 sqr^1_p w: 0 #xpls w: 0 #sqr^1_p^1_0 w: 0 sqr^1_p^1_0 w: 0 #dec w: x1 _ w: 0 p w: 0 #sqr^1_p^1_s w: 0 0 w: 0 #quad w: 0 quad w: 0 #sqr^1_p w: 0 sqr w: 0 xpls w: 0 USABLE RULES: { } Removed DPs: #11 Number of SCCs: 1, DPs: 5 SCC { #1 #3 #7 #10 #12 } POLO(Sum)... succeeded. sqr^1_p^1_s w: 0 dec w: 0 s w: x1 + 3 sqr^1_p w: 0 #xpls w: 0 #sqr^1_p^1_0 w: x1 sqr^1_p^1_0 w: 0 #dec w: 0 _ w: 0 p w: 0 #sqr^1_p^1_s w: x1 + x2 + 1 0 w: 1 #quad w: 0 quad w: 0 #sqr^1_p w: x1 + x2 sqr w: 0 xpls w: 0 USABLE RULES: { } Removed DPs: #1 #3 #7 #10 #12 Number of SCCs: 0, DPs: 0 ... Input TRS: 1: dec(0(),D) -> 0() 2: dec(X,0()) -> X 3: dec(s(X),s(D)) -> dec(X,D) 4: xpls(0(),X) -> X 5: xpls(s(X),Y) -> s(xpls(X,Y)) 6: quad(0()) -> 0() 7: quad(s(X)) -> s(s(s(s(quad(X))))) 8: sqr(p(0(),0())) -> 0() 9: sqr(p(s(s(X)),Y)) -> sqr(p(X,s(Y))) 10: sqr(p(s(0()),Y)) -> xpls(quad(sqr(p(Y,0()))),s(quad(Y))) 11: sqr(p(0(),s(Y))) -> quad(sqr(p(s(Y),0()))) 12: _(X1,X2) -> X1 13: _(X1,X2) -> X2 Number of strict rules: 13 Direct POLO(bPol) ... removes: 8 1 12 13 2 dec w: 2 * x1 + x2 + 1651 s w: x1 _ w: 2 * x1 + 2 * x2 + 1 p w: x1 + 2 * x2 + 112 0 w: 0 quad w: x1 sqr w: x1 + 1102 xpls w: x1 + x2 Number of strict rules: 8 Direct POLO(bPol) ... failed. Uncurrying sqr^1_p sqr 3: dec(s(X),s(D)) -> dec(X,D) 4: xpls(0(),X) -> X 5: xpls(s(X),Y) -> s(xpls(X,Y)) 6: quad(0()) -> 0() 7: quad(s(X)) -> s(s(s(s(quad(X))))) 9: sqr^1_p^1_s(s(X),Y) -> sqr^1_p(X,s(Y)) 10: sqr^1_p^1_s(0(),Y) -> xpls(quad(sqr^1_p(Y,0())),s(quad(Y))) 11: sqr^1_p^1_0(s(Y)) -> quad(sqr^1_p^1_s(Y,0())) 14: sqr(p(_1,_2)) ->= sqr^1_p(_1,_2) 15: sqr^1_p(0(),_1) ->= sqr^1_p^1_0(_1) 16: sqr^1_p(s(_1),_2) ->= sqr^1_p^1_s(_1,_2) Number of strict rules: 8 Direct POLO(bPol) ... removes: 14 sqr^1_p^1_s w: x1 + 2 * x2 + 3415 dec w: x1 + x2 s w: x1 sqr^1_p w: x1 + 2 * x2 + 3415 sqr^1_p^1_0 w: x1 + 3415 _ w: x1 + x2 p w: 2 * x1 + 2 * x2 + 1 0 w: 0 quad w: x1 sqr w: 2 * x1 + 5853 xpls w: x1 + x2 Number of strict rules: 8 Direct POLO(bPol) ... failed. Dependency Pairs: #1: #sqr^1_p^1_s(s(X),Y) -> #sqr^1_p(X,s(Y)) #2: #sqr^1_p^1_0(s(Y)) -> #quad(sqr^1_p^1_s(Y,0())) #3: #sqr^1_p^1_0(s(Y)) -> #sqr^1_p^1_s(Y,0()) #4: #quad(s(X)) -> #quad(X) #5: #sqr^1_p^1_s(0(),Y) -> #xpls(quad(sqr^1_p(Y,0())),s(quad(Y))) #6: #sqr^1_p^1_s(0(),Y) -> #quad(sqr^1_p(Y,0())) #7: #sqr^1_p^1_s(0(),Y) -> #sqr^1_p(Y,0()) #8: #sqr^1_p^1_s(0(),Y) -> #quad(Y) #9: #xpls(s(X),Y) -> #xpls(X,Y) #10: #sqr^1_p(s(_1),_2) ->? #sqr^1_p^1_s(_1,_2) #11: #dec(s(X),s(D)) -> #dec(X,D) #12: #sqr^1_p(0(),_1) ->? #sqr^1_p^1_0(_1) Number of SCCs: 4, DPs: 8 SCC { #4 } POLO(Sum)... succeeded. sqr^1_p^1_s w: 0 dec w: 0 s w: x1 + 1 sqr^1_p w: 0 #xpls w: 0 #sqr^1_p^1_0 w: 0 sqr^1_p^1_0 w: 0 #dec w: 0 _ w: 0 p w: 0 #sqr^1_p^1_s w: 0 0 w: 0 #quad w: x1 quad w: 0 #sqr^1_p w: 0 sqr w: 0 xpls w: 0 USABLE RULES: { } Removed DPs: #4 Number of SCCs: 3, DPs: 7 SCC { #9 } POLO(Sum)... succeeded. sqr^1_p^1_s w: 0 dec w: 0 s w: x1 + 1 sqr^1_p w: 0 #xpls w: x1 #sqr^1_p^1_0 w: 0 sqr^1_p^1_0 w: 0 #dec w: 0 _ w: 0 p w: 0 #sqr^1_p^1_s w: 0 0 w: 0 #quad w: 0 quad w: 0 #sqr^1_p w: 0 sqr w: 0 xpls w: 0 USABLE RULES: { } Removed DPs: #9 Number of SCCs: 2, DPs: 6 SCC { #11 } POLO(Sum)... succeeded. sqr^1_p^1_s w: 0 dec w: 0 s w: x1 + 1 sqr^1_p w: 0 #xpls w: 0 #sqr^1_p^1_0 w: 0 sqr^1_p^1_0 w: 0 #dec w: x1 _ w: 0 p w: 0 #sqr^1_p^1_s w: 0 0 w: 0 #quad w: 0 quad w: 0 #sqr^1_p w: 0 sqr w: 0 xpls w: 0 USABLE RULES: { } Removed DPs: #11 Number of SCCs: 1, DPs: 5 SCC { #1 #3 #7 #10 #12 } POLO(Sum)... succeeded. sqr^1_p^1_s w: 0 dec w: 0 s w: x1 + 3 sqr^1_p w: 0 #xpls w: 0 #sqr^1_p^1_0 w: x1 sqr^1_p^1_0 w: 0 #dec w: 0 _ w: 0 p w: 0 #sqr^1_p^1_s w: x1 + x2 + 1 0 w: 1 #quad w: 0 quad w: 0 #sqr^1_p w: x1 + x2 sqr w: 0 xpls w: 0 USABLE RULES: { } Removed DPs: #1 #3 #7 #10 #12 Number of SCCs: 0, DPs: 0 >>YES ******** Signature ******** rec : (nat,nat,nat,((nat,nat) -> nat)) -> nat 0 : nat s : nat -> nat dec : (nat,nat) -> nat sumsqr : nat -> nat xpls : (nat,nat) -> nat sqr : nat -> nat p : (nat,nat) -> nat ******** Computation rules ******** (4) rec(0,D,U,F) => U (5) rec(s(X),s(D),U,F) => rec(dec(X,D),s(D),F[U,X],F) (6) sumsqr(X) => rec(X,s(0),0,z1.z2.xpls(sqr(p(s(z2),0)),z1)) ******** General Schema criterion ******** Found constructors: 0, s, p Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>OK Checking (1) dec(0,D) => 0 (fun dec>0) >>True Checking (2) dec(X,0) => X (meta X)[is acc in X,0] [is acc in X] >>True Checking (3) dec(s(X),s(D)) => dec(X,D) (fun dec=dec) subterm comparison of args w. LR LR (meta X)[is acc in s(X),s(D)] [is positive in s(X)] [is acc in X] (meta D)[is acc in s(X),s(D)] [is positive in s(X)] [is positive in s(D)] [is acc in D] >>True Checking (4) rec(0,D,U,F) => U (meta U)[is acc in 0,D,U,F] [is positive in 0] [is acc in U] >>True Checking (5) rec(s(X),s(D),U,F) => rec(dec(X,D),s(D),F[U,X],F) (fun rec=rec) subterm comparison of args w. LR LR >>False Try again using status RL Checking (1) dec(0,D) => 0 (fun dec>0) >>True Checking (2) dec(X,0) => X (meta X)[is acc in X,0] [is acc in X] >>True Checking (3) dec(s(X),s(D)) => dec(X,D) (fun dec=dec) subterm comparison of args w. RL RL (meta X)[is acc in s(X),s(D)] [is positive in s(X)] [is acc in X] (meta D)[is acc in s(X),s(D)] [is positive in s(X)] [is positive in s(D)] [is acc in D] >>True Checking (4) rec(0,D,U,F) => U (meta U)[is acc in 0,D,U,F] [is positive in 0] [is acc in U] >>True Checking (5) rec(s(X),s(D),U,F) => rec(dec(X,D),s(D),F[U,X],F) (fun rec=rec) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (1) dec(0,D) => 0 (fun dec>0) >>True Checking (2) dec(X,0) => X (meta X)[is acc in X,0] [is acc in X] >>True Checking (3) dec(s(X),s(D)) => dec(X,D) (fun dec=dec) subterm comparison of args w. Mul Mul (meta X)[is acc in s(X),s(D)] [is positive in s(X)] [is acc in X] (meta D)[is acc in s(X),s(D)] [is positive in s(X)] [is positive in s(D)] [is acc in D] >>True Checking (4) rec(0,D,U,F) => U (meta U)[is acc in 0,D,U,F] [is positive in 0] [is acc in U] >>True Checking (5) rec(s(X),s(D),U,F) => rec(dec(X,D),s(D),F[U,X],F) (fun rec=rec) subterm comparison of args w. Mul Mul >>False Found constructors: 0, s, dec, xpls, sqr, p Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>OK Checking (4) rec(0,D,U,F) => U (meta U)[is acc in 0,D,U,F] [is positive in 0] [is acc in U] >>True Checking (5) rec(s(X),s(D),U,F) => rec(dec(X,D),s(D),F[U,X],F) (fun rec=rec) subterm comparison of args w. LR LR >>False Try again using status RL Checking (4) rec(0,D,U,F) => U (meta U)[is acc in 0,D,U,F] [is positive in 0] [is acc in U] >>True Checking (5) rec(s(X),s(D),U,F) => rec(dec(X,D),s(D),F[U,X],F) (fun rec=rec) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (4) rec(0,D,U,F) => U (meta U)[is acc in 0,D,U,F] [is positive in 0] [is acc in U] >>True Checking (5) rec(s(X),s(D),U,F) => rec(dec(X,D),s(D),F[U,X],F) (fun rec=rec) subterm comparison of args w. Mul Mul >>False #No idea.. ******** Signature ******** 0 : nat s : nat -> nat dec : (nat,nat) -> nat rec : (nat,nat,nat,((nat,nat) -> nat)) -> nat sumsqr : nat -> nat xpls : (nat,nat) -> nat quad : nat -> nat sqr : nat -> nat p : (nat,nat) -> nat ******** Computation Rules ******** (1) dec(0,D) => 0 (2) dec(X,0) => X (3) dec(s(X),s(D)) => dec(X,D) (4) rec(0,D,U,F) => U (5) rec(s(X),s(D),U,F) => rec(dec(X,D),s(D),F[U,X],F) (6) sumsqr(X) => rec(X,s(0),0,z1.z2.xpls(sqr(p(s(z2),0)),z1)) (7) xpls(0,X) => X (8) xpls(s(X),Y) => s(xpls(X,Y)) (9) quad(0) => 0 (10) quad(s(X)) => s(s(s(s(quad(X))))) (11) sqr(p(0,0)) => 0 (12) sqr(p(s(s(X)),Y)) => sqr(p(X,s(Y))) (13) sqr(p(s(0),Y)) => xpls(quad(sqr(p(Y,0))),s(quad(Y))) (14) sqr(p(0,s(Y))) => quad(sqr(p(s(Y),0))) MAYBE