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


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


YES
We consider the system theBenchmark.

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

  0 : [] --> o 
  active : [o] --> o 
  and : [o * o] --> o 
  mark : [o] --> o 
  ok : [o] --> o 
  plus : [o * o] --> o 
  proper : [o] --> o 
  s : [o] --> o 
  top : [o] --> o 
  tt : [] --> o 
  x : [o * o] --> o 

  active(and(tt, X)) => mark(X) 
  active(plus(X, 0)) => mark(X) 
  active(plus(X, s(Y))) => mark(s(plus(X, Y))) 
  active(x(X, 0)) => mark(0) 
  active(x(X, s(Y))) => mark(plus(x(X, Y), X)) 
  active(and(X, Y)) => and(active(X), Y) 
  active(plus(X, Y)) => plus(active(X), Y) 
  active(plus(X, Y)) => plus(X, active(Y)) 
  active(s(X)) => s(active(X)) 
  active(x(X, Y)) => x(active(X), Y) 
  active(x(X, Y)) => x(X, active(Y)) 
  and(mark(X), Y) => mark(and(X, Y)) 
  plus(mark(X), Y) => mark(plus(X, Y)) 
  plus(X, mark(Y)) => mark(plus(X, Y)) 
  s(mark(X)) => mark(s(X)) 
  x(mark(X), Y) => mark(x(X, Y)) 
  x(X, mark(Y)) => mark(x(X, Y)) 
  proper(and(X, Y)) => and(proper(X), proper(Y)) 
  proper(tt) => ok(tt) 
  proper(plus(X, Y)) => plus(proper(X), proper(Y)) 
  proper(0) => ok(0) 
  proper(s(X)) => s(proper(X)) 
  proper(x(X, Y)) => x(proper(X), proper(Y)) 
  and(ok(X), ok(Y)) => ok(and(X, Y)) 
  plus(ok(X), ok(Y)) => ok(plus(X, Y)) 
  s(ok(X)) => ok(s(X)) 
  x(ok(X), ok(Y)) => ok(x(X, Y)) 
  top(mark(X)) => top(proper(X)) 
  top(ok(X)) => top(active(X)) 

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

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

  active(and(tt, X)) >? mark(X) 
  active(plus(X, 0)) >? mark(X) 
  active(plus(X, s(Y))) >? mark(s(plus(X, Y))) 
  active(x(X, 0)) >? mark(0) 
  active(x(X, s(Y))) >? mark(plus(x(X, Y), X)) 
  active(and(X, Y)) >? and(active(X), Y) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  active(s(X)) >? s(active(X)) 
  active(x(X, Y)) >? x(active(X), Y) 
  active(x(X, Y)) >? x(X, active(Y)) 
  and(mark(X), Y) >? mark(and(X, Y)) 
  plus(mark(X), Y) >? mark(plus(X, Y)) 
  plus(X, mark(Y)) >? mark(plus(X, Y)) 
  s(mark(X)) >? mark(s(X)) 
  x(mark(X), Y) >? mark(x(X, Y)) 
  x(X, mark(Y)) >? mark(x(X, Y)) 
  proper(and(X, Y)) >? and(proper(X), proper(Y)) 
  proper(tt) >? ok(tt) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  proper(0) >? ok(0) 
  proper(s(X)) >? s(proper(X)) 
  proper(x(X, Y)) >? x(proper(X), proper(Y)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  s(ok(X)) >? ok(s(X)) 
  x(ok(X), ok(Y)) >? ok(x(X, Y)) 
  top(mark(X)) >? top(proper(X)) 
  top(ok(X)) >? top(active(X)) 

about to try horpo

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

Argument functions:

  [[active(x_1)]] = x_1 
  [[ok(x_1)]] = x_1 
  [[proper(x_1)]] = x_1 
  [[tt]] = _|_ 

We choose Lex = {and} and Mul = {0, mark, plus, s, top, x}, and the following precedence: and > top > x > plus > s > mark > 0

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

  and(_|_, X) >= mark(X) 
  plus(X, 0) > mark(X) 
  plus(X, s(Y)) >= mark(s(plus(X, Y))) 
  x(X, 0) >= mark(0) 
  x(X, s(Y)) >= mark(plus(x(X, Y), X)) 
  and(X, Y) >= and(X, Y) 
  plus(X, Y) >= plus(X, Y) 
  plus(X, Y) >= plus(X, Y) 
  s(X) >= s(X) 
  x(X, Y) >= x(X, Y) 
  x(X, Y) >= x(X, Y) 
  and(mark(X), Y) > mark(and(X, Y)) 
  plus(mark(X), Y) >= mark(plus(X, Y)) 
  plus(X, mark(Y)) > mark(plus(X, Y)) 
  s(mark(X)) > mark(s(X)) 
  x(mark(X), Y) >= mark(x(X, Y)) 
  x(X, mark(Y)) >= mark(x(X, Y)) 
  and(X, Y) >= and(X, Y) 
  _|_ >= _|_ 
  plus(X, Y) >= plus(X, Y) 
  0 >= 0 
  s(X) >= s(X) 
  x(X, Y) >= x(X, Y) 
  and(X, Y) >= and(X, Y) 
  plus(X, Y) >= plus(X, Y) 
  s(X) >= s(X) 
  x(X, Y) >= x(X, Y) 
  top(mark(X)) >= top(X) 
  top(X) >= top(X) 

With these choices, we have:

  1] and(_|_, X) >= mark(X)  because [2], by (Star) 
  2] and*(_|_, X) >= mark(X)  because and > mark and [3], by (Copy) 
  3] and*(_|_, X) >= X  because [4], by (Select) 
  4] X >= X  by (Meta) 

  5] plus(X, 0) > mark(X)  because [6], by definition 
  6] plus*(X, 0) >= mark(X)  because plus > mark and [7], by (Copy) 
  7] plus*(X, 0) >= X  because [8], by (Select) 
  8] X >= X  by (Meta) 

  9] plus(X, s(Y)) >= mark(s(plus(X, Y)))  because [10], by (Star) 
  10] plus*(X, s(Y)) >= mark(s(plus(X, Y)))  because plus > mark and [11], by (Copy) 
  11] plus*(X, s(Y)) >= s(plus(X, Y))  because plus > s and [12], by (Copy) 
  12] plus*(X, s(Y)) >= plus(X, Y)  because plus in Mul, [13] and [14], by (Stat) 
  13] X >= X  by (Meta) 
  14] s(Y) > Y  because [15], by definition 
  15] s*(Y) >= Y  because [16], by (Select) 
  16] Y >= Y  by (Meta) 

  17] x(X, 0) >= mark(0)  because [18], by (Star) 
  18] x*(X, 0) >= mark(0)  because x > mark and [19], by (Copy) 
  19] x*(X, 0) >= 0  because [20], by (Select) 
  20] 0 >= 0  by (Fun) 

  21] x(X, s(Y)) >= mark(plus(x(X, Y), X))  because [22], by (Star) 
  22] x*(X, s(Y)) >= mark(plus(x(X, Y), X))  because x > mark and [23], by (Copy) 
  23] x*(X, s(Y)) >= plus(x(X, Y), X)  because x > plus, [24] and [25], by (Copy) 
  24] x*(X, s(Y)) >= x(X, Y)  because x in Mul, [13] and [14], by (Stat) 
  25] x*(X, s(Y)) >= X  because [13], by (Select) 

  26] and(X, Y) >= and(X, Y)  because [27] and [28], by (Fun) 
  27] X >= X  by (Meta) 
  28] Y >= Y  by (Meta) 

  29] plus(X, Y) >= plus(X, Y)  because plus in Mul, [27] and [28], by (Fun) 

  30] plus(X, Y) >= plus(X, Y)  because plus in Mul, [27] and [31], by (Fun) 
  31] Y >= Y  by (Meta) 

  32] s(X) >= s(X)  because s in Mul and [33], by (Fun) 
  33] X >= X  by (Meta) 

  34] x(X, Y) >= x(X, Y)  because x in Mul, [27] and [31], by (Fun) 

  35] x(X, Y) >= x(X, Y)  because x in Mul, [27] and [31], by (Fun) 

  36] and(mark(X), Y) > mark(and(X, Y))  because [37], by definition 
  37] and*(mark(X), Y) >= mark(and(X, Y))  because and > mark and [38], by (Copy) 
  38] and*(mark(X), Y) >= and(X, Y)  because [39], [41] and [43], by (Stat) 
  39] mark(X) > X  because [40], by definition 
  40] mark*(X) >= X  because [27], by (Select) 
  41] and*(mark(X), Y) >= X  because [42], by (Select) 
  42] mark(X) >= X  because [40], by (Star) 
  43] and*(mark(X), Y) >= Y  because [31], by (Select) 

  44] plus(mark(X), Y) >= mark(plus(X, Y))  because [45], by (Star) 
  45] plus*(mark(X), Y) >= mark(plus(X, Y))  because plus > mark and [46], by (Copy) 
  46] plus*(mark(X), Y) >= plus(X, Y)  because plus in Mul, [39] and [31], by (Stat) 

  47] plus(X, mark(Y)) > mark(plus(X, Y))  because [48], by definition 
  48] plus*(X, mark(Y)) >= mark(plus(X, Y))  because plus > mark and [49], by (Copy) 
  49] plus*(X, mark(Y)) >= plus(X, Y)  because plus in Mul, [27] and [50], by (Stat) 
  50] mark(Y) > Y  because [51], by definition 
  51] mark*(Y) >= Y  because [31], by (Select) 

  52] s(mark(X)) > mark(s(X))  because [53], by definition 
  53] s*(mark(X)) >= mark(s(X))  because s > mark and [54], by (Copy) 
  54] s*(mark(X)) >= s(X)  because s in Mul and [55], by (Stat) 
  55] mark(X) > X  because [56], by definition 
  56] mark*(X) >= X  because [33], by (Select) 

  57] x(mark(X), Y) >= mark(x(X, Y))  because [58], by (Star) 
  58] x*(mark(X), Y) >= mark(x(X, Y))  because x > mark and [59], by (Copy) 
  59] x*(mark(X), Y) >= x(X, Y)  because x in Mul, [39] and [31], by (Stat) 

  60] x(X, mark(Y)) >= mark(x(X, Y))  because [61], by (Star) 
  61] x*(X, mark(Y)) >= mark(x(X, Y))  because x > mark and [62], by (Copy) 
  62] x*(X, mark(Y)) >= x(X, Y)  because x in Mul, [27] and [50], by (Stat) 

  63] and(X, Y) >= and(X, Y)  because [64] and [65], by (Fun) 
  64] X >= X  by (Meta) 
  65] Y >= Y  by (Meta) 

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

  67] plus(X, Y) >= plus(X, Y)  because plus in Mul, [64] and [65], by (Fun) 

  68] 0 >= 0  by (Fun) 

  69] s(X) >= s(X)  because s in Mul and [70], by (Fun) 
  70] X >= X  by (Meta) 

  71] x(X, Y) >= x(X, Y)  because x in Mul, [64] and [65], by (Fun) 

  72] and(X, Y) >= and(X, Y)  because [73] and [74], by (Fun) 
  73] X >= X  by (Meta) 
  74] Y >= Y  by (Meta) 

  75] plus(X, Y) >= plus(X, Y)  because plus in Mul, [73] and [74], by (Fun) 

  76] s(X) >= s(X)  because s in Mul and [77], by (Fun) 
  77] X >= X  by (Meta) 

  78] x(X, Y) >= x(X, Y)  because x in Mul, [73] and [74], by (Fun) 

  79] top(mark(X)) >= top(X)  because top in Mul and [80], by (Fun) 
  80] mark(X) >= X  because [56], by (Star) 

  81] top(X) >= top(X)  because top in Mul and [82], by (Fun) 
  82] X >= X  by (Meta) 

We can thus remove the following rules:

  active(plus(X, 0)) => mark(X) 
  and(mark(X), Y) => mark(and(X, Y)) 
  plus(X, mark(Y)) => mark(plus(X, Y)) 
  s(mark(X)) => mark(s(X)) 

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

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

  active(and(tt, X)) >? mark(X) 
  active(plus(X, s(Y))) >? mark(s(plus(X, Y))) 
  active(x(X, 0)) >? mark(0) 
  active(x(X, s(Y))) >? mark(plus(x(X, Y), X)) 
  active(and(X, Y)) >? and(active(X), Y) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  active(s(X)) >? s(active(X)) 
  active(x(X, Y)) >? x(active(X), Y) 
  active(x(X, Y)) >? x(X, active(Y)) 
  plus(mark(X), Y) >? mark(plus(X, Y)) 
  x(mark(X), Y) >? mark(x(X, Y)) 
  x(X, mark(Y)) >? mark(x(X, Y)) 
  proper(and(X, Y)) >? and(proper(X), proper(Y)) 
  proper(tt) >? ok(tt) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  proper(0) >? ok(0) 
  proper(s(X)) >? s(proper(X)) 
  proper(x(X, Y)) >? x(proper(X), proper(Y)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  s(ok(X)) >? ok(s(X)) 
  x(ok(X), ok(Y)) >? ok(x(X, Y)) 
  top(mark(X)) >? top(proper(X)) 
  top(ok(X)) >? top(active(X)) 

about to try horpo

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

Argument functions:

  [[active(x_1)]] = x_1 
  [[and(x_1, x_2)]] = and(x_2, x_1) 
  [[ok(x_1)]] = x_1 
  [[proper(x_1)]] = x_1 
  [[tt]] = _|_ 

We choose Lex = {and} and Mul = {0, mark, plus, s, top, x}, and the following precedence: and > top > x > 0 > plus > mark > s

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

  and(_|_, X) >= mark(X) 
  plus(X, s(Y)) >= mark(s(plus(X, Y))) 
  x(X, 0) >= mark(0) 
  x(X, s(Y)) >= mark(plus(x(X, Y), X)) 
  and(X, Y) >= and(X, Y) 
  plus(X, Y) >= plus(X, Y) 
  plus(X, Y) >= plus(X, Y) 
  s(X) >= s(X) 
  x(X, Y) >= x(X, Y) 
  x(X, Y) >= x(X, Y) 
  plus(mark(X), Y) >= mark(plus(X, Y)) 
  x(mark(X), Y) >= mark(x(X, Y)) 
  x(X, mark(Y)) > mark(x(X, Y)) 
  and(X, Y) >= and(X, Y) 
  _|_ >= _|_ 
  plus(X, Y) >= plus(X, Y) 
  0 >= 0 
  s(X) >= s(X) 
  x(X, Y) >= x(X, Y) 
  and(X, Y) >= and(X, Y) 
  plus(X, Y) >= plus(X, Y) 
  s(X) >= s(X) 
  x(X, Y) >= x(X, Y) 
  top(mark(X)) >= top(X) 
  top(X) >= top(X) 

With these choices, we have:

  1] and(_|_, X) >= mark(X)  because [2], by (Star) 
  2] and*(_|_, X) >= mark(X)  because and > mark and [3], by (Copy) 
  3] and*(_|_, X) >= X  because [4], by (Select) 
  4] X >= X  by (Meta) 

  5] plus(X, s(Y)) >= mark(s(plus(X, Y)))  because [6], by (Star) 
  6] plus*(X, s(Y)) >= mark(s(plus(X, Y)))  because plus > mark and [7], by (Copy) 
  7] plus*(X, s(Y)) >= s(plus(X, Y))  because plus > s and [8], by (Copy) 
  8] plus*(X, s(Y)) >= plus(X, Y)  because plus in Mul, [9] and [10], by (Stat) 
  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] x(X, 0) >= mark(0)  because [14], by (Star) 
  14] x*(X, 0) >= mark(0)  because x > mark and [15], by (Copy) 
  15] x*(X, 0) >= 0  because x > 0, by (Copy) 

  16] x(X, s(Y)) >= mark(plus(x(X, Y), X))  because [17], by (Star) 
  17] x*(X, s(Y)) >= mark(plus(x(X, Y), X))  because x > mark and [18], by (Copy) 
  18] x*(X, s(Y)) >= plus(x(X, Y), X)  because x > plus, [19] and [20], by (Copy) 
  19] x*(X, s(Y)) >= x(X, Y)  because x in Mul, [9] and [10], by (Stat) 
  20] x*(X, s(Y)) >= X  because [9], by (Select) 

  21] and(X, Y) >= and(X, Y)  because [22] and [23], by (Fun) 
  22] X >= X  by (Meta) 
  23] Y >= Y  by (Meta) 

  24] plus(X, Y) >= plus(X, Y)  because plus in Mul, [22] and [23], by (Fun) 

  25] plus(X, Y) >= plus(X, Y)  because plus in Mul, [22] and [26], by (Fun) 
  26] Y >= Y  by (Meta) 

  27] s(X) >= s(X)  because s in Mul and [28], by (Fun) 
  28] X >= X  by (Meta) 

  29] x(X, Y) >= x(X, Y)  because x in Mul, [22] and [26], by (Fun) 

  30] x(X, Y) >= x(X, Y)  because x in Mul, [22] and [26], by (Fun) 

  31] plus(mark(X), Y) >= mark(plus(X, Y))  because [32], by (Star) 
  32] plus*(mark(X), Y) >= mark(plus(X, Y))  because plus > mark and [33], by (Copy) 
  33] plus*(mark(X), Y) >= plus(X, Y)  because plus in Mul, [34] and [26], by (Stat) 
  34] mark(X) > X  because [35], by definition 
  35] mark*(X) >= X  because [22], by (Select) 

  36] x(mark(X), Y) >= mark(x(X, Y))  because [37], by (Star) 
  37] x*(mark(X), Y) >= mark(x(X, Y))  because x > mark and [38], by (Copy) 
  38] x*(mark(X), Y) >= x(X, Y)  because x in Mul, [34] and [26], by (Stat) 

  39] x(X, mark(Y)) > mark(x(X, Y))  because [40], by definition 
  40] x*(X, mark(Y)) >= mark(x(X, Y))  because x > mark and [41], by (Copy) 
  41] x*(X, mark(Y)) >= x(X, Y)  because x in Mul, [22] and [42], by (Stat) 
  42] mark(Y) > Y  because [43], by definition 
  43] mark*(Y) >= Y  because [26], by (Select) 

  44] and(X, Y) >= and(X, Y)  because [45] and [46], by (Fun) 
  45] X >= X  by (Meta) 
  46] Y >= Y  by (Meta) 

  47] _|_ >= _|_  by (Bot) 

  48] plus(X, Y) >= plus(X, Y)  because plus in Mul, [45] and [46], by (Fun) 

  49] 0 >= 0  by (Fun) 

  50] s(X) >= s(X)  because s in Mul and [51], by (Fun) 
  51] X >= X  by (Meta) 

  52] x(X, Y) >= x(X, Y)  because x in Mul, [45] and [46], by (Fun) 

  53] and(X, Y) >= and(X, Y)  because [54] and [55], by (Fun) 
  54] X >= X  by (Meta) 
  55] Y >= Y  by (Meta) 

  56] plus(X, Y) >= plus(X, Y)  because plus in Mul, [54] and [55], by (Fun) 

  57] s(X) >= s(X)  because s in Mul and [58], by (Fun) 
  58] X >= X  by (Meta) 

  59] x(X, Y) >= x(X, Y)  because x in Mul, [54] and [55], by (Fun) 

  60] top(mark(X)) >= top(X)  because top in Mul and [61], by (Fun) 
  61] mark(X) >= X  because [62], by (Star) 
  62] mark*(X) >= X  because [58], by (Select) 

  63] top(X) >= top(X)  because top in Mul and [64], by (Fun) 
  64] X >= X  by (Meta) 

We can thus remove the following rules:

  x(X, mark(Y)) => mark(x(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]):

  active(and(tt, X)) >? mark(X) 
  active(plus(X, s(Y))) >? mark(s(plus(X, Y))) 
  active(x(X, 0)) >? mark(0) 
  active(x(X, s(Y))) >? mark(plus(x(X, Y), X)) 
  active(and(X, Y)) >? and(active(X), Y) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  active(s(X)) >? s(active(X)) 
  active(x(X, Y)) >? x(active(X), Y) 
  active(x(X, Y)) >? x(X, active(Y)) 
  plus(mark(X), Y) >? mark(plus(X, Y)) 
  x(mark(X), Y) >? mark(x(X, Y)) 
  proper(and(X, Y)) >? and(proper(X), proper(Y)) 
  proper(tt) >? ok(tt) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  proper(0) >? ok(0) 
  proper(s(X)) >? s(proper(X)) 
  proper(x(X, Y)) >? x(proper(X), proper(Y)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  s(ok(X)) >? ok(s(X)) 
  x(ok(X), ok(Y)) >? ok(x(X, Y)) 
  top(mark(X)) >? top(proper(X)) 
  top(ok(X)) >? top(active(X)) 

about to try horpo

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

Argument functions:

  [[active(x_1)]] = x_1 
  [[ok(x_1)]] = x_1 
  [[proper(x_1)]] = x_1 

We choose Lex = {} and Mul = {0, and, mark, plus, s, top, tt, x}, and the following precedence: 0 > and > top > tt > x > plus > mark > s

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

  and(tt, X) >= mark(X) 
  plus(X, s(Y)) >= mark(s(plus(X, Y))) 
  x(X, 0) >= mark(0) 
  x(X, s(Y)) >= mark(plus(x(X, Y), X)) 
  and(X, Y) >= and(X, Y) 
  plus(X, Y) >= plus(X, Y) 
  plus(X, Y) >= plus(X, Y) 
  s(X) >= s(X) 
  x(X, Y) >= x(X, Y) 
  x(X, Y) >= x(X, Y) 
  plus(mark(X), Y) > mark(plus(X, Y)) 
  x(mark(X), Y) >= mark(x(X, Y)) 
  and(X, Y) >= and(X, Y) 
  tt >= tt 
  plus(X, Y) >= plus(X, Y) 
  0 >= 0 
  s(X) >= s(X) 
  x(X, Y) >= x(X, Y) 
  and(X, Y) >= and(X, Y) 
  plus(X, Y) >= plus(X, Y) 
  s(X) >= s(X) 
  x(X, Y) >= x(X, Y) 
  top(mark(X)) >= top(X) 
  top(X) >= top(X) 

With these choices, we have:

  1] and(tt, X) >= mark(X)  because [2], by (Star) 
  2] and*(tt, X) >= mark(X)  because and > mark and [3], by (Copy) 
  3] and*(tt, X) >= X  because [4], by (Select) 
  4] X >= X  by (Meta) 

  5] plus(X, s(Y)) >= mark(s(plus(X, Y)))  because [6], by (Star) 
  6] plus*(X, s(Y)) >= mark(s(plus(X, Y)))  because plus > mark and [7], by (Copy) 
  7] plus*(X, s(Y)) >= s(plus(X, Y))  because plus > s and [8], by (Copy) 
  8] plus*(X, s(Y)) >= plus(X, Y)  because plus in Mul, [9] and [10], by (Stat) 
  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] x(X, 0) >= mark(0)  because [14], by (Star) 
  14] x*(X, 0) >= mark(0)  because x > mark and [15], by (Copy) 
  15] x*(X, 0) >= 0  because [16], by (Select) 
  16] 0 >= 0  by (Fun) 

  17] x(X, s(Y)) >= mark(plus(x(X, Y), X))  because [18], by (Star) 
  18] x*(X, s(Y)) >= mark(plus(x(X, Y), X))  because x > mark and [19], by (Copy) 
  19] x*(X, s(Y)) >= plus(x(X, Y), X)  because x > plus, [20] and [21], by (Copy) 
  20] x*(X, s(Y)) >= x(X, Y)  because x in Mul, [9] and [10], by (Stat) 
  21] x*(X, s(Y)) >= X  because [9], by (Select) 

  22] and(X, Y) >= and(X, Y)  because and in Mul, [23] and [24], by (Fun) 
  23] X >= X  by (Meta) 
  24] Y >= Y  by (Meta) 

  25] plus(X, Y) >= plus(X, Y)  because plus in Mul, [23] and [24], by (Fun) 

  26] plus(X, Y) >= plus(X, Y)  because plus in Mul, [23] and [27], by (Fun) 
  27] Y >= Y  by (Meta) 

  28] s(X) >= s(X)  because s in Mul and [29], by (Fun) 
  29] X >= X  by (Meta) 

  30] x(X, Y) >= x(X, Y)  because x in Mul, [23] and [27], by (Fun) 

  31] x(X, Y) >= x(X, Y)  because x in Mul, [23] and [27], by (Fun) 

  32] plus(mark(X), Y) > mark(plus(X, Y))  because [33], by definition 
  33] plus*(mark(X), Y) >= mark(plus(X, Y))  because plus > mark and [34], by (Copy) 
  34] plus*(mark(X), Y) >= plus(X, Y)  because plus in Mul, [35] and [27], by (Stat) 
  35] mark(X) > X  because [36], by definition 
  36] mark*(X) >= X  because [23], by (Select) 

  37] x(mark(X), Y) >= mark(x(X, Y))  because [38], by (Star) 
  38] x*(mark(X), Y) >= mark(x(X, Y))  because x > mark and [39], by (Copy) 
  39] x*(mark(X), Y) >= x(X, Y)  because x in Mul, [35] and [27], by (Stat) 

  40] and(X, Y) >= and(X, Y)  because and in Mul, [41] and [42], by (Fun) 
  41] X >= X  by (Meta) 
  42] Y >= Y  by (Meta) 

  43] tt >= tt  by (Fun) 

  44] plus(X, Y) >= plus(X, Y)  because plus in Mul, [41] and [42], by (Fun) 

  45] 0 >= 0  by (Fun) 

  46] s(X) >= s(X)  because s in Mul and [47], by (Fun) 
  47] X >= X  by (Meta) 

  48] x(X, Y) >= x(X, Y)  because x in Mul, [41] and [42], by (Fun) 

  49] and(X, Y) >= and(X, Y)  because and in Mul, [50] and [51], by (Fun) 
  50] X >= X  by (Meta) 
  51] Y >= Y  by (Meta) 

  52] plus(X, Y) >= plus(X, Y)  because plus in Mul, [50] and [51], by (Fun) 

  53] s(X) >= s(X)  because s in Mul and [54], by (Fun) 
  54] X >= X  by (Meta) 

  55] x(X, Y) >= x(X, Y)  because x in Mul, [50] and [51], by (Fun) 

  56] top(mark(X)) >= top(X)  because top in Mul and [57], by (Fun) 
  57] mark(X) >= X  because [58], by (Star) 
  58] mark*(X) >= X  because [54], by (Select) 

  59] top(X) >= top(X)  because top in Mul and [60], by (Fun) 
  60] X >= X  by (Meta) 

We can thus remove the following rules:

  plus(mark(X), Y) => mark(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]):

  active(and(tt, X)) >? mark(X) 
  active(plus(X, s(Y))) >? mark(s(plus(X, Y))) 
  active(x(X, 0)) >? mark(0) 
  active(x(X, s(Y))) >? mark(plus(x(X, Y), X)) 
  active(and(X, Y)) >? and(active(X), Y) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  active(s(X)) >? s(active(X)) 
  active(x(X, Y)) >? x(active(X), Y) 
  active(x(X, Y)) >? x(X, active(Y)) 
  x(mark(X), Y) >? mark(x(X, Y)) 
  proper(and(X, Y)) >? and(proper(X), proper(Y)) 
  proper(tt) >? ok(tt) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  proper(0) >? ok(0) 
  proper(s(X)) >? s(proper(X)) 
  proper(x(X, Y)) >? x(proper(X), proper(Y)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  s(ok(X)) >? ok(s(X)) 
  x(ok(X), ok(Y)) >? ok(x(X, Y)) 
  top(mark(X)) >? top(proper(X)) 
  top(ok(X)) >? top(active(X)) 

about to try horpo

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

Argument functions:

  [[active(x_1)]] = x_1 
  [[ok(x_1)]] = x_1 
  [[proper(x_1)]] = x_1 

We choose Lex = {} and Mul = {0, and, mark, plus, s, top, tt, x}, and the following precedence: 0 > and > top > tt > x > plus > mark > s

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

  and(tt, X) > mark(X) 
  plus(X, s(Y)) >= mark(s(plus(X, Y))) 
  x(X, 0) >= mark(0) 
  x(X, s(Y)) > mark(plus(x(X, Y), X)) 
  and(X, Y) >= and(X, Y) 
  plus(X, Y) >= plus(X, Y) 
  plus(X, Y) >= plus(X, Y) 
  s(X) >= s(X) 
  x(X, Y) >= x(X, Y) 
  x(X, Y) >= x(X, Y) 
  x(mark(X), Y) >= mark(x(X, Y)) 
  and(X, Y) >= and(X, Y) 
  tt >= tt 
  plus(X, Y) >= plus(X, Y) 
  0 >= 0 
  s(X) >= s(X) 
  x(X, Y) >= x(X, Y) 
  and(X, Y) >= and(X, Y) 
  plus(X, Y) >= plus(X, Y) 
  s(X) >= s(X) 
  x(X, Y) >= x(X, Y) 
  top(mark(X)) >= top(X) 
  top(X) >= top(X) 

With these choices, we have:

  1] and(tt, X) > mark(X)  because [2], by definition 
  2] and*(tt, X) >= mark(X)  because and > mark and [3], by (Copy) 
  3] and*(tt, X) >= X  because [4], by (Select) 
  4] X >= X  by (Meta) 

  5] plus(X, s(Y)) >= mark(s(plus(X, Y)))  because [6], by (Star) 
  6] plus*(X, s(Y)) >= mark(s(plus(X, Y)))  because plus > mark and [7], by (Copy) 
  7] plus*(X, s(Y)) >= s(plus(X, Y))  because plus > s and [8], by (Copy) 
  8] plus*(X, s(Y)) >= plus(X, Y)  because plus in Mul, [9] and [10], by (Stat) 
  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] x(X, 0) >= mark(0)  because [14], by (Star) 
  14] x*(X, 0) >= mark(0)  because x > mark and [15], by (Copy) 
  15] x*(X, 0) >= 0  because [16], by (Select) 
  16] 0 >= 0  by (Fun) 

  17] x(X, s(Y)) > mark(plus(x(X, Y), X))  because [18], by definition 
  18] x*(X, s(Y)) >= mark(plus(x(X, Y), X))  because x > mark and [19], by (Copy) 
  19] x*(X, s(Y)) >= plus(x(X, Y), X)  because x > plus, [20] and [21], by (Copy) 
  20] x*(X, s(Y)) >= x(X, Y)  because x in Mul, [9] and [10], by (Stat) 
  21] x*(X, s(Y)) >= X  because [9], by (Select) 

  22] and(X, Y) >= and(X, Y)  because and in Mul, [23] and [24], by (Fun) 
  23] X >= X  by (Meta) 
  24] Y >= Y  by (Meta) 

  25] plus(X, Y) >= plus(X, Y)  because plus in Mul, [23] and [24], by (Fun) 

  26] plus(X, Y) >= plus(X, Y)  because plus in Mul, [23] and [27], by (Fun) 
  27] Y >= Y  by (Meta) 

  28] s(X) >= s(X)  because s in Mul and [29], by (Fun) 
  29] X >= X  by (Meta) 

  30] x(X, Y) >= x(X, Y)  because x in Mul, [23] and [27], by (Fun) 

  31] x(X, Y) >= x(X, Y)  because x in Mul, [23] and [27], by (Fun) 

  32] x(mark(X), Y) >= mark(x(X, Y))  because [33], by (Star) 
  33] x*(mark(X), Y) >= mark(x(X, Y))  because x > mark and [34], by (Copy) 
  34] x*(mark(X), Y) >= x(X, Y)  because x in Mul, [35] and [27], by (Stat) 
  35] mark(X) > X  because [36], by definition 
  36] mark*(X) >= X  because [23], by (Select) 

  37] and(X, Y) >= and(X, Y)  because and in Mul, [38] and [39], by (Fun) 
  38] X >= X  by (Meta) 
  39] Y >= Y  by (Meta) 

  40] tt >= tt  by (Fun) 

  41] plus(X, Y) >= plus(X, Y)  because plus in Mul, [38] and [39], by (Fun) 

  42] 0 >= 0  by (Fun) 

  43] s(X) >= s(X)  because s in Mul and [44], by (Fun) 
  44] X >= X  by (Meta) 

  45] x(X, Y) >= x(X, Y)  because x in Mul, [38] and [39], by (Fun) 

  46] and(X, Y) >= and(X, Y)  because and in Mul, [47] and [48], by (Fun) 
  47] X >= X  by (Meta) 
  48] Y >= Y  by (Meta) 

  49] plus(X, Y) >= plus(X, Y)  because plus in Mul, [47] and [48], by (Fun) 

  50] s(X) >= s(X)  because s in Mul and [51], by (Fun) 
  51] X >= X  by (Meta) 

  52] x(X, Y) >= x(X, Y)  because x in Mul, [47] and [48], by (Fun) 

  53] top(mark(X)) >= top(X)  because top in Mul and [54], by (Fun) 
  54] mark(X) >= X  because [55], by (Star) 
  55] mark*(X) >= X  because [51], by (Select) 

  56] top(X) >= top(X)  because top in Mul and [57], by (Fun) 
  57] X >= X  by (Meta) 

We can thus remove the following rules:

  active(and(tt, X)) => mark(X) 
  active(x(X, s(Y))) => mark(plus(x(X, Y), X)) 

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

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

  active(plus(X, s(Y))) >? mark(s(plus(X, Y))) 
  active(x(X, 0)) >? mark(0) 
  active(and(X, Y)) >? and(active(X), Y) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  active(s(X)) >? s(active(X)) 
  active(x(X, Y)) >? x(active(X), Y) 
  active(x(X, Y)) >? x(X, active(Y)) 
  x(mark(X), Y) >? mark(x(X, Y)) 
  proper(and(X, Y)) >? and(proper(X), proper(Y)) 
  proper(tt) >? ok(tt) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  proper(0) >? ok(0) 
  proper(s(X)) >? s(proper(X)) 
  proper(x(X, Y)) >? x(proper(X), proper(Y)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  s(ok(X)) >? ok(s(X)) 
  x(ok(X), ok(Y)) >? ok(x(X, Y)) 
  top(mark(X)) >? top(proper(X)) 
  top(ok(X)) >? top(active(X)) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  active = \y0.y0 
  and = \y0y1.y1 + 2y0 
  mark = \y0.y0 
  ok = \y0.y0 
  plus = \y0y1.1 + 2y0 + 3y1 
  proper = \y0.y0 
  s = \y0.1 + y0 
  top = \y0.y0 
  tt = 0 
  x = \y0y1.y0 + y1 

Using this interpretation, the requirements translate to:

  [[active(plus(_x0, s(_x1)))]] = 4 + 2x0 + 3x1 > 2 + 2x0 + 3x1 = [[mark(s(plus(_x0, _x1)))]] 
  [[active(x(_x0, 0))]] = x0 >= 0 = [[mark(0)]] 
  [[active(and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(active(_x0), _x1)]] 
  [[active(plus(_x0, _x1))]] = 1 + 2x0 + 3x1 >= 1 + 2x0 + 3x1 = [[plus(active(_x0), _x1)]] 
  [[active(plus(_x0, _x1))]] = 1 + 2x0 + 3x1 >= 1 + 2x0 + 3x1 = [[plus(_x0, active(_x1))]] 
  [[active(s(_x0))]] = 1 + x0 >= 1 + x0 = [[s(active(_x0))]] 
  [[active(x(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[x(active(_x0), _x1)]] 
  [[active(x(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[x(_x0, active(_x1))]] 
  [[x(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[mark(x(_x0, _x1))]] 
  [[proper(and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(proper(_x0), proper(_x1))]] 
  [[proper(tt)]] = 0 >= 0 = [[ok(tt)]] 
  [[proper(plus(_x0, _x1))]] = 1 + 2x0 + 3x1 >= 1 + 2x0 + 3x1 = [[plus(proper(_x0), proper(_x1))]] 
  [[proper(0)]] = 0 >= 0 = [[ok(0)]] 
  [[proper(s(_x0))]] = 1 + x0 >= 1 + x0 = [[s(proper(_x0))]] 
  [[proper(x(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[x(proper(_x0), proper(_x1))]] 
  [[and(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(and(_x0, _x1))]] 
  [[plus(ok(_x0), ok(_x1))]] = 1 + 2x0 + 3x1 >= 1 + 2x0 + 3x1 = [[ok(plus(_x0, _x1))]] 
  [[s(ok(_x0))]] = 1 + x0 >= 1 + x0 = [[ok(s(_x0))]] 
  [[x(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(x(_x0, _x1))]] 
  [[top(mark(_x0))]] = x0 >= x0 = [[top(proper(_x0))]] 
  [[top(ok(_x0))]] = x0 >= x0 = [[top(active(_x0))]] 

We can thus remove the following rules:

  active(plus(X, s(Y))) => mark(s(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]):

  active(x(X, 0)) >? mark(0) 
  active(and(X, Y)) >? and(active(X), Y) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  active(s(X)) >? s(active(X)) 
  active(x(X, Y)) >? x(active(X), Y) 
  active(x(X, Y)) >? x(X, active(Y)) 
  x(mark(X), Y) >? mark(x(X, Y)) 
  proper(and(X, Y)) >? and(proper(X), proper(Y)) 
  proper(tt) >? ok(tt) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  proper(0) >? ok(0) 
  proper(s(X)) >? s(proper(X)) 
  proper(x(X, Y)) >? x(proper(X), proper(Y)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  s(ok(X)) >? ok(s(X)) 
  x(ok(X), ok(Y)) >? ok(x(X, Y)) 
  top(mark(X)) >? top(proper(X)) 
  top(ok(X)) >? top(active(X)) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  active = \y0.y0 
  and = \y0y1.y1 + 2y0 
  mark = \y0.y0 
  ok = \y0.y0 
  plus = \y0y1.2y0 + 2y1 
  proper = \y0.y0 
  s = \y0.2y0 
  top = \y0.2y0 
  tt = 0 
  x = \y0y1.1 + 2y0 + 2y1 

Using this interpretation, the requirements translate to:

  [[active(x(_x0, 0))]] = 1 + 2x0 > 0 = [[mark(0)]] 
  [[active(and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(active(_x0), _x1)]] 
  [[active(plus(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(active(_x0), _x1)]] 
  [[active(plus(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(_x0, active(_x1))]] 
  [[active(s(_x0))]] = 2x0 >= 2x0 = [[s(active(_x0))]] 
  [[active(x(_x0, _x1))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[x(active(_x0), _x1)]] 
  [[active(x(_x0, _x1))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[x(_x0, active(_x1))]] 
  [[x(mark(_x0), _x1)]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[mark(x(_x0, _x1))]] 
  [[proper(and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(proper(_x0), proper(_x1))]] 
  [[proper(tt)]] = 0 >= 0 = [[ok(tt)]] 
  [[proper(plus(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(proper(_x0), proper(_x1))]] 
  [[proper(0)]] = 0 >= 0 = [[ok(0)]] 
  [[proper(s(_x0))]] = 2x0 >= 2x0 = [[s(proper(_x0))]] 
  [[proper(x(_x0, _x1))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[x(proper(_x0), proper(_x1))]] 
  [[and(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(and(_x0, _x1))]] 
  [[plus(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(plus(_x0, _x1))]] 
  [[s(ok(_x0))]] = 2x0 >= 2x0 = [[ok(s(_x0))]] 
  [[x(ok(_x0), ok(_x1))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[ok(x(_x0, _x1))]] 
  [[top(mark(_x0))]] = 2x0 >= 2x0 = [[top(proper(_x0))]] 
  [[top(ok(_x0))]] = 2x0 >= 2x0 = [[top(active(_x0))]] 

We can thus remove the following rules:

  active(x(X, 0)) => mark(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]):

  active(and(X, Y)) >? and(active(X), Y) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  active(s(X)) >? s(active(X)) 
  active(x(X, Y)) >? x(active(X), Y) 
  active(x(X, Y)) >? x(X, active(Y)) 
  x(mark(X), Y) >? mark(x(X, Y)) 
  proper(and(X, Y)) >? and(proper(X), proper(Y)) 
  proper(tt) >? ok(tt) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  proper(0) >? ok(0) 
  proper(s(X)) >? s(proper(X)) 
  proper(x(X, Y)) >? x(proper(X), proper(Y)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  s(ok(X)) >? ok(s(X)) 
  x(ok(X), ok(Y)) >? ok(x(X, Y)) 
  top(mark(X)) >? top(proper(X)) 
  top(ok(X)) >? top(active(X)) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  active = \y0.y0 
  and = \y0y1.y1 + 2y0 
  mark = \y0.1 + y0 
  ok = \y0.2y0 
  plus = \y0y1.y0 + y1 
  proper = \y0.y0 
  s = \y0.2y0 
  top = \y0.y0 
  tt = 0 
  x = \y0y1.y1 + 2y0 

Using this interpretation, the requirements translate to:

  [[active(and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(active(_x0), _x1)]] 
  [[active(plus(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[plus(active(_x0), _x1)]] 
  [[active(plus(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[plus(_x0, active(_x1))]] 
  [[active(s(_x0))]] = 2x0 >= 2x0 = [[s(active(_x0))]] 
  [[active(x(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[x(active(_x0), _x1)]] 
  [[active(x(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[x(_x0, active(_x1))]] 
  [[x(mark(_x0), _x1)]] = 2 + x1 + 2x0 > 1 + x1 + 2x0 = [[mark(x(_x0, _x1))]] 
  [[proper(and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(proper(_x0), proper(_x1))]] 
  [[proper(tt)]] = 0 >= 0 = [[ok(tt)]] 
  [[proper(plus(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[plus(proper(_x0), proper(_x1))]] 
  [[proper(0)]] = 0 >= 0 = [[ok(0)]] 
  [[proper(s(_x0))]] = 2x0 >= 2x0 = [[s(proper(_x0))]] 
  [[proper(x(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[x(proper(_x0), proper(_x1))]] 
  [[and(ok(_x0), ok(_x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[ok(and(_x0, _x1))]] 
  [[plus(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(plus(_x0, _x1))]] 
  [[s(ok(_x0))]] = 4x0 >= 4x0 = [[ok(s(_x0))]] 
  [[x(ok(_x0), ok(_x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[ok(x(_x0, _x1))]] 
  [[top(mark(_x0))]] = 1 + x0 > x0 = [[top(proper(_x0))]] 
  [[top(ok(_x0))]] = 2x0 >= x0 = [[top(active(_x0))]] 

We can thus remove the following rules:

  x(mark(X), Y) => mark(x(X, Y)) 
  top(mark(X)) => top(proper(X)) 

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

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

  active(and(X, Y)) >? and(active(X), Y) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  active(s(X)) >? s(active(X)) 
  active(x(X, Y)) >? x(active(X), Y) 
  active(x(X, Y)) >? x(X, active(Y)) 
  proper(and(X, Y)) >? and(proper(X), proper(Y)) 
  proper(tt) >? ok(tt) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  proper(0) >? ok(0) 
  proper(s(X)) >? s(proper(X)) 
  proper(x(X, Y)) >? x(proper(X), proper(Y)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  s(ok(X)) >? ok(s(X)) 
  x(ok(X), ok(Y)) >? ok(x(X, Y)) 
  top(ok(X)) >? top(active(X)) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  active = \y0.y0 
  and = \y0y1.y0 + 2y1 
  ok = \y0.y0 
  plus = \y0y1.y0 + 2y1 
  proper = \y0.2y0 
  s = \y0.2y0 
  top = \y0.2y0 
  tt = 0 
  x = \y0y1.1 + y0 + y1 

Using this interpretation, the requirements translate to:

  [[active(and(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[and(active(_x0), _x1)]] 
  [[active(plus(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(active(_x0), _x1)]] 
  [[active(plus(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(_x0, active(_x1))]] 
  [[active(s(_x0))]] = 2x0 >= 2x0 = [[s(active(_x0))]] 
  [[active(x(_x0, _x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[x(active(_x0), _x1)]] 
  [[active(x(_x0, _x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[x(_x0, active(_x1))]] 
  [[proper(and(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[and(proper(_x0), proper(_x1))]] 
  [[proper(tt)]] = 0 >= 0 = [[ok(tt)]] 
  [[proper(plus(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[plus(proper(_x0), proper(_x1))]] 
  [[proper(0)]] = 0 >= 0 = [[ok(0)]] 
  [[proper(s(_x0))]] = 4x0 >= 4x0 = [[s(proper(_x0))]] 
  [[proper(x(_x0, _x1))]] = 2 + 2x0 + 2x1 > 1 + 2x0 + 2x1 = [[x(proper(_x0), proper(_x1))]] 
  [[and(ok(_x0), ok(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[ok(and(_x0, _x1))]] 
  [[plus(ok(_x0), ok(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[ok(plus(_x0, _x1))]] 
  [[s(ok(_x0))]] = 2x0 >= 2x0 = [[ok(s(_x0))]] 
  [[x(ok(_x0), ok(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[ok(x(_x0, _x1))]] 
  [[top(ok(_x0))]] = 2x0 >= 2x0 = [[top(active(_x0))]] 

We can thus remove the following rules:

  proper(x(X, Y)) => x(proper(X), proper(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]):

  active(and(X, Y)) >? and(active(X), Y) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  active(s(X)) >? s(active(X)) 
  active(x(X, Y)) >? x(active(X), Y) 
  active(x(X, Y)) >? x(X, active(Y)) 
  proper(and(X, Y)) >? and(proper(X), proper(Y)) 
  proper(tt) >? ok(tt) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  proper(0) >? ok(0) 
  proper(s(X)) >? s(proper(X)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  s(ok(X)) >? ok(s(X)) 
  x(ok(X), ok(Y)) >? ok(x(X, Y)) 
  top(ok(X)) >? top(active(X)) 

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

The following interpretation satisfies the requirements:

  0 = 2 
  active = \y0.y0 
  and = \y0y1.y0 + y1 
  ok = \y0.y0 
  plus = \y0y1.y1 + 2y0 
  proper = \y0.2y0 
  s = \y0.2y0 
  top = \y0.2y0 
  tt = 0 
  x = \y0y1.y0 + y1 

Using this interpretation, the requirements translate to:

  [[active(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[and(active(_x0), _x1)]] 
  [[active(plus(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[plus(active(_x0), _x1)]] 
  [[active(plus(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[plus(_x0, active(_x1))]] 
  [[active(s(_x0))]] = 2x0 >= 2x0 = [[s(active(_x0))]] 
  [[active(x(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[x(active(_x0), _x1)]] 
  [[active(x(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[x(_x0, active(_x1))]] 
  [[proper(and(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[and(proper(_x0), proper(_x1))]] 
  [[proper(tt)]] = 0 >= 0 = [[ok(tt)]] 
  [[proper(plus(_x0, _x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[plus(proper(_x0), proper(_x1))]] 
  [[proper(0)]] = 4 > 2 = [[ok(0)]] 
  [[proper(s(_x0))]] = 4x0 >= 4x0 = [[s(proper(_x0))]] 
  [[and(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(and(_x0, _x1))]] 
  [[plus(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(plus(_x0, _x1))]] 
  [[s(ok(_x0))]] = 2x0 >= 2x0 = [[ok(s(_x0))]] 
  [[x(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(x(_x0, _x1))]] 
  [[top(ok(_x0))]] = 2x0 >= 2x0 = [[top(active(_x0))]] 

We can thus remove the following rules:

  proper(0) => ok(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]):

  active(and(X, Y)) >? and(active(X), Y) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  active(s(X)) >? s(active(X)) 
  active(x(X, Y)) >? x(active(X), Y) 
  active(x(X, Y)) >? x(X, active(Y)) 
  proper(and(X, Y)) >? and(proper(X), proper(Y)) 
  proper(tt) >? ok(tt) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  proper(s(X)) >? s(proper(X)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  s(ok(X)) >? ok(s(X)) 
  x(ok(X), ok(Y)) >? ok(x(X, Y)) 
  top(ok(X)) >? top(active(X)) 

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

The following interpretation satisfies the requirements:

  active = \y0.2 + 2y0 
  and = \y0y1.3 + y1 + 2y0 
  ok = \y0.3 + 3y0 
  plus = \y0y1.3 + y0 + 2y1 
  proper = \y0.3 + 3y0 
  s = \y0.y0 
  top = \y0.3y0 
  tt = 0 
  x = \y0y1.3 + 2y0 + 2y1 

Using this interpretation, the requirements translate to:

  [[active(and(_x0, _x1))]] = 8 + 2x1 + 4x0 > 7 + x1 + 4x0 = [[and(active(_x0), _x1)]] 
  [[active(plus(_x0, _x1))]] = 8 + 2x0 + 4x1 > 5 + 2x0 + 2x1 = [[plus(active(_x0), _x1)]] 
  [[active(plus(_x0, _x1))]] = 8 + 2x0 + 4x1 > 7 + x0 + 4x1 = [[plus(_x0, active(_x1))]] 
  [[active(s(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[s(active(_x0))]] 
  [[active(x(_x0, _x1))]] = 8 + 4x0 + 4x1 > 7 + 2x1 + 4x0 = [[x(active(_x0), _x1)]] 
  [[active(x(_x0, _x1))]] = 8 + 4x0 + 4x1 > 7 + 2x0 + 4x1 = [[x(_x0, active(_x1))]] 
  [[proper(and(_x0, _x1))]] = 12 + 3x1 + 6x0 >= 12 + 3x1 + 6x0 = [[and(proper(_x0), proper(_x1))]] 
  [[proper(tt)]] = 3 >= 3 = [[ok(tt)]] 
  [[proper(plus(_x0, _x1))]] = 12 + 3x0 + 6x1 >= 12 + 3x0 + 6x1 = [[plus(proper(_x0), proper(_x1))]] 
  [[proper(s(_x0))]] = 3 + 3x0 >= 3 + 3x0 = [[s(proper(_x0))]] 
  [[and(ok(_x0), ok(_x1))]] = 12 + 3x1 + 6x0 >= 12 + 3x1 + 6x0 = [[ok(and(_x0, _x1))]] 
  [[plus(ok(_x0), ok(_x1))]] = 12 + 3x0 + 6x1 >= 12 + 3x0 + 6x1 = [[ok(plus(_x0, _x1))]] 
  [[s(ok(_x0))]] = 3 + 3x0 >= 3 + 3x0 = [[ok(s(_x0))]] 
  [[x(ok(_x0), ok(_x1))]] = 15 + 6x0 + 6x1 > 12 + 6x0 + 6x1 = [[ok(x(_x0, _x1))]] 
  [[top(ok(_x0))]] = 9 + 9x0 > 6 + 6x0 = [[top(active(_x0))]] 

We can thus remove the following rules:

  active(and(X, Y)) => and(active(X), Y) 
  active(plus(X, Y)) => plus(active(X), Y) 
  active(plus(X, Y)) => plus(X, active(Y)) 
  active(x(X, Y)) => x(active(X), Y) 
  active(x(X, Y)) => x(X, active(Y)) 
  x(ok(X), ok(Y)) => ok(x(X, Y)) 
  top(ok(X)) => top(active(X)) 

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

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

  active(s(X)) >? s(active(X)) 
  proper(and(X, Y)) >? and(proper(X), proper(Y)) 
  proper(tt) >? ok(tt) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  proper(s(X)) >? s(proper(X)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  s(ok(X)) >? ok(s(X)) 

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

The following interpretation satisfies the requirements:

  active = \y0.2 + 3y0 
  and = \y0y1.3 + y1 + 2y0 
  ok = \y0.1 + y0 
  plus = \y0y1.3 + y1 + 2y0 
  proper = \y0.2 + 3y0 
  s = \y0.3 + 2y0 
  tt = 3 

Using this interpretation, the requirements translate to:

  [[active(s(_x0))]] = 11 + 6x0 > 7 + 6x0 = [[s(active(_x0))]] 
  [[proper(and(_x0, _x1))]] = 11 + 3x1 + 6x0 > 9 + 3x1 + 6x0 = [[and(proper(_x0), proper(_x1))]] 
  [[proper(tt)]] = 11 > 4 = [[ok(tt)]] 
  [[proper(plus(_x0, _x1))]] = 11 + 3x1 + 6x0 > 9 + 3x1 + 6x0 = [[plus(proper(_x0), proper(_x1))]] 
  [[proper(s(_x0))]] = 11 + 6x0 > 7 + 6x0 = [[s(proper(_x0))]] 
  [[and(ok(_x0), ok(_x1))]] = 6 + x1 + 2x0 > 4 + x1 + 2x0 = [[ok(and(_x0, _x1))]] 
  [[plus(ok(_x0), ok(_x1))]] = 6 + x1 + 2x0 > 4 + x1 + 2x0 = [[ok(plus(_x0, _x1))]] 
  [[s(ok(_x0))]] = 5 + 2x0 > 4 + 2x0 = [[ok(s(_x0))]] 

We can thus remove the following rules:

  active(s(X)) => s(active(X)) 
  proper(and(X, Y)) => and(proper(X), proper(Y)) 
  proper(tt) => ok(tt) 
  proper(plus(X, Y)) => plus(proper(X), proper(Y)) 
  proper(s(X)) => s(proper(X)) 
  and(ok(X), ok(Y)) => ok(and(X, Y)) 
  plus(ok(X), ok(Y)) => ok(plus(X, Y)) 
  s(ok(X)) => ok(s(X)) 

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.