/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: 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: log2(s(0()),0()) -> 0() 7: log2(0(),s(Y)) -> s(log2(s(Y),0())) 8: log2(s(0()),s(Y)) -> s(log2(s(Y),0())) 9: log2(s(s(X)),Y) -> log2(X,s(Y)) 10: _(X1,X2) -> X1 11: _(X1,X2) -> X2 Number of strict rules: 11 Direct POLO(bPol) ... removes: 4 1 10 11 6 2 dec w: x1 + x2 + 1 s w: x1 _ w: 2 * x1 + 2 * x2 + 1 0 w: 1797 xpls w: 2 * x1 + x2 + 1 log2 w: x1 + x2 + 281 Number of strict rules: 5 Direct POLO(bPol) ... removes: 8 3 5 dec w: 2 * x1 + x2 + 1798 s w: x1 + 8587 _ w: 2 * x1 + 2 * x2 + 1 0 w: 0 xpls w: 2 * x1 + x2 + 591 log2 w: x1 + 2 * x2 + 2616 Number of strict rules: 2 Direct POLO(bPol) ... failed. Uncurrying log2 7: log2^1_0(s(Y)) -> s(log2^1_s(Y,0())) 9: log2^1_s(s(X),Y) -> log2(X,s(Y)) 12: log2(0(),_1) ->= log2^1_0(_1) 13: log2(s(_1),_2) ->= log2^1_s(_1,_2) Number of strict rules: 2 Direct POLO(bPol) ... removes: 7 12 9 13 dec w: x1 + x2 s w: x1 + 3 _ w: x1 + x2 0 w: 1237 log2^1_0 w: 2 * x1 + 4755 log2^1_s w: 2 * x1 + 2 * x2 + 2283 xpls w: x1 + x2 log2 w: 2 * x1 + 2 * x2 + 2282 Number of strict rules: 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: log2(s(0()),0()) -> 0() 7: log2(0(),s(Y)) -> s(log2(s(Y),0())) 8: log2(s(0()),s(Y)) -> s(log2(s(Y),0())) 9: log2(s(s(X)),Y) -> log2(X,s(Y)) 10: _(X1,X2) -> X1 11: _(X1,X2) -> X2 Number of strict rules: 11 Direct POLO(bPol) ... removes: 4 1 10 11 6 2 dec w: x1 + x2 + 1 s w: x1 _ w: 2 * x1 + 2 * x2 + 1 0 w: 1797 xpls w: 2 * x1 + x2 + 1 log2 w: x1 + x2 + 281 Number of strict rules: 5 Direct POLO(bPol) ... removes: 8 3 5 dec w: 2 * x1 + x2 + 1798 s w: x1 + 8587 _ w: 2 * x1 + 2 * x2 + 1 0 w: 0 xpls w: 2 * x1 + x2 + 591 log2 w: x1 + 2 * x2 + 2616 Number of strict rules: 2 Direct POLO(bPol) ... failed. Uncurrying log2 7: log2^1_0(s(Y)) -> s(log2^1_s(Y,0())) 9: log2^1_s(s(X),Y) -> log2(X,s(Y)) 12: log2(0(),_1) ->= log2^1_0(_1) 13: log2(s(_1),_2) ->= log2^1_s(_1,_2) Number of strict rules: 2 Direct POLO(bPol) ... removes: 7 12 9 13 dec w: x1 + x2 s w: x1 + 3 _ w: x1 + x2 0 w: 1237 log2^1_0 w: 2 * x1 + 4755 log2^1_s w: 2 * x1 + 2 * x2 + 2283 xpls w: x1 + x2 log2 w: 2 * x1 + 2 * x2 + 2282 Number of strict rules: 0 >>YES ******** Signature ******** grec : (nat,nat,nat,((nat,nat) -> nat)) -> nat 0 : nat s : nat -> nat dec : (nat,nat) -> nat sumlog : nat -> nat xpls : (nat,nat) -> nat log2 : (nat,nat) -> nat ******** Computation rules ******** (4) grec(0,D,U,F) => U (5) grec(s(X),s(D),U,F) => grec(dec(X,D),s(D),F[U,X],F) (6) sumlog(X) => grec(X,s(s(0)),0,z1.z2.xpls(log2(s(z2),0),z1)) ******** General Schema criterion ******** Found constructors: 0, s 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) grec(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) grec(s(X),s(D),U,F) => grec(dec(X,D),s(D),F[U,X],F) (fun grec=grec) 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) grec(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) grec(s(X),s(D),U,F) => grec(dec(X,D),s(D),F[U,X],F) (fun grec=grec) 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) grec(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) grec(s(X),s(D),U,F) => grec(dec(X,D),s(D),F[U,X],F) (fun grec=grec) subterm comparison of args w. Mul Mul >>False Found constructors: 0, s, dec, xpls, log2 Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>OK Checking (4) grec(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) grec(s(X),s(D),U,F) => grec(dec(X,D),s(D),F[U,X],F) (fun grec=grec) subterm comparison of args w. LR LR >>False Try again using status RL Checking (4) grec(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) grec(s(X),s(D),U,F) => grec(dec(X,D),s(D),F[U,X],F) (fun grec=grec) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (4) grec(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) grec(s(X),s(D),U,F) => grec(dec(X,D),s(D),F[U,X],F) (fun grec=grec) subterm comparison of args w. Mul Mul >>False #No idea.. ******** Signature ******** 0 : nat s : nat -> nat dec : (nat,nat) -> nat grec : (nat,nat,nat,((nat,nat) -> nat)) -> nat sumlog : nat -> nat xpls : (nat,nat) -> nat log2 : (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) grec(0,D,U,F) => U (5) grec(s(X),s(D),U,F) => grec(dec(X,D),s(D),F[U,X],F) (6) sumlog(X) => grec(X,s(s(0)),0,z1.z2.xpls(log2(s(z2),0),z1)) (7) xpls(0,X) => X (8) xpls(s(X),Y) => s(xpls(X,Y)) (9) log2(s(0),0) => 0 (10) log2(0,s(Y)) => s(log2(s(Y),0)) (11) log2(s(0),s(Y)) => s(log2(s(Y),0)) (12) log2(s(s(X)),Y) => log2(X,s(Y)) MAYBE