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

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

  active(U11(tt, X)) => mark(X) 
  active(U21(tt, X, Y)) => mark(s(plus(Y, X))) 
  active(and(tt, X)) => mark(X) 
  active(isNat(0)) => mark(tt) 
  active(isNat(plus(X, Y))) => mark(and(isNat(X), isNat(Y))) 
  active(isNat(s(X))) => mark(isNat(X)) 
  active(plus(X, 0)) => mark(U11(isNat(X), X)) 
  active(plus(X, s(Y))) => mark(U21(and(isNat(Y), isNat(X)), Y, X)) 
  active(U11(X, Y)) => U11(active(X), Y) 
  active(U21(X, Y, Z)) => U21(active(X), Y, Z) 
  active(s(X)) => s(active(X)) 
  active(plus(X, Y)) => plus(active(X), Y) 
  active(plus(X, Y)) => plus(X, active(Y)) 
  active(and(X, Y)) => and(active(X), Y) 
  U11(mark(X), Y) => mark(U11(X, Y)) 
  U21(mark(X), Y, Z) => mark(U21(X, Y, Z)) 
  s(mark(X)) => mark(s(X)) 
  plus(mark(X), Y) => mark(plus(X, Y)) 
  plus(X, mark(Y)) => mark(plus(X, Y)) 
  and(mark(X), Y) => mark(and(X, Y)) 
  proper(U11(X, Y)) => U11(proper(X), proper(Y)) 
  proper(tt) => ok(tt) 
  proper(U21(X, Y, Z)) => U21(proper(X), proper(Y), proper(Z)) 
  proper(s(X)) => s(proper(X)) 
  proper(plus(X, Y)) => plus(proper(X), proper(Y)) 
  proper(and(X, Y)) => and(proper(X), proper(Y)) 
  proper(isNat(X)) => isNat(proper(X)) 
  proper(0) => ok(0) 
  U11(ok(X), ok(Y)) => ok(U11(X, Y)) 
  U21(ok(X), ok(Y), ok(Z)) => ok(U21(X, Y, Z)) 
  s(ok(X)) => ok(s(X)) 
  plus(ok(X), ok(Y)) => ok(plus(X, Y)) 
  and(ok(X), ok(Y)) => ok(and(X, Y)) 
  isNat(ok(X)) => ok(isNat(X)) 
  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(U11(tt, X)) >? mark(X) 
  active(U21(tt, X, Y)) >? mark(s(plus(Y, X))) 
  active(and(tt, X)) >? mark(X) 
  active(isNat(0)) >? mark(tt) 
  active(isNat(plus(X, Y))) >? mark(and(isNat(X), isNat(Y))) 
  active(isNat(s(X))) >? mark(isNat(X)) 
  active(plus(X, 0)) >? mark(U11(isNat(X), X)) 
  active(plus(X, s(Y))) >? mark(U21(and(isNat(Y), isNat(X)), Y, X)) 
  active(U11(X, Y)) >? U11(active(X), Y) 
  active(U21(X, Y, Z)) >? U21(active(X), Y, Z) 
  active(s(X)) >? s(active(X)) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  active(and(X, Y)) >? and(active(X), Y) 
  U11(mark(X), Y) >? mark(U11(X, Y)) 
  U21(mark(X), Y, Z) >? mark(U21(X, Y, Z)) 
  s(mark(X)) >? mark(s(X)) 
  plus(mark(X), Y) >? mark(plus(X, Y)) 
  plus(X, mark(Y)) >? mark(plus(X, Y)) 
  and(mark(X), Y) >? mark(and(X, Y)) 
  proper(U11(X, Y)) >? U11(proper(X), proper(Y)) 
  proper(tt) >? ok(tt) 
  proper(U21(X, Y, Z)) >? U21(proper(X), proper(Y), proper(Z)) 
  proper(s(X)) >? s(proper(X)) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  proper(and(X, Y)) >? and(proper(X), proper(Y)) 
  proper(isNat(X)) >? isNat(proper(X)) 
  proper(0) >? ok(0) 
  U11(ok(X), ok(Y)) >? ok(U11(X, Y)) 
  U21(ok(X), ok(Y), ok(Z)) >? ok(U21(X, Y, Z)) 
  s(ok(X)) >? ok(s(X)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  isNat(ok(X)) >? ok(isNat(X)) 
  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:

  [[U21(x_1, x_2, x_3)]] = U21(x_3, x_2, x_1) 
  [[active(x_1)]] = x_1 
  [[isNat(x_1)]] = x_1 
  [[ok(x_1)]] = x_1 
  [[proper(x_1)]] = x_1 
  [[tt]] = _|_ 

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

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

  U11(_|_, X) > mark(X) 
  U21(_|_, X, Y) >= mark(s(plus(Y, X))) 
  and(_|_, X) > mark(X) 
  0 >= mark(_|_) 
  plus(X, Y) > mark(and(X, Y)) 
  s(X) > mark(X) 
  plus(X, 0) > mark(U11(X, X)) 
  plus(X, s(Y)) > mark(U21(and(Y, X), Y, X)) 
  U11(X, Y) >= U11(X, Y) 
  U21(X, Y, Z) >= U21(X, Y, Z) 
  s(X) >= s(X) 
  plus(X, Y) >= plus(X, Y) 
  plus(X, Y) >= plus(X, Y) 
  and(X, Y) >= and(X, Y) 
  U11(mark(X), Y) > mark(U11(X, Y)) 
  U21(mark(X), Y, Z) > mark(U21(X, Y, Z)) 
  s(mark(X)) > mark(s(X)) 
  plus(mark(X), Y) >= mark(plus(X, Y)) 
  plus(X, mark(Y)) >= mark(plus(X, Y)) 
  and(mark(X), Y) >= mark(and(X, Y)) 
  U11(X, Y) >= U11(X, Y) 
  _|_ >= _|_ 
  U21(X, Y, Z) >= U21(X, Y, Z) 
  s(X) >= s(X) 
  plus(X, Y) >= plus(X, Y) 
  and(X, Y) >= and(X, Y) 
  X >= X 
  0 >= 0 
  U11(X, Y) >= U11(X, Y) 
  U21(X, Y, Z) >= U21(X, Y, Z) 
  s(X) >= s(X) 
  plus(X, Y) >= plus(X, Y) 
  and(X, Y) >= and(X, Y) 
  X >= X 
  top(mark(X)) >= top(X) 
  top(X) >= top(X) 

With these choices, we have:

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

  5] U21(_|_, X, Y) >= mark(s(plus(Y, X)))  because [6], by (Star) 
  6] U21*(_|_, X, Y) >= mark(s(plus(Y, X)))  because U21 > mark and [7], by (Copy) 
  7] U21*(_|_, X, Y) >= s(plus(Y, X))  because U21 > s and [8], by (Copy) 
  8] U21*(_|_, X, Y) >= plus(Y, X)  because U21 = plus, [9], [10], [11] and [12], by (Stat) 
  9] X >= X  by (Meta) 
  10] Y >= Y  by (Meta) 
  11] U21*(_|_, X, Y) >= Y  because [10], by (Select) 
  12] U21*(_|_, X, Y) >= X  because [9], by (Select) 

  13] and(_|_, X) > mark(X)  because [14], by definition 
  14] and*(_|_, X) >= mark(X)  because and > mark and [15], by (Copy) 
  15] and*(_|_, X) >= X  because [16], by (Select) 
  16] X >= X  by (Meta) 

  17] 0 >= mark(_|_)  because [18], by (Star) 
  18] 0* >= mark(_|_)  because 0 > mark and [19], by (Copy) 
  19] 0* >= _|_  by (Bot) 

  20] plus(X, Y) > mark(and(X, Y))  because [21], by definition 
  21] plus*(X, Y) >= mark(and(X, Y))  because plus > mark and [22], by (Copy) 
  22] plus*(X, Y) >= and(X, Y)  because plus > and, [23] and [25], by (Copy) 
  23] plus*(X, Y) >= X  because [24], by (Select) 
  24] X >= X  by (Meta) 
  25] plus*(X, Y) >= Y  because [26], by (Select) 
  26] Y >= Y  by (Meta) 

  27] s(X) > mark(X)  because [28], by definition 
  28] s*(X) >= mark(X)  because s > mark and [29], by (Copy) 
  29] s*(X) >= X  because [24], by (Select) 

  30] plus(X, 0) > mark(U11(X, X))  because [31], by definition 
  31] plus*(X, 0) >= mark(U11(X, X))  because plus > mark and [32], by (Copy) 
  32] plus*(X, 0) >= U11(X, X)  because plus > U11, [33] and [33], by (Copy) 
  33] plus*(X, 0) >= X  because [10], by (Select) 

  34] plus(X, s(Y)) > mark(U21(and(Y, X), Y, X))  because [35], by definition 
  35] plus*(X, s(Y)) >= mark(U21(and(Y, X), Y, X))  because plus > mark and [36], by (Copy) 
  36] plus*(X, s(Y)) >= U21(and(Y, X), Y, X)  because plus = U21, [10], [37], [39], [40] and [42], by (Stat) 
  37] s(Y) > Y  because [38], by definition 
  38] s*(Y) >= Y  because [9], by (Select) 
  39] plus*(X, s(Y)) >= and(Y, X)  because plus > and, [40] and [42], by (Copy) 
  40] plus*(X, s(Y)) >= Y  because [41], by (Select) 
  41] s(Y) >= Y  because [38], by (Star) 
  42] plus*(X, s(Y)) >= X  because [10], by (Select) 

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

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

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

  50] plus(X, Y) >= plus(X, Y)  because [44] and [45], by (Fun) 

  51] plus(X, Y) >= plus(X, Y)  because [44] and [52], by (Fun) 
  52] Y >= Y  by (Meta) 

  53] and(X, Y) >= and(X, Y)  because and in Mul, [44] and [52], by (Fun) 

  54] U11(mark(X), Y) > mark(U11(X, Y))  because [55], by definition 
  55] U11*(mark(X), Y) >= mark(U11(X, Y))  because U11 > mark and [56], by (Copy) 
  56] U11*(mark(X), Y) >= U11(X, Y)  because U11 in Mul, [57] and [52], by (Stat) 
  57] mark(X) > X  because [58], by definition 
  58] mark*(X) >= X  because [44], by (Select) 

  59] U21(mark(X), Y, Z) > mark(U21(X, Y, Z))  because [60], by definition 
  60] U21*(mark(X), Y, Z) >= mark(U21(X, Y, Z))  because U21 > mark and [61], by (Copy) 
  61] U21*(mark(X), Y, Z) >= U21(X, Y, Z)  because [57], [52], [47], [62], [64] and [65], by (Stat) 
  62] U21*(mark(X), Y, Z) >= X  because [63], by (Select) 
  63] mark(X) >= X  because [58], by (Star) 
  64] U21*(mark(X), Y, Z) >= Y  because [52], by (Select) 
  65] U21*(mark(X), Y, Z) >= Z  because [47], by (Select) 

  66] s(mark(X)) > mark(s(X))  because [67], by definition 
  67] s*(mark(X)) >= mark(s(X))  because s > mark and [68], by (Copy) 
  68] s*(mark(X)) >= s(X)  because s in Mul and [69], by (Stat) 
  69] mark(X) > X  because [70], by definition 
  70] mark*(X) >= X  because [49], by (Select) 

  71] plus(mark(X), Y) >= mark(plus(X, Y))  because [72], by (Star) 
  72] plus*(mark(X), Y) >= mark(plus(X, Y))  because plus > mark and [73], by (Copy) 
  73] plus*(mark(X), Y) >= plus(X, Y)  because [57], [74] and [75], by (Stat) 
  74] plus*(mark(X), Y) >= X  because [63], by (Select) 
  75] plus*(mark(X), Y) >= Y  because [52], by (Select) 

  76] plus(X, mark(Y)) >= mark(plus(X, Y))  because [77], by (Star) 
  77] plus*(X, mark(Y)) >= mark(plus(X, Y))  because plus > mark and [78], by (Copy) 
  78] plus*(X, mark(Y)) >= plus(X, Y)  because [44], [79], [81] and [82], by (Stat) 
  79] mark(Y) > Y  because [80], by definition 
  80] mark*(Y) >= Y  because [52], by (Select) 
  81] plus*(X, mark(Y)) >= X  because [44], by (Select) 
  82] plus*(X, mark(Y)) >= Y  because [83], by (Select) 
  83] mark(Y) >= Y  because [80], by (Star) 

  84] and(mark(X), Y) >= mark(and(X, Y))  because [85], by (Star) 
  85] and*(mark(X), Y) >= mark(and(X, Y))  because and > mark and [86], by (Copy) 
  86] and*(mark(X), Y) >= and(X, Y)  because and in Mul, [57] and [52], by (Stat) 

  87] U11(X, Y) >= U11(X, Y)  because U11 in Mul, [88] and [89], by (Fun) 
  88] X >= X  by (Meta) 
  89] Y >= Y  by (Meta) 

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

  91] U21(X, Y, Z) >= U21(X, Y, Z)  because [88], [89] and [92], by (Fun) 
  92] Z >= Z  by (Meta) 

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

  95] plus(X, Y) >= plus(X, Y)  because [88] and [89], by (Fun) 

  96] and(X, Y) >= and(X, Y)  because and in Mul, [88] and [89], by (Fun) 

  97] X >= X  by (Meta) 

  98] 0 >= 0  by (Fun) 

  99] U11(X, Y) >= U11(X, Y)  because U11 in Mul, [100] and [101], by (Fun) 
  100] X >= X  by (Meta) 
  101] Y >= Y  by (Meta) 

  102] U21(X, Y, Z) >= U21(X, Y, Z)  because [100], [101] and [103], by (Fun) 
  103] Z >= Z  by (Meta) 

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

  106] plus(X, Y) >= plus(X, Y)  because [100] and [101], by (Fun) 

  107] and(X, Y) >= and(X, Y)  because and in Mul, [100] and [101], by (Fun) 

  108] X >= X  by (Meta) 

  109] top(mark(X)) >= top(X)  because top in Mul and [110], by (Fun) 
  110] mark(X) >= X  because [70], by (Star) 

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

We can thus remove the following rules:

  active(U11(tt, X)) => mark(X) 
  active(and(tt, X)) => mark(X) 
  active(isNat(plus(X, Y))) => mark(and(isNat(X), isNat(Y))) 
  active(isNat(s(X))) => mark(isNat(X)) 
  active(plus(X, 0)) => mark(U11(isNat(X), X)) 
  active(plus(X, s(Y))) => mark(U21(and(isNat(Y), isNat(X)), Y, X)) 
  U11(mark(X), Y) => mark(U11(X, Y)) 
  U21(mark(X), Y, Z) => mark(U21(X, Y, Z)) 
  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(U21(tt, X, Y)) >? mark(s(plus(Y, X))) 
  active(isNat(0)) >? mark(tt) 
  active(U11(X, Y)) >? U11(active(X), Y) 
  active(U21(X, Y, Z)) >? U21(active(X), Y, Z) 
  active(s(X)) >? s(active(X)) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  active(and(X, Y)) >? and(active(X), Y) 
  plus(mark(X), Y) >? mark(plus(X, Y)) 
  plus(X, mark(Y)) >? mark(plus(X, Y)) 
  and(mark(X), Y) >? mark(and(X, Y)) 
  proper(U11(X, Y)) >? U11(proper(X), proper(Y)) 
  proper(tt) >? ok(tt) 
  proper(U21(X, Y, Z)) >? U21(proper(X), proper(Y), proper(Z)) 
  proper(s(X)) >? s(proper(X)) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  proper(and(X, Y)) >? and(proper(X), proper(Y)) 
  proper(isNat(X)) >? isNat(proper(X)) 
  proper(0) >? ok(0) 
  U11(ok(X), ok(Y)) >? ok(U11(X, Y)) 
  U21(ok(X), ok(Y), ok(Z)) >? ok(U21(X, Y, Z)) 
  s(ok(X)) >? ok(s(X)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  isNat(ok(X)) >? ok(isNat(X)) 
  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 
  U11 = \y0y1.y0 + 2y1 
  U21 = \y0y1y2.2 + 2y0 + 2y1 + 2y2 
  active = \y0.y0 
  and = \y0y1.y0 + y1 
  isNat = \y0.1 + 2y0 
  mark = \y0.y0 
  ok = \y0.y0 
  plus = \y0y1.y0 + y1 
  proper = \y0.y0 
  s = \y0.2y0 
  top = \y0.y0 
  tt = 0 

Using this interpretation, the requirements translate to:

  [[active(U21(tt, _x0, _x1))]] = 2 + 2x0 + 2x1 > 2x0 + 2x1 = [[mark(s(plus(_x1, _x0)))]] 
  [[active(isNat(0))]] = 1 > 0 = [[mark(tt)]] 
  [[active(U11(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U11(active(_x0), _x1)]] 
  [[active(U21(_x0, _x1, _x2))]] = 2 + 2x0 + 2x1 + 2x2 >= 2 + 2x0 + 2x1 + 2x2 = [[U21(active(_x0), _x1, _x2)]] 
  [[active(s(_x0))]] = 2x0 >= 2x0 = [[s(active(_x0))]] 
  [[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(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[and(active(_x0), _x1)]] 
  [[plus(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[mark(plus(_x0, _x1))]] 
  [[plus(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[mark(plus(_x0, _x1))]] 
  [[and(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[mark(and(_x0, _x1))]] 
  [[proper(U11(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U11(proper(_x0), proper(_x1))]] 
  [[proper(tt)]] = 0 >= 0 = [[ok(tt)]] 
  [[proper(U21(_x0, _x1, _x2))]] = 2 + 2x0 + 2x1 + 2x2 >= 2 + 2x0 + 2x1 + 2x2 = [[U21(proper(_x0), proper(_x1), proper(_x2))]] 
  [[proper(s(_x0))]] = 2x0 >= 2x0 = [[s(proper(_x0))]] 
  [[proper(plus(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[plus(proper(_x0), proper(_x1))]] 
  [[proper(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[and(proper(_x0), proper(_x1))]] 
  [[proper(isNat(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[isNat(proper(_x0))]] 
  [[proper(0)]] = 0 >= 0 = [[ok(0)]] 
  [[U11(ok(_x0), ok(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[ok(U11(_x0, _x1))]] 
  [[U21(ok(_x0), ok(_x1), ok(_x2))]] = 2 + 2x0 + 2x1 + 2x2 >= 2 + 2x0 + 2x1 + 2x2 = [[ok(U21(_x0, _x1, _x2))]] 
  [[s(ok(_x0))]] = 2x0 >= 2x0 = [[ok(s(_x0))]] 
  [[plus(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(plus(_x0, _x1))]] 
  [[and(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(and(_x0, _x1))]] 
  [[isNat(ok(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[ok(isNat(_x0))]] 
  [[top(mark(_x0))]] = x0 >= x0 = [[top(proper(_x0))]] 
  [[top(ok(_x0))]] = x0 >= x0 = [[top(active(_x0))]] 

We can thus remove the following rules:

  active(U21(tt, X, Y)) => mark(s(plus(Y, X))) 
  active(isNat(0)) => mark(tt) 

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(U11(X, Y)) >? U11(active(X), Y) 
  active(U21(X, Y, Z)) >? U21(active(X), Y, Z) 
  active(s(X)) >? s(active(X)) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  active(and(X, Y)) >? and(active(X), Y) 
  plus(mark(X), Y) >? mark(plus(X, Y)) 
  plus(X, mark(Y)) >? mark(plus(X, Y)) 
  and(mark(X), Y) >? mark(and(X, Y)) 
  proper(U11(X, Y)) >? U11(proper(X), proper(Y)) 
  proper(tt) >? ok(tt) 
  proper(U21(X, Y, Z)) >? U21(proper(X), proper(Y), proper(Z)) 
  proper(s(X)) >? s(proper(X)) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  proper(and(X, Y)) >? and(proper(X), proper(Y)) 
  proper(isNat(X)) >? isNat(proper(X)) 
  proper(0) >? ok(0) 
  U11(ok(X), ok(Y)) >? ok(U11(X, Y)) 
  U21(ok(X), ok(Y), ok(Z)) >? ok(U21(X, Y, Z)) 
  s(ok(X)) >? ok(s(X)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  isNat(ok(X)) >? ok(isNat(X)) 
  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 
  U11 = \y0y1.y0 + y1 
  U21 = \y0y1y2.y0 + y1 + y2 
  active = \y0.y0 
  and = \y0y1.y1 + 2y0 
  isNat = \y0.y0 
  mark = \y0.2 + y0 
  ok = \y0.2y0 
  plus = \y0y1.y0 + 2y1 
  proper = \y0.y0 
  s = \y0.y0 
  top = \y0.2y0 
  tt = 0 

Using this interpretation, the requirements translate to:

  [[active(U11(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U11(active(_x0), _x1)]] 
  [[active(U21(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U21(active(_x0), _x1, _x2)]] 
  [[active(s(_x0))]] = x0 >= x0 = [[s(active(_x0))]] 
  [[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(and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(active(_x0), _x1)]] 
  [[plus(mark(_x0), _x1)]] = 2 + x0 + 2x1 >= 2 + x0 + 2x1 = [[mark(plus(_x0, _x1))]] 
  [[plus(_x0, mark(_x1))]] = 4 + x0 + 2x1 > 2 + x0 + 2x1 = [[mark(plus(_x0, _x1))]] 
  [[and(mark(_x0), _x1)]] = 4 + x1 + 2x0 > 2 + x1 + 2x0 = [[mark(and(_x0, _x1))]] 
  [[proper(U11(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U11(proper(_x0), proper(_x1))]] 
  [[proper(tt)]] = 0 >= 0 = [[ok(tt)]] 
  [[proper(U21(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U21(proper(_x0), proper(_x1), proper(_x2))]] 
  [[proper(s(_x0))]] = x0 >= x0 = [[s(proper(_x0))]] 
  [[proper(plus(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(proper(_x0), proper(_x1))]] 
  [[proper(and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(proper(_x0), proper(_x1))]] 
  [[proper(isNat(_x0))]] = x0 >= x0 = [[isNat(proper(_x0))]] 
  [[proper(0)]] = 0 >= 0 = [[ok(0)]] 
  [[U11(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(U11(_x0, _x1))]] 
  [[U21(ok(_x0), ok(_x1), ok(_x2))]] = 2x0 + 2x1 + 2x2 >= 2x0 + 2x1 + 2x2 = [[ok(U21(_x0, _x1, _x2))]] 
  [[s(ok(_x0))]] = 2x0 >= 2x0 = [[ok(s(_x0))]] 
  [[plus(ok(_x0), ok(_x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[ok(plus(_x0, _x1))]] 
  [[and(ok(_x0), ok(_x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[ok(and(_x0, _x1))]] 
  [[isNat(ok(_x0))]] = 2x0 >= 2x0 = [[ok(isNat(_x0))]] 
  [[top(mark(_x0))]] = 4 + 2x0 > 2x0 = [[top(proper(_x0))]] 
  [[top(ok(_x0))]] = 4x0 >= 2x0 = [[top(active(_x0))]] 

We can thus remove the following rules:

  plus(X, mark(Y)) => mark(plus(X, Y)) 
  and(mark(X), Y) => mark(and(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(U11(X, Y)) >? U11(active(X), Y) 
  active(U21(X, Y, Z)) >? U21(active(X), Y, Z) 
  active(s(X)) >? s(active(X)) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  active(and(X, Y)) >? and(active(X), Y) 
  plus(mark(X), Y) >? mark(plus(X, Y)) 
  proper(U11(X, Y)) >? U11(proper(X), proper(Y)) 
  proper(tt) >? ok(tt) 
  proper(U21(X, Y, Z)) >? U21(proper(X), proper(Y), proper(Z)) 
  proper(s(X)) >? s(proper(X)) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  proper(and(X, Y)) >? and(proper(X), proper(Y)) 
  proper(isNat(X)) >? isNat(proper(X)) 
  proper(0) >? ok(0) 
  U11(ok(X), ok(Y)) >? ok(U11(X, Y)) 
  U21(ok(X), ok(Y), ok(Z)) >? ok(U21(X, Y, Z)) 
  s(ok(X)) >? ok(s(X)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  isNat(ok(X)) >? ok(isNat(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 
  U11 = \y0y1.y1 + 2y0 
  U21 = \y0y1y2.y0 + y1 + 2y2 
  active = \y0.y0 
  and = \y0y1.1 + y1 + 2y0 
  isNat = \y0.1 + 2y0 
  mark = \y0.y0 
  ok = \y0.y0 
  plus = \y0y1.y0 + 2y1 
  proper = \y0.3y0 
  s = \y0.2y0 
  top = \y0.2y0 
  tt = 3 

Using this interpretation, the requirements translate to:

  [[active(U11(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U11(active(_x0), _x1)]] 
  [[active(U21(_x0, _x1, _x2))]] = x0 + x1 + 2x2 >= x0 + x1 + 2x2 = [[U21(active(_x0), _x1, _x2)]] 
  [[active(s(_x0))]] = 2x0 >= 2x0 = [[s(active(_x0))]] 
  [[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(and(_x0, _x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[and(active(_x0), _x1)]] 
  [[plus(mark(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[mark(plus(_x0, _x1))]] 
  [[proper(U11(_x0, _x1))]] = 3x1 + 6x0 >= 3x1 + 6x0 = [[U11(proper(_x0), proper(_x1))]] 
  [[proper(tt)]] = 9 > 3 = [[ok(tt)]] 
  [[proper(U21(_x0, _x1, _x2))]] = 3x0 + 3x1 + 6x2 >= 3x0 + 3x1 + 6x2 = [[U21(proper(_x0), proper(_x1), proper(_x2))]] 
  [[proper(s(_x0))]] = 6x0 >= 6x0 = [[s(proper(_x0))]] 
  [[proper(plus(_x0, _x1))]] = 3x0 + 6x1 >= 3x0 + 6x1 = [[plus(proper(_x0), proper(_x1))]] 
  [[proper(and(_x0, _x1))]] = 3 + 3x1 + 6x0 > 1 + 3x1 + 6x0 = [[and(proper(_x0), proper(_x1))]] 
  [[proper(isNat(_x0))]] = 3 + 6x0 > 1 + 6x0 = [[isNat(proper(_x0))]] 
  [[proper(0)]] = 0 >= 0 = [[ok(0)]] 
  [[U11(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U11(_x0, _x1))]] 
  [[U21(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + 2x2 >= x0 + x1 + 2x2 = [[ok(U21(_x0, _x1, _x2))]] 
  [[s(ok(_x0))]] = 2x0 >= 2x0 = [[ok(s(_x0))]] 
  [[plus(ok(_x0), ok(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[ok(plus(_x0, _x1))]] 
  [[and(ok(_x0), ok(_x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[ok(and(_x0, _x1))]] 
  [[isNat(ok(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[ok(isNat(_x0))]] 
  [[top(ok(_x0))]] = 2x0 >= 2x0 = [[top(active(_x0))]] 

We can thus remove the following rules:

  proper(tt) => ok(tt) 
  proper(and(X, Y)) => and(proper(X), proper(Y)) 
  proper(isNat(X)) => isNat(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(U11(X, Y)) >? U11(active(X), Y) 
  active(U21(X, Y, Z)) >? U21(active(X), Y, Z) 
  active(s(X)) >? s(active(X)) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  active(and(X, Y)) >? and(active(X), Y) 
  plus(mark(X), Y) >? mark(plus(X, Y)) 
  proper(U11(X, Y)) >? U11(proper(X), proper(Y)) 
  proper(U21(X, Y, Z)) >? U21(proper(X), proper(Y), proper(Z)) 
  proper(s(X)) >? s(proper(X)) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  proper(0) >? ok(0) 
  U11(ok(X), ok(Y)) >? ok(U11(X, Y)) 
  U21(ok(X), ok(Y), ok(Z)) >? ok(U21(X, Y, Z)) 
  s(ok(X)) >? ok(s(X)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  isNat(ok(X)) >? ok(isNat(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 = 3 
  U11 = \y0y1.1 + 2y0 + 2y1 
  U21 = \y0y1y2.1 + y0 + y1 + y2 
  active = \y0.y0 
  and = \y0y1.y0 + y1 
  isNat = \y0.3y0 
  mark = \y0.y0 
  ok = \y0.y0 
  plus = \y0y1.y0 + 2y1 
  proper = \y0.3y0 
  s = \y0.2y0 
  top = \y0.y0 

Using this interpretation, the requirements translate to:

  [[active(U11(_x0, _x1))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[U11(active(_x0), _x1)]] 
  [[active(U21(_x0, _x1, _x2))]] = 1 + x0 + x1 + x2 >= 1 + x0 + x1 + x2 = [[U21(active(_x0), _x1, _x2)]] 
  [[active(s(_x0))]] = 2x0 >= 2x0 = [[s(active(_x0))]] 
  [[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(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[and(active(_x0), _x1)]] 
  [[plus(mark(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[mark(plus(_x0, _x1))]] 
  [[proper(U11(_x0, _x1))]] = 3 + 6x0 + 6x1 > 1 + 6x0 + 6x1 = [[U11(proper(_x0), proper(_x1))]] 
  [[proper(U21(_x0, _x1, _x2))]] = 3 + 3x0 + 3x1 + 3x2 > 1 + 3x0 + 3x1 + 3x2 = [[U21(proper(_x0), proper(_x1), proper(_x2))]] 
  [[proper(s(_x0))]] = 6x0 >= 6x0 = [[s(proper(_x0))]] 
  [[proper(plus(_x0, _x1))]] = 3x0 + 6x1 >= 3x0 + 6x1 = [[plus(proper(_x0), proper(_x1))]] 
  [[proper(0)]] = 9 > 3 = [[ok(0)]] 
  [[U11(ok(_x0), ok(_x1))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[ok(U11(_x0, _x1))]] 
  [[U21(ok(_x0), ok(_x1), ok(_x2))]] = 1 + x0 + x1 + x2 >= 1 + x0 + x1 + x2 = [[ok(U21(_x0, _x1, _x2))]] 
  [[s(ok(_x0))]] = 2x0 >= 2x0 = [[ok(s(_x0))]] 
  [[plus(ok(_x0), ok(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[ok(plus(_x0, _x1))]] 
  [[and(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(and(_x0, _x1))]] 
  [[isNat(ok(_x0))]] = 3x0 >= 3x0 = [[ok(isNat(_x0))]] 
  [[top(ok(_x0))]] = x0 >= x0 = [[top(active(_x0))]] 

We can thus remove the following rules:

  proper(U11(X, Y)) => U11(proper(X), proper(Y)) 
  proper(U21(X, Y, Z)) => U21(proper(X), proper(Y), proper(Z)) 
  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(U11(X, Y)) >? U11(active(X), Y) 
  active(U21(X, Y, Z)) >? U21(active(X), Y, Z) 
  active(s(X)) >? s(active(X)) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  active(and(X, Y)) >? and(active(X), Y) 
  plus(mark(X), Y) >? mark(plus(X, Y)) 
  proper(s(X)) >? s(proper(X)) 
  proper(plus(X, Y)) >? plus(proper(X), proper(Y)) 
  U11(ok(X), ok(Y)) >? ok(U11(X, Y)) 
  U21(ok(X), ok(Y), ok(Z)) >? ok(U21(X, Y, Z)) 
  s(ok(X)) >? ok(s(X)) 
  plus(ok(X), ok(Y)) >? ok(plus(X, Y)) 
  and(ok(X), ok(Y)) >? ok(and(X, Y)) 
  isNat(ok(X)) >? ok(isNat(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:

  U11 = \y0y1.1 + 2y0 + 2y1 
  U21 = \y0y1y2.y2 + 2y0 + 2y1 
  active = \y0.2y0 
  and = \y0y1.2 + 2y0 + 2y1 
  isNat = \y0.3y0 
  mark = \y0.y0 
  ok = \y0.2 + 2y0 
  plus = \y0y1.y1 + 2y0 
  proper = \y0.3y0 
  s = \y0.y0 
  top = \y0.2y0 

Using this interpretation, the requirements translate to:

  [[active(U11(_x0, _x1))]] = 2 + 4x0 + 4x1 > 1 + 2x1 + 4x0 = [[U11(active(_x0), _x1)]] 
  [[active(U21(_x0, _x1, _x2))]] = 2x2 + 4x0 + 4x1 >= x2 + 2x1 + 4x0 = [[U21(active(_x0), _x1, _x2)]] 
  [[active(s(_x0))]] = 2x0 >= 2x0 = [[s(active(_x0))]] 
  [[active(plus(_x0, _x1))]] = 2x1 + 4x0 >= x1 + 4x0 = [[plus(active(_x0), _x1)]] 
  [[active(plus(_x0, _x1))]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[plus(_x0, active(_x1))]] 
  [[active(and(_x0, _x1))]] = 4 + 4x0 + 4x1 > 2 + 2x1 + 4x0 = [[and(active(_x0), _x1)]] 
  [[plus(mark(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[mark(plus(_x0, _x1))]] 
  [[proper(s(_x0))]] = 3x0 >= 3x0 = [[s(proper(_x0))]] 
  [[proper(plus(_x0, _x1))]] = 3x1 + 6x0 >= 3x1 + 6x0 = [[plus(proper(_x0), proper(_x1))]] 
  [[U11(ok(_x0), ok(_x1))]] = 9 + 4x0 + 4x1 > 4 + 4x0 + 4x1 = [[ok(U11(_x0, _x1))]] 
  [[U21(ok(_x0), ok(_x1), ok(_x2))]] = 10 + 2x2 + 4x0 + 4x1 > 2 + 2x2 + 4x0 + 4x1 = [[ok(U21(_x0, _x1, _x2))]] 
  [[s(ok(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[ok(s(_x0))]] 
  [[plus(ok(_x0), ok(_x1))]] = 6 + 2x1 + 4x0 > 2 + 2x1 + 4x0 = [[ok(plus(_x0, _x1))]] 
  [[and(ok(_x0), ok(_x1))]] = 10 + 4x0 + 4x1 > 6 + 4x0 + 4x1 = [[ok(and(_x0, _x1))]] 
  [[isNat(ok(_x0))]] = 6 + 6x0 > 2 + 6x0 = [[ok(isNat(_x0))]] 
  [[top(ok(_x0))]] = 4 + 4x0 > 4x0 = [[top(active(_x0))]] 

We can thus remove the following rules:

  active(U11(X, Y)) => U11(active(X), Y) 
  active(and(X, Y)) => and(active(X), Y) 
  U11(ok(X), ok(Y)) => ok(U11(X, Y)) 
  U21(ok(X), ok(Y), ok(Z)) => ok(U21(X, Y, Z)) 
  plus(ok(X), ok(Y)) => ok(plus(X, Y)) 
  and(ok(X), ok(Y)) => ok(and(X, Y)) 
  isNat(ok(X)) => ok(isNat(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(U21(X, Y, Z)) >? U21(active(X), Y, Z) 
  active(s(X)) >? s(active(X)) 
  active(plus(X, Y)) >? plus(active(X), Y) 
  active(plus(X, Y)) >? plus(X, active(Y)) 
  plus(mark(X), Y) >? mark(plus(X, Y)) 
  proper(s(X)) >? s(proper(X)) 
  proper(plus(X, Y)) >? plus(proper(X), proper(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:

  U21 = \y0y1y2.y0 + y1 + y2 
  active = \y0.2 + 3y0 
  mark = \y0.1 + y0 
  ok = \y0.1 + y0 
  plus = \y0y1.3 + y1 + 2y0 
  proper = \y0.2 + 3y0 
  s = \y0.3 + 2y0 

Using this interpretation, the requirements translate to:

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

We can thus remove the following rules:

  active(s(X)) => s(active(X)) 
  active(plus(X, Y)) => plus(active(X), Y) 
  active(plus(X, Y)) => plus(X, active(Y)) 
  plus(mark(X), Y) => mark(plus(X, Y)) 
  proper(s(X)) => s(proper(X)) 
  proper(plus(X, Y)) => plus(proper(X), proper(Y)) 
  s(ok(X)) => ok(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(U21(X, Y, Z)) >? U21(active(X), Y, Z) 

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

The following interpretation satisfies the requirements:

  U21 = \y0y1y2.1 + y0 + y1 + y2 
  active = \y0.3y0 

Using this interpretation, the requirements translate to:

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

We can thus remove the following rules:

  active(U21(X, Y, Z)) => U21(active(X), 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.