/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: min(X,0()) -> 0()
    2: min(0(),Y) -> 0()
    3: min(s(U),s(V)) -> s(min(U,V))
    4: diff(W,0()) -> W
    5: diff(0(),P) -> P
    6: diff(s(X1),s(Y1)) -> diff(X1,Y1)
    7: gcd(s(U1),0()) -> s(U1)
    8: gcd(0(),s(V1)) -> s(V1)
    9: gcd(s(W1),s(P1)) -> gcd(diff(W1,P1),s(min(W1,P1)))
    10: _(X1,X2) -> X1
    11: _(X1,X2) -> X2
Number of strict rules: 11
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
   #1: #diff(s(X1),s(Y1)) -> #diff(X1,Y1)
   #2: #gcd(s(W1),s(P1)) -> #gcd(diff(W1,P1),s(min(W1,P1)))
   #3: #gcd(s(W1),s(P1)) -> #diff(W1,P1)
   #4: #gcd(s(W1),s(P1)) -> #min(W1,P1)
   #5: #min(s(U),s(V)) -> #min(U,V)
Number of SCCs: 3, DPs: 3
  SCC { #1 }
POLO(Sum)... succeeded.
      diff	w: 0
      s 	w: x1 + 1
      gcd	w: 0
      #min	w: 0
      _ 	w: 0
      0 	w: 0
      #diff	w: x1 + x2
      #_ 	w: 0
      min	w: 0
      #gcd	w: 0
    USABLE RULES: { }
    Removed DPs: #1
Number of SCCs: 2, DPs: 2
  SCC { #5 }
POLO(Sum)... succeeded.
      diff	w: 0
      s 	w: x1 + 1
      gcd	w: 0
      #min	w: x1
      _ 	w: 0
      0 	w: 0
      #diff	w: 0
      #_ 	w: 0
      min	w: 0
      #gcd	w: 0
    USABLE RULES: { }
    Removed DPs: #5
Number of SCCs: 1, DPs: 1
  SCC { #2 }
POLO(Sum)... POLO(max)... succeeded.
      diff	w: max(x1 + 8815, x2 + 8366)
      s 	w: x1 + 11255
      gcd	w: 0
      #min	w: 0
      _ 	w: 0
      0 	w: 1
      #diff	w: 0
      #_ 	w: 0
      min	w: max(x1 + 2438)
      #gcd	w: max(x1 + 2974, x2 + 535)
    USABLE RULES: { 1..6 }
    Removed DPs: #2
Number of SCCs: 0, DPs: 0

...
Input TRS:
    1: min(X,0()) -> 0()
    2: min(0(),Y) -> 0()
    3: min(s(U),s(V)) -> s(min(U,V))
    4: diff(W,0()) -> W
    5: diff(0(),P) -> P
    6: diff(s(X1),s(Y1)) -> diff(X1,Y1)
    7: gcd(s(U1),0()) -> s(U1)
    8: gcd(0(),s(V1)) -> s(V1)
    9: gcd(s(W1),s(P1)) -> gcd(diff(W1,P1),s(min(W1,P1)))
    10: _(X1,X2) -> X1
    11: _(X1,X2) -> X2
Number of strict rules: 11
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
   #1: #diff(s(X1),s(Y1)) -> #diff(X1,Y1)
   #2: #gcd(s(W1),s(P1)) -> #gcd(diff(W1,P1),s(min(W1,P1)))
   #3: #gcd(s(W1),s(P1)) -> #diff(W1,P1)
   #4: #gcd(s(W1),s(P1)) -> #min(W1,P1)
   #5: #min(s(U),s(V)) -> #min(U,V)
Number of SCCs: 3, DPs: 3
  SCC { #1 }
POLO(Sum)... succeeded.
      diff	w: 0
      s 	w: x1 + 1
      gcd	w: 0
      #min	w: 0
      _ 	w: 0
      0 	w: 0
      #diff	w: x1 + x2
      #_ 	w: 0
      min	w: 0
      #gcd	w: 0
    USABLE RULES: { }
    Removed DPs: #1
Number of SCCs: 2, DPs: 2
  SCC { #5 }
POLO(Sum)... succeeded.
      diff	w: 0
      s 	w: x1 + 1
      gcd	w: 0
      #min	w: x1
      _ 	w: 0
      0 	w: 0
      #diff	w: 0
      #_ 	w: 0
      min	w: 0
      #gcd	w: 0
    USABLE RULES: { }
    Removed DPs: #5
Number of SCCs: 1, DPs: 1
  SCC { #2 }
POLO(Sum)... POLO(max)... succeeded.
      diff	w: max(x1 + 8815, x2 + 8366)
      s 	w: x1 + 11255
      gcd	w: 0
      #min	w: 0
      _ 	w: 0
      0 	w: 1
      #diff	w: 0
      #_ 	w: 0
      min	w: max(x1 + 2438)
      #gcd	w: max(x1 + 2974, x2 + 535)
    USABLE RULES: { 1..6 }
    Removed DPs: #2
Number of SCCs: 0, DPs: 0
>>YES

******** Signature ********
 build : nat -> list
 0 : nat
 nil : list
 collapse : list -> nat
 cons : ((nat -> nat),list) -> list
 s : nat -> nat
 gcd : (nat,nat) -> nat
******** Computation rules ********
 (12)  build(0) => nil
 (10)  collapse(nil) => 0
 (11)  collapse(cons(F2,Y2)) => F2[collapse(Y2)]
 (13)  build(s(U2)) => cons(%X.gcd(%X,U2),build(U2))


******** General Schema criterion ********
Found constructors: 0, cons, nil, s
Checking type order >>OK
Checking positivity of constructors >>OK
Checking function dependency >>OK
Checking  (1) min(X,0) => 0
 (fun min>0) >>True
Checking  (2) min(0,Y) => 0
 (fun min>0) >>True
Checking  (3) min(s(U),s(V)) => s(min(U,V))
 (fun min>s)
 (fun min=min) subterm comparison of args w. LR LR
 (meta U)[is acc in s(U),s(V)] [is positive in s(U)] [is acc in U] 
 (meta V)[is acc in s(U),s(V)] [is positive in s(U)] [is positive in s(V)] [is acc in V]  >>True
Checking  (4) diff(W,0) => W
 (meta W)[is acc in W,0] [is acc in W]  >>True
Checking  (5) diff(0,P) => P
 (meta P)[is acc in 0,P] [is positive in 0] [is acc in P]  >>True
Checking  (6) diff(s(X1),s(Y1)) => diff(X1,Y1)
 (fun diff=diff) subterm comparison of args w. LR LR
 (meta X1)[is acc in s(X1),s(Y1)] [is positive in s(X1)] [is acc in X1] 
 (meta Y1)[is acc in s(X1),s(Y1)] [is positive in s(X1)] [is positive in s(Y1)] [is acc in Y1]  >>True
Checking  (7) gcd(s(U1),0) => s(U1)
 (fun gcd>s)
 (meta U1)[is acc in s(U1),0] [is positive in s(U1)] [is acc in U1]  >>True
Checking  (8) gcd(0,s(V1)) => s(V1)
 (fun gcd>s)
 (meta V1)[is acc in 0,s(V1)] [is positive in 0] [is positive in s(V1)] [is acc in V1]  >>True
Checking  (9) gcd(s(W1),s(P1)) => gcd(diff(W1,P1),s(min(W1,P1)))
 (fun gcd=gcd) subterm comparison of args w. LR LR >>False

Try again using status RL
Checking  (1) min(X,0) => 0
 (fun min>0) >>True
Checking  (2) min(0,Y) => 0
 (fun min>0) >>True
Checking  (3) min(s(U),s(V)) => s(min(U,V))
 (fun min>s)
 (fun min=min) subterm comparison of args w. RL RL
 (meta U)[is acc in s(U),s(V)] [is positive in s(U)] [is acc in U] 
 (meta V)[is acc in s(U),s(V)] [is positive in s(U)] [is positive in s(V)] [is acc in V]  >>True
Checking  (4) diff(W,0) => W
 (meta W)[is acc in W,0] [is acc in W]  >>True
Checking  (5) diff(0,P) => P
 (meta P)[is acc in 0,P] [is positive in 0] [is acc in P]  >>True
Checking  (6) diff(s(X1),s(Y1)) => diff(X1,Y1)
 (fun diff=diff) subterm comparison of args w. RL RL
 (meta X1)[is acc in s(X1),s(Y1)] [is positive in s(X1)] [is acc in X1] 
 (meta Y1)[is acc in s(X1),s(Y1)] [is positive in s(X1)] [is positive in s(Y1)] [is acc in Y1]  >>True
Checking  (7) gcd(s(U1),0) => s(U1)
 (fun gcd>s)
 (meta U1)[is acc in s(U1),0] [is positive in s(U1)] [is acc in U1]  >>True
Checking  (8) gcd(0,s(V1)) => s(V1)
 (fun gcd>s)
 (meta V1)[is acc in 0,s(V1)] [is positive in 0] [is positive in s(V1)] [is acc in V1]  >>True
Checking  (9) gcd(s(W1),s(P1)) => gcd(diff(W1,P1),s(min(W1,P1)))
 (fun gcd=gcd) subterm comparison of args w. RL RL >>False

Try again using status Mul
Checking  (1) min(X,0) => 0
 (fun min>0) >>True
Checking  (2) min(0,Y) => 0
 (fun min>0) >>True
Checking  (3) min(s(U),s(V)) => s(min(U,V))
 (fun min>s)
 (fun min=min) subterm comparison of args w. Mul Mul
 (meta U)[is acc in s(U),s(V)] [is positive in s(U)] [is acc in U] 
 (meta V)[is acc in s(U),s(V)] [is positive in s(U)] [is positive in s(V)] [is acc in V]  >>True
Checking  (4) diff(W,0) => W
 (meta W)[is acc in W,0] [is acc in W]  >>True
Checking  (5) diff(0,P) => P
 (meta P)[is acc in 0,P] [is positive in 0] [is acc in P]  >>True
Checking  (6) diff(s(X1),s(Y1)) => diff(X1,Y1)
 (fun diff=diff) subterm comparison of args w. Mul Mul
 (meta X1)[is acc in s(X1),s(Y1)] [is positive in s(X1)] [is acc in X1] 
 (meta Y1)[is acc in s(X1),s(Y1)] [is positive in s(X1)] [is positive in s(Y1)] [is acc in Y1]  >>True
Checking  (7) gcd(s(U1),0) => s(U1)
 (fun gcd>s)
 (meta U1)[is acc in s(U1),0] [is positive in s(U1)] [is acc in U1]  >>True
Checking  (8) gcd(0,s(V1)) => s(V1)
 (fun gcd>s)
 (meta V1)[is acc in 0,s(V1)] [is positive in 0] [is positive in s(V1)] [is acc in V1]  >>True
Checking  (9) gcd(s(W1),s(P1)) => gcd(diff(W1,P1),s(min(W1,P1)))
 (fun gcd=gcd) subterm comparison of args w. Mul Mul >>False
Found constructors: 0, nil, cons, s, gcd
Checking type order >>OK
Checking positivity of constructors >>OK
Checking function dependency >>OK
Checking  (12) build(0) => nil
 (fun build>nil) >>True
Checking  (10) collapse(nil) => 0
 (fun collapse>0) >>True
Checking  (11) collapse(cons(F2,Y2)) => F2[collapse(Y2)]
 (meta F2)[is acc in cons(F2,Y2)] [is positive in cons(F2,Y2)] [is acc in F2] 
 (fun collapse=collapse) subterm comparison of args w. LR LR
 (meta Y2)[is acc in cons(F2,Y2)] [is positive in cons(F2,Y2)] [is acc in Y2]  >>True
Checking  (13) build(s(U2)) => cons(%X.gcd(%X,U2),build(U2))
 (fun build>cons)
 (fun build>gcd)
 (meta U2)[is acc in s(U2)] [is positive in s(U2)] [is acc in U2] 
 (fun build=build) subterm comparison of args w. LR LR
 (meta U2)[is acc in s(U2)] [is positive in s(U2)] [is acc in U2]  >>True
#SN!
******** Signature ********
 0 : nat
 build : nat -> list
 collapse : list -> nat
 cons : ((nat -> nat),list) -> list
 diff : (nat,nat) -> nat
 gcd : (nat,nat) -> nat
 min : (nat,nat) -> nat
 nil : list
 s : nat -> nat
******** Computation Rules ********
 (1)  min(X,0) => 0
 (2)  min(0,Y) => 0
 (3)  min(s(U),s(V)) => s(min(U,V))
 (4)  diff(W,0) => W
 (5)  diff(0,P) => P
 (6)  diff(s(X1),s(Y1)) => diff(X1,Y1)
 (7)  gcd(s(U1),0) => s(U1)
 (8)  gcd(0,s(V1)) => s(V1)
 (9)  gcd(s(W1),s(P1)) => gcd(diff(W1,P1),s(min(W1,P1)))
 (10)  collapse(nil) => 0
 (11)  collapse(cons(F2,Y2)) => F2[collapse(Y2)]
 (12)  build(0) => nil
 (13)  build(s(U2)) => cons(%X.gcd(%X,U2),build(U2))

YES