/export/starexec/sandbox2/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


YES
We consider the system theBenchmark.

We are asked to determine termination of the following first-order TRS.

  circ : [o * o] --> o 
  cons : [o * o] --> o 
  id : [] --> o 
  lift : [] --> o 
  msubst : [o * o] --> o 
  sop : [o] --> o 
  sortSu : [o] --> o 
  subst : [o * o] --> o 
  te : [o] --> o 

  sortSu(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) => sortSu(cons(te(msubst(te(X), sortSu(Z))), sortSu(circ(sortSu(Y), sortSu(Z))))) 
  sortSu(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) => sortSu(cons(te(Y), sortSu(circ(sortSu(X), sortSu(Z))))) 
  sortSu(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) => sortSu(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y))))) 
  sortSu(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) => sortSu(circ(sortSu(X), sortSu(circ(sortSu(Y), sortSu(Z))))) 
  sortSu(circ(sortSu(X), sortSu(id))) => sortSu(X) 
  sortSu(circ(sortSu(id), sortSu(X))) => sortSu(X) 
  sortSu(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) => sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y))))), sortSu(Z))) 
  te(subst(te(X), sortSu(id))) => te(X) 
  te(msubst(te(X), sortSu(id))) => te(X) 
  te(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) => te(msubst(te(X), sortSu(circ(sortSu(Y), sortSu(Z))))) 

We use the dependency pair framework as described in [Kop12, Ch. 6/7], with static dependency pairs (see [KusIsoSakBla09] and the adaptation for AFSMs in [Kop12, Ch. 7.8]).

We thus obtain the following dependency pair problem (P_0, R_0, minimal, formative):

  Dependency Pairs P_0:

    0] sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(cons(te(msubst(te(X), sortSu(Z))), sortSu(circ(sortSu(Y), sortSu(Z)))))   
    1] sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> te#(msubst(te(X), sortSu(Z)))   
    2] sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> te#(X)   
    3] sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Z)   
    4] sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(circ(sortSu(Y), sortSu(Z)))   
    5] sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Y)   
    6] sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Z)   
    7] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) =#> sortSu#(cons(te(Y), sortSu(circ(sortSu(X), sortSu(Z)))))   
    8] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) =#> te#(Y)   
    9] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) =#> sortSu#(circ(sortSu(X), sortSu(Z)))   
    10] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) =#> sortSu#(X)   
    11] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) =#> sortSu#(Z)   
    12] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) =#> sortSu#(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y)))))   
    13] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) =#> sortSu#(circ(sortSu(X), sortSu(Y)))   
    14] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) =#> sortSu#(X)   
    15] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) =#> sortSu#(Y)   
    16] sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(circ(sortSu(X), sortSu(circ(sortSu(Y), sortSu(Z)))))   
    17] sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(X)   
    18] sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(circ(sortSu(Y), sortSu(Z)))   
    19] sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Y)   
    20] sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Z)   
    21] sortSu#(circ(sortSu(X), sortSu(id))) =#> sortSu#(X)   
    22] sortSu#(circ(sortSu(id), sortSu(X))) =#> sortSu#(X)   
    23] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y))))), sortSu(Z)))   
    24] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y)))))   
    25] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(circ(sortSu(X), sortSu(Y)))   
    26] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(X)   
    27] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(Y)   
    28] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(Z)   
    29] te#(subst(te(X), sortSu(id))) =#> te#(X)   
    30] te#(msubst(te(X), sortSu(id))) =#> te#(X)   
    31] te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) =#> te#(msubst(te(X), sortSu(circ(sortSu(Y), sortSu(Z)))))   
    32] te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) =#> te#(X)   
    33] te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(circ(sortSu(Y), sortSu(Z)))   
    34] te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Y)   
    35] te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Z)   

  Rules R_0:

    sortSu(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) => sortSu(cons(te(msubst(te(X), sortSu(Z))), sortSu(circ(sortSu(Y), sortSu(Z))))) 
    sortSu(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) => sortSu(cons(te(Y), sortSu(circ(sortSu(X), sortSu(Z))))) 
    sortSu(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) => sortSu(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y))))) 
    sortSu(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) => sortSu(circ(sortSu(X), sortSu(circ(sortSu(Y), sortSu(Z))))) 
    sortSu(circ(sortSu(X), sortSu(id))) => sortSu(X) 
    sortSu(circ(sortSu(id), sortSu(X))) => sortSu(X) 
    sortSu(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) => sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y))))), sortSu(Z))) 
    te(subst(te(X), sortSu(id))) => te(X) 
    te(msubst(te(X), sortSu(id))) => te(X) 
    te(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) => te(msubst(te(X), sortSu(circ(sortSu(Y), sortSu(Z))))) 

Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_0, R_0, minimal, formative).

We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows:

    * 0 :  
    * 1 : 30, 31, 32, 33, 34, 35 
    * 2 : 29, 30, 31, 32, 33, 34, 35 
    * 3 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 4 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 5 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 6 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 7 :  
    * 8 : 29, 30, 31, 32, 33, 34, 35 
    * 9 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 10 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 11 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 12 :  
    * 13 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 14 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 15 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 16 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 17 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 18 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 19 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 20 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 21 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 22 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 23 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 24 :  
    * 25 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 26 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 27 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 28 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 29 : 29, 30, 31, 32, 33, 34, 35 
    * 30 : 29, 30, 31, 32, 33, 34, 35 
    * 31 : 30, 31, 32, 33, 34, 35 
    * 32 : 29, 30, 31, 32, 33, 34, 35 
    * 33 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 34 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 
    * 35 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 

This graph has the following strongly connected components:

  P_1:

    sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> te#(msubst(te(X), sortSu(Z)))   
    sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> te#(X)   
    sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Z)   
    sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(circ(sortSu(Y), sortSu(Z)))   
    sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Y)   
    sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Z)   
    sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) =#> te#(Y)   
    sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) =#> sortSu#(circ(sortSu(X), sortSu(Z)))   
    sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) =#> sortSu#(X)   
    sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) =#> sortSu#(Z)   
    sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) =#> sortSu#(circ(sortSu(X), sortSu(Y)))   
    sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) =#> sortSu#(X)   
    sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) =#> sortSu#(Y)   
    sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(circ(sortSu(X), sortSu(circ(sortSu(Y), sortSu(Z)))))   
    sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(X)   
    sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(circ(sortSu(Y), sortSu(Z)))   
    sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Y)   
    sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Z)   
    sortSu#(circ(sortSu(X), sortSu(id))) =#> sortSu#(X)   
    sortSu#(circ(sortSu(id), sortSu(X))) =#> sortSu#(X)   
    sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y))))), sortSu(Z)))   
    sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(circ(sortSu(X), sortSu(Y)))   
    sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(X)   
    sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(Y)   
    sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(Z)   
    te#(subst(te(X), sortSu(id))) =#> te#(X)   
    te#(msubst(te(X), sortSu(id))) =#> te#(X)   
    te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) =#> te#(msubst(te(X), sortSu(circ(sortSu(Y), sortSu(Z)))))   
    te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) =#> te#(X)   
    te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(circ(sortSu(Y), sortSu(Z)))   
    te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Y)   
    te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Z)   

By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_0, R_0, m, f) by (P_1, R_0, m, f).

Thus, the original system is terminating if (P_1, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_1, R_0, minimal, formative).

We will use the reduction pair processor [Kop12, Thm. 7.16].  It suffices to find a standard reduction pair [Kop12, Def. 6.69].  Thus, we must orient:

  sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) >? te#(msubst(te(X), sortSu(Z))) 
  sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) >? te#(X) 
  sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) >? sortSu#(Z) 
  sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) >? sortSu#(circ(sortSu(Y), sortSu(Z))) 
  sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) >? sortSu#(Y) 
  sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) >? sortSu#(Z) 
  sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) >? te#(Y) 
  sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) >? sortSu#(circ(sortSu(X), sortSu(Z))) 
  sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) >? sortSu#(X) 
  sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) >? sortSu#(Z) 
  sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) >? sortSu#(circ(sortSu(X), sortSu(Y))) 
  sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) >? sortSu#(X) 
  sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) >? sortSu#(Y) 
  sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) >? sortSu#(circ(sortSu(X), sortSu(circ(sortSu(Y), sortSu(Z))))) 
  sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) >? sortSu#(X) 
  sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) >? sortSu#(circ(sortSu(Y), sortSu(Z))) 
  sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) >? sortSu#(Y) 
  sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) >? sortSu#(Z) 
  sortSu#(circ(sortSu(X), sortSu(id))) >? sortSu#(X) 
  sortSu#(circ(sortSu(id), sortSu(X))) >? sortSu#(X) 
  sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) >? sortSu#(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y))))), sortSu(Z))) 
  sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) >? sortSu#(circ(sortSu(X), sortSu(Y))) 
  sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) >? sortSu#(X) 
  sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) >? sortSu#(Y) 
  sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) >? sortSu#(Z) 
  te#(subst(te(X), sortSu(id))) >? te#(X) 
  te#(msubst(te(X), sortSu(id))) >? te#(X) 
  te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) >? te#(msubst(te(X), sortSu(circ(sortSu(Y), sortSu(Z))))) 
  te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) >? te#(X) 
  te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) >? sortSu#(circ(sortSu(Y), sortSu(Z))) 
  te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) >? sortSu#(Y) 
  te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) >? sortSu#(Z) 
  sortSu(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) >= sortSu(cons(te(msubst(te(X), sortSu(Z))), sortSu(circ(sortSu(Y), sortSu(Z))))) 
  sortSu(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) >= sortSu(cons(te(Y), sortSu(circ(sortSu(X), sortSu(Z))))) 
  sortSu(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) >= sortSu(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y))))) 
  sortSu(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) >= sortSu(circ(sortSu(X), sortSu(circ(sortSu(Y), sortSu(Z))))) 
  sortSu(circ(sortSu(X), sortSu(id))) >= sortSu(X) 
  sortSu(circ(sortSu(id), sortSu(X))) >= sortSu(X) 
  sortSu(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) >= sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y))))), sortSu(Z))) 
  te(subst(te(X), sortSu(id))) >= te(X) 
  te(msubst(te(X), sortSu(id))) >= te(X) 
  te(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) >= te(msubst(te(X), sortSu(circ(sortSu(Y), sortSu(Z))))) 

We orient these requirements with a polynomial interpretation in the natural numbers.

The following interpretation satisfies the requirements:

  circ = \y0y1.3 + 2y1 + 3y0 + y0y1 
  cons = \y0y1.2 + y1 + 3y0 
  id = 3 
  lift = 0 
  msubst = \y0y1.3y0 + y0y1 
  sop = \y0.0 
  sortSu = \y0.2y0 
  sortSu# = \y0.2y0 
  subst = \y0y1.3 + y0y1 
  te = \y0.2 + 2y0 
  te# = \y0.2y0 

Using this interpretation, the requirements translate to:

  [[sortSu#(circ(sortSu(cons(te(_x0), sortSu(_x1))), sortSu(_x2)))]] = 102 + 16x1x2 + 24x1 + 48x0x2 + 72x0 + 72x2 > 12 + 8x0x2 + 8x2 + 12x0 = [[te#(msubst(te(_x0), sortSu(_x2)))]] 
  [[sortSu#(circ(sortSu(cons(te(_x0), sortSu(_x1))), sortSu(_x2)))]] = 102 + 16x1x2 + 24x1 + 48x0x2 + 72x0 + 72x2 > 2x0 = [[te#(_x0)]] 
  [[sortSu#(circ(sortSu(cons(te(_x0), sortSu(_x1))), sortSu(_x2)))]] = 102 + 16x1x2 + 24x1 + 48x0x2 + 72x0 + 72x2 > 2x2 = [[sortSu#(_x2)]] 
  [[sortSu#(circ(sortSu(cons(te(_x0), sortSu(_x1))), sortSu(_x2)))]] = 102 + 16x1x2 + 24x1 + 48x0x2 + 72x0 + 72x2 > 6 + 8x1x2 + 8x2 + 12x1 = [[sortSu#(circ(sortSu(_x1), sortSu(_x2)))]] 
  [[sortSu#(circ(sortSu(cons(te(_x0), sortSu(_x1))), sortSu(_x2)))]] = 102 + 16x1x2 + 24x1 + 48x0x2 + 72x0 + 72x2 > 2x1 = [[sortSu#(_x1)]] 
  [[sortSu#(circ(sortSu(cons(te(_x0), sortSu(_x1))), sortSu(_x2)))]] = 102 + 16x1x2 + 24x1 + 48x0x2 + 72x0 + 72x2 > 2x2 = [[sortSu#(_x2)]] 
  [[sortSu#(circ(sortSu(cons(sop(lift), sortSu(_x0))), sortSu(cons(te(_x1), sortSu(_x2)))))]] = 222 + 32x0x2 + 48x2 + 96x0x1 + 144x1 + 152x0 > 2x1 = [[te#(_x1)]] 
  [[sortSu#(circ(sortSu(cons(sop(lift), sortSu(_x0))), sortSu(cons(te(_x1), sortSu(_x2)))))]] = 222 + 32x0x2 + 48x2 + 96x0x1 + 144x1 + 152x0 > 6 + 8x0x2 + 8x2 + 12x0 = [[sortSu#(circ(sortSu(_x0), sortSu(_x2)))]] 
  [[sortSu#(circ(sortSu(cons(sop(lift), sortSu(_x0))), sortSu(cons(te(_x1), sortSu(_x2)))))]] = 222 + 32x0x2 + 48x2 + 96x0x1 + 144x1 + 152x0 > 2x0 = [[sortSu#(_x0)]] 
  [[sortSu#(circ(sortSu(cons(sop(lift), sortSu(_x0))), sortSu(cons(te(_x1), sortSu(_x2)))))]] = 222 + 32x0x2 + 48x2 + 96x0x1 + 144x1 + 152x0 > 2x2 = [[sortSu#(_x2)]] 
  [[sortSu#(circ(sortSu(cons(sop(lift), sortSu(_x0))), sortSu(cons(sop(lift), sortSu(_x1)))))]] = 78 + 32x0x1 + 48x1 + 56x0 > 6 + 8x0x1 + 8x1 + 12x0 = [[sortSu#(circ(sortSu(_x0), sortSu(_x1)))]] 
  [[sortSu#(circ(sortSu(cons(sop(lift), sortSu(_x0))), sortSu(cons(sop(lift), sortSu(_x1)))))]] = 78 + 32x0x1 + 48x1 + 56x0 > 2x0 = [[sortSu#(_x0)]] 
  [[sortSu#(circ(sortSu(cons(sop(lift), sortSu(_x0))), sortSu(cons(sop(lift), sortSu(_x1)))))]] = 78 + 32x0x1 + 48x1 + 56x0 > 2x1 = [[sortSu#(_x1)]] 
  [[sortSu#(circ(sortSu(circ(sortSu(_x0), sortSu(_x1))), sortSu(_x2)))]] = 42 + 32x0x1x2 + 32x1x2 + 32x2 + 48x0x1 + 48x0x2 + 48x1 + 72x0 > 30 + 32x0x1x2 + 32x0x2 + 32x1x2 + 32x2 + 36x0 + 48x0x1 + 48x1 = [[sortSu#(circ(sortSu(_x0), sortSu(circ(sortSu(_x1), sortSu(_x2)))))]] 
  [[sortSu#(circ(sortSu(circ(sortSu(_x0), sortSu(_x1))), sortSu(_x2)))]] = 42 + 32x0x1x2 + 32x1x2 + 32x2 + 48x0x1 + 48x0x2 + 48x1 + 72x0 > 2x0 = [[sortSu#(_x0)]] 
  [[sortSu#(circ(sortSu(circ(sortSu(_x0), sortSu(_x1))), sortSu(_x2)))]] = 42 + 32x0x1x2 + 32x1x2 + 32x2 + 48x0x1 + 48x0x2 + 48x1 + 72x0 > 6 + 8x1x2 + 8x2 + 12x1 = [[sortSu#(circ(sortSu(_x1), sortSu(_x2)))]] 
  [[sortSu#(circ(sortSu(circ(sortSu(_x0), sortSu(_x1))), sortSu(_x2)))]] = 42 + 32x0x1x2 + 32x1x2 + 32x2 + 48x0x1 + 48x0x2 + 48x1 + 72x0 > 2x1 = [[sortSu#(_x1)]] 
  [[sortSu#(circ(sortSu(circ(sortSu(_x0), sortSu(_x1))), sortSu(_x2)))]] = 42 + 32x0x1x2 + 32x1x2 + 32x2 + 48x0x1 + 48x0x2 + 48x1 + 72x0 > 2x2 = [[sortSu#(_x2)]] 
  [[sortSu#(circ(sortSu(_x0), sortSu(id)))]] = 30 + 36x0 > 2x0 = [[sortSu#(_x0)]] 
  [[sortSu#(circ(sortSu(id), sortSu(_x0)))]] = 42 + 32x0 > 2x0 = [[sortSu#(_x0)]] 
  [[sortSu#(circ(sortSu(cons(sop(lift), sortSu(_x0))), sortSu(circ(sortSu(cons(sop(lift), sortSu(_x1))), sortSu(_x2)))))]] = 390 + 128x0x1x2 + 192x0x1 + 192x0x2 + 192x1x2 + 264x0 + 288x1 + 288x2 > 102 + 64x0x1x2 + 64x1x2 + 72x2 + 96x0x1 + 96x0x2 + 96x1 + 144x0 = [[sortSu#(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(_x0), sortSu(_x1))))), sortSu(_x2)))]] 
  [[sortSu#(circ(sortSu(cons(sop(lift), sortSu(_x0))), sortSu(circ(sortSu(cons(sop(lift), sortSu(_x1))), sortSu(_x2)))))]] = 390 + 128x0x1x2 + 192x0x1 + 192x0x2 + 192x1x2 + 264x0 + 288x1 + 288x2 > 6 + 8x0x1 + 8x1 + 12x0 = [[sortSu#(circ(sortSu(_x0), sortSu(_x1)))]] 
  [[sortSu#(circ(sortSu(cons(sop(lift), sortSu(_x0))), sortSu(circ(sortSu(cons(sop(lift), sortSu(_x1))), sortSu(_x2)))))]] = 390 + 128x0x1x2 + 192x0x1 + 192x0x2 + 192x1x2 + 264x0 + 288x1 + 288x2 > 2x0 = [[sortSu#(_x0)]] 
  [[sortSu#(circ(sortSu(cons(sop(lift), sortSu(_x0))), sortSu(circ(sortSu(cons(sop(lift), sortSu(_x1))), sortSu(_x2)))))]] = 390 + 128x0x1x2 + 192x0x1 + 192x0x2 + 192x1x2 + 264x0 + 288x1 + 288x2 > 2x1 = [[sortSu#(_x1)]] 
  [[sortSu#(circ(sortSu(cons(sop(lift), sortSu(_x0))), sortSu(circ(sortSu(cons(sop(lift), sortSu(_x1))), sortSu(_x2)))))]] = 390 + 128x0x1x2 + 192x0x1 + 192x0x2 + 192x1x2 + 264x0 + 288x1 + 288x2 > 2x2 = [[sortSu#(_x2)]] 
  [[te#(subst(te(_x0), sortSu(id)))]] = 30 + 24x0 > 2x0 = [[te#(_x0)]] 
  [[te#(msubst(te(_x0), sortSu(id)))]] = 36 + 36x0 > 2x0 = [[te#(_x0)]] 
  [[te#(msubst(te(msubst(te(_x0), sortSu(_x1))), sortSu(_x2)))]] = 84 + 32x0x1x2 + 32x1x2 + 48x0x1 + 48x0x2 + 48x1 + 56x2 + 72x0 > 36 + 32x0x1x2 + 32x0x2 + 32x1x2 + 32x2 + 36x0 + 48x0x1 + 48x1 = [[te#(msubst(te(_x0), sortSu(circ(sortSu(_x1), sortSu(_x2)))))]] 
  [[te#(msubst(te(msubst(te(_x0), sortSu(_x1))), sortSu(_x2)))]] = 84 + 32x0x1x2 + 32x1x2 + 48x0x1 + 48x0x2 + 48x1 + 56x2 + 72x0 > 2x0 = [[te#(_x0)]] 
  [[te#(msubst(te(msubst(te(_x0), sortSu(_x1))), sortSu(_x2)))]] = 84 + 32x0x1x2 + 32x1x2 + 48x0x1 + 48x0x2 + 48x1 + 56x2 + 72x0 > 6 + 8x1x2 + 8x2 + 12x1 = [[sortSu#(circ(sortSu(_x1), sortSu(_x2)))]] 
  [[te#(msubst(te(msubst(te(_x0), sortSu(_x1))), sortSu(_x2)))]] = 84 + 32x0x1x2 + 32x1x2 + 48x0x1 + 48x0x2 + 48x1 + 56x2 + 72x0 > 2x1 = [[sortSu#(_x1)]] 
  [[te#(msubst(te(msubst(te(_x0), sortSu(_x1))), sortSu(_x2)))]] = 84 + 32x0x1x2 + 32x1x2 + 48x0x1 + 48x0x2 + 48x1 + 56x2 + 72x0 > 2x2 = [[sortSu#(_x2)]] 
  [[sortSu(circ(sortSu(cons(te(_x0), sortSu(_x1))), sortSu(_x2)))]] = 102 + 16x1x2 + 24x1 + 48x0x2 + 72x0 + 72x2 >= 100 + 16x1x2 + 24x1 + 48x0x2 + 64x2 + 72x0 = [[sortSu(cons(te(msubst(te(_x0), sortSu(_x2))), sortSu(circ(sortSu(_x1), sortSu(_x2)))))]] 
  [[sortSu(circ(sortSu(cons(sop(lift), sortSu(_x0))), sortSu(cons(te(_x1), sortSu(_x2)))))]] = 222 + 32x0x2 + 48x2 + 96x0x1 + 144x1 + 152x0 >= 28 + 12x1 + 16x0x2 + 16x2 + 24x0 = [[sortSu(cons(te(_x1), sortSu(circ(sortSu(_x0), sortSu(_x2)))))]] 
  [[sortSu(circ(sortSu(cons(sop(lift), sortSu(_x0))), sortSu(cons(sop(lift), sortSu(_x1)))))]] = 78 + 32x0x1 + 48x1 + 56x0 >= 16 + 16x0x1 + 16x1 + 24x0 = [[sortSu(cons(sop(lift), sortSu(circ(sortSu(_x0), sortSu(_x1)))))]] 
  [[sortSu(circ(sortSu(circ(sortSu(_x0), sortSu(_x1))), sortSu(_x2)))]] = 42 + 32x0x1x2 + 32x1x2 + 32x2 + 48x0x1 + 48x0x2 + 48x1 + 72x0 >= 30 + 32x0x1x2 + 32x0x2 + 32x1x2 + 32x2 + 36x0 + 48x0x1 + 48x1 = [[sortSu(circ(sortSu(_x0), sortSu(circ(sortSu(_x1), sortSu(_x2)))))]] 
  [[sortSu(circ(sortSu(_x0), sortSu(id)))]] = 30 + 36x0 >= 2x0 = [[sortSu(_x0)]] 
  [[sortSu(circ(sortSu(id), sortSu(_x0)))]] = 42 + 32x0 >= 2x0 = [[sortSu(_x0)]] 
  [[sortSu(circ(sortSu(cons(sop(lift), sortSu(_x0))), sortSu(circ(sortSu(cons(sop(lift), sortSu(_x1))), sortSu(_x2)))))]] = 390 + 128x0x1x2 + 192x0x1 + 192x0x2 + 192x1x2 + 264x0 + 288x1 + 288x2 >= 102 + 64x0x1x2 + 64x1x2 + 72x2 + 96x0x1 + 96x0x2 + 96x1 + 144x0 = [[sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(_x0), sortSu(_x1))))), sortSu(_x2)))]] 
  [[te(subst(te(_x0), sortSu(id)))]] = 32 + 24x0 >= 2 + 2x0 = [[te(_x0)]] 
  [[te(msubst(te(_x0), sortSu(id)))]] = 38 + 36x0 >= 2 + 2x0 = [[te(_x0)]] 
  [[te(msubst(te(msubst(te(_x0), sortSu(_x1))), sortSu(_x2)))]] = 86 + 32x0x1x2 + 32x1x2 + 48x0x1 + 48x0x2 + 48x1 + 56x2 + 72x0 >= 38 + 32x0x1x2 + 32x0x2 + 32x1x2 + 32x2 + 36x0 + 48x0x1 + 48x1 = [[te(msubst(te(_x0), sortSu(circ(sortSu(_x1), sortSu(_x2)))))]] 

By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_1, R_0) by ({}, R_0).  By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed.

As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination.


+++ Citations +++

[Kop12]  C. Kop.  Higher Order Termination.  PhD Thesis, 2012.
[KusIsoSakBla09]  K. Kusakari, Y. Isogai, M. Sakai, and F. Blanqui.  Static Dependency Pair Method Based On Strong Computability for Higher-Order Rewrite Systems.  In volume 92(10) of IEICE Transactions on Information and Systems.  2007--2015, 2009.