/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.

  cons : [o * o] --> o 
  if : [o * o] --> o 
  iff : [o * o] --> o 
  intersect!450ii!450in : [o * o] --> o 
  intersect!450ii!450out : [] --> o 
  nil : [] --> o 
  p : [o] --> o 
  reduce!450ii!450in : [o * o] --> o 
  reduce!450ii!450out : [] --> o 
  sequent : [o * o] --> o 
  tautology!450i!450in : [o] --> o 
  tautology!450i!450out : [] --> o 
  u!4501!4501 : [o] --> o 
  u!45010!4501 : [o] --> o 
  u!45011!4501 : [o] --> o 
  u!45012!4501 : [o * o * o * o * o] --> o 
  u!45012!4502 : [o] --> o 
  u!45013!4501 : [o] --> o 
  u!45014!4501 : [o] --> o 
  u!45015!4501 : [o] --> o 
  u!45016!4501 : [o] --> o 
  u!4502!4501 : [o] --> o 
  u!4503!4501 : [o] --> o 
  u!4504!4501 : [o] --> o 
  u!4505!4501 : [o] --> o 
  u!4506!4501 : [o * o * o * o * o] --> o 
  u!4506!4502 : [o] --> o 
  u!4507!4501 : [o] --> o 
  u!4508!4501 : [o] --> o 
  u!4509!4501 : [o] --> o 
  x!4502a : [o * o] --> o 
  x!4502b : [o * o] --> o 
  x!4502d : [o] --> o 

  intersect!450ii!450in(cons(X, Y), cons(X, Z)) => intersect!450ii!450out 
  intersect!450ii!450in(X, cons(Y, Z)) => u!4501!4501(intersect!450ii!450in(X, Z)) 
  u!4501!4501(intersect!450ii!450out) => intersect!450ii!450out 
  intersect!450ii!450in(cons(X, Y), Z) => u!4502!4501(intersect!450ii!450in(Y, Z)) 
  u!4502!4501(intersect!450ii!450out) => intersect!450ii!450out 
  reduce!450ii!450in(sequent(cons(if(X, Y), Z), U), V) => u!4503!4501(reduce!450ii!450in(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V)) 
  u!4503!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(iff(X, Y), Z), U), V) => u!4504!4501(reduce!450ii!450in(sequent(cons(x!4502a(if(X, Y), if(Y, X)), Z), U), V)) 
  u!4504!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502a(X, Y), Z), U), V) => u!4505!4501(reduce!450ii!450in(sequent(cons(X, cons(Y, Z)), U), V)) 
  u!4505!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502b(X, Y), Z), U), V) => u!4506!4501(reduce!450ii!450in(sequent(cons(X, Z), U), V), Y, Z, U, V) 
  u!4506!4501(reduce!450ii!450out, X, Y, Z, U) => u!4506!4502(reduce!450ii!450in(sequent(cons(X, Y), Z), U)) 
  u!4506!4502(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502d(X), Y), Z), U) => u!4507!4501(reduce!450ii!450in(sequent(Y, cons(X, Z)), U)) 
  u!4507!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(if(Y, Z), U)), V) => u!4508!4501(reduce!450ii!450in(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V)) 
  u!4508!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(iff(Y, Z), U)), V) => u!4509!4501(reduce!450ii!450in(sequent(X, cons(x!4502a(if(Y, Z), if(Z, Y)), U)), V)) 
  u!4509!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(p(X), Y), Z), sequent(U, V)) => u!45010!4501(reduce!450ii!450in(sequent(Y, Z), sequent(cons(p(X), U), V))) 
  u!45010!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502b(Y, Z), U)), V) => u!45011!4501(reduce!450ii!450in(sequent(X, cons(Y, cons(Z, U))), V)) 
  u!45011!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502a(Y, Z), U)), V) => u!45012!4501(reduce!450ii!450in(sequent(X, cons(Y, U)), V), X, Z, U, V) 
  u!45012!4501(reduce!450ii!450out, X, Y, Z, U) => u!45012!4502(reduce!450ii!450in(sequent(X, cons(Y, Z)), U)) 
  u!45012!4502(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502d(Y), Z)), U) => u!45013!4501(reduce!450ii!450in(sequent(cons(Y, X), Z), U)) 
  u!45013!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(nil, cons(p(X), Y)), sequent(Z, U)) => u!45014!4501(reduce!450ii!450in(sequent(nil, Y), sequent(Z, cons(p(X), U)))) 
  u!45014!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(nil, nil), sequent(X, Y)) => u!45015!4501(intersect!450ii!450in(X, Y)) 
  u!45015!4501(intersect!450ii!450out) => reduce!450ii!450out 
  tautology!450i!450in(X) => u!45016!4501(reduce!450ii!450in(sequent(nil, cons(X, nil)), sequent(nil, nil))) 
  u!45016!4501(reduce!450ii!450out) => tautology!450i!450out 

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, all):

  Dependency Pairs P_0:

    0] intersect!450ii!450in#(X, cons(Y, Z)) =#> u!4501!4501#(intersect!450ii!450in(X, Z))   
    1] intersect!450ii!450in#(X, cons(Y, Z)) =#> intersect!450ii!450in#(X, Z)   
    2] intersect!450ii!450in#(cons(X, Y), Z) =#> u!4502!4501#(intersect!450ii!450in(Y, Z))   
    3] intersect!450ii!450in#(cons(X, Y), Z) =#> intersect!450ii!450in#(Y, Z)   
    4] reduce!450ii!450in#(sequent(cons(if(X, Y), Z), U), V) =#> u!4503!4501#(reduce!450ii!450in(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V))   
    5] reduce!450ii!450in#(sequent(cons(if(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V)   
    6] reduce!450ii!450in#(sequent(cons(iff(X, Y), Z), U), V) =#> u!4504!4501#(reduce!450ii!450in(sequent(cons(x!4502a(if(X, Y), if(Y, X)), Z), U), V))   
    7] reduce!450ii!450in#(sequent(cons(iff(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(x!4502a(if(X, Y), if(Y, X)), Z), U), V)   
    8] reduce!450ii!450in#(sequent(cons(x!4502a(X, Y), Z), U), V) =#> u!4505!4501#(reduce!450ii!450in(sequent(cons(X, cons(Y, Z)), U), V))   
    9] reduce!450ii!450in#(sequent(cons(x!4502a(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(X, cons(Y, Z)), U), V)   
    10] reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) =#> u!4506!4501#(reduce!450ii!450in(sequent(cons(X, Z), U), V), Y, Z, U, V)   
    11] reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(X, Z), U), V)   
    12] u!4506!4501#(reduce!450ii!450out, X, Y, Z, U) =#> u!4506!4502#(reduce!450ii!450in(sequent(cons(X, Y), Z), U))   
    13] u!4506!4501#(reduce!450ii!450out, X, Y, Z, U) =#> reduce!450ii!450in#(sequent(cons(X, Y), Z), U)   
    14] reduce!450ii!450in#(sequent(cons(x!4502d(X), Y), Z), U) =#> u!4507!4501#(reduce!450ii!450in(sequent(Y, cons(X, Z)), U))   
    15] reduce!450ii!450in#(sequent(cons(x!4502d(X), Y), Z), U) =#> reduce!450ii!450in#(sequent(Y, cons(X, Z)), U)   
    16] reduce!450ii!450in#(sequent(X, cons(if(Y, Z), U)), V) =#> u!4508!4501#(reduce!450ii!450in(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V))   
    17] reduce!450ii!450in#(sequent(X, cons(if(Y, Z), U)), V) =#> reduce!450ii!450in#(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V)   
    18] reduce!450ii!450in#(sequent(X, cons(iff(Y, Z), U)), V) =#> u!4509!4501#(reduce!450ii!450in(sequent(X, cons(x!4502a(if(Y, Z), if(Z, Y)), U)), V))   
    19] reduce!450ii!450in#(sequent(X, cons(iff(Y, Z), U)), V) =#> reduce!450ii!450in#(sequent(X, cons(x!4502a(if(Y, Z), if(Z, Y)), U)), V)   
    20] reduce!450ii!450in#(sequent(cons(p(X), Y), Z), sequent(U, V)) =#> u!45010!4501#(reduce!450ii!450in(sequent(Y, Z), sequent(cons(p(X), U), V)))   
    21] reduce!450ii!450in#(sequent(cons(p(X), Y), Z), sequent(U, V)) =#> reduce!450ii!450in#(sequent(Y, Z), sequent(cons(p(X), U), V))   
    22] reduce!450ii!450in#(sequent(X, cons(x!4502b(Y, Z), U)), V) =#> u!45011!4501#(reduce!450ii!450in(sequent(X, cons(Y, cons(Z, U))), V))   
    23] reduce!450ii!450in#(sequent(X, cons(x!4502b(Y, Z), U)), V) =#> reduce!450ii!450in#(sequent(X, cons(Y, cons(Z, U))), V)   
    24] reduce!450ii!450in#(sequent(X, cons(x!4502a(Y, Z), U)), V) =#> u!45012!4501#(reduce!450ii!450in(sequent(X, cons(Y, U)), V), X, Z, U, V)   
    25] reduce!450ii!450in#(sequent(X, cons(x!4502a(Y, Z), U)), V) =#> reduce!450ii!450in#(sequent(X, cons(Y, U)), V)   
    26] u!45012!4501#(reduce!450ii!450out, X, Y, Z, U) =#> u!45012!4502#(reduce!450ii!450in(sequent(X, cons(Y, Z)), U))   
    27] u!45012!4501#(reduce!450ii!450out, X, Y, Z, U) =#> reduce!450ii!450in#(sequent(X, cons(Y, Z)), U)   
    28] reduce!450ii!450in#(sequent(X, cons(x!4502d(Y), Z)), U) =#> u!45013!4501#(reduce!450ii!450in(sequent(cons(Y, X), Z), U))   
    29] reduce!450ii!450in#(sequent(X, cons(x!4502d(Y), Z)), U) =#> reduce!450ii!450in#(sequent(cons(Y, X), Z), U)   
    30] reduce!450ii!450in#(sequent(nil, cons(p(X), Y)), sequent(Z, U)) =#> u!45014!4501#(reduce!450ii!450in(sequent(nil, Y), sequent(Z, cons(p(X), U))))   
    31] reduce!450ii!450in#(sequent(nil, cons(p(X), Y)), sequent(Z, U)) =#> reduce!450ii!450in#(sequent(nil, Y), sequent(Z, cons(p(X), U)))   
    32] reduce!450ii!450in#(sequent(nil, nil), sequent(X, Y)) =#> u!45015!4501#(intersect!450ii!450in(X, Y))   
    33] reduce!450ii!450in#(sequent(nil, nil), sequent(X, Y)) =#> intersect!450ii!450in#(X, Y)   
    34] tautology!450i!450in#(X) =#> u!45016!4501#(reduce!450ii!450in(sequent(nil, cons(X, nil)), sequent(nil, nil)))   
    35] tautology!450i!450in#(X) =#> reduce!450ii!450in#(sequent(nil, cons(X, nil)), sequent(nil, nil))   

  Rules R_0:

    intersect!450ii!450in(cons(X, Y), cons(X, Z)) => intersect!450ii!450out 
    intersect!450ii!450in(X, cons(Y, Z)) => u!4501!4501(intersect!450ii!450in(X, Z)) 
    u!4501!4501(intersect!450ii!450out) => intersect!450ii!450out 
    intersect!450ii!450in(cons(X, Y), Z) => u!4502!4501(intersect!450ii!450in(Y, Z)) 
    u!4502!4501(intersect!450ii!450out) => intersect!450ii!450out 
    reduce!450ii!450in(sequent(cons(if(X, Y), Z), U), V) => u!4503!4501(reduce!450ii!450in(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V)) 
    u!4503!4501(reduce!450ii!450out) => reduce!450ii!450out 
    reduce!450ii!450in(sequent(cons(iff(X, Y), Z), U), V) => u!4504!4501(reduce!450ii!450in(sequent(cons(x!4502a(if(X, Y), if(Y, X)), Z), U), V)) 
    u!4504!4501(reduce!450ii!450out) => reduce!450ii!450out 
    reduce!450ii!450in(sequent(cons(x!4502a(X, Y), Z), U), V) => u!4505!4501(reduce!450ii!450in(sequent(cons(X, cons(Y, Z)), U), V)) 
    u!4505!4501(reduce!450ii!450out) => reduce!450ii!450out 
    reduce!450ii!450in(sequent(cons(x!4502b(X, Y), Z), U), V) => u!4506!4501(reduce!450ii!450in(sequent(cons(X, Z), U), V), Y, Z, U, V) 
    u!4506!4501(reduce!450ii!450out, X, Y, Z, U) => u!4506!4502(reduce!450ii!450in(sequent(cons(X, Y), Z), U)) 
    u!4506!4502(reduce!450ii!450out) => reduce!450ii!450out 
    reduce!450ii!450in(sequent(cons(x!4502d(X), Y), Z), U) => u!4507!4501(reduce!450ii!450in(sequent(Y, cons(X, Z)), U)) 
    u!4507!4501(reduce!450ii!450out) => reduce!450ii!450out 
    reduce!450ii!450in(sequent(X, cons(if(Y, Z), U)), V) => u!4508!4501(reduce!450ii!450in(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V)) 
    u!4508!4501(reduce!450ii!450out) => reduce!450ii!450out 
    reduce!450ii!450in(sequent(X, cons(iff(Y, Z), U)), V) => u!4509!4501(reduce!450ii!450in(sequent(X, cons(x!4502a(if(Y, Z), if(Z, Y)), U)), V)) 
    u!4509!4501(reduce!450ii!450out) => reduce!450ii!450out 
    reduce!450ii!450in(sequent(cons(p(X), Y), Z), sequent(U, V)) => u!45010!4501(reduce!450ii!450in(sequent(Y, Z), sequent(cons(p(X), U), V))) 
    u!45010!4501(reduce!450ii!450out) => reduce!450ii!450out 
    reduce!450ii!450in(sequent(X, cons(x!4502b(Y, Z), U)), V) => u!45011!4501(reduce!450ii!450in(sequent(X, cons(Y, cons(Z, U))), V)) 
    u!45011!4501(reduce!450ii!450out) => reduce!450ii!450out 
    reduce!450ii!450in(sequent(X, cons(x!4502a(Y, Z), U)), V) => u!45012!4501(reduce!450ii!450in(sequent(X, cons(Y, U)), V), X, Z, U, V) 
    u!45012!4501(reduce!450ii!450out, X, Y, Z, U) => u!45012!4502(reduce!450ii!450in(sequent(X, cons(Y, Z)), U)) 
    u!45012!4502(reduce!450ii!450out) => reduce!450ii!450out 
    reduce!450ii!450in(sequent(X, cons(x!4502d(Y), Z)), U) => u!45013!4501(reduce!450ii!450in(sequent(cons(Y, X), Z), U)) 
    u!45013!4501(reduce!450ii!450out) => reduce!450ii!450out 
    reduce!450ii!450in(sequent(nil, cons(p(X), Y)), sequent(Z, U)) => u!45014!4501(reduce!450ii!450in(sequent(nil, Y), sequent(Z, cons(p(X), U)))) 
    u!45014!4501(reduce!450ii!450out) => reduce!450ii!450out 
    reduce!450ii!450in(sequent(nil, nil), sequent(X, Y)) => u!45015!4501(intersect!450ii!450in(X, Y)) 
    u!45015!4501(intersect!450ii!450out) => reduce!450ii!450out 
    tautology!450i!450in(X) => u!45016!4501(reduce!450ii!450in(sequent(nil, cons(X, nil)), sequent(nil, nil))) 
    u!45016!4501(reduce!450ii!450out) => tautology!450i!450out 

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

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

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

This graph has the following strongly connected components:

  P_1:

    intersect!450ii!450in#(X, cons(Y, Z)) =#> intersect!450ii!450in#(X, Z)   
    intersect!450ii!450in#(cons(X, Y), Z) =#> intersect!450ii!450in#(Y, Z)   

  P_2:

    reduce!450ii!450in#(sequent(cons(if(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V)   
    reduce!450ii!450in#(sequent(cons(iff(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(x!4502a(if(X, Y), if(Y, X)), Z), U), V)   
    reduce!450ii!450in#(sequent(cons(x!4502a(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(X, cons(Y, Z)), U), V)   
    reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) =#> u!4506!4501#(reduce!450ii!450in(sequent(cons(X, Z), U), V), Y, Z, U, V)   
    reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(X, Z), U), V)   
    u!4506!4501#(reduce!450ii!450out, X, Y, Z, U) =#> reduce!450ii!450in#(sequent(cons(X, Y), Z), U)   
    reduce!450ii!450in#(sequent(cons(x!4502d(X), Y), Z), U) =#> reduce!450ii!450in#(sequent(Y, cons(X, Z)), U)   
    reduce!450ii!450in#(sequent(X, cons(if(Y, Z), U)), V) =#> reduce!450ii!450in#(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V)   
    reduce!450ii!450in#(sequent(X, cons(iff(Y, Z), U)), V) =#> reduce!450ii!450in#(sequent(X, cons(x!4502a(if(Y, Z), if(Z, Y)), U)), V)   
    reduce!450ii!450in#(sequent(cons(p(X), Y), Z), sequent(U, V)) =#> reduce!450ii!450in#(sequent(Y, Z), sequent(cons(p(X), U), V))   
    reduce!450ii!450in#(sequent(X, cons(x!4502b(Y, Z), U)), V) =#> reduce!450ii!450in#(sequent(X, cons(Y, cons(Z, U))), V)   
    reduce!450ii!450in#(sequent(X, cons(x!4502a(Y, Z), U)), V) =#> u!45012!4501#(reduce!450ii!450in(sequent(X, cons(Y, U)), V), X, Z, U, V)   
    reduce!450ii!450in#(sequent(X, cons(x!4502a(Y, Z), U)), V) =#> reduce!450ii!450in#(sequent(X, cons(Y, U)), V)   
    u!45012!4501#(reduce!450ii!450out, X, Y, Z, U) =#> reduce!450ii!450in#(sequent(X, cons(Y, Z)), U)   
    reduce!450ii!450in#(sequent(X, cons(x!4502d(Y), Z)), U) =#> reduce!450ii!450in#(sequent(cons(Y, X), Z), U)   
    reduce!450ii!450in#(sequent(nil, cons(p(X), Y)), sequent(Z, U)) =#> reduce!450ii!450in#(sequent(nil, Y), sequent(Z, cons(p(X), U)))   

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) and (P_2, R_0, m, f).

Thus, the original system is terminating if each of (P_1, R_0, minimal, all) and (P_2, R_0, minimal, all) is finite.

We consider the dependency pair problem (P_2, R_0, minimal, all).

We will use the reduction pair processor with usable rules [Kop12, Thm. 7.44].  The usable rules of (P_2, R_0) are:

  intersect!450ii!450in(cons(X, Y), cons(X, Z)) => intersect!450ii!450out 
  intersect!450ii!450in(X, cons(Y, Z)) => u!4501!4501(intersect!450ii!450in(X, Z)) 
  u!4501!4501(intersect!450ii!450out) => intersect!450ii!450out 
  intersect!450ii!450in(cons(X, Y), Z) => u!4502!4501(intersect!450ii!450in(Y, Z)) 
  u!4502!4501(intersect!450ii!450out) => intersect!450ii!450out 
  reduce!450ii!450in(sequent(cons(if(X, Y), Z), U), V) => u!4503!4501(reduce!450ii!450in(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V)) 
  u!4503!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(iff(X, Y), Z), U), V) => u!4504!4501(reduce!450ii!450in(sequent(cons(x!4502a(if(X, Y), if(Y, X)), Z), U), V)) 
  u!4504!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502a(X, Y), Z), U), V) => u!4505!4501(reduce!450ii!450in(sequent(cons(X, cons(Y, Z)), U), V)) 
  u!4505!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502b(X, Y), Z), U), V) => u!4506!4501(reduce!450ii!450in(sequent(cons(X, Z), U), V), Y, Z, U, V) 
  u!4506!4501(reduce!450ii!450out, X, Y, Z, U) => u!4506!4502(reduce!450ii!450in(sequent(cons(X, Y), Z), U)) 
  u!4506!4502(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502d(X), Y), Z), U) => u!4507!4501(reduce!450ii!450in(sequent(Y, cons(X, Z)), U)) 
  u!4507!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(if(Y, Z), U)), V) => u!4508!4501(reduce!450ii!450in(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V)) 
  u!4508!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(iff(Y, Z), U)), V) => u!4509!4501(reduce!450ii!450in(sequent(X, cons(x!4502a(if(Y, Z), if(Z, Y)), U)), V)) 
  u!4509!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(p(X), Y), Z), sequent(U, V)) => u!45010!4501(reduce!450ii!450in(sequent(Y, Z), sequent(cons(p(X), U), V))) 
  u!45010!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502b(Y, Z), U)), V) => u!45011!4501(reduce!450ii!450in(sequent(X, cons(Y, cons(Z, U))), V)) 
  u!45011!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502a(Y, Z), U)), V) => u!45012!4501(reduce!450ii!450in(sequent(X, cons(Y, U)), V), X, Z, U, V) 
  u!45012!4501(reduce!450ii!450out, X, Y, Z, U) => u!45012!4502(reduce!450ii!450in(sequent(X, cons(Y, Z)), U)) 
  u!45012!4502(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502d(Y), Z)), U) => u!45013!4501(reduce!450ii!450in(sequent(cons(Y, X), Z), U)) 
  u!45013!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(nil, cons(p(X), Y)), sequent(Z, U)) => u!45014!4501(reduce!450ii!450in(sequent(nil, Y), sequent(Z, cons(p(X), U)))) 
  u!45014!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(nil, nil), sequent(X, Y)) => u!45015!4501(intersect!450ii!450in(X, Y)) 
  u!45015!4501(intersect!450ii!450out) => reduce!450ii!450out 

It suffices to find a standard reduction pair [Kop12, Def. 6.69].  Thus, we must orient:

  reduce!450ii!450in#(sequent(cons(if(X, Y), Z), U), V) >? reduce!450ii!450in#(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V) 
  reduce!450ii!450in#(sequent(cons(iff(X, Y), Z), U), V) >? reduce!450ii!450in#(sequent(cons(x!4502a(if(X, Y), if(Y, X)), Z), U), V) 
  reduce!450ii!450in#(sequent(cons(x!4502a(X, Y), Z), U), V) >? reduce!450ii!450in#(sequent(cons(X, cons(Y, Z)), U), V) 
  reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) >? u!4506!4501#(reduce!450ii!450in(sequent(cons(X, Z), U), V), Y, Z, U, V) 
  reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) >? reduce!450ii!450in#(sequent(cons(X, Z), U), V) 
  u!4506!4501#(reduce!450ii!450out, X, Y, Z, U) >? reduce!450ii!450in#(sequent(cons(X, Y), Z), U) 
  reduce!450ii!450in#(sequent(cons(x!4502d(X), Y), Z), U) >? reduce!450ii!450in#(sequent(Y, cons(X, Z)), U) 
  reduce!450ii!450in#(sequent(X, cons(if(Y, Z), U)), V) >? reduce!450ii!450in#(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V) 
  reduce!450ii!450in#(sequent(X, cons(iff(Y, Z), U)), V) >? reduce!450ii!450in#(sequent(X, cons(x!4502a(if(Y, Z), if(Z, Y)), U)), V) 
  reduce!450ii!450in#(sequent(cons(p(X), Y), Z), sequent(U, V)) >? reduce!450ii!450in#(sequent(Y, Z), sequent(cons(p(X), U), V)) 
  reduce!450ii!450in#(sequent(X, cons(x!4502b(Y, Z), U)), V) >? reduce!450ii!450in#(sequent(X, cons(Y, cons(Z, U))), V) 
  reduce!450ii!450in#(sequent(X, cons(x!4502a(Y, Z), U)), V) >? u!45012!4501#(reduce!450ii!450in(sequent(X, cons(Y, U)), V), X, Z, U, V) 
  reduce!450ii!450in#(sequent(X, cons(x!4502a(Y, Z), U)), V) >? reduce!450ii!450in#(sequent(X, cons(Y, U)), V) 
  u!45012!4501#(reduce!450ii!450out, X, Y, Z, U) >? reduce!450ii!450in#(sequent(X, cons(Y, Z)), U) 
  reduce!450ii!450in#(sequent(X, cons(x!4502d(Y), Z)), U) >? reduce!450ii!450in#(sequent(cons(Y, X), Z), U) 
  reduce!450ii!450in#(sequent(nil, cons(p(X), Y)), sequent(Z, U)) >? reduce!450ii!450in#(sequent(nil, Y), sequent(Z, cons(p(X), U))) 
  intersect!450ii!450in(cons(X, Y), cons(X, Z)) >= intersect!450ii!450out 
  intersect!450ii!450in(X, cons(Y, Z)) >= u!4501!4501(intersect!450ii!450in(X, Z)) 
  u!4501!4501(intersect!450ii!450out) >= intersect!450ii!450out 
  intersect!450ii!450in(cons(X, Y), Z) >= u!4502!4501(intersect!450ii!450in(Y, Z)) 
  u!4502!4501(intersect!450ii!450out) >= intersect!450ii!450out 
  reduce!450ii!450in(sequent(cons(if(X, Y), Z), U), V) >= u!4503!4501(reduce!450ii!450in(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V)) 
  u!4503!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(iff(X, Y), Z), U), V) >= u!4504!4501(reduce!450ii!450in(sequent(cons(x!4502a(if(X, Y), if(Y, X)), Z), U), V)) 
  u!4504!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502a(X, Y), Z), U), V) >= u!4505!4501(reduce!450ii!450in(sequent(cons(X, cons(Y, Z)), U), V)) 
  u!4505!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502b(X, Y), Z), U), V) >= u!4506!4501(reduce!450ii!450in(sequent(cons(X, Z), U), V), Y, Z, U, V) 
  u!4506!4501(reduce!450ii!450out, X, Y, Z, U) >= u!4506!4502(reduce!450ii!450in(sequent(cons(X, Y), Z), U)) 
  u!4506!4502(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502d(X), Y), Z), U) >= u!4507!4501(reduce!450ii!450in(sequent(Y, cons(X, Z)), U)) 
  u!4507!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(if(Y, Z), U)), V) >= u!4508!4501(reduce!450ii!450in(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V)) 
  u!4508!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(iff(Y, Z), U)), V) >= u!4509!4501(reduce!450ii!450in(sequent(X, cons(x!4502a(if(Y, Z), if(Z, Y)), U)), V)) 
  u!4509!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(p(X), Y), Z), sequent(U, V)) >= u!45010!4501(reduce!450ii!450in(sequent(Y, Z), sequent(cons(p(X), U), V))) 
  u!45010!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502b(Y, Z), U)), V) >= u!45011!4501(reduce!450ii!450in(sequent(X, cons(Y, cons(Z, U))), V)) 
  u!45011!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502a(Y, Z), U)), V) >= u!45012!4501(reduce!450ii!450in(sequent(X, cons(Y, U)), V), X, Z, U, V) 
  u!45012!4501(reduce!450ii!450out, X, Y, Z, U) >= u!45012!4502(reduce!450ii!450in(sequent(X, cons(Y, Z)), U)) 
  u!45012!4502(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502d(Y), Z)), U) >= u!45013!4501(reduce!450ii!450in(sequent(cons(Y, X), Z), U)) 
  u!45013!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(nil, cons(p(X), Y)), sequent(Z, U)) >= u!45014!4501(reduce!450ii!450in(sequent(nil, Y), sequent(Z, cons(p(X), U)))) 
  u!45014!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(nil, nil), sequent(X, Y)) >= u!45015!4501(intersect!450ii!450in(X, Y)) 
  u!45015!4501(intersect!450ii!450out) >= reduce!450ii!450out 

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

We consider usable_rules with respect to the following argument filtering:

  u!45012!4501#(x_1,x_2,x_3,x_4,x_5) = u!45012!4501#(x_2x_3,x_4,x_5) 
  u!4506!4501#(x_1,x_2,x_3,x_4,x_5) = u!4506!4501#(x_2x_3,x_4,x_5) 

This leaves the following ordering requirements:

  reduce!450ii!450in#(sequent(cons(if(X, Y), Z), U), V) >= reduce!450ii!450in#(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V) 
  reduce!450ii!450in#(sequent(cons(iff(X, Y), Z), U), V) >= reduce!450ii!450in#(sequent(cons(x!4502a(if(X, Y), if(Y, X)), Z), U), V) 
  reduce!450ii!450in#(sequent(cons(x!4502a(X, Y), Z), U), V) >= reduce!450ii!450in#(sequent(cons(X, cons(Y, Z)), U), V) 
  reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) >= u!4506!4501#(reduce!450ii!450in(sequent(cons(X, Z), U), V), Y, Z, U, V) 
  reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) >= reduce!450ii!450in#(sequent(cons(X, Z), U), V) 
  u!4506!4501#(reduce!450ii!450out, X, Y, Z, U) >= reduce!450ii!450in#(sequent(cons(X, Y), Z), U) 
  reduce!450ii!450in#(sequent(cons(x!4502d(X), Y), Z), U) >= reduce!450ii!450in#(sequent(Y, cons(X, Z)), U) 
  reduce!450ii!450in#(sequent(X, cons(if(Y, Z), U)), V) >= reduce!450ii!450in#(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V) 
  reduce!450ii!450in#(sequent(X, cons(iff(Y, Z), U)), V) >= reduce!450ii!450in#(sequent(X, cons(x!4502a(if(Y, Z), if(Z, Y)), U)), V) 
  reduce!450ii!450in#(sequent(cons(p(X), Y), Z), sequent(U, V)) >= reduce!450ii!450in#(sequent(Y, Z), sequent(cons(p(X), U), V)) 
  reduce!450ii!450in#(sequent(X, cons(x!4502b(Y, Z), U)), V) >= reduce!450ii!450in#(sequent(X, cons(Y, cons(Z, U))), V) 
  reduce!450ii!450in#(sequent(X, cons(x!4502a(Y, Z), U)), V) > u!45012!4501#(reduce!450ii!450in(sequent(X, cons(Y, U)), V), X, Z, U, V) 
  reduce!450ii!450in#(sequent(X, cons(x!4502a(Y, Z), U)), V) >= reduce!450ii!450in#(sequent(X, cons(Y, U)), V) 
  u!45012!4501#(reduce!450ii!450out, X, Y, Z, U) >= reduce!450ii!450in#(sequent(X, cons(Y, Z)), U) 
  reduce!450ii!450in#(sequent(X, cons(x!4502d(Y), Z)), U) >= reduce!450ii!450in#(sequent(cons(Y, X), Z), U) 
  reduce!450ii!450in#(sequent(nil, cons(p(X), Y)), sequent(Z, U)) >= reduce!450ii!450in#(sequent(nil, Y), sequent(Z, cons(p(X), U))) 

The following interpretation satisfies the requirements:

  cons = \y0y1.y0 + y1 
  if = \y0y1.y0 + y1 
  iff = \y0y1.3 + 3y0 + 3y1 
  intersect!450ii!450in = \y0y1.0 
  intersect!450ii!450out = 0 
  nil = 0 
  p = \y0.0 
  reduce!450ii!450in = \y0y1.0 
  reduce!450ii!450in# = \y0y1.y0 
  reduce!450ii!450out = 0 
  sequent = \y0y1.y0 + y1 
  u!4501!4501 = \y0.0 
  u!45010!4501 = \y0.0 
  u!45011!4501 = \y0.0 
  u!45012!4501 = \y0y1y2y3y4.0 
  u!45012!4501# = \y0y1y2y3y4.y1 + y2 + y3 
  u!45012!4502 = \y0.0 
  u!45013!4501 = \y0.0 
  u!45014!4501 = \y0.0 
  u!45015!4501 = \y0.0 
  u!4502!4501 = \y0.0 
  u!4503!4501 = \y0.0 
  u!4504!4501 = \y0.0 
  u!4505!4501 = \y0.0 
  u!4506!4501 = \y0y1y2y3y4.0 
  u!4506!4501# = \y0y1y2y3y4.y1 + y2 + y3 
  u!4506!4502 = \y0.0 
  u!4507!4501 = \y0.0 
  u!4508!4501 = \y0.0 
  u!4509!4501 = \y0.0 
  x!4502a = \y0y1.2 + y0 + 2y1 
  x!4502b = \y0y1.y0 + y1 
  x!4502d = \y0.y0 

Using this interpretation, the requirements translate to:

  [[reduce!450ii!450in#(sequent(cons(if(_x0, _x1), _x2), _x3), _x4)]] = x0 + x1 + x2 + x3 >= x0 + x1 + x2 + x3 = [[reduce!450ii!450in#(sequent(cons(x!4502b(x!4502d(_x1), _x0), _x2), _x3), _x4)]] 
  [[reduce!450ii!450in#(sequent(cons(iff(_x0, _x1), _x2), _x3), _x4)]] = 3 + x2 + x3 + 3x0 + 3x1 > 2 + x2 + x3 + 3x0 + 3x1 = [[reduce!450ii!450in#(sequent(cons(x!4502a(if(_x0, _x1), if(_x1, _x0)), _x2), _x3), _x4)]] 
  [[reduce!450ii!450in#(sequent(cons(x!4502a(_x0, _x1), _x2), _x3), _x4)]] = 2 + x0 + x2 + x3 + 2x1 > x0 + x1 + x2 + x3 = [[reduce!450ii!450in#(sequent(cons(_x0, cons(_x1, _x2)), _x3), _x4)]] 
  [[reduce!450ii!450in#(sequent(cons(x!4502b(_x0, _x1), _x2), _x3), _x4)]] = x0 + x1 + x2 + x3 >= x1 + x2 + x3 = [[u!4506!4501#(reduce!450ii!450in(sequent(cons(_x0, _x2), _x3), _x4), _x1, _x2, _x3, _x4)]] 
  [[reduce!450ii!450in#(sequent(cons(x!4502b(_x0, _x1), _x2), _x3), _x4)]] = x0 + x1 + x2 + x3 >= x0 + x2 + x3 = [[reduce!450ii!450in#(sequent(cons(_x0, _x2), _x3), _x4)]] 
  [[u!4506!4501#(reduce!450ii!450out, _x0, _x1, _x2, _x3)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[reduce!450ii!450in#(sequent(cons(_x0, _x1), _x2), _x3)]] 
  [[reduce!450ii!450in#(sequent(cons(x!4502d(_x0), _x1), _x2), _x3)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[reduce!450ii!450in#(sequent(_x1, cons(_x0, _x2)), _x3)]] 
  [[reduce!450ii!450in#(sequent(_x0, cons(if(_x1, _x2), _x3)), _x4)]] = x0 + x1 + x2 + x3 >= x0 + x1 + x2 + x3 = [[reduce!450ii!450in#(sequent(_x0, cons(x!4502b(x!4502d(_x2), _x1), _x3)), _x4)]] 
  [[reduce!450ii!450in#(sequent(_x0, cons(iff(_x1, _x2), _x3)), _x4)]] = 3 + x0 + x3 + 3x1 + 3x2 > 2 + x0 + x3 + 3x1 + 3x2 = [[reduce!450ii!450in#(sequent(_x0, cons(x!4502a(if(_x1, _x2), if(_x2, _x1)), _x3)), _x4)]] 
  [[reduce!450ii!450in#(sequent(cons(p(_x0), _x1), _x2), sequent(_x3, _x4))]] = x1 + x2 >= x1 + x2 = [[reduce!450ii!450in#(sequent(_x1, _x2), sequent(cons(p(_x0), _x3), _x4))]] 
  [[reduce!450ii!450in#(sequent(_x0, cons(x!4502b(_x1, _x2), _x3)), _x4)]] = x0 + x1 + x2 + x3 >= x0 + x1 + x2 + x3 = [[reduce!450ii!450in#(sequent(_x0, cons(_x1, cons(_x2, _x3))), _x4)]] 
  [[reduce!450ii!450in#(sequent(_x0, cons(x!4502a(_x1, _x2), _x3)), _x4)]] = 2 + x0 + x1 + x3 + 2x2 > x0 + x2 + x3 = [[u!45012!4501#(reduce!450ii!450in(sequent(_x0, cons(_x1, _x3)), _x4), _x0, _x2, _x3, _x4)]] 
  [[reduce!450ii!450in#(sequent(_x0, cons(x!4502a(_x1, _x2), _x3)), _x4)]] = 2 + x0 + x1 + x3 + 2x2 > x0 + x1 + x3 = [[reduce!450ii!450in#(sequent(_x0, cons(_x1, _x3)), _x4)]] 
  [[u!45012!4501#(reduce!450ii!450out, _x0, _x1, _x2, _x3)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[reduce!450ii!450in#(sequent(_x0, cons(_x1, _x2)), _x3)]] 
  [[reduce!450ii!450in#(sequent(_x0, cons(x!4502d(_x1), _x2)), _x3)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[reduce!450ii!450in#(sequent(cons(_x1, _x0), _x2), _x3)]] 
  [[reduce!450ii!450in#(sequent(nil, cons(p(_x0), _x1)), sequent(_x2, _x3))]] = x1 >= x1 = [[reduce!450ii!450in#(sequent(nil, _x1), sequent(_x2, cons(p(_x0), _x3)))]] 

By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_2, R_0, minimal, all) by (P_3, R_0, minimal, all), where P_3 consists of:

  reduce!450ii!450in#(sequent(cons(if(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V)   
  reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) =#> u!4506!4501#(reduce!450ii!450in(sequent(cons(X, Z), U), V), Y, Z, U, V)   
  reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(X, Z), U), V)   
  u!4506!4501#(reduce!450ii!450out, X, Y, Z, U) =#> reduce!450ii!450in#(sequent(cons(X, Y), Z), U)   
  reduce!450ii!450in#(sequent(cons(x!4502d(X), Y), Z), U) =#> reduce!450ii!450in#(sequent(Y, cons(X, Z)), U)   
  reduce!450ii!450in#(sequent(X, cons(if(Y, Z), U)), V) =#> reduce!450ii!450in#(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V)   
  reduce!450ii!450in#(sequent(cons(p(X), Y), Z), sequent(U, V)) =#> reduce!450ii!450in#(sequent(Y, Z), sequent(cons(p(X), U), V))   
  reduce!450ii!450in#(sequent(X, cons(x!4502b(Y, Z), U)), V) =#> reduce!450ii!450in#(sequent(X, cons(Y, cons(Z, U))), V)   
  u!45012!4501#(reduce!450ii!450out, X, Y, Z, U) =#> reduce!450ii!450in#(sequent(X, cons(Y, Z)), U)   
  reduce!450ii!450in#(sequent(X, cons(x!4502d(Y), Z)), U) =#> reduce!450ii!450in#(sequent(cons(Y, X), Z), U)   
  reduce!450ii!450in#(sequent(nil, cons(p(X), Y)), sequent(Z, U)) =#> reduce!450ii!450in#(sequent(nil, Y), sequent(Z, cons(p(X), U)))   

Thus, the original system is terminating if each of (P_1, R_0, minimal, all) and (P_3, R_0, minimal, all) is finite.

We consider the dependency pair problem (P_3, R_0, minimal, all).

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, 2, 5, 7, 9 
    * 1 : 3 
    * 2 : 0, 1, 2, 4, 5, 6, 7, 9 
    * 3 : 0, 1, 2, 4, 5, 6, 7, 9 
    * 4 : 0, 1, 2, 4, 5, 6, 7, 9, 10 
    * 5 : 0, 1, 2, 4, 6, 7 
    * 6 : 0, 1, 2, 4, 5, 6, 7, 9, 10 
    * 7 : 0, 1, 2, 4, 5, 6, 7, 9, 10 
    * 8 : 0, 1, 2, 4, 5, 6, 7, 9, 10 
    * 9 : 0, 1, 2, 4, 5, 6, 7, 9 
    * 10 : 5, 7, 9, 10 

This graph has the following strongly connected components:

  P_4:

    reduce!450ii!450in#(sequent(cons(if(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V)   
    reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) =#> u!4506!4501#(reduce!450ii!450in(sequent(cons(X, Z), U), V), Y, Z, U, V)   
    reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(X, Z), U), V)   
    u!4506!4501#(reduce!450ii!450out, X, Y, Z, U) =#> reduce!450ii!450in#(sequent(cons(X, Y), Z), U)   
    reduce!450ii!450in#(sequent(cons(x!4502d(X), Y), Z), U) =#> reduce!450ii!450in#(sequent(Y, cons(X, Z)), U)   
    reduce!450ii!450in#(sequent(X, cons(if(Y, Z), U)), V) =#> reduce!450ii!450in#(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V)   
    reduce!450ii!450in#(sequent(cons(p(X), Y), Z), sequent(U, V)) =#> reduce!450ii!450in#(sequent(Y, Z), sequent(cons(p(X), U), V))   
    reduce!450ii!450in#(sequent(X, cons(x!4502b(Y, Z), U)), V) =#> reduce!450ii!450in#(sequent(X, cons(Y, cons(Z, U))), V)   
    reduce!450ii!450in#(sequent(X, cons(x!4502d(Y), Z)), U) =#> reduce!450ii!450in#(sequent(cons(Y, X), Z), U)   
    reduce!450ii!450in#(sequent(nil, cons(p(X), Y)), sequent(Z, U)) =#> reduce!450ii!450in#(sequent(nil, Y), sequent(Z, cons(p(X), U)))   

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

Thus, the original system is terminating if each of (P_1, R_0, minimal, all) and (P_4, R_0, minimal, all) is finite.

We consider the dependency pair problem (P_4, R_0, minimal, all).

We will use the reduction pair processor with usable rules [Kop12, Thm. 7.44].  The usable rules of (P_4, R_0) are:

  intersect!450ii!450in(cons(X, Y), cons(X, Z)) => intersect!450ii!450out 
  intersect!450ii!450in(X, cons(Y, Z)) => u!4501!4501(intersect!450ii!450in(X, Z)) 
  u!4501!4501(intersect!450ii!450out) => intersect!450ii!450out 
  intersect!450ii!450in(cons(X, Y), Z) => u!4502!4501(intersect!450ii!450in(Y, Z)) 
  u!4502!4501(intersect!450ii!450out) => intersect!450ii!450out 
  reduce!450ii!450in(sequent(cons(if(X, Y), Z), U), V) => u!4503!4501(reduce!450ii!450in(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V)) 
  u!4503!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(iff(X, Y), Z), U), V) => u!4504!4501(reduce!450ii!450in(sequent(cons(x!4502a(if(X, Y), if(Y, X)), Z), U), V)) 
  u!4504!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502a(X, Y), Z), U), V) => u!4505!4501(reduce!450ii!450in(sequent(cons(X, cons(Y, Z)), U), V)) 
  u!4505!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502b(X, Y), Z), U), V) => u!4506!4501(reduce!450ii!450in(sequent(cons(X, Z), U), V), Y, Z, U, V) 
  u!4506!4501(reduce!450ii!450out, X, Y, Z, U) => u!4506!4502(reduce!450ii!450in(sequent(cons(X, Y), Z), U)) 
  u!4506!4502(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502d(X), Y), Z), U) => u!4507!4501(reduce!450ii!450in(sequent(Y, cons(X, Z)), U)) 
  u!4507!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(if(Y, Z), U)), V) => u!4508!4501(reduce!450ii!450in(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V)) 
  u!4508!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(iff(Y, Z), U)), V) => u!4509!4501(reduce!450ii!450in(sequent(X, cons(x!4502a(if(Y, Z), if(Z, Y)), U)), V)) 
  u!4509!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(p(X), Y), Z), sequent(U, V)) => u!45010!4501(reduce!450ii!450in(sequent(Y, Z), sequent(cons(p(X), U), V))) 
  u!45010!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502b(Y, Z), U)), V) => u!45011!4501(reduce!450ii!450in(sequent(X, cons(Y, cons(Z, U))), V)) 
  u!45011!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502a(Y, Z), U)), V) => u!45012!4501(reduce!450ii!450in(sequent(X, cons(Y, U)), V), X, Z, U, V) 
  u!45012!4501(reduce!450ii!450out, X, Y, Z, U) => u!45012!4502(reduce!450ii!450in(sequent(X, cons(Y, Z)), U)) 
  u!45012!4502(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502d(Y), Z)), U) => u!45013!4501(reduce!450ii!450in(sequent(cons(Y, X), Z), U)) 
  u!45013!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(nil, cons(p(X), Y)), sequent(Z, U)) => u!45014!4501(reduce!450ii!450in(sequent(nil, Y), sequent(Z, cons(p(X), U)))) 
  u!45014!4501(reduce!450ii!450out) => reduce!450ii!450out 
  reduce!450ii!450in(sequent(nil, nil), sequent(X, Y)) => u!45015!4501(intersect!450ii!450in(X, Y)) 
  u!45015!4501(intersect!450ii!450out) => reduce!450ii!450out 

It suffices to find a standard reduction pair [Kop12, Def. 6.69].  Thus, we must orient:

  reduce!450ii!450in#(sequent(cons(if(X, Y), Z), U), V) >? reduce!450ii!450in#(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V) 
  reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) >? u!4506!4501#(reduce!450ii!450in(sequent(cons(X, Z), U), V), Y, Z, U, V) 
  reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) >? reduce!450ii!450in#(sequent(cons(X, Z), U), V) 
  u!4506!4501#(reduce!450ii!450out, X, Y, Z, U) >? reduce!450ii!450in#(sequent(cons(X, Y), Z), U) 
  reduce!450ii!450in#(sequent(cons(x!4502d(X), Y), Z), U) >? reduce!450ii!450in#(sequent(Y, cons(X, Z)), U) 
  reduce!450ii!450in#(sequent(X, cons(if(Y, Z), U)), V) >? reduce!450ii!450in#(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V) 
  reduce!450ii!450in#(sequent(cons(p(X), Y), Z), sequent(U, V)) >? reduce!450ii!450in#(sequent(Y, Z), sequent(cons(p(X), U), V)) 
  reduce!450ii!450in#(sequent(X, cons(x!4502b(Y, Z), U)), V) >? reduce!450ii!450in#(sequent(X, cons(Y, cons(Z, U))), V) 
  reduce!450ii!450in#(sequent(X, cons(x!4502d(Y), Z)), U) >? reduce!450ii!450in#(sequent(cons(Y, X), Z), U) 
  reduce!450ii!450in#(sequent(nil, cons(p(X), Y)), sequent(Z, U)) >? reduce!450ii!450in#(sequent(nil, Y), sequent(Z, cons(p(X), U))) 
  intersect!450ii!450in(cons(X, Y), cons(X, Z)) >= intersect!450ii!450out 
  intersect!450ii!450in(X, cons(Y, Z)) >= u!4501!4501(intersect!450ii!450in(X, Z)) 
  u!4501!4501(intersect!450ii!450out) >= intersect!450ii!450out 
  intersect!450ii!450in(cons(X, Y), Z) >= u!4502!4501(intersect!450ii!450in(Y, Z)) 
  u!4502!4501(intersect!450ii!450out) >= intersect!450ii!450out 
  reduce!450ii!450in(sequent(cons(if(X, Y), Z), U), V) >= u!4503!4501(reduce!450ii!450in(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V)) 
  u!4503!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(iff(X, Y), Z), U), V) >= u!4504!4501(reduce!450ii!450in(sequent(cons(x!4502a(if(X, Y), if(Y, X)), Z), U), V)) 
  u!4504!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502a(X, Y), Z), U), V) >= u!4505!4501(reduce!450ii!450in(sequent(cons(X, cons(Y, Z)), U), V)) 
  u!4505!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502b(X, Y), Z), U), V) >= u!4506!4501(reduce!450ii!450in(sequent(cons(X, Z), U), V), Y, Z, U, V) 
  u!4506!4501(reduce!450ii!450out, X, Y, Z, U) >= u!4506!4502(reduce!450ii!450in(sequent(cons(X, Y), Z), U)) 
  u!4506!4502(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(x!4502d(X), Y), Z), U) >= u!4507!4501(reduce!450ii!450in(sequent(Y, cons(X, Z)), U)) 
  u!4507!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(if(Y, Z), U)), V) >= u!4508!4501(reduce!450ii!450in(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V)) 
  u!4508!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(iff(Y, Z), U)), V) >= u!4509!4501(reduce!450ii!450in(sequent(X, cons(x!4502a(if(Y, Z), if(Z, Y)), U)), V)) 
  u!4509!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(cons(p(X), Y), Z), sequent(U, V)) >= u!45010!4501(reduce!450ii!450in(sequent(Y, Z), sequent(cons(p(X), U), V))) 
  u!45010!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502b(Y, Z), U)), V) >= u!45011!4501(reduce!450ii!450in(sequent(X, cons(Y, cons(Z, U))), V)) 
  u!45011!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502a(Y, Z), U)), V) >= u!45012!4501(reduce!450ii!450in(sequent(X, cons(Y, U)), V), X, Z, U, V) 
  u!45012!4501(reduce!450ii!450out, X, Y, Z, U) >= u!45012!4502(reduce!450ii!450in(sequent(X, cons(Y, Z)), U)) 
  u!45012!4502(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(X, cons(x!4502d(Y), Z)), U) >= u!45013!4501(reduce!450ii!450in(sequent(cons(Y, X), Z), U)) 
  u!45013!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(nil, cons(p(X), Y)), sequent(Z, U)) >= u!45014!4501(reduce!450ii!450in(sequent(nil, Y), sequent(Z, cons(p(X), U)))) 
  u!45014!4501(reduce!450ii!450out) >= reduce!450ii!450out 
  reduce!450ii!450in(sequent(nil, nil), sequent(X, Y)) >= u!45015!4501(intersect!450ii!450in(X, Y)) 
  u!45015!4501(intersect!450ii!450out) >= reduce!450ii!450out 

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

We consider usable_rules with respect to the following argument filtering:

  u!4506!4501#(x_1,x_2,x_3,x_4,x_5) = u!4506!4501#(x_2x_3,x_4,x_5) 

This leaves the following ordering requirements:

  reduce!450ii!450in#(sequent(cons(if(X, Y), Z), U), V) >= reduce!450ii!450in#(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V) 
  reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) >= u!4506!4501#(reduce!450ii!450in(sequent(cons(X, Z), U), V), Y, Z, U, V) 
  reduce!450ii!450in#(sequent(cons(x!4502b(X, Y), Z), U), V) >= reduce!450ii!450in#(sequent(cons(X, Z), U), V) 
  u!4506!4501#(reduce!450ii!450out, X, Y, Z, U) >= reduce!450ii!450in#(sequent(cons(X, Y), Z), U) 
  reduce!450ii!450in#(sequent(cons(x!4502d(X), Y), Z), U) >= reduce!450ii!450in#(sequent(Y, cons(X, Z)), U) 
  reduce!450ii!450in#(sequent(X, cons(if(Y, Z), U)), V) >= reduce!450ii!450in#(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V) 
  reduce!450ii!450in#(sequent(cons(p(X), Y), Z), sequent(U, V)) >= reduce!450ii!450in#(sequent(Y, Z), sequent(cons(p(X), U), V)) 
  reduce!450ii!450in#(sequent(X, cons(x!4502b(Y, Z), U)), V) > reduce!450ii!450in#(sequent(X, cons(Y, cons(Z, U))), V) 
  reduce!450ii!450in#(sequent(X, cons(x!4502d(Y), Z)), U) >= reduce!450ii!450in#(sequent(cons(Y, X), Z), U) 
  reduce!450ii!450in#(sequent(nil, cons(p(X), Y)), sequent(Z, U)) >= reduce!450ii!450in#(sequent(nil, Y), sequent(Z, cons(p(X), U))) 

The following interpretation satisfies the requirements:

  cons = \y0y1.y0 + y1 
  if = \y0y1.2 + y0 + 2y1 
  iff = \y0y1.3 
  intersect!450ii!450in = \y0y1.0 
  intersect!450ii!450out = 0 
  nil = 0 
  p = \y0.0 
  reduce!450ii!450in = \y0y1.0 
  reduce!450ii!450in# = \y0y1.y0 
  reduce!450ii!450out = 0 
  sequent = \y0y1.y1 + 2y0 
  u!4501!4501 = \y0.0 
  u!45010!4501 = \y0.0 
  u!45011!4501 = \y0.0 
  u!45012!4501 = \y0y1y2y3y4.0 
  u!45012!4502 = \y0.0 
  u!45013!4501 = \y0.0 
  u!45014!4501 = \y0.0 
  u!45015!4501 = \y0.0 
  u!4502!4501 = \y0.0 
  u!4503!4501 = \y0.0 
  u!4504!4501 = \y0.0 
  u!4505!4501 = \y0.0 
  u!4506!4501 = \y0y1y2y3y4.0 
  u!4506!4501# = \y0y1y2y3y4.y3 + 2y1 + 2y2 
  u!4506!4502 = \y0.0 
  u!4507!4501 = \y0.0 
  u!4508!4501 = \y0.0 
  u!4509!4501 = \y0.0 
  x!4502a = \y0y1.0 
  x!4502b = \y0y1.2 + y0 + y1 
  x!4502d = \y0.2y0 

Using this interpretation, the requirements translate to:

  [[reduce!450ii!450in#(sequent(cons(if(_x0, _x1), _x2), _x3), _x4)]] = 4 + x3 + 2x0 + 2x2 + 4x1 >= 4 + x3 + 2x0 + 2x2 + 4x1 = [[reduce!450ii!450in#(sequent(cons(x!4502b(x!4502d(_x1), _x0), _x2), _x3), _x4)]] 
  [[reduce!450ii!450in#(sequent(cons(x!4502b(_x0, _x1), _x2), _x3), _x4)]] = 4 + x3 + 2x0 + 2x1 + 2x2 > x3 + 2x1 + 2x2 = [[u!4506!4501#(reduce!450ii!450in(sequent(cons(_x0, _x2), _x3), _x4), _x1, _x2, _x3, _x4)]] 
  [[reduce!450ii!450in#(sequent(cons(x!4502b(_x0, _x1), _x2), _x3), _x4)]] = 4 + x3 + 2x0 + 2x1 + 2x2 > x3 + 2x0 + 2x2 = [[reduce!450ii!450in#(sequent(cons(_x0, _x2), _x3), _x4)]] 
  [[u!4506!4501#(reduce!450ii!450out, _x0, _x1, _x2, _x3)]] = x2 + 2x0 + 2x1 >= x2 + 2x0 + 2x1 = [[reduce!450ii!450in#(sequent(cons(_x0, _x1), _x2), _x3)]] 
  [[reduce!450ii!450in#(sequent(cons(x!4502d(_x0), _x1), _x2), _x3)]] = x2 + 2x1 + 4x0 >= x0 + x2 + 2x1 = [[reduce!450ii!450in#(sequent(_x1, cons(_x0, _x2)), _x3)]] 
  [[reduce!450ii!450in#(sequent(_x0, cons(if(_x1, _x2), _x3)), _x4)]] = 2 + x1 + x3 + 2x0 + 2x2 >= 2 + x1 + x3 + 2x0 + 2x2 = [[reduce!450ii!450in#(sequent(_x0, cons(x!4502b(x!4502d(_x2), _x1), _x3)), _x4)]] 
  [[reduce!450ii!450in#(sequent(cons(p(_x0), _x1), _x2), sequent(_x3, _x4))]] = x2 + 2x1 >= x2 + 2x1 = [[reduce!450ii!450in#(sequent(_x1, _x2), sequent(cons(p(_x0), _x3), _x4))]] 
  [[reduce!450ii!450in#(sequent(_x0, cons(x!4502b(_x1, _x2), _x3)), _x4)]] = 2 + x1 + x2 + x3 + 2x0 > x1 + x2 + x3 + 2x0 = [[reduce!450ii!450in#(sequent(_x0, cons(_x1, cons(_x2, _x3))), _x4)]] 
  [[reduce!450ii!450in#(sequent(_x0, cons(x!4502d(_x1), _x2)), _x3)]] = x2 + 2x0 + 2x1 >= x2 + 2x0 + 2x1 = [[reduce!450ii!450in#(sequent(cons(_x1, _x0), _x2), _x3)]] 
  [[reduce!450ii!450in#(sequent(nil, cons(p(_x0), _x1)), sequent(_x2, _x3))]] = x1 >= x1 = [[reduce!450ii!450in#(sequent(nil, _x1), sequent(_x2, cons(p(_x0), _x3)))]] 

By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_4, R_0, minimal, all) by (P_5, R_0, minimal, all), where P_5 consists of:

  reduce!450ii!450in#(sequent(cons(if(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V)   
  u!4506!4501#(reduce!450ii!450out, X, Y, Z, U) =#> reduce!450ii!450in#(sequent(cons(X, Y), Z), U)   
  reduce!450ii!450in#(sequent(cons(x!4502d(X), Y), Z), U) =#> reduce!450ii!450in#(sequent(Y, cons(X, Z)), U)   
  reduce!450ii!450in#(sequent(X, cons(if(Y, Z), U)), V) =#> reduce!450ii!450in#(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V)   
  reduce!450ii!450in#(sequent(cons(p(X), Y), Z), sequent(U, V)) =#> reduce!450ii!450in#(sequent(Y, Z), sequent(cons(p(X), U), V))   
  reduce!450ii!450in#(sequent(X, cons(x!4502d(Y), Z)), U) =#> reduce!450ii!450in#(sequent(cons(Y, X), Z), U)   
  reduce!450ii!450in#(sequent(nil, cons(p(X), Y)), sequent(Z, U)) =#> reduce!450ii!450in#(sequent(nil, Y), sequent(Z, cons(p(X), U)))   

Thus, the original system is terminating if each of (P_1, R_0, minimal, all) and (P_5, R_0, minimal, all) is finite.

We consider the dependency pair problem (P_5, R_0, minimal, all).

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

    * 0 : 3, 5 
    * 1 : 0, 2, 3, 4, 5 
    * 2 : 0, 2, 3, 4, 5, 6 
    * 3 : 0, 2, 4 
    * 4 : 0, 2, 3, 4, 5, 6 
    * 5 : 0, 2, 3, 4, 5 
    * 6 : 3, 5, 6 

This graph has the following strongly connected components:

  P_6:

    reduce!450ii!450in#(sequent(cons(if(X, Y), Z), U), V) =#> reduce!450ii!450in#(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V)   
    reduce!450ii!450in#(sequent(cons(x!4502d(X), Y), Z), U) =#> reduce!450ii!450in#(sequent(Y, cons(X, Z)), U)   
    reduce!450ii!450in#(sequent(X, cons(if(Y, Z), U)), V) =#> reduce!450ii!450in#(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V)   
    reduce!450ii!450in#(sequent(cons(p(X), Y), Z), sequent(U, V)) =#> reduce!450ii!450in#(sequent(Y, Z), sequent(cons(p(X), U), V))   
    reduce!450ii!450in#(sequent(X, cons(x!4502d(Y), Z)), U) =#> reduce!450ii!450in#(sequent(cons(Y, X), Z), U)   
    reduce!450ii!450in#(sequent(nil, cons(p(X), Y)), sequent(Z, U)) =#> reduce!450ii!450in#(sequent(nil, Y), sequent(Z, cons(p(X), U)))   

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

Thus, the original system is terminating if each of (P_1, R_0, minimal, all) and (P_6, R_0, minimal, all) is finite.

We consider the dependency pair problem (P_6, R_0, minimal, all).

We will use the reduction pair processor with usable rules [Kop12, Thm. 7.44].  (P_6, R_0) has no usable rules.

It suffices to find a standard reduction pair [Kop12, Def. 6.69].  Thus, we must orient:

  reduce!450ii!450in#(sequent(cons(if(X, Y), Z), U), V) >? reduce!450ii!450in#(sequent(cons(x!4502b(x!4502d(Y), X), Z), U), V) 
  reduce!450ii!450in#(sequent(cons(x!4502d(X), Y), Z), U) >? reduce!450ii!450in#(sequent(Y, cons(X, Z)), U) 
  reduce!450ii!450in#(sequent(X, cons(if(Y, Z), U)), V) >? reduce!450ii!450in#(sequent(X, cons(x!4502b(x!4502d(Z), Y), U)), V) 
  reduce!450ii!450in#(sequent(cons(p(X), Y), Z), sequent(U, V)) >? reduce!450ii!450in#(sequent(Y, Z), sequent(cons(p(X), U), V)) 
  reduce!450ii!450in#(sequent(X, cons(x!4502d(Y), Z)), U) >? reduce!450ii!450in#(sequent(cons(Y, X), Z), U) 
  reduce!450ii!450in#(sequent(nil, cons(p(X), Y)), sequent(Z, U)) >? reduce!450ii!450in#(sequent(nil, Y), sequent(Z, cons(p(X), U))) 

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

The following interpretation satisfies the requirements:

  cons = \y0y1.y0 + y1 
  if = \y0y1.3 
  nil = 0 
  p = \y0.1 
  reduce!450ii!450in# = \y0y1.y0 
  sequent = \y0y1.y0 + y1 
  x!4502b = \y0y1.0 
  x!4502d = \y0.3 + y0 

Using this interpretation, the requirements translate to:

  [[reduce!450ii!450in#(sequent(cons(if(_x0, _x1), _x2), _x3), _x4)]] = 3 + x2 + x3 > x2 + x3 = [[reduce!450ii!450in#(sequent(cons(x!4502b(x!4502d(_x1), _x0), _x2), _x3), _x4)]] 
  [[reduce!450ii!450in#(sequent(cons(x!4502d(_x0), _x1), _x2), _x3)]] = 3 + x0 + x1 + x2 > x0 + x1 + x2 = [[reduce!450ii!450in#(sequent(_x1, cons(_x0, _x2)), _x3)]] 
  [[reduce!450ii!450in#(sequent(_x0, cons(if(_x1, _x2), _x3)), _x4)]] = 3 + x0 + x3 > x0 + x3 = [[reduce!450ii!450in#(sequent(_x0, cons(x!4502b(x!4502d(_x2), _x1), _x3)), _x4)]] 
  [[reduce!450ii!450in#(sequent(cons(p(_x0), _x1), _x2), sequent(_x3, _x4))]] = 1 + x1 + x2 > x1 + x2 = [[reduce!450ii!450in#(sequent(_x1, _x2), sequent(cons(p(_x0), _x3), _x4))]] 
  [[reduce!450ii!450in#(sequent(_x0, cons(x!4502d(_x1), _x2)), _x3)]] = 3 + x0 + x1 + x2 > x0 + x1 + x2 = [[reduce!450ii!450in#(sequent(cons(_x1, _x0), _x2), _x3)]] 
  [[reduce!450ii!450in#(sequent(nil, cons(p(_x0), _x1)), sequent(_x2, _x3))]] = 1 + x1 > x1 = [[reduce!450ii!450in#(sequent(nil, _x1), sequent(_x2, cons(p(_x0), _x3)))]] 

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

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

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

We apply the subterm criterion with the following projection function:

  nu(intersect!450ii!450in#) = 2 

Thus, we can orient the dependency pairs as follows:

  nu(intersect!450ii!450in#(X, cons(Y, Z))) = cons(Y, Z) |> Z = nu(intersect!450ii!450in#(X, Z)) 
  nu(intersect!450ii!450in#(cons(X, Y), Z)) = Z = Z = nu(intersect!450ii!450in#(Y, Z)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_1, R_0, minimal, f) by (P_7, R_0, minimal, f), where P_7 contains:

  intersect!450ii!450in#(cons(X, Y), Z) =#> intersect!450ii!450in#(Y, Z)   

Thus, the original system is terminating if (P_7, R_0, minimal, all) is finite.

We consider the dependency pair problem (P_7, R_0, minimal, all).

We apply the subterm criterion with the following projection function:

  nu(intersect!450ii!450in#) = 1 

Thus, we can orient the dependency pairs as follows:

  nu(intersect!450ii!450in#(cons(X, Y), Z)) = cons(X, Y) |> Y = nu(intersect!450ii!450in#(Y, Z)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_7, R_0, minimal, f) by ({}, R_0, minimal, f).  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.