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

  !plus : [o * o] --> o 
  !times : [o * o] --> o 
  0 : [] --> o 
  app : [o * o] --> o 
  cons : [o * o] --> o 
  nil : [] --> o 
  prod : [o] --> o 
  s : [o] --> o 
  sum : [o] --> o 

  !plus(X, 0) => X 
  !plus(0, X) => X 
  !plus(s(X), s(Y)) => s(s(!plus(X, Y))) 
  !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, Z)) 
  !times(X, 0) => 0 
  !times(0, X) => 0 
  !times(s(X), s(Y)) => s(!plus(!times(X, Y), !plus(X, Y))) 
  !times(!times(X, Y), Z) => !times(X, !times(Y, Z)) 
  app(nil, X) => X 
  app(cons(X, Y), Z) => cons(X, app(Y, Z)) 
  sum(nil) => 0 
  sum(cons(X, Y)) => !plus(X, sum(Y)) 
  sum(app(X, Y)) => !plus(sum(X), sum(Y)) 
  prod(nil) => s(0) 
  prod(cons(X, Y)) => !times(X, prod(Y)) 
  prod(app(X, Y)) => !times(prod(X), prod(Y)) 

We use rule removal, following [Kop12, Theorem 2.23].

This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):

  !plus(X, 0) >? X 
  !plus(0, X) >? X 
  !plus(s(X), s(Y)) >? s(s(!plus(X, Y))) 
  !plus(!plus(X, Y), Z) >? !plus(X, !plus(Y, Z)) 
  !times(X, 0) >? 0 
  !times(0, X) >? 0 
  !times(s(X), s(Y)) >? s(!plus(!times(X, Y), !plus(X, Y))) 
  !times(!times(X, Y), Z) >? !times(X, !times(Y, Z)) 
  app(nil, X) >? X 
  app(cons(X, Y), Z) >? cons(X, app(Y, Z)) 
  sum(nil) >? 0 
  sum(cons(X, Y)) >? !plus(X, sum(Y)) 
  sum(app(X, Y)) >? !plus(sum(X), sum(Y)) 
  prod(nil) >? s(0) 
  prod(cons(X, Y)) >? !times(X, prod(Y)) 
  prod(app(X, Y)) >? !times(prod(X), prod(Y)) 

about to try horpo

We use a recursive path ordering as defined in [Kop12, Chapter 5].

Argument functions:

  [[0]] = _|_ 

We choose Lex = {!plus, !times} and Mul = {app, cons, nil, prod, s, sum}, and the following precedence: nil > app > prod > !times > sum > cons > !plus > s

Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows:

  !plus(X, _|_) > X 
  !plus(_|_, X) > X 
  !plus(s(X), s(Y)) > s(s(!plus(X, Y))) 
  !plus(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) 
  !times(X, _|_) >= _|_ 
  !times(_|_, X) > _|_ 
  !times(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y))) 
  !times(!times(X, Y), Z) >= !times(X, !times(Y, Z)) 
  app(nil, X) >= X 
  app(cons(X, Y), Z) >= cons(X, app(Y, Z)) 
  sum(nil) >= _|_ 
  sum(cons(X, Y)) > !plus(X, sum(Y)) 
  sum(app(X, Y)) >= !plus(sum(X), sum(Y)) 
  prod(nil) >= s(_|_) 
  prod(cons(X, Y)) >= !times(X, prod(Y)) 
  prod(app(X, Y)) >= !times(prod(X), prod(Y)) 

With these choices, we have:

  1] !plus(X, _|_) > X  because [2], by definition 
  2] !plus*(X, _|_) >= X  because [3], by (Select) 
  3] X >= X  by (Meta) 

  4] !plus(_|_, X) > X  because [5], by definition 
  5] !plus*(_|_, X) >= X  because [3], by (Select) 

  6] !plus(s(X), s(Y)) > s(s(!plus(X, Y)))  because [7], by definition 
  7] !plus*(s(X), s(Y)) >= s(s(!plus(X, Y)))  because !plus > s and [8], by (Copy) 
  8] !plus*(s(X), s(Y)) >= s(!plus(X, Y))  because !plus > s and [9], by (Copy) 
  9] !plus*(s(X), s(Y)) >= !plus(X, Y)  because [10], [12] and [14], by (Stat) 
  10] s(X) > X  because [11], by definition 
  11] s*(X) >= X  because [3], by (Select) 
  12] !plus*(s(X), s(Y)) >= X  because [13], by (Select) 
  13] s(X) >= X  because [11], by (Star) 
  14] !plus*(s(X), s(Y)) >= Y  because [15], by (Select) 
  15] s(Y) >= Y  because [16], by (Star) 
  16] s*(Y) >= Y  because [17], by (Select) 
  17] Y >= Y  by (Meta) 

  18] !plus(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z))  because [19], by (Star) 
  19] !plus*(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z))  because [20], [22] and [24], by (Stat) 
  20] !plus(X, Y) > X  because [21], by definition 
  21] !plus*(X, Y) >= X  because [3], by (Select) 
  22] !plus*(!plus(X, Y), Z) >= X  because [23], by (Select) 
  23] !plus(X, Y) >= X  because [21], by (Star) 
  24] !plus*(!plus(X, Y), Z) >= !plus(Y, Z)  because [25], [27] and [29], by (Stat) 
  25] !plus(X, Y) > Y  because [26], by definition 
  26] !plus*(X, Y) >= Y  because [17], by (Select) 
  27] !plus*(!plus(X, Y), Z) >= Y  because [28], by (Select) 
  28] !plus(X, Y) >= Y  because [26], by (Star) 
  29] !plus*(!plus(X, Y), Z) >= Z  because [30], by (Select) 
  30] Z >= Z  by (Meta) 

  31] !times(X, _|_) >= _|_  by (Bot) 

  32] !times(_|_, X) > _|_  because [33], by definition 
  33] !times*(_|_, X) >= _|_  by (Bot) 

  34] !times(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y)))  because [35], by (Star) 
  35] !times*(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y)))  because !times > s and [36], by (Copy) 
  36] !times*(s(X), s(Y)) >= !plus(!times(X, Y), !plus(X, Y))  because !times > !plus, [37] and [40], by (Copy) 
  37] !times*(s(X), s(Y)) >= !times(X, Y)  because [10], [38] and [39], by (Stat) 
  38] !times*(s(X), s(Y)) >= X  because [13], by (Select) 
  39] !times*(s(X), s(Y)) >= Y  because [15], by (Select) 
  40] !times*(s(X), s(Y)) >= !plus(X, Y)  because !times > !plus, [38] and [39], by (Copy) 

  41] !times(!times(X, Y), Z) >= !times(X, !times(Y, Z))  because [42], by (Star) 
  42] !times*(!times(X, Y), Z) >= !times(X, !times(Y, Z))  because [43], [45] and [47], by (Stat) 
  43] !times(X, Y) > X  because [44], by definition 
  44] !times*(X, Y) >= X  because [3], by (Select) 
  45] !times*(!times(X, Y), Z) >= X  because [46], by (Select) 
  46] !times(X, Y) >= X  because [44], by (Star) 
  47] !times*(!times(X, Y), Z) >= !times(Y, Z)  because [48], [50] and [52], by (Stat) 
  48] !times(X, Y) > Y  because [49], by definition 
  49] !times*(X, Y) >= Y  because [17], by (Select) 
  50] !times*(!times(X, Y), Z) >= Y  because [51], by (Select) 
  51] !times(X, Y) >= Y  because [49], by (Star) 
  52] !times*(!times(X, Y), Z) >= Z  because [30], by (Select) 

  53] app(nil, X) >= X  because [54], by (Star) 
  54] app*(nil, X) >= X  because [55], by (Select) 
  55] X >= X  by (Meta) 

  56] app(cons(X, Y), Z) >= cons(X, app(Y, Z))  because [57], by (Star) 
  57] app*(cons(X, Y), Z) >= cons(X, app(Y, Z))  because app > cons, [58] and [61], by (Copy) 
  58] app*(cons(X, Y), Z) >= X  because [59], by (Select) 
  59] cons(X, Y) >= X  because [60], by (Star) 
  60] cons*(X, Y) >= X  because [3], by (Select) 
  61] app*(cons(X, Y), Z) >= app(Y, Z)  because app in Mul, [62] and [65], by (Stat) 
  62] cons(X, Y) > Y  because [63], by definition 
  63] cons*(X, Y) >= Y  because [64], by (Select) 
  64] Y >= Y  by (Meta) 
  65] Z >= Z  by (Meta) 

  66] sum(nil) >= _|_  by (Bot) 

  67] sum(cons(X, Y)) > !plus(X, sum(Y))  because [68], by definition 
  68] sum*(cons(X, Y)) >= !plus(X, sum(Y))  because sum > !plus, [69] and [72], by (Copy) 
  69] sum*(cons(X, Y)) >= X  because [70], by (Select) 
  70] cons(X, Y) >= X  because [71], by (Star) 
  71] cons*(X, Y) >= X  because [3], by (Select) 
  72] sum*(cons(X, Y)) >= sum(Y)  because sum in Mul and [73], by (Stat) 
  73] cons(X, Y) > Y  because [74], by definition 
  74] cons*(X, Y) >= Y  because [55], by (Select) 

  75] sum(app(X, Y)) >= !plus(sum(X), sum(Y))  because [76], by (Star) 
  76] sum*(app(X, Y)) >= !plus(sum(X), sum(Y))  because sum > !plus, [77] and [80], by (Copy) 
  77] sum*(app(X, Y)) >= sum(X)  because sum in Mul and [78], by (Stat) 
  78] app(X, Y) > X  because [79], by definition 
  79] app*(X, Y) >= X  because [64], by (Select) 
  80] sum*(app(X, Y)) >= sum(Y)  because [81], by (Select) 
  81] app(X, Y) >= sum(Y)  because [82], by (Star) 
  82] app*(X, Y) >= sum(Y)  because app > sum and [83], by (Copy) 
  83] app*(X, Y) >= Y  because [65], by (Select) 

  84] prod(nil) >= s(_|_)  because [85], by (Star) 
  85] prod*(nil) >= s(_|_)  because prod > s and [86], by (Copy) 
  86] prod*(nil) >= _|_  by (Bot) 

  87] prod(cons(X, Y)) >= !times(X, prod(Y))  because [88], by (Star) 
  88] prod*(cons(X, Y)) >= !times(X, prod(Y))  because prod > !times, [89] and [90], by (Copy) 
  89] prod*(cons(X, Y)) >= X  because [70], by (Select) 
  90] prod*(cons(X, Y)) >= prod(Y)  because prod in Mul and [73], by (Stat) 

  91] prod(app(X, Y)) >= !times(prod(X), prod(Y))  because [92], by (Star) 
  92] prod*(app(X, Y)) >= !times(prod(X), prod(Y))  because prod > !times, [93] and [96], by (Copy) 
  93] prod*(app(X, Y)) >= prod(X)  because [94], by (Select) 
  94] app(X, Y) >= prod(X)  because [95], by (Star) 
  95] app*(X, Y) >= prod(X)  because app > prod and [79], by (Copy) 
  96] prod*(app(X, Y)) >= prod(Y)  because [97], by (Select) 
  97] app(X, Y) >= prod(Y)  because [98], by (Star) 
  98] app*(X, Y) >= prod(Y)  because app > prod and [83], by (Copy) 

We can thus remove the following rules:

  !plus(X, 0) => X 
  !plus(0, X) => X 
  !plus(s(X), s(Y)) => s(s(!plus(X, Y))) 
  !times(0, X) => 0 
  sum(cons(X, Y)) => !plus(X, sum(Y)) 

We use rule removal, following [Kop12, Theorem 2.23].

This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):

  !plus(!plus(X, Y), Z) >? !plus(X, !plus(Y, Z)) 
  !times(X, 0) >? 0 
  !times(s(X), s(Y)) >? s(!plus(!times(X, Y), !plus(X, Y))) 
  !times(!times(X, Y), Z) >? !times(X, !times(Y, Z)) 
  app(nil, X) >? X 
  app(cons(X, Y), Z) >? cons(X, app(Y, Z)) 
  sum(nil) >? 0 
  sum(app(X, Y)) >? !plus(sum(X), sum(Y)) 
  prod(nil) >? s(0) 
  prod(cons(X, Y)) >? !times(X, prod(Y)) 
  prod(app(X, Y)) >? !times(prod(X), prod(Y)) 

about to try horpo

We use a recursive path ordering as defined in [Kop12, Chapter 5].

Argument functions:

  [[0]] = _|_ 
  [[sum(x_1)]] = x_1 

We choose Lex = {!plus, !times} and Mul = {app, cons, nil, prod, s}, and the following precedence: app > cons > !times > !plus > nil > prod = s

Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows:

  !plus(!plus(X, Y), Z) > !plus(X, !plus(Y, Z)) 
  !times(X, _|_) >= _|_ 
  !times(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y))) 
  !times(!times(X, Y), Z) > !times(X, !times(Y, Z)) 
  app(nil, X) >= X 
  app(cons(X, Y), Z) >= cons(X, app(Y, Z)) 
  nil >= _|_ 
  app(X, Y) >= !plus(X, Y) 
  prod(nil) >= s(_|_) 
  prod(cons(X, Y)) >= !times(X, prod(Y)) 
  prod(app(X, Y)) > !times(prod(X), prod(Y)) 

With these choices, we have:

  1] !plus(!plus(X, Y), Z) > !plus(X, !plus(Y, Z))  because [2], by definition 
  2] !plus*(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z))  because [3], [6] and [8], by (Stat) 
  3] !plus(X, Y) > X  because [4], by definition 
  4] !plus*(X, Y) >= X  because [5], by (Select) 
  5] X >= X  by (Meta) 
  6] !plus*(!plus(X, Y), Z) >= X  because [7], by (Select) 
  7] !plus(X, Y) >= X  because [4], by (Star) 
  8] !plus*(!plus(X, Y), Z) >= !plus(Y, Z)  because [9], [12] and [14], by (Stat) 
  9] !plus(X, Y) > Y  because [10], by definition 
  10] !plus*(X, Y) >= Y  because [11], by (Select) 
  11] Y >= Y  by (Meta) 
  12] !plus*(!plus(X, Y), Z) >= Y  because [13], by (Select) 
  13] !plus(X, Y) >= Y  because [10], by (Star) 
  14] !plus*(!plus(X, Y), Z) >= Z  because [15], by (Select) 
  15] Z >= Z  by (Meta) 

  16] !times(X, _|_) >= _|_  by (Bot) 

  17] !times(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y)))  because [18], by (Star) 
  18] !times*(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y)))  because !times > s and [19], by (Copy) 
  19] !times*(s(X), s(Y)) >= !plus(!times(X, Y), !plus(X, Y))  because !times > !plus, [20] and [28], by (Copy) 
  20] !times*(s(X), s(Y)) >= !times(X, Y)  because [21], [23], [25] and [26], by (Stat) 
  21] s(X) >= X  because [22], by (Star) 
  22] s*(X) >= X  because [5], by (Select) 
  23] s(Y) > Y  because [24], by definition 
  24] s*(Y) >= Y  because [11], by (Select) 
  25] !times*(s(X), s(Y)) >= X  because [21], by (Select) 
  26] !times*(s(X), s(Y)) >= Y  because [27], by (Select) 
  27] s(Y) >= Y  because [24], by (Star) 
  28] !times*(s(X), s(Y)) >= !plus(X, Y)  because !times > !plus, [25] and [26], by (Copy) 

  29] !times(!times(X, Y), Z) > !times(X, !times(Y, Z))  because [30], by definition 
  30] !times*(!times(X, Y), Z) >= !times(X, !times(Y, Z))  because [31], [33] and [35], by (Stat) 
  31] !times(X, Y) > X  because [32], by definition 
  32] !times*(X, Y) >= X  because [5], by (Select) 
  33] !times*(!times(X, Y), Z) >= X  because [34], by (Select) 
  34] !times(X, Y) >= X  because [32], by (Star) 
  35] !times*(!times(X, Y), Z) >= !times(Y, Z)  because [36], [38] and [40], by (Stat) 
  36] !times(X, Y) > Y  because [37], by definition 
  37] !times*(X, Y) >= Y  because [11], by (Select) 
  38] !times*(!times(X, Y), Z) >= Y  because [39], by (Select) 
  39] !times(X, Y) >= Y  because [37], by (Star) 
  40] !times*(!times(X, Y), Z) >= Z  because [15], by (Select) 

  41] app(nil, X) >= X  because [42], by (Star) 
  42] app*(nil, X) >= X  because [43], by (Select) 
  43] X >= X  by (Meta) 

  44] app(cons(X, Y), Z) >= cons(X, app(Y, Z))  because [45], by (Star) 
  45] app*(cons(X, Y), Z) >= cons(X, app(Y, Z))  because app > cons, [46] and [49], by (Copy) 
  46] app*(cons(X, Y), Z) >= X  because [47], by (Select) 
  47] cons(X, Y) >= X  because [48], by (Star) 
  48] cons*(X, Y) >= X  because [5], by (Select) 
  49] app*(cons(X, Y), Z) >= app(Y, Z)  because app in Mul, [50] and [53], by (Stat) 
  50] cons(X, Y) > Y  because [51], by definition 
  51] cons*(X, Y) >= Y  because [52], by (Select) 
  52] Y >= Y  by (Meta) 
  53] Z >= Z  by (Meta) 

  54] nil >= _|_  by (Bot) 

  55] app(X, Y) >= !plus(X, Y)  because [56], by (Star) 
  56] app*(X, Y) >= !plus(X, Y)  because app > !plus, [57] and [58], by (Copy) 
  57] app*(X, Y) >= X  because [52], by (Select) 
  58] app*(X, Y) >= Y  because [53], by (Select) 

  59] prod(nil) >= s(_|_)  because prod = s, prod in Mul and [60], by (Fun) 
  60] nil >= _|_  by (Bot) 

  61] prod(cons(X, Y)) >= !times(X, prod(Y))  because [62], by (Star) 
  62] prod*(cons(X, Y)) >= !times(X, prod(Y))  because [63], by (Select) 
  63] cons(X, Y) >= !times(X, prod(Y))  because [64], by (Star) 
  64] cons*(X, Y) >= !times(X, prod(Y))  because cons > !times, [65] and [66], by (Copy) 
  65] cons*(X, Y) >= X  because [5], by (Select) 
  66] cons*(X, Y) >= prod(Y)  because cons > prod and [67], by (Copy) 
  67] cons*(X, Y) >= Y  because [43], by (Select) 

  68] prod(app(X, Y)) > !times(prod(X), prod(Y))  because [69], by definition 
  69] prod*(app(X, Y)) >= !times(prod(X), prod(Y))  because [70], by (Select) 
  70] app(X, Y) >= !times(prod(X), prod(Y))  because [71], by (Star) 
  71] app*(X, Y) >= !times(prod(X), prod(Y))  because app > !times, [72] and [73], by (Copy) 
  72] app*(X, Y) >= prod(X)  because app > prod and [57], by (Copy) 
  73] app*(X, Y) >= prod(Y)  because app > prod and [58], by (Copy) 

We can thus remove the following rules:

  !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, Z)) 
  !times(!times(X, Y), Z) => !times(X, !times(Y, Z)) 
  prod(app(X, Y)) => !times(prod(X), prod(Y)) 

We use rule removal, following [Kop12, Theorem 2.23].

This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):

  !times(X, 0) >? 0 
  !times(s(X), s(Y)) >? s(!plus(!times(X, Y), !plus(X, Y))) 
  app(nil, X) >? X 
  app(cons(X, Y), Z) >? cons(X, app(Y, Z)) 
  sum(nil) >? 0 
  sum(app(X, Y)) >? !plus(sum(X), sum(Y)) 
  prod(nil) >? s(0) 
  prod(cons(X, Y)) >? !times(X, prod(Y)) 

about to try horpo

We use a recursive path ordering as defined in [Kop12, Chapter 5].

Argument functions:

  [[0]] = _|_ 

We choose Lex = {} and Mul = {!plus, !times, app, cons, nil, prod, s, sum}, and the following precedence: app > nil > cons > prod > !times > s > !plus > sum

Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows:

  !times(X, _|_) >= _|_ 
  !times(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y))) 
  app(nil, X) > X 
  app(cons(X, Y), Z) >= cons(X, app(Y, Z)) 
  sum(nil) > _|_ 
  sum(app(X, Y)) > !plus(sum(X), sum(Y)) 
  prod(nil) > s(_|_) 
  prod(cons(X, Y)) > !times(X, prod(Y)) 

With these choices, we have:

  1] !times(X, _|_) >= _|_  by (Bot) 

  2] !times(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y)))  because [3], by (Star) 
  3] !times*(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y)))  because !times > s and [4], by (Copy) 
  4] !times*(s(X), s(Y)) >= !plus(!times(X, Y), !plus(X, Y))  because !times > !plus, [5] and [12], by (Copy) 
  5] !times*(s(X), s(Y)) >= !times(X, Y)  because !times in Mul, [6] and [9], by (Stat) 
  6] s(X) >= X  because [7], by (Star) 
  7] s*(X) >= X  because [8], by (Select) 
  8] X >= X  by (Meta) 
  9] s(Y) > Y  because [10], by definition 
  10] s*(Y) >= Y  because [11], by (Select) 
  11] Y >= Y  by (Meta) 
  12] !times*(s(X), s(Y)) >= !plus(X, Y)  because !times > !plus, [13] and [14], by (Copy) 
  13] !times*(s(X), s(Y)) >= X  because [6], by (Select) 
  14] !times*(s(X), s(Y)) >= Y  because [15], by (Select) 
  15] s(Y) >= Y  because [10], by (Star) 

  16] app(nil, X) > X  because [17], by definition 
  17] app*(nil, X) >= X  because [18], by (Select) 
  18] X >= X  by (Meta) 

  19] app(cons(X, Y), Z) >= cons(X, app(Y, Z))  because [20], by (Star) 
  20] app*(cons(X, Y), Z) >= cons(X, app(Y, Z))  because app > cons, [21] and [24], by (Copy) 
  21] app*(cons(X, Y), Z) >= X  because [22], by (Select) 
  22] cons(X, Y) >= X  because [23], by (Star) 
  23] cons*(X, Y) >= X  because [8], by (Select) 
  24] app*(cons(X, Y), Z) >= app(Y, Z)  because app in Mul, [25] and [28], by (Stat) 
  25] cons(X, Y) > Y  because [26], by definition 
  26] cons*(X, Y) >= Y  because [27], by (Select) 
  27] Y >= Y  by (Meta) 
  28] Z >= Z  by (Meta) 

  29] sum(nil) > _|_  because [30], by definition 
  30] sum*(nil) >= _|_  by (Bot) 

  31] sum(app(X, Y)) > !plus(sum(X), sum(Y))  because [32], by definition 
  32] sum*(app(X, Y)) >= !plus(sum(X), sum(Y))  because [33], by (Select) 
  33] app(X, Y) >= !plus(sum(X), sum(Y))  because [34], by (Star) 
  34] app*(X, Y) >= !plus(sum(X), sum(Y))  because app > !plus, [35] and [37], by (Copy) 
  35] app*(X, Y) >= sum(X)  because app > sum and [36], by (Copy) 
  36] app*(X, Y) >= X  because [27], by (Select) 
  37] app*(X, Y) >= sum(Y)  because app > sum and [38], by (Copy) 
  38] app*(X, Y) >= Y  because [28], by (Select) 

  39] prod(nil) > s(_|_)  because [40], by definition 
  40] prod*(nil) >= s(_|_)  because prod > s and [41], by (Copy) 
  41] prod*(nil) >= _|_  by (Bot) 

  42] prod(cons(X, Y)) > !times(X, prod(Y))  because [43], by definition 
  43] prod*(cons(X, Y)) >= !times(X, prod(Y))  because prod > !times, [44] and [47], by (Copy) 
  44] prod*(cons(X, Y)) >= X  because [45], by (Select) 
  45] cons(X, Y) >= X  because [46], by (Star) 
  46] cons*(X, Y) >= X  because [8], by (Select) 
  47] prod*(cons(X, Y)) >= prod(Y)  because [48], by (Select) 
  48] cons(X, Y) >= prod(Y)  because [49], by (Star) 
  49] cons*(X, Y) >= prod(Y)  because cons > prod and [50], by (Copy) 
  50] cons*(X, Y) >= Y  because [18], by (Select) 

We can thus remove the following rules:

  app(nil, X) => X 
  sum(nil) => 0 
  sum(app(X, Y)) => !plus(sum(X), sum(Y)) 
  prod(nil) => s(0) 
  prod(cons(X, Y)) => !times(X, prod(Y)) 

We use rule removal, following [Kop12, Theorem 2.23].

This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):

  !times(X, 0) >? 0 
  !times(s(X), s(Y)) >? s(!plus(!times(X, Y), !plus(X, Y))) 
  app(cons(X, Y), Z) >? cons(X, app(Y, Z)) 

about to try horpo

We use a recursive path ordering as defined in [Kop12, Chapter 5].

We choose Lex = {} and Mul = {!plus, !times, 0, app, cons, s}, and the following precedence: app > !times > !plus > s > 0 > cons

With these choices, we have:

  1] !times(X, 0) > 0  because [2], by definition 
  2] !times*(X, 0) >= 0  because !times > 0, by (Copy) 

  3] !times(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y)))  because [4], by (Star) 
  4] !times*(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y)))  because !times > s and [5], by (Copy) 
  5] !times*(s(X), s(Y)) >= !plus(!times(X, Y), !plus(X, Y))  because !times > !plus, [6] and [13], by (Copy) 
  6] !times*(s(X), s(Y)) >= !times(X, Y)  because !times in Mul, [7] and [10], by (Stat) 
  7] s(X) >= X  because [8], by (Star) 
  8] s*(X) >= X  because [9], by (Select) 
  9] X >= X  by (Meta) 
  10] s(Y) > Y  because [11], by definition 
  11] s*(Y) >= Y  because [12], by (Select) 
  12] Y >= Y  by (Meta) 
  13] !times*(s(X), s(Y)) >= !plus(X, Y)  because !times > !plus, [14] and [15], by (Copy) 
  14] !times*(s(X), s(Y)) >= X  because [7], by (Select) 
  15] !times*(s(X), s(Y)) >= Y  because [16], by (Select) 
  16] s(Y) >= Y  because [11], by (Star) 

  17] app(cons(X, Y), Z) >= cons(X, app(Y, Z))  because [18], by (Star) 
  18] app*(cons(X, Y), Z) >= cons(X, app(Y, Z))  because app > cons, [19] and [22], by (Copy) 
  19] app*(cons(X, Y), Z) >= X  because [20], by (Select) 
  20] cons(X, Y) >= X  because [21], by (Star) 
  21] cons*(X, Y) >= X  because [9], by (Select) 
  22] app*(cons(X, Y), Z) >= app(Y, Z)  because app in Mul, [23] and [26], by (Stat) 
  23] cons(X, Y) > Y  because [24], by definition 
  24] cons*(X, Y) >= Y  because [25], by (Select) 
  25] Y >= Y  by (Meta) 
  26] Z >= Z  by (Meta) 

We can thus remove the following rules:

  !times(X, 0) => 0 

We use rule removal, following [Kop12, Theorem 2.23].

This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):

  !times(s(X), s(Y)) >? s(!plus(!times(X, Y), !plus(X, Y))) 
  app(cons(X, Y), Z) >? cons(X, app(Y, Z)) 

about to try horpo

We use a recursive path ordering as defined in [Kop12, Chapter 5].

We choose Lex = {} and Mul = {!plus, !times, app, cons, s}, and the following precedence: app > !times > cons > s > !plus

With these choices, we have:

  1] !times(s(X), s(Y)) > s(!plus(!times(X, Y), !plus(X, Y)))  because [2], by definition 
  2] !times*(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y)))  because !times > s and [3], by (Copy) 
  3] !times*(s(X), s(Y)) >= !plus(!times(X, Y), !plus(X, Y))  because !times > !plus, [4] and [11], by (Copy) 
  4] !times*(s(X), s(Y)) >= !times(X, Y)  because !times in Mul, [5] and [8], by (Stat) 
  5] s(X) > X  because [6], by definition 
  6] s*(X) >= X  because [7], by (Select) 
  7] X >= X  by (Meta) 
  8] s(Y) >= Y  because [9], by (Star) 
  9] s*(Y) >= Y  because [10], by (Select) 
  10] Y >= Y  by (Meta) 
  11] !times*(s(X), s(Y)) >= !plus(X, Y)  because !times > !plus, [12] and [14], by (Copy) 
  12] !times*(s(X), s(Y)) >= X  because [13], by (Select) 
  13] s(X) >= X  because [6], by (Star) 
  14] !times*(s(X), s(Y)) >= Y  because [8], by (Select) 

  15] app(cons(X, Y), Z) >= cons(X, app(Y, Z))  because [16], by (Star) 
  16] app*(cons(X, Y), Z) >= cons(X, app(Y, Z))  because app > cons, [17] and [20], by (Copy) 
  17] app*(cons(X, Y), Z) >= X  because [18], by (Select) 
  18] cons(X, Y) >= X  because [19], by (Star) 
  19] cons*(X, Y) >= X  because [7], by (Select) 
  20] app*(cons(X, Y), Z) >= app(Y, Z)  because app in Mul, [21] and [24], by (Stat) 
  21] cons(X, Y) > Y  because [22], by definition 
  22] cons*(X, Y) >= Y  because [23], by (Select) 
  23] Y >= Y  by (Meta) 
  24] Z >= Z  by (Meta) 

We can thus remove the following rules:

  !times(s(X), s(Y)) => s(!plus(!times(X, Y), !plus(X, Y))) 

We use rule removal, following [Kop12, Theorem 2.23].

This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):

  app(cons(X, Y), Z) >? cons(X, app(Y, Z)) 

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

The following interpretation satisfies the requirements:

  app = \y0y1.y1 + 3y0 
  cons = \y0y1.1 + y0 + y1 

Using this interpretation, the requirements translate to:

  [[app(cons(_x0, _x1), _x2)]] = 3 + x2 + 3x0 + 3x1 > 1 + x0 + x2 + 3x1 = [[cons(_x0, app(_x1, _x2))]] 

We can thus remove the following rules:

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

All rules were succesfully removed.  Thus, termination of the original system has been reduced to termination of the beta-rule, which is well-known to hold.


+++ Citations +++

[Kop12]  C. Kop.  Higher Order Termination.  PhD Thesis, 2012.