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

  !940 : [] --> o 
  !minus : [o * o] --> o 
  !plus : [o * o] --> o 
  !times : [o * o] --> o 
  0 : [o] --> o 
  1 : [o] --> o 
  app : [o * o] --> o 
  cons : [o * o] --> o 
  eq : [o * o] --> o 
  false : [] --> o 
  ge : [o * o] --> o 
  if : [o * o * o] --> o 
  ifinter : [o * o * o * o] --> o 
  inter : [o * o] --> o 
  log : [o] --> o 
  log!450 : [o] --> o 
  mem : [o * o] --> o 
  nil : [] --> o 
  not : [o] --> o 
  prod : [o] --> o 
  sum : [o] --> o 
  true : [] --> o 

  0(!940) => !940 
  !plus(X, !940) => X 
  !plus(!940, X) => X 
  !plus(0(X), 0(Y)) => 0(!plus(X, Y)) 
  !plus(0(X), 1(Y)) => 1(!plus(X, Y)) 
  !plus(1(X), 0(Y)) => 1(!plus(X, Y)) 
  !plus(1(X), 1(Y)) => 0(!plus(!plus(X, Y), 1(!940))) 
  !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, Z)) 
  !minus(!940, X) => !940 
  !minus(X, !940) => X 
  !minus(0(X), 0(Y)) => 0(!minus(X, Y)) 
  !minus(0(X), 1(Y)) => 1(!minus(!minus(X, Y), 1(!940))) 
  !minus(1(X), 0(Y)) => 1(!minus(X, Y)) 
  !minus(1(X), 1(Y)) => 0(!minus(X, Y)) 
  not(true) => false 
  not(false) => true 
  if(true, X, Y) => X 
  if(false, X, Y) => Y 
  eq(!940, !940) => true 
  eq(!940, 1(X)) => false 
  eq(1(X), !940) => false 
  eq(!940, 0(X)) => eq(!940, X) 
  eq(0(X), !940) => eq(X, !940) 
  eq(1(X), 1(Y)) => eq(X, Y) 
  eq(0(X), 1(Y)) => false 
  eq(1(X), 0(Y)) => false 
  eq(0(X), 0(Y)) => eq(X, Y) 
  ge(0(X), 0(Y)) => ge(X, Y) 
  ge(0(X), 1(Y)) => not(ge(Y, X)) 
  ge(1(X), 0(Y)) => ge(X, Y) 
  ge(1(X), 1(Y)) => ge(X, Y) 
  ge(X, !940) => true 
  ge(!940, 0(X)) => ge(!940, X) 
  ge(!940, 1(X)) => false 
  log(X) => !minus(log!450(X), 1(!940)) 
  log!450(!940) => !940 
  log!450(1(X)) => !plus(log!450(X), 1(!940)) 
  log!450(0(X)) => if(ge(X, 1(!940)), !plus(log!450(X), 1(!940)), !940) 
  !times(!940, X) => !940 
  !times(0(X), Y) => 0(!times(X, Y)) 
  !times(1(X), Y) => !plus(0(!times(X, Y)), Y) 
  !times(!times(X, Y), Z) => !times(X, !times(Y, Z)) 
  !times(X, !plus(Y, Z)) => !plus(!times(X, Y), !times(X, Z)) 
  app(nil, X) => X 
  app(cons(X, Y), Z) => cons(X, app(Y, Z)) 
  sum(nil) => 0(!940) 
  sum(cons(X, Y)) => !plus(X, sum(Y)) 
  sum(app(X, Y)) => !plus(sum(X), sum(Y)) 
  prod(nil) => 1(!940) 
  prod(cons(X, Y)) => !times(X, prod(Y)) 
  prod(app(X, Y)) => !times(prod(X), prod(Y)) 
  mem(X, nil) => false 
  mem(X, cons(Y, Z)) => if(eq(X, Y), true, mem(X, Z)) 
  inter(X, nil) => nil 
  inter(nil, X) => nil 
  inter(app(X, Y), Z) => app(inter(X, Z), inter(Y, Z)) 
  inter(X, app(Y, Z)) => app(inter(X, Y), inter(X, Z)) 
  inter(cons(X, Y), Z) => ifinter(mem(X, Z), X, Y, Z) 
  inter(X, cons(Y, Z)) => ifinter(mem(Y, X), Y, Z, X) 
  ifinter(true, X, Y, Z) => cons(X, inter(Y, Z)) 
  ifinter(false, X, Y, Z) => inter(Y, 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] !plus#(0(X), 0(Y)) =#> 0#(!plus(X, Y))   
    1] !plus#(0(X), 0(Y)) =#> !plus#(X, Y)   
    2] !plus#(0(X), 1(Y)) =#> !plus#(X, Y)   
    3] !plus#(1(X), 0(Y)) =#> !plus#(X, Y)   
    4] !plus#(1(X), 1(Y)) =#> 0#(!plus(!plus(X, Y), 1(!940)))   
    5] !plus#(1(X), 1(Y)) =#> !plus#(!plus(X, Y), 1(!940))   
    6] !plus#(1(X), 1(Y)) =#> !plus#(X, Y)   
    7] !plus#(!plus(X, Y), Z) =#> !plus#(X, !plus(Y, Z))   
    8] !plus#(!plus(X, Y), Z) =#> !plus#(Y, Z)   
    9] !minus#(0(X), 0(Y)) =#> 0#(!minus(X, Y))   
    10] !minus#(0(X), 0(Y)) =#> !minus#(X, Y)   
    11] !minus#(0(X), 1(Y)) =#> !minus#(!minus(X, Y), 1(!940))   
    12] !minus#(0(X), 1(Y)) =#> !minus#(X, Y)   
    13] !minus#(1(X), 0(Y)) =#> !minus#(X, Y)   
    14] !minus#(1(X), 1(Y)) =#> 0#(!minus(X, Y))   
    15] !minus#(1(X), 1(Y)) =#> !minus#(X, Y)   
    16] eq#(!940, 0(X)) =#> eq#(!940, X)   
    17] eq#(0(X), !940) =#> eq#(X, !940)   
    18] eq#(1(X), 1(Y)) =#> eq#(X, Y)   
    19] eq#(0(X), 0(Y)) =#> eq#(X, Y)   
    20] ge#(0(X), 0(Y)) =#> ge#(X, Y)   
    21] ge#(0(X), 1(Y)) =#> not#(ge(Y, X))   
    22] ge#(0(X), 1(Y)) =#> ge#(Y, X)   
    23] ge#(1(X), 0(Y)) =#> ge#(X, Y)   
    24] ge#(1(X), 1(Y)) =#> ge#(X, Y)   
    25] ge#(!940, 0(X)) =#> ge#(!940, X)   
    26] log#(X) =#> !minus#(log!450(X), 1(!940))   
    27] log#(X) =#> log!450#(X)   
    28] log!450#(1(X)) =#> !plus#(log!450(X), 1(!940))   
    29] log!450#(1(X)) =#> log!450#(X)   
    30] log!450#(0(X)) =#> if#(ge(X, 1(!940)), !plus(log!450(X), 1(!940)), !940)   
    31] log!450#(0(X)) =#> ge#(X, 1(!940))   
    32] log!450#(0(X)) =#> !plus#(log!450(X), 1(!940))   
    33] log!450#(0(X)) =#> log!450#(X)   
    34] !times#(0(X), Y) =#> 0#(!times(X, Y))   
    35] !times#(0(X), Y) =#> !times#(X, Y)   
    36] !times#(1(X), Y) =#> !plus#(0(!times(X, Y)), Y)   
    37] !times#(1(X), Y) =#> 0#(!times(X, Y))   
    38] !times#(1(X), Y) =#> !times#(X, Y)   
    39] !times#(!times(X, Y), Z) =#> !times#(X, !times(Y, Z))   
    40] !times#(!times(X, Y), Z) =#> !times#(Y, Z)   
    41] !times#(X, !plus(Y, Z)) =#> !plus#(!times(X, Y), !times(X, Z))   
    42] !times#(X, !plus(Y, Z)) =#> !times#(X, Y)   
    43] !times#(X, !plus(Y, Z)) =#> !times#(X, Z)   
    44] app#(cons(X, Y), Z) =#> app#(Y, Z)   
    45] sum#(nil) =#> 0#(!940)   
    46] sum#(cons(X, Y)) =#> !plus#(X, sum(Y))   
    47] sum#(cons(X, Y)) =#> sum#(Y)   
    48] sum#(app(X, Y)) =#> !plus#(sum(X), sum(Y))   
    49] sum#(app(X, Y)) =#> sum#(X)   
    50] sum#(app(X, Y)) =#> sum#(Y)   
    51] prod#(cons(X, Y)) =#> !times#(X, prod(Y))   
    52] prod#(cons(X, Y)) =#> prod#(Y)   
    53] prod#(app(X, Y)) =#> !times#(prod(X), prod(Y))   
    54] prod#(app(X, Y)) =#> prod#(X)   
    55] prod#(app(X, Y)) =#> prod#(Y)   
    56] mem#(X, cons(Y, Z)) =#> if#(eq(X, Y), true, mem(X, Z))   
    57] mem#(X, cons(Y, Z)) =#> eq#(X, Y)   
    58] mem#(X, cons(Y, Z)) =#> mem#(X, Z)   
    59] inter#(app(X, Y), Z) =#> app#(inter(X, Z), inter(Y, Z))   
    60] inter#(app(X, Y), Z) =#> inter#(X, Z)   
    61] inter#(app(X, Y), Z) =#> inter#(Y, Z)   
    62] inter#(X, app(Y, Z)) =#> app#(inter(X, Y), inter(X, Z))   
    63] inter#(X, app(Y, Z)) =#> inter#(X, Y)   
    64] inter#(X, app(Y, Z)) =#> inter#(X, Z)   
    65] inter#(cons(X, Y), Z) =#> ifinter#(mem(X, Z), X, Y, Z)   
    66] inter#(cons(X, Y), Z) =#> mem#(X, Z)   
    67] inter#(X, cons(Y, Z)) =#> ifinter#(mem(Y, X), Y, Z, X)   
    68] inter#(X, cons(Y, Z)) =#> mem#(Y, X)   
    69] ifinter#(true, X, Y, Z) =#> inter#(Y, Z)   
    70] ifinter#(false, X, Y, Z) =#> inter#(Y, Z)   

  Rules R_0:

    0(!940) => !940 
    !plus(X, !940) => X 
    !plus(!940, X) => X 
    !plus(0(X), 0(Y)) => 0(!plus(X, Y)) 
    !plus(0(X), 1(Y)) => 1(!plus(X, Y)) 
    !plus(1(X), 0(Y)) => 1(!plus(X, Y)) 
    !plus(1(X), 1(Y)) => 0(!plus(!plus(X, Y), 1(!940))) 
    !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, Z)) 
    !minus(!940, X) => !940 
    !minus(X, !940) => X 
    !minus(0(X), 0(Y)) => 0(!minus(X, Y)) 
    !minus(0(X), 1(Y)) => 1(!minus(!minus(X, Y), 1(!940))) 
    !minus(1(X), 0(Y)) => 1(!minus(X, Y)) 
    !minus(1(X), 1(Y)) => 0(!minus(X, Y)) 
    not(true) => false 
    not(false) => true 
    if(true, X, Y) => X 
    if(false, X, Y) => Y 
    eq(!940, !940) => true 
    eq(!940, 1(X)) => false 
    eq(1(X), !940) => false 
    eq(!940, 0(X)) => eq(!940, X) 
    eq(0(X), !940) => eq(X, !940) 
    eq(1(X), 1(Y)) => eq(X, Y) 
    eq(0(X), 1(Y)) => false 
    eq(1(X), 0(Y)) => false 
    eq(0(X), 0(Y)) => eq(X, Y) 
    ge(0(X), 0(Y)) => ge(X, Y) 
    ge(0(X), 1(Y)) => not(ge(Y, X)) 
    ge(1(X), 0(Y)) => ge(X, Y) 
    ge(1(X), 1(Y)) => ge(X, Y) 
    ge(X, !940) => true 
    ge(!940, 0(X)) => ge(!940, X) 
    ge(!940, 1(X)) => false 
    log(X) => !minus(log!450(X), 1(!940)) 
    log!450(!940) => !940 
    log!450(1(X)) => !plus(log!450(X), 1(!940)) 
    log!450(0(X)) => if(ge(X, 1(!940)), !plus(log!450(X), 1(!940)), !940) 
    !times(!940, X) => !940 
    !times(0(X), Y) => 0(!times(X, Y)) 
    !times(1(X), Y) => !plus(0(!times(X, Y)), Y) 
    !times(!times(X, Y), Z) => !times(X, !times(Y, Z)) 
    !times(X, !plus(Y, Z)) => !plus(!times(X, Y), !times(X, Z)) 
    app(nil, X) => X 
    app(cons(X, Y), Z) => cons(X, app(Y, Z)) 
    sum(nil) => 0(!940) 
    sum(cons(X, Y)) => !plus(X, sum(Y)) 
    sum(app(X, Y)) => !plus(sum(X), sum(Y)) 
    prod(nil) => 1(!940) 
    prod(cons(X, Y)) => !times(X, prod(Y)) 
    prod(app(X, Y)) => !times(prod(X), prod(Y)) 
    mem(X, nil) => false 
    mem(X, cons(Y, Z)) => if(eq(X, Y), true, mem(X, Z)) 
    inter(X, nil) => nil 
    inter(nil, X) => nil 
    inter(app(X, Y), Z) => app(inter(X, Z), inter(Y, Z)) 
    inter(X, app(Y, Z)) => app(inter(X, Y), inter(X, Z)) 
    inter(cons(X, Y), Z) => ifinter(mem(X, Z), X, Y, Z) 
    inter(X, cons(Y, Z)) => ifinter(mem(Y, X), Y, Z, X) 
    ifinter(true, X, Y, Z) => cons(X, inter(Y, Z)) 
    ifinter(false, X, Y, Z) => inter(Y, 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 : 0, 1, 2, 3, 4, 5, 6, 7, 8 
    * 2 : 0, 1, 2, 3, 4, 5, 6, 7, 8 
    * 3 : 0, 1, 2, 3, 4, 5, 6, 7, 8 
    * 4 :  
    * 5 : 2, 4, 5, 6, 7, 8 
    * 6 : 0, 1, 2, 3, 4, 5, 6, 7, 8 
    * 7 : 0, 1, 2, 3, 4, 5, 6, 7, 8 
    * 8 : 0, 1, 2, 3, 4, 5, 6, 7, 8 
    * 9 :  
    * 10 : 9, 10, 11, 12, 13, 14, 15 
    * 11 : 11, 12, 14, 15 
    * 12 : 9, 10, 11, 12, 13, 14, 15 
    * 13 : 9, 10, 11, 12, 13, 14, 15 
    * 14 :  
    * 15 : 9, 10, 11, 12, 13, 14, 15 
    * 16 : 16 
    * 17 : 17 
    * 18 : 16, 17, 18, 19 
    * 19 : 16, 17, 18, 19 
    * 20 : 20, 21, 22, 23, 24, 25 
    * 21 :  
    * 22 : 20, 21, 22, 23, 24, 25 
    * 23 : 20, 21, 22, 23, 24, 25 
    * 24 : 20, 21, 22, 23, 24, 25 
    * 25 : 25 
    * 26 : 11, 12, 14, 15 
    * 27 : 28, 29, 30, 31, 32, 33 
    * 28 : 2, 4, 5, 6, 7, 8 
    * 29 : 28, 29, 30, 31, 32, 33 
    * 30 :  
    * 31 : 21, 22, 24 
    * 32 : 2, 4, 5, 6, 7, 8 
    * 33 : 28, 29, 30, 31, 32, 33 
    * 34 :  
    * 35 : 34, 35, 36, 37, 38, 39, 40, 41, 42, 43 
    * 36 : 0, 1, 2 
    * 37 :  
    * 38 : 34, 35, 36, 37, 38, 39, 40, 41, 42, 43 
    * 39 : 34, 35, 36, 37, 38, 39, 40, 41, 42, 43 
    * 40 : 34, 35, 36, 37, 38, 39, 40, 41, 42, 43 
    * 41 : 0, 1, 2, 3, 4, 5, 6, 7, 8 
    * 42 : 34, 35, 36, 37, 38, 39, 40, 41, 42, 43 
    * 43 : 34, 35, 36, 37, 38, 39, 40, 41, 42, 43 
    * 44 : 44 
    * 45 :  
    * 46 : 0, 1, 2, 3, 4, 5, 6, 7, 8 
    * 47 : 45, 46, 47, 48, 49, 50 
    * 48 : 0, 1, 2, 3, 4, 5, 6, 7, 8 
    * 49 : 45, 46, 47, 48, 49, 50 
    * 50 : 45, 46, 47, 48, 49, 50 
    * 51 : 34, 35, 36, 37, 38, 39, 40, 41, 42, 43 
    * 52 : 51, 52, 53, 54, 55 
    * 53 : 34, 35, 36, 37, 38, 39, 40, 41, 42, 43 
    * 54 : 51, 52, 53, 54, 55 
    * 55 : 51, 52, 53, 54, 55 
    * 56 :  
    * 57 : 16, 17, 18, 19 
    * 58 : 56, 57, 58 
    * 59 : 44 
    * 60 : 59, 60, 61, 62, 63, 64, 65, 66, 67, 68 
    * 61 : 59, 60, 61, 62, 63, 64, 65, 66, 67, 68 
    * 62 : 44 
    * 63 : 59, 60, 61, 62, 63, 64, 65, 66, 67, 68 
    * 64 : 59, 60, 61, 62, 63, 64, 65, 66, 67, 68 
    * 65 : 69, 70 
    * 66 : 56, 57, 58 
    * 67 : 69, 70 
    * 68 : 56, 57, 58 
    * 69 : 59, 60, 61, 62, 63, 64, 65, 66, 67, 68 
    * 70 : 59, 60, 61, 62, 63, 64, 65, 66, 67, 68 

This graph has the following strongly connected components:

  P_1:

    !plus#(0(X), 0(Y)) =#> !plus#(X, Y)   
    !plus#(0(X), 1(Y)) =#> !plus#(X, Y)   
    !plus#(1(X), 0(Y)) =#> !plus#(X, Y)   
    !plus#(1(X), 1(Y)) =#> !plus#(!plus(X, Y), 1(!940))   
    !plus#(1(X), 1(Y)) =#> !plus#(X, Y)   
    !plus#(!plus(X, Y), Z) =#> !plus#(X, !plus(Y, Z))   
    !plus#(!plus(X, Y), Z) =#> !plus#(Y, Z)   

  P_2:

    !minus#(0(X), 0(Y)) =#> !minus#(X, Y)   
    !minus#(0(X), 1(Y)) =#> !minus#(!minus(X, Y), 1(!940))   
    !minus#(0(X), 1(Y)) =#> !minus#(X, Y)   
    !minus#(1(X), 0(Y)) =#> !minus#(X, Y)   
    !minus#(1(X), 1(Y)) =#> !minus#(X, Y)   

  P_3:

    eq#(!940, 0(X)) =#> eq#(!940, X)   

  P_4:

    eq#(0(X), !940) =#> eq#(X, !940)   

  P_5:

    eq#(1(X), 1(Y)) =#> eq#(X, Y)   
    eq#(0(X), 0(Y)) =#> eq#(X, Y)   

  P_6:

    ge#(0(X), 0(Y)) =#> ge#(X, Y)   
    ge#(0(X), 1(Y)) =#> ge#(Y, X)   
    ge#(1(X), 0(Y)) =#> ge#(X, Y)   
    ge#(1(X), 1(Y)) =#> ge#(X, Y)   

  P_7:

    ge#(!940, 0(X)) =#> ge#(!940, X)   

  P_8:

    log!450#(1(X)) =#> log!450#(X)   
    log!450#(0(X)) =#> log!450#(X)   

  P_9:

    !times#(0(X), Y) =#> !times#(X, Y)   
    !times#(1(X), Y) =#> !times#(X, Y)   
    !times#(!times(X, Y), Z) =#> !times#(X, !times(Y, Z))   
    !times#(!times(X, Y), Z) =#> !times#(Y, Z)   
    !times#(X, !plus(Y, Z)) =#> !times#(X, Y)   
    !times#(X, !plus(Y, Z)) =#> !times#(X, Z)   

  P_10:

    app#(cons(X, Y), Z) =#> app#(Y, Z)   

  P_11:

    sum#(cons(X, Y)) =#> sum#(Y)   
    sum#(app(X, Y)) =#> sum#(X)   
    sum#(app(X, Y)) =#> sum#(Y)   

  P_12:

    prod#(cons(X, Y)) =#> prod#(Y)   
    prod#(app(X, Y)) =#> prod#(X)   
    prod#(app(X, Y)) =#> prod#(Y)   

  P_13:

    mem#(X, cons(Y, Z)) =#> mem#(X, Z)   

  P_14:

    inter#(app(X, Y), Z) =#> inter#(X, Z)   
    inter#(app(X, Y), Z) =#> inter#(Y, Z)   
    inter#(X, app(Y, Z)) =#> inter#(X, Y)   
    inter#(X, app(Y, Z)) =#> inter#(X, Z)   
    inter#(cons(X, Y), Z) =#> ifinter#(mem(X, Z), X, Y, Z)   
    inter#(X, cons(Y, Z)) =#> ifinter#(mem(Y, X), Y, Z, X)   
    ifinter#(true, X, Y, Z) =#> inter#(Y, Z)   
    ifinter#(false, X, Y, Z) =#> inter#(Y, 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), (P_2, R_0, m, f), (P_3, R_0, m, f), (P_4, R_0, m, f), (P_5, R_0, m, f), (P_6, R_0, m, f), (P_7, R_0, m, f), (P_8, R_0, m, f), (P_9, R_0, m, f), (P_10, R_0, m, f), (P_11, R_0, m, f), (P_12, R_0, m, f), (P_13, R_0, m, f) and (P_14, R_0, m, f).

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative), (P_8, R_0, minimal, formative), (P_9, R_0, minimal, formative), (P_10, R_0, minimal, formative), (P_11, R_0, minimal, formative), (P_12, R_0, minimal, formative), (P_13, R_0, minimal, formative) and (P_14, R_0, minimal, formative) is finite.

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

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

  if(true, X, Y) => X 
  if(false, X, Y) => Y 
  eq(!940, !940) => true 
  eq(!940, 1(X)) => false 
  eq(1(X), !940) => false 
  eq(!940, 0(X)) => eq(!940, X) 
  eq(0(X), !940) => eq(X, !940) 
  eq(1(X), 1(Y)) => eq(X, Y) 
  eq(0(X), 1(Y)) => false 
  eq(1(X), 0(Y)) => false 
  eq(0(X), 0(Y)) => eq(X, Y) 
  mem(X, nil) => false 
  mem(X, cons(Y, Z)) => if(eq(X, Y), true, mem(X, Z)) 

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

  inter#(app(X, Y), Z) >? inter#(X, Z) 
  inter#(app(X, Y), Z) >? inter#(Y, Z) 
  inter#(X, app(Y, Z)) >? inter#(X, Y) 
  inter#(X, app(Y, Z)) >? inter#(X, Z) 
  inter#(cons(X, Y), Z) >? ifinter#(mem(X, Z), X, Y, Z) 
  inter#(X, cons(Y, Z)) >? ifinter#(mem(Y, X), Y, Z, X) 
  ifinter#(true, X, Y, Z) >? inter#(Y, Z) 
  ifinter#(false, X, Y, Z) >? inter#(Y, Z) 
  if(true, X, Y) >= X 
  if(false, X, Y) >= Y 
  eq(!940, !940) >= true 
  eq(!940, 1(X)) >= false 
  eq(1(X), !940) >= false 
  eq(!940, 0(X)) >= eq(!940, X) 
  eq(0(X), !940) >= eq(X, !940) 
  eq(1(X), 1(Y)) >= eq(X, Y) 
  eq(0(X), 1(Y)) >= false 
  eq(1(X), 0(Y)) >= false 
  eq(0(X), 0(Y)) >= eq(X, Y) 
  mem(X, nil) >= false 
  mem(X, cons(Y, Z)) >= if(eq(X, Y), true, mem(X, Z)) 

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

We consider usable_rules with respect to the following argument filtering:

  if(x_1,x_2,x_3) = if(x_2x_3) 

This leaves the following ordering requirements:

  inter#(app(X, Y), Z) > inter#(X, Z) 
  inter#(app(X, Y), Z) >= inter#(Y, Z) 
  inter#(X, app(Y, Z)) >= inter#(X, Y) 
  inter#(X, app(Y, Z)) >= inter#(X, Z) 
  inter#(cons(X, Y), Z) >= ifinter#(mem(X, Z), X, Y, Z) 
  inter#(X, cons(Y, Z)) >= ifinter#(mem(Y, X), Y, Z, X) 
  ifinter#(true, X, Y, Z) >= inter#(Y, Z) 
  ifinter#(false, X, Y, Z) >= inter#(Y, Z) 
  if(true, X, Y) >= X 
  if(false, X, Y) >= Y 
  mem(X, nil) >= false 
  mem(X, cons(Y, Z)) >= if(eq(X, Y), true, mem(X, Z)) 

The following interpretation satisfies the requirements:

  !940 = 3 
  0 = \y0.3 
  1 = \y0.3 
  app = \y0y1.3 + y0 + y1 
  cons = \y0y1.3 + y0 + 2y1 
  eq = \y0y1.3 
  false = 0 
  if = \y0y1y2.y2 + 2y1 
  ifinter# = \y0y1y2y3.y3 + 2y2 
  inter# = \y0y1.y1 + 2y0 
  mem = \y0y1.0 
  nil = 3 
  true = 0 

Using this interpretation, the requirements translate to:

  [[inter#(app(_x0, _x1), _x2)]] = 6 + x2 + 2x0 + 2x1 > x2 + 2x0 = [[inter#(_x0, _x2)]] 
  [[inter#(app(_x0, _x1), _x2)]] = 6 + x2 + 2x0 + 2x1 > x2 + 2x1 = [[inter#(_x1, _x2)]] 
  [[inter#(_x0, app(_x1, _x2))]] = 3 + x1 + x2 + 2x0 > x1 + 2x0 = [[inter#(_x0, _x1)]] 
  [[inter#(_x0, app(_x1, _x2))]] = 3 + x1 + x2 + 2x0 > x2 + 2x0 = [[inter#(_x0, _x2)]] 
  [[inter#(cons(_x0, _x1), _x2)]] = 6 + x2 + 2x0 + 4x1 > x2 + 2x1 = [[ifinter#(mem(_x0, _x2), _x0, _x1, _x2)]] 
  [[inter#(_x0, cons(_x1, _x2))]] = 3 + x1 + 2x0 + 2x2 > x0 + 2x2 = [[ifinter#(mem(_x1, _x0), _x1, _x2, _x0)]] 
  [[ifinter#(true, _x0, _x1, _x2)]] = x2 + 2x1 >= x2 + 2x1 = [[inter#(_x1, _x2)]] 
  [[ifinter#(false, _x0, _x1, _x2)]] = x2 + 2x1 >= x2 + 2x1 = [[inter#(_x1, _x2)]] 
  [[if(true, _x0, _x1)]] = x1 + 2x0 >= x0 = [[_x0]] 
  [[if(false, _x0, _x1)]] = x1 + 2x0 >= x1 = [[_x1]] 
  [[mem(_x0, nil)]] = 0 >= 0 = [[false]] 
  [[mem(_x0, cons(_x1, _x2))]] = 0 >= 0 = [[if(eq(_x0, _x1), true, mem(_x0, _x2))]] 

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

  ifinter#(true, X, Y, Z) =#> inter#(Y, Z)   
  ifinter#(false, X, Y, Z) =#> inter#(Y, Z)   

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative), (P_8, R_0, minimal, formative), (P_9, R_0, minimal, formative), (P_10, R_0, minimal, formative), (P_11, R_0, minimal, formative), (P_12, R_0, minimal, formative), (P_13, R_0, minimal, formative) and (P_15, R_0, minimal, formative) is finite.

We consider the dependency pair problem (P_15, 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 :  

This graph has no strongly connected components.  By [Kop12, Thm. 7.31], this implies finiteness of the dependency pair problem.

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative), (P_8, R_0, minimal, formative), (P_9, R_0, minimal, formative), (P_10, R_0, minimal, formative), (P_11, R_0, minimal, formative), (P_12, R_0, minimal, formative) and (P_13, R_0, minimal, formative) is finite.

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

We apply the subterm criterion with the following projection function:

  nu(mem#) = 2 

Thus, we can orient the dependency pairs as follows:

  nu(mem#(X, cons(Y, Z))) = cons(Y, Z) |> Z = nu(mem#(X, Z)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_13, R_0, minimal, f) by ({}, R_0, minimal, f).  By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed.

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative), (P_8, R_0, minimal, formative), (P_9, R_0, minimal, formative), (P_10, R_0, minimal, formative), (P_11, R_0, minimal, formative) and (P_12, R_0, minimal, formative) is finite.

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

We apply the subterm criterion with the following projection function:

  nu(prod#) = 1 

Thus, we can orient the dependency pairs as follows:

  nu(prod#(cons(X, Y))) = cons(X, Y) |> Y = nu(prod#(Y)) 
  nu(prod#(app(X, Y))) = app(X, Y) |> X = nu(prod#(X)) 
  nu(prod#(app(X, Y))) = app(X, Y) |> Y = nu(prod#(Y)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_12, R_0, minimal, f) by ({}, R_0, minimal, f).  By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed.

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative), (P_8, R_0, minimal, formative), (P_9, R_0, minimal, formative), (P_10, R_0, minimal, formative) and (P_11, R_0, minimal, formative) is finite.

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

We apply the subterm criterion with the following projection function:

  nu(sum#) = 1 

Thus, we can orient the dependency pairs as follows:

  nu(sum#(cons(X, Y))) = cons(X, Y) |> Y = nu(sum#(Y)) 
  nu(sum#(app(X, Y))) = app(X, Y) |> X = nu(sum#(X)) 
  nu(sum#(app(X, Y))) = app(X, Y) |> Y = nu(sum#(Y)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_11, R_0, minimal, f) by ({}, R_0, minimal, f).  By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed.

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative), (P_8, R_0, minimal, formative), (P_9, R_0, minimal, formative) and (P_10, R_0, minimal, formative) is finite.

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

We apply the subterm criterion with the following projection function:

  nu(app#) = 1 

Thus, we can orient the dependency pairs as follows:

  nu(app#(cons(X, Y), Z)) = cons(X, Y) |> Y = nu(app#(Y, Z)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_10, R_0, minimal, f) by ({}, R_0, minimal, f).  By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed.

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative), (P_8, R_0, minimal, formative) and (P_9, R_0, minimal, formative) is finite.

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

We apply the subterm criterion with the following projection function:

  nu(!times#) = 1 

Thus, we can orient the dependency pairs as follows:

  nu(!times#(0(X), Y)) = 0(X) |> X = nu(!times#(X, Y)) 
  nu(!times#(1(X), Y)) = 1(X) |> X = nu(!times#(X, Y)) 
  nu(!times#(!times(X, Y), Z)) = !times(X, Y) |> X = nu(!times#(X, !times(Y, Z))) 
  nu(!times#(!times(X, Y), Z)) = !times(X, Y) |> Y = nu(!times#(Y, Z)) 
  nu(!times#(X, !plus(Y, Z))) = X = X = nu(!times#(X, Y)) 
  nu(!times#(X, !plus(Y, Z))) = X = X = nu(!times#(X, Z)) 

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

  !times#(X, !plus(Y, Z)) =#> !times#(X, Y)   
  !times#(X, !plus(Y, Z)) =#> !times#(X, Z)   

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative), (P_8, R_0, minimal, formative) and (P_16, R_0, minimal, formative) is finite.

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

We apply the subterm criterion with the following projection function:

  nu(!times#) = 2 

Thus, we can orient the dependency pairs as follows:

  nu(!times#(X, !plus(Y, Z))) = !plus(Y, Z) |> Y = nu(!times#(X, Y)) 
  nu(!times#(X, !plus(Y, Z))) = !plus(Y, Z) |> Z = nu(!times#(X, Z)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_16, R_0, minimal, f) by ({}, R_0, minimal, f).  By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed.

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative) and (P_8, R_0, minimal, formative) is finite.

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

We apply the subterm criterion with the following projection function:

  nu(log!450#) = 1 

Thus, we can orient the dependency pairs as follows:

  nu(log!450#(1(X))) = 1(X) |> X = nu(log!450#(X)) 
  nu(log!450#(0(X))) = 0(X) |> X = nu(log!450#(X)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_8, R_0, minimal, f) by ({}, R_0, minimal, f).  By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed.

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative) and (P_7, R_0, minimal, formative) is finite.

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

We apply the subterm criterion with the following projection function:

  nu(ge#) = 2 

Thus, we can orient the dependency pairs as follows:

  nu(ge#(!940, 0(X))) = 0(X) |> X = nu(ge#(!940, X)) 

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.

Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative) and (P_6, R_0, minimal, formative) is finite.

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

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:

  ge#(0(X), 0(Y)) >? ge#(X, Y) 
  ge#(0(X), 1(Y)) >? ge#(Y, X) 
  ge#(1(X), 0(Y)) >? ge#(X, Y) 
  ge#(1(X), 1(Y)) >? ge#(X, Y) 

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

The following interpretation satisfies the requirements:

  0 = \y0.3 + y0 
  1 = \y0.3 + y0 
  ge# = \y0y1.y0 + y1 

Using this interpretation, the requirements translate to:

  [[ge#(0(_x0), 0(_x1))]] = 6 + x0 + x1 > x0 + x1 = [[ge#(_x0, _x1)]] 
  [[ge#(0(_x0), 1(_x1))]] = 6 + x0 + x1 > x0 + x1 = [[ge#(_x1, _x0)]] 
  [[ge#(1(_x0), 0(_x1))]] = 6 + x0 + x1 > x0 + x1 = [[ge#(_x0, _x1)]] 
  [[ge#(1(_x0), 1(_x1))]] = 6 + x0 + x1 > x0 + x1 = [[ge#(_x0, _x1)]] 

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 each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative) and (P_5, R_0, minimal, formative) is finite.

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

We apply the subterm criterion with the following projection function:

  nu(eq#) = 1 

Thus, we can orient the dependency pairs as follows:

  nu(eq#(1(X), 1(Y))) = 1(X) |> X = nu(eq#(X, Y)) 
  nu(eq#(0(X), 0(Y))) = 0(X) |> X = nu(eq#(X, Y)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_5, R_0, minimal, f) by ({}, R_0, minimal, f).  By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed.

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

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

We apply the subterm criterion with the following projection function:

  nu(eq#) = 1 

Thus, we can orient the dependency pairs as follows:

  nu(eq#(0(X), !940)) = 0(X) |> X = nu(eq#(X, !940)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_4, R_0, minimal, f) by ({}, R_0, minimal, f).  By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed.

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

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

We apply the subterm criterion with the following projection function:

  nu(eq#) = 2 

Thus, we can orient the dependency pairs as follows:

  nu(eq#(!940, 0(X))) = 0(X) |> X = nu(eq#(!940, X)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_3, R_0, minimal, f) by ({}, R_0, minimal, f).  By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed.

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

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

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

  0(!940) => !940 
  !minus(!940, X) => !940 
  !minus(X, !940) => X 
  !minus(0(X), 0(Y)) => 0(!minus(X, Y)) 
  !minus(0(X), 1(Y)) => 1(!minus(!minus(X, Y), 1(!940))) 
  !minus(1(X), 0(Y)) => 1(!minus(X, Y)) 
  !minus(1(X), 1(Y)) => 0(!minus(X, Y)) 

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

  !minus#(0(X), 0(Y)) >? !minus#(X, Y) 
  !minus#(0(X), 1(Y)) >? !minus#(!minus(X, Y), 1(!940)) 
  !minus#(0(X), 1(Y)) >? !minus#(X, Y) 
  !minus#(1(X), 0(Y)) >? !minus#(X, Y) 
  !minus#(1(X), 1(Y)) >? !minus#(X, Y) 
  0(!940) >= !940 
  !minus(!940, X) >= !940 
  !minus(X, !940) >= X 
  !minus(0(X), 0(Y)) >= 0(!minus(X, Y)) 
  !minus(0(X), 1(Y)) >= 1(!minus(!minus(X, Y), 1(!940))) 
  !minus(1(X), 0(Y)) >= 1(!minus(X, Y)) 
  !minus(1(X), 1(Y)) >= 0(!minus(X, Y)) 

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

The following interpretation satisfies the requirements:

  !940 = 0 
  !minus = \y0y1.y0 
  !minus# = \y0y1.y0 
  0 = \y0.1 + 2y0 
  1 = \y0.1 + 2y0 

Using this interpretation, the requirements translate to:

  [[!minus#(0(_x0), 0(_x1))]] = 1 + 2x0 > x0 = [[!minus#(_x0, _x1)]] 
  [[!minus#(0(_x0), 1(_x1))]] = 1 + 2x0 > x0 = [[!minus#(!minus(_x0, _x1), 1(!940))]] 
  [[!minus#(0(_x0), 1(_x1))]] = 1 + 2x0 > x0 = [[!minus#(_x0, _x1)]] 
  [[!minus#(1(_x0), 0(_x1))]] = 1 + 2x0 > x0 = [[!minus#(_x0, _x1)]] 
  [[!minus#(1(_x0), 1(_x1))]] = 1 + 2x0 > x0 = [[!minus#(_x0, _x1)]] 
  [[0(!940)]] = 1 >= 0 = [[!940]] 
  [[!minus(!940, _x0)]] = 0 >= 0 = [[!940]] 
  [[!minus(_x0, !940)]] = x0 >= x0 = [[_x0]] 
  [[!minus(0(_x0), 0(_x1))]] = 1 + 2x0 >= 1 + 2x0 = [[0(!minus(_x0, _x1))]] 
  [[!minus(0(_x0), 1(_x1))]] = 1 + 2x0 >= 1 + 2x0 = [[1(!minus(!minus(_x0, _x1), 1(!940)))]] 
  [[!minus(1(_x0), 0(_x1))]] = 1 + 2x0 >= 1 + 2x0 = [[1(!minus(_x0, _x1))]] 
  [[!minus(1(_x0), 1(_x1))]] = 1 + 2x0 >= 1 + 2x0 = [[0(!minus(_x0, _x1))]] 

By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace a dependency pair problem (P_2, 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, formative) is finite.

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

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

  0(!940) => !940 
  !plus(X, !940) => X 
  !plus(!940, X) => X 
  !plus(0(X), 0(Y)) => 0(!plus(X, Y)) 
  !plus(0(X), 1(Y)) => 1(!plus(X, Y)) 
  !plus(1(X), 0(Y)) => 1(!plus(X, Y)) 
  !plus(1(X), 1(Y)) => 0(!plus(!plus(X, Y), 1(!940))) 
  !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, Z)) 

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

  !plus#(0(X), 0(Y)) >? !plus#(X, Y) 
  !plus#(0(X), 1(Y)) >? !plus#(X, Y) 
  !plus#(1(X), 0(Y)) >? !plus#(X, Y) 
  !plus#(1(X), 1(Y)) >? !plus#(!plus(X, Y), 1(!940)) 
  !plus#(1(X), 1(Y)) >? !plus#(X, Y) 
  !plus#(!plus(X, Y), Z) >? !plus#(X, !plus(Y, Z)) 
  !plus#(!plus(X, Y), Z) >? !plus#(Y, Z) 
  0(!940) >= !940 
  !plus(X, !940) >= X 
  !plus(!940, X) >= X 
  !plus(0(X), 0(Y)) >= 0(!plus(X, Y)) 
  !plus(0(X), 1(Y)) >= 1(!plus(X, Y)) 
  !plus(1(X), 0(Y)) >= 1(!plus(X, Y)) 
  !plus(1(X), 1(Y)) >= 0(!plus(!plus(X, Y), 1(!940))) 
  !plus(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) 

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

The following interpretation satisfies the requirements:

  !940 = 0 
  !plus = \y0y1.y0 + y1 
  !plus# = \y0y1.2y0 + 2y1 
  0 = \y0.2y0 
  1 = \y0.2 + 2y0 

Using this interpretation, the requirements translate to:

  [[!plus#(0(_x0), 0(_x1))]] = 4x0 + 4x1 >= 2x0 + 2x1 = [[!plus#(_x0, _x1)]] 
  [[!plus#(0(_x0), 1(_x1))]] = 4 + 4x0 + 4x1 > 2x0 + 2x1 = [[!plus#(_x0, _x1)]] 
  [[!plus#(1(_x0), 0(_x1))]] = 4 + 4x0 + 4x1 > 2x0 + 2x1 = [[!plus#(_x0, _x1)]] 
  [[!plus#(1(_x0), 1(_x1))]] = 8 + 4x0 + 4x1 > 4 + 2x0 + 2x1 = [[!plus#(!plus(_x0, _x1), 1(!940))]] 
  [[!plus#(1(_x0), 1(_x1))]] = 8 + 4x0 + 4x1 > 2x0 + 2x1 = [[!plus#(_x0, _x1)]] 
  [[!plus#(!plus(_x0, _x1), _x2)]] = 2x0 + 2x1 + 2x2 >= 2x0 + 2x1 + 2x2 = [[!plus#(_x0, !plus(_x1, _x2))]] 
  [[!plus#(!plus(_x0, _x1), _x2)]] = 2x0 + 2x1 + 2x2 >= 2x1 + 2x2 = [[!plus#(_x1, _x2)]] 
  [[0(!940)]] = 0 >= 0 = [[!940]] 
  [[!plus(_x0, !940)]] = x0 >= x0 = [[_x0]] 
  [[!plus(!940, _x0)]] = x0 >= x0 = [[_x0]] 
  [[!plus(0(_x0), 0(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[0(!plus(_x0, _x1))]] 
  [[!plus(0(_x0), 1(_x1))]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[1(!plus(_x0, _x1))]] 
  [[!plus(1(_x0), 0(_x1))]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[1(!plus(_x0, _x1))]] 
  [[!plus(1(_x0), 1(_x1))]] = 4 + 2x0 + 2x1 >= 4 + 2x0 + 2x1 = [[0(!plus(!plus(_x0, _x1), 1(!940)))]] 
  [[!plus(!plus(_x0, _x1), _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[!plus(_x0, !plus(_x1, _x2))]] 

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

  !plus#(0(X), 0(Y)) =#> !plus#(X, Y)   
  !plus#(!plus(X, Y), Z) =#> !plus#(X, !plus(Y, Z))   
  !plus#(!plus(X, Y), Z) =#> !plus#(Y, Z)   

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

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

We apply the subterm criterion with the following projection function:

  nu(!plus#) = 1 

Thus, we can orient the dependency pairs as follows:

  nu(!plus#(0(X), 0(Y))) = 0(X) |> X = nu(!plus#(X, Y)) 
  nu(!plus#(!plus(X, Y), Z)) = !plus(X, Y) |> X = nu(!plus#(X, !plus(Y, Z))) 
  nu(!plus#(!plus(X, Y), Z)) = !plus(X, Y) |> Y = nu(!plus#(Y, Z)) 

By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_17, 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.