/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 
  U11 : [o * o] --> o 
  U21 : [o * o * o] --> o 
  a!6220!6220U11 : [o * o] --> o 
  a!6220!6220U21 : [o * o * o] --> o 
  a!6220!6220and : [o * o] --> o 
  a!6220!6220isNat : [o] --> o 
  a!6220!6220plus : [o * o] --> o 
  and : [o * o] --> o 
  isNat : [o] --> o 
  mark : [o] --> o 
  plus : [o * o] --> o 
  s : [o] --> o 
  tt : [] --> o 

  a!6220!6220U11(tt, X) => mark(X) 
  a!6220!6220U21(tt, X, Y) => s(a!6220!6220plus(mark(Y), mark(X))) 
  a!6220!6220and(tt, X) => mark(X) 
  a!6220!6220isNat(0) => tt 
  a!6220!6220isNat(plus(X, Y)) => a!6220!6220and(a!6220!6220isNat(X), isNat(Y)) 
  a!6220!6220isNat(s(X)) => a!6220!6220isNat(X) 
  a!6220!6220plus(X, 0) => a!6220!6220U11(a!6220!6220isNat(X), X) 
  a!6220!6220plus(X, s(Y)) => a!6220!6220U21(a!6220!6220and(a!6220!6220isNat(Y), isNat(X)), Y, X) 
  mark(U11(X, Y)) => a!6220!6220U11(mark(X), Y) 
  mark(U21(X, Y, Z)) => a!6220!6220U21(mark(X), Y, Z) 
  mark(plus(X, Y)) => a!6220!6220plus(mark(X), mark(Y)) 
  mark(and(X, Y)) => a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) => a!6220!6220isNat(X) 
  mark(tt) => tt 
  mark(s(X)) => s(mark(X)) 
  mark(0) => 0 
  a!6220!6220U11(X, Y) => U11(X, Y) 
  a!6220!6220U21(X, Y, Z) => U21(X, Y, Z) 
  a!6220!6220plus(X, Y) => plus(X, Y) 
  a!6220!6220and(X, Y) => and(X, Y) 
  a!6220!6220isNat(X) => isNat(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]):

  a!6220!6220U11(tt, X) >? mark(X) 
  a!6220!6220U21(tt, X, Y) >? s(a!6220!6220plus(mark(Y), mark(X))) 
  a!6220!6220and(tt, X) >? mark(X) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220isNat(plus(X, Y)) >? a!6220!6220and(a!6220!6220isNat(X), isNat(Y)) 
  a!6220!6220isNat(s(X)) >? a!6220!6220isNat(X) 
  a!6220!6220plus(X, 0) >? a!6220!6220U11(a!6220!6220isNat(X), X) 
  a!6220!6220plus(X, s(Y)) >? a!6220!6220U21(a!6220!6220and(a!6220!6220isNat(Y), isNat(X)), Y, X) 
  mark(U11(X, Y)) >? a!6220!6220U11(mark(X), Y) 
  mark(U21(X, Y, Z)) >? a!6220!6220U21(mark(X), Y, Z) 
  mark(plus(X, Y)) >? a!6220!6220plus(mark(X), mark(Y)) 
  mark(and(X, Y)) >? a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(tt) >? tt 
  mark(s(X)) >? s(mark(X)) 
  mark(0) >? 0 
  a!6220!6220U11(X, Y) >? U11(X, Y) 
  a!6220!6220U21(X, Y, Z) >? U21(X, Y, Z) 
  a!6220!6220plus(X, Y) >? plus(X, Y) 
  a!6220!6220and(X, Y) >? and(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 

about to try horpo

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

Argument functions:

  [[0]] = _|_ 
  [[U21(x_1, x_2, x_3)]] = U21(x_2, x_3, x_1) 
  [[a!6220!6220U21(x_1, x_2, x_3)]] = a!6220!6220U21(x_2, x_3, x_1) 
  [[a!6220!6220and(x_1, x_2)]] = a!6220!6220and(x_2, x_1) 
  [[a!6220!6220plus(x_1, x_2)]] = a!6220!6220plus(x_2, x_1) 
  [[and(x_1, x_2)]] = and(x_2, x_1) 
  [[mark(x_1)]] = x_1 
  [[plus(x_1, x_2)]] = plus(x_2, x_1) 
  [[tt]] = _|_ 

We choose Lex = {U21, a!6220!6220U21, a!6220!6220and, a!6220!6220plus, and, plus} and Mul = {U11, a!6220!6220U11, a!6220!6220isNat, isNat, s}, and the following precedence: U21 = a!6220!6220U21 = a!6220!6220plus = plus > U11 = a!6220!6220U11 > a!6220!6220isNat = isNat = s > a!6220!6220and = and

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

  a!6220!6220U11(_|_, X) >= X 
  a!6220!6220U21(_|_, X, Y) >= s(a!6220!6220plus(Y, X)) 
  a!6220!6220and(_|_, X) >= X 
  a!6220!6220isNat(_|_) >= _|_ 
  a!6220!6220isNat(plus(X, Y)) > a!6220!6220and(a!6220!6220isNat(X), isNat(Y)) 
  a!6220!6220isNat(s(X)) > a!6220!6220isNat(X) 
  a!6220!6220plus(X, _|_) > a!6220!6220U11(a!6220!6220isNat(X), X) 
  a!6220!6220plus(X, s(Y)) >= a!6220!6220U21(a!6220!6220and(a!6220!6220isNat(Y), isNat(X)), Y, X) 
  U11(X, Y) >= a!6220!6220U11(X, Y) 
  U21(X, Y, Z) >= a!6220!6220U21(X, Y, Z) 
  plus(X, Y) >= a!6220!6220plus(X, Y) 
  and(X, Y) >= a!6220!6220and(X, Y) 
  isNat(X) >= a!6220!6220isNat(X) 
  _|_ >= _|_ 
  s(X) >= s(X) 
  _|_ >= _|_ 
  a!6220!6220U11(X, Y) >= U11(X, Y) 
  a!6220!6220U21(X, Y, Z) >= U21(X, Y, Z) 
  a!6220!6220plus(X, Y) >= plus(X, Y) 
  a!6220!6220and(X, Y) >= and(X, Y) 
  a!6220!6220isNat(X) >= isNat(X) 

With these choices, we have:

  1] a!6220!6220U11(_|_, X) >= X  because [2], by (Star) 
  2] a!6220!6220U11*(_|_, X) >= X  because [3], by (Select) 
  3] X >= X  by (Meta) 

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

  11] a!6220!6220and(_|_, X) >= X  because [12], by (Star) 
  12] a!6220!6220and*(_|_, X) >= X  because [13], by (Select) 
  13] X >= X  by (Meta) 

  14] a!6220!6220isNat(_|_) >= _|_  by (Bot) 

  15] a!6220!6220isNat(plus(X, Y)) > a!6220!6220and(a!6220!6220isNat(X), isNat(Y))  because [16], by definition 
  16] a!6220!6220isNat*(plus(X, Y)) >= a!6220!6220and(a!6220!6220isNat(X), isNat(Y))  because a!6220!6220isNat > a!6220!6220and, [17] and [22], by (Copy) 
  17] a!6220!6220isNat*(plus(X, Y)) >= a!6220!6220isNat(X)  because [18], by (Select) 
  18] plus(X, Y) >= a!6220!6220isNat(X)  because [19], by (Star) 
  19] plus*(X, Y) >= a!6220!6220isNat(X)  because plus > a!6220!6220isNat and [20], by (Copy) 
  20] plus*(X, Y) >= X  because [21], by (Select) 
  21] X >= X  by (Meta) 
  22] a!6220!6220isNat*(plus(X, Y)) >= isNat(Y)  because [23], by (Select) 
  23] plus(X, Y) >= isNat(Y)  because [24], by (Star) 
  24] plus*(X, Y) >= isNat(Y)  because plus > isNat and [25], by (Copy) 
  25] plus*(X, Y) >= Y  because [26], by (Select) 
  26] Y >= Y  by (Meta) 

  27] a!6220!6220isNat(s(X)) > a!6220!6220isNat(X)  because [28], by definition 
  28] a!6220!6220isNat*(s(X)) >= a!6220!6220isNat(X)  because [29], by (Select) 
  29] s(X) >= a!6220!6220isNat(X)  because s = a!6220!6220isNat, s in Mul and [30], by (Fun) 
  30] X >= X  by (Meta) 

  31] a!6220!6220plus(X, _|_) > a!6220!6220U11(a!6220!6220isNat(X), X)  because [32], by definition 
  32] a!6220!6220plus*(X, _|_) >= a!6220!6220U11(a!6220!6220isNat(X), X)  because a!6220!6220plus > a!6220!6220U11, [33] and [34], by (Copy) 
  33] a!6220!6220plus*(X, _|_) >= a!6220!6220isNat(X)  because a!6220!6220plus > a!6220!6220isNat and [34], by (Copy) 
  34] a!6220!6220plus*(X, _|_) >= X  because [8], by (Select) 

  35] a!6220!6220plus(X, s(Y)) >= a!6220!6220U21(a!6220!6220and(a!6220!6220isNat(Y), isNat(X)), Y, X)  because [36], by (Star) 
  36] a!6220!6220plus*(X, s(Y)) >= a!6220!6220U21(a!6220!6220and(a!6220!6220isNat(Y), isNat(X)), Y, X)  because a!6220!6220plus = a!6220!6220U21, [37], [39], [41] and [44], by (Stat) 
  37] s(Y) > Y  because [38], by definition 
  38] s*(Y) >= Y  because [7], by (Select) 
  39] a!6220!6220plus*(X, s(Y)) >= a!6220!6220and(a!6220!6220isNat(Y), isNat(X))  because a!6220!6220plus > a!6220!6220and, [40] and [43], by (Copy) 
  40] a!6220!6220plus*(X, s(Y)) >= a!6220!6220isNat(Y)  because a!6220!6220plus > a!6220!6220isNat and [41], by (Copy) 
  41] a!6220!6220plus*(X, s(Y)) >= Y  because [42], by (Select) 
  42] s(Y) >= Y  because [38], by (Star) 
  43] a!6220!6220plus*(X, s(Y)) >= isNat(X)  because a!6220!6220plus > isNat and [44], by (Copy) 
  44] a!6220!6220plus*(X, s(Y)) >= X  because [8], by (Select) 

  45] U11(X, Y) >= a!6220!6220U11(X, Y)  because U11 = a!6220!6220U11, U11 in Mul, [46] and [47], by (Fun) 
  46] X >= X  by (Meta) 
  47] Y >= Y  by (Meta) 

  48] U21(X, Y, Z) >= a!6220!6220U21(X, Y, Z)  because U21 = a!6220!6220U21, [46], [47] and [49], by (Fun) 
  49] Z >= Z  by (Meta) 

  50] plus(X, Y) >= a!6220!6220plus(X, Y)  because plus = a!6220!6220plus, [46] and [51], by (Fun) 
  51] Y >= Y  by (Meta) 

  52] and(X, Y) >= a!6220!6220and(X, Y)  because and = a!6220!6220and, [46] and [51], by (Fun) 

  53] isNat(X) >= a!6220!6220isNat(X)  because isNat = a!6220!6220isNat, isNat in Mul and [54], by (Fun) 
  54] X >= X  by (Meta) 

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

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

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

  59] a!6220!6220U11(X, Y) >= U11(X, Y)  because a!6220!6220U11 = U11, a!6220!6220U11 in Mul, [46] and [51], by (Fun) 

  60] a!6220!6220U21(X, Y, Z) >= U21(X, Y, Z)  because a!6220!6220U21 = U21, [46], [51] and [49], by (Fun) 

  61] a!6220!6220plus(X, Y) >= plus(X, Y)  because a!6220!6220plus = plus, [46] and [51], by (Fun) 

  62] a!6220!6220and(X, Y) >= and(X, Y)  because a!6220!6220and = and, [46] and [51], by (Fun) 

  63] a!6220!6220isNat(X) >= isNat(X)  because a!6220!6220isNat = isNat, a!6220!6220isNat in Mul and [57], by (Fun) 

We can thus remove the following rules:

  a!6220!6220isNat(plus(X, Y)) => a!6220!6220and(a!6220!6220isNat(X), isNat(Y)) 
  a!6220!6220isNat(s(X)) => a!6220!6220isNat(X) 
  a!6220!6220plus(X, 0) => a!6220!6220U11(a!6220!6220isNat(X), 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]):

  a!6220!6220U11(tt, X) >? mark(X) 
  a!6220!6220U21(tt, X, Y) >? s(a!6220!6220plus(mark(Y), mark(X))) 
  a!6220!6220and(tt, X) >? mark(X) 
  a!6220!6220isNat(0) >? tt 
  a!6220!6220plus(X, s(Y)) >? a!6220!6220U21(a!6220!6220and(a!6220!6220isNat(Y), isNat(X)), Y, X) 
  mark(U11(X, Y)) >? a!6220!6220U11(mark(X), Y) 
  mark(U21(X, Y, Z)) >? a!6220!6220U21(mark(X), Y, Z) 
  mark(plus(X, Y)) >? a!6220!6220plus(mark(X), mark(Y)) 
  mark(and(X, Y)) >? a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(tt) >? tt 
  mark(s(X)) >? s(mark(X)) 
  mark(0) >? 0 
  a!6220!6220U11(X, Y) >? U11(X, Y) 
  a!6220!6220U21(X, Y, Z) >? U21(X, Y, Z) 
  a!6220!6220plus(X, Y) >? plus(X, Y) 
  a!6220!6220and(X, Y) >? and(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 

about to try horpo

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

Argument functions:

  [[0]] = _|_ 
  [[U21(x_1, x_2, x_3)]] = U21(x_2, x_3, x_1) 
  [[a!6220!6220U21(x_1, x_2, x_3)]] = a!6220!6220U21(x_2, x_3, x_1) 
  [[a!6220!6220plus(x_1, x_2)]] = a!6220!6220plus(x_2, x_1) 
  [[mark(x_1)]] = x_1 
  [[plus(x_1, x_2)]] = plus(x_2, x_1) 
  [[tt]] = _|_ 

We choose Lex = {U21, a!6220!6220U21, a!6220!6220plus, plus} and Mul = {U11, a!6220!6220U11, a!6220!6220and, a!6220!6220isNat, and, isNat, s}, and the following precedence: U11 = a!6220!6220U11 > U21 = a!6220!6220U21 = a!6220!6220plus = plus > a!6220!6220and = and > a!6220!6220isNat = isNat > s

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

  a!6220!6220U11(_|_, X) >= X 
  a!6220!6220U21(_|_, X, Y) >= s(a!6220!6220plus(Y, X)) 
  a!6220!6220and(_|_, X) >= X 
  a!6220!6220isNat(_|_) > _|_ 
  a!6220!6220plus(X, s(Y)) >= a!6220!6220U21(a!6220!6220and(a!6220!6220isNat(Y), isNat(X)), Y, X) 
  U11(X, Y) >= a!6220!6220U11(X, Y) 
  U21(X, Y, Z) >= a!6220!6220U21(X, Y, Z) 
  plus(X, Y) >= a!6220!6220plus(X, Y) 
  and(X, Y) >= a!6220!6220and(X, Y) 
  isNat(X) >= a!6220!6220isNat(X) 
  _|_ >= _|_ 
  s(X) >= s(X) 
  _|_ >= _|_ 
  a!6220!6220U11(X, Y) >= U11(X, Y) 
  a!6220!6220U21(X, Y, Z) >= U21(X, Y, Z) 
  a!6220!6220plus(X, Y) >= plus(X, Y) 
  a!6220!6220and(X, Y) >= and(X, Y) 
  a!6220!6220isNat(X) >= isNat(X) 

With these choices, we have:

  1] a!6220!6220U11(_|_, X) >= X  because [2], by (Star) 
  2] a!6220!6220U11*(_|_, X) >= X  because [3], by (Select) 
  3] X >= X  by (Meta) 

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

  11] a!6220!6220and(_|_, X) >= X  because [12], by (Star) 
  12] a!6220!6220and*(_|_, X) >= X  because [13], by (Select) 
  13] X >= X  by (Meta) 

  14] a!6220!6220isNat(_|_) > _|_  because [15], by definition 
  15] a!6220!6220isNat*(_|_) >= _|_  by (Bot) 

  16] a!6220!6220plus(X, s(Y)) >= a!6220!6220U21(a!6220!6220and(a!6220!6220isNat(Y), isNat(X)), Y, X)  because [17], by (Star) 
  17] a!6220!6220plus*(X, s(Y)) >= a!6220!6220U21(a!6220!6220and(a!6220!6220isNat(Y), isNat(X)), Y, X)  because a!6220!6220plus = a!6220!6220U21, [18], [20], [22] and [25], by (Stat) 
  18] s(Y) > Y  because [19], by definition 
  19] s*(Y) >= Y  because [7], by (Select) 
  20] a!6220!6220plus*(X, s(Y)) >= a!6220!6220and(a!6220!6220isNat(Y), isNat(X))  because a!6220!6220plus > a!6220!6220and, [21] and [24], by (Copy) 
  21] a!6220!6220plus*(X, s(Y)) >= a!6220!6220isNat(Y)  because a!6220!6220plus > a!6220!6220isNat and [22], by (Copy) 
  22] a!6220!6220plus*(X, s(Y)) >= Y  because [23], by (Select) 
  23] s(Y) >= Y  because [19], by (Star) 
  24] a!6220!6220plus*(X, s(Y)) >= isNat(X)  because a!6220!6220plus > isNat and [25], by (Copy) 
  25] a!6220!6220plus*(X, s(Y)) >= X  because [8], by (Select) 

  26] U11(X, Y) >= a!6220!6220U11(X, Y)  because U11 = a!6220!6220U11, U11 in Mul, [27] and [28], by (Fun) 
  27] X >= X  by (Meta) 
  28] Y >= Y  by (Meta) 

  29] U21(X, Y, Z) >= a!6220!6220U21(X, Y, Z)  because U21 = a!6220!6220U21, [27], [28] and [30], by (Fun) 
  30] Z >= Z  by (Meta) 

  31] plus(X, Y) >= a!6220!6220plus(X, Y)  because plus = a!6220!6220plus, [27] and [32], by (Fun) 
  32] Y >= Y  by (Meta) 

  33] and(X, Y) >= a!6220!6220and(X, Y)  because and = a!6220!6220and, and in Mul, [27] and [32], by (Fun) 

  34] isNat(X) >= a!6220!6220isNat(X)  because isNat = a!6220!6220isNat, isNat in Mul and [35], by (Fun) 
  35] X >= X  by (Meta) 

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

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

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

  40] a!6220!6220U11(X, Y) >= U11(X, Y)  because a!6220!6220U11 = U11, a!6220!6220U11 in Mul, [27] and [32], by (Fun) 

  41] a!6220!6220U21(X, Y, Z) >= U21(X, Y, Z)  because a!6220!6220U21 = U21, [27], [32] and [30], by (Fun) 

  42] a!6220!6220plus(X, Y) >= plus(X, Y)  because a!6220!6220plus = plus, [27] and [32], by (Fun) 

  43] a!6220!6220and(X, Y) >= and(X, Y)  because a!6220!6220and = and, a!6220!6220and in Mul, [27] and [32], by (Fun) 

  44] a!6220!6220isNat(X) >= isNat(X)  because a!6220!6220isNat = isNat, a!6220!6220isNat in Mul and [38], by (Fun) 

We can thus remove the following rules:

  a!6220!6220isNat(0) => 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]):

  a!6220!6220U11(tt, X) >? mark(X) 
  a!6220!6220U21(tt, X, Y) >? s(a!6220!6220plus(mark(Y), mark(X))) 
  a!6220!6220and(tt, X) >? mark(X) 
  a!6220!6220plus(X, s(Y)) >? a!6220!6220U21(a!6220!6220and(a!6220!6220isNat(Y), isNat(X)), Y, X) 
  mark(U11(X, Y)) >? a!6220!6220U11(mark(X), Y) 
  mark(U21(X, Y, Z)) >? a!6220!6220U21(mark(X), Y, Z) 
  mark(plus(X, Y)) >? a!6220!6220plus(mark(X), mark(Y)) 
  mark(and(X, Y)) >? a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(tt) >? tt 
  mark(s(X)) >? s(mark(X)) 
  mark(0) >? 0 
  a!6220!6220U11(X, Y) >? U11(X, Y) 
  a!6220!6220U21(X, Y, Z) >? U21(X, Y, Z) 
  a!6220!6220plus(X, Y) >? plus(X, Y) 
  a!6220!6220and(X, Y) >? and(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 

about to try horpo

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

Argument functions:

  [[0]] = _|_ 
  [[U21(x_1, x_2, x_3)]] = U21(x_2, x_3, x_1) 
  [[a!6220!6220U21(x_1, x_2, x_3)]] = a!6220!6220U21(x_2, x_3, x_1) 
  [[a!6220!6220plus(x_1, x_2)]] = a!6220!6220plus(x_2, x_1) 
  [[mark(x_1)]] = x_1 
  [[plus(x_1, x_2)]] = plus(x_2, x_1) 
  [[tt]] = _|_ 

We choose Lex = {U21, a!6220!6220U21, a!6220!6220plus, plus} and Mul = {U11, a!6220!6220U11, a!6220!6220and, a!6220!6220isNat, and, isNat, s}, and the following precedence: U11 = a!6220!6220U11 > U21 = a!6220!6220U21 = a!6220!6220plus = plus > a!6220!6220and = and > a!6220!6220isNat = isNat > s

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

  a!6220!6220U11(_|_, X) >= X 
  a!6220!6220U21(_|_, X, Y) >= s(a!6220!6220plus(Y, X)) 
  a!6220!6220and(_|_, X) > X 
  a!6220!6220plus(X, s(Y)) > a!6220!6220U21(a!6220!6220and(a!6220!6220isNat(Y), isNat(X)), Y, X) 
  U11(X, Y) >= a!6220!6220U11(X, Y) 
  U21(X, Y, Z) >= a!6220!6220U21(X, Y, Z) 
  plus(X, Y) >= a!6220!6220plus(X, Y) 
  and(X, Y) >= a!6220!6220and(X, Y) 
  isNat(X) >= a!6220!6220isNat(X) 
  _|_ >= _|_ 
  s(X) >= s(X) 
  _|_ >= _|_ 
  a!6220!6220U11(X, Y) >= U11(X, Y) 
  a!6220!6220U21(X, Y, Z) >= U21(X, Y, Z) 
  a!6220!6220plus(X, Y) >= plus(X, Y) 
  a!6220!6220and(X, Y) >= and(X, Y) 
  a!6220!6220isNat(X) >= isNat(X) 

With these choices, we have:

  1] a!6220!6220U11(_|_, X) >= X  because [2], by (Star) 
  2] a!6220!6220U11*(_|_, X) >= X  because [3], by (Select) 
  3] X >= X  by (Meta) 

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

  11] a!6220!6220and(_|_, X) > X  because [12], by definition 
  12] a!6220!6220and*(_|_, X) >= X  because [13], by (Select) 
  13] X >= X  by (Meta) 

  14] a!6220!6220plus(X, s(Y)) > a!6220!6220U21(a!6220!6220and(a!6220!6220isNat(Y), isNat(X)), Y, X)  because [15], by definition 
  15] a!6220!6220plus*(X, s(Y)) >= a!6220!6220U21(a!6220!6220and(a!6220!6220isNat(Y), isNat(X)), Y, X)  because a!6220!6220plus = a!6220!6220U21, [16], [18], [20] and [23], by (Stat) 
  16] s(Y) > Y  because [17], by definition 
  17] s*(Y) >= Y  because [7], by (Select) 
  18] a!6220!6220plus*(X, s(Y)) >= a!6220!6220and(a!6220!6220isNat(Y), isNat(X))  because a!6220!6220plus > a!6220!6220and, [19] and [22], by (Copy) 
  19] a!6220!6220plus*(X, s(Y)) >= a!6220!6220isNat(Y)  because a!6220!6220plus > a!6220!6220isNat and [20], by (Copy) 
  20] a!6220!6220plus*(X, s(Y)) >= Y  because [21], by (Select) 
  21] s(Y) >= Y  because [17], by (Star) 
  22] a!6220!6220plus*(X, s(Y)) >= isNat(X)  because a!6220!6220plus > isNat and [23], by (Copy) 
  23] a!6220!6220plus*(X, s(Y)) >= X  because [8], by (Select) 

  24] U11(X, Y) >= a!6220!6220U11(X, Y)  because U11 = a!6220!6220U11, U11 in Mul, [25] and [26], by (Fun) 
  25] X >= X  by (Meta) 
  26] Y >= Y  by (Meta) 

  27] U21(X, Y, Z) >= a!6220!6220U21(X, Y, Z)  because U21 = a!6220!6220U21, [25], [26] and [28], by (Fun) 
  28] Z >= Z  by (Meta) 

  29] plus(X, Y) >= a!6220!6220plus(X, Y)  because plus = a!6220!6220plus, [25] and [30], by (Fun) 
  30] Y >= Y  by (Meta) 

  31] and(X, Y) >= a!6220!6220and(X, Y)  because and = a!6220!6220and, and in Mul, [25] and [30], by (Fun) 

  32] isNat(X) >= a!6220!6220isNat(X)  because isNat = a!6220!6220isNat, isNat in Mul and [33], by (Fun) 
  33] X >= X  by (Meta) 

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

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

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

  38] a!6220!6220U11(X, Y) >= U11(X, Y)  because a!6220!6220U11 = U11, a!6220!6220U11 in Mul, [25] and [30], by (Fun) 

  39] a!6220!6220U21(X, Y, Z) >= U21(X, Y, Z)  because a!6220!6220U21 = U21, [25], [30] and [28], by (Fun) 

  40] a!6220!6220plus(X, Y) >= plus(X, Y)  because a!6220!6220plus = plus, [25] and [30], by (Fun) 

  41] a!6220!6220and(X, Y) >= and(X, Y)  because a!6220!6220and = and, a!6220!6220and in Mul, [25] and [30], by (Fun) 

  42] a!6220!6220isNat(X) >= isNat(X)  because a!6220!6220isNat = isNat, a!6220!6220isNat in Mul and [36], by (Fun) 

We can thus remove the following rules:

  a!6220!6220and(tt, X) => mark(X) 
  a!6220!6220plus(X, s(Y)) => a!6220!6220U21(a!6220!6220and(a!6220!6220isNat(Y), isNat(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]):

  a!6220!6220U11(tt, X) >? mark(X) 
  a!6220!6220U21(tt, X, Y) >? s(a!6220!6220plus(mark(Y), mark(X))) 
  mark(U11(X, Y)) >? a!6220!6220U11(mark(X), Y) 
  mark(U21(X, Y, Z)) >? a!6220!6220U21(mark(X), Y, Z) 
  mark(plus(X, Y)) >? a!6220!6220plus(mark(X), mark(Y)) 
  mark(and(X, Y)) >? a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(tt) >? tt 
  mark(s(X)) >? s(mark(X)) 
  mark(0) >? 0 
  a!6220!6220U11(X, Y) >? U11(X, Y) 
  a!6220!6220U21(X, Y, Z) >? U21(X, Y, Z) 
  a!6220!6220plus(X, Y) >? plus(X, Y) 
  a!6220!6220and(X, Y) >? and(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 

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

The following interpretation satisfies the requirements:

  0 = 3 
  U11 = \y0y1.y1 + 2y0 
  U21 = \y0y1y2.y1 + 2y0 + 2y2 
  a!6220!6220U11 = \y0y1.y1 + 2y0 
  a!6220!6220U21 = \y0y1y2.y1 + 2y0 + 2y2 
  a!6220!6220and = \y0y1.y0 + y1 
  a!6220!6220isNat = \y0.y0 
  a!6220!6220plus = \y0y1.y0 + y1 
  and = \y0y1.y0 + y1 
  isNat = \y0.y0 
  mark = \y0.y0 
  plus = \y0y1.y0 + y1 
  s = \y0.3 + y0 
  tt = 2 

Using this interpretation, the requirements translate to:

  [[a!6220!6220U11(tt, _x0)]] = 4 + x0 > x0 = [[mark(_x0)]] 
  [[a!6220!6220U21(tt, _x0, _x1)]] = 4 + x0 + 2x1 > 3 + x0 + x1 = [[s(a!6220!6220plus(mark(_x1), mark(_x0)))]] 
  [[mark(U11(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[a!6220!6220U11(mark(_x0), _x1)]] 
  [[mark(U21(_x0, _x1, _x2))]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[a!6220!6220U21(mark(_x0), _x1, _x2)]] 
  [[mark(plus(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[a!6220!6220plus(mark(_x0), mark(_x1))]] 
  [[mark(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[a!6220!6220and(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = x0 >= x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(tt)]] = 2 >= 2 = [[tt]] 
  [[mark(s(_x0))]] = 3 + x0 >= 3 + x0 = [[s(mark(_x0))]] 
  [[mark(0)]] = 3 >= 3 = [[0]] 
  [[a!6220!6220U11(_x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[U11(_x0, _x1)]] 
  [[a!6220!6220U21(_x0, _x1, _x2)]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[U21(_x0, _x1, _x2)]] 
  [[a!6220!6220plus(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[plus(_x0, _x1)]] 
  [[a!6220!6220and(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = x0 >= x0 = [[isNat(_x0)]] 

We can thus remove the following rules:

  a!6220!6220U11(tt, X) => mark(X) 
  a!6220!6220U21(tt, X, Y) => s(a!6220!6220plus(mark(Y), mark(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]):

  mark(U11(X, Y)) >? a!6220!6220U11(mark(X), Y) 
  mark(U21(X, Y, Z)) >? a!6220!6220U21(mark(X), Y, Z) 
  mark(plus(X, Y)) >? a!6220!6220plus(mark(X), mark(Y)) 
  mark(and(X, Y)) >? a!6220!6220and(mark(X), Y) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(tt) >? tt 
  mark(s(X)) >? s(mark(X)) 
  mark(0) >? 0 
  a!6220!6220U11(X, Y) >? U11(X, Y) 
  a!6220!6220U21(X, Y, Z) >? U21(X, Y, Z) 
  a!6220!6220plus(X, Y) >? plus(X, Y) 
  a!6220!6220and(X, Y) >? and(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  U11 = \y0y1.3 + y0 + 2y1 
  U21 = \y0y1y2.y0 + y1 + 2y2 
  a!6220!6220U11 = \y0y1.3 + y0 + 2y1 
  a!6220!6220U21 = \y0y1y2.y0 + 2y1 + 2y2 
  a!6220!6220and = \y0y1.1 + y0 + 2y1 
  a!6220!6220isNat = \y0.y0 
  a!6220!6220plus = \y0y1.1 + y0 + y1 
  and = \y0y1.1 + y0 + 2y1 
  isNat = \y0.y0 
  mark = \y0.2y0 
  plus = \y0y1.1 + y0 + y1 
  s = \y0.y0 
  tt = 1 

Using this interpretation, the requirements translate to:

  [[mark(U11(_x0, _x1))]] = 6 + 2x0 + 4x1 > 3 + 2x0 + 2x1 = [[a!6220!6220U11(mark(_x0), _x1)]] 
  [[mark(U21(_x0, _x1, _x2))]] = 2x0 + 2x1 + 4x2 >= 2x0 + 2x1 + 2x2 = [[a!6220!6220U21(mark(_x0), _x1, _x2)]] 
  [[mark(plus(_x0, _x1))]] = 2 + 2x0 + 2x1 > 1 + 2x0 + 2x1 = [[a!6220!6220plus(mark(_x0), mark(_x1))]] 
  [[mark(and(_x0, _x1))]] = 2 + 2x0 + 4x1 > 1 + 2x0 + 2x1 = [[a!6220!6220and(mark(_x0), _x1)]] 
  [[mark(isNat(_x0))]] = 2x0 >= x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(tt)]] = 2 > 1 = [[tt]] 
  [[mark(s(_x0))]] = 2x0 >= 2x0 = [[s(mark(_x0))]] 
  [[mark(0)]] = 0 >= 0 = [[0]] 
  [[a!6220!6220U11(_x0, _x1)]] = 3 + x0 + 2x1 >= 3 + x0 + 2x1 = [[U11(_x0, _x1)]] 
  [[a!6220!6220U21(_x0, _x1, _x2)]] = x0 + 2x1 + 2x2 >= x0 + x1 + 2x2 = [[U21(_x0, _x1, _x2)]] 
  [[a!6220!6220plus(_x0, _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[plus(_x0, _x1)]] 
  [[a!6220!6220and(_x0, _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[and(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = x0 >= x0 = [[isNat(_x0)]] 

We can thus remove the following rules:

  mark(U11(X, Y)) => a!6220!6220U11(mark(X), Y) 
  mark(plus(X, Y)) => a!6220!6220plus(mark(X), mark(Y)) 
  mark(and(X, Y)) => a!6220!6220and(mark(X), Y) 
  mark(tt) => 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]):

  mark(U21(X, Y, Z)) >? a!6220!6220U21(mark(X), Y, Z) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  mark(s(X)) >? s(mark(X)) 
  mark(0) >? 0 
  a!6220!6220U11(X, Y) >? U11(X, Y) 
  a!6220!6220U21(X, Y, Z) >? U21(X, Y, Z) 
  a!6220!6220plus(X, Y) >? plus(X, Y) 
  a!6220!6220and(X, Y) >? and(X, Y) 
  a!6220!6220isNat(X) >? isNat(X) 

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

The following interpretation satisfies the requirements:

  0 = 2 
  U11 = \y0y1.y0 + y1 
  U21 = \y0y1y2.y0 + y2 + 2y1 
  a!6220!6220U11 = \y0y1.3 + y0 + y1 
  a!6220!6220U21 = \y0y1y2.y0 + y2 + 2y1 
  a!6220!6220and = \y0y1.3 + y0 + 2y1 
  a!6220!6220isNat = \y0.2 + 2y0 
  a!6220!6220plus = \y0y1.3 + 2y0 + 2y1 
  and = \y0y1.y0 + y1 
  isNat = \y0.1 + 2y0 
  mark = \y0.2y0 
  plus = \y0y1.y0 + y1 
  s = \y0.1 + y0 

Using this interpretation, the requirements translate to:

  [[mark(U21(_x0, _x1, _x2))]] = 2x0 + 2x2 + 4x1 >= x2 + 2x0 + 2x1 = [[a!6220!6220U21(mark(_x0), _x1, _x2)]] 
  [[mark(isNat(_x0))]] = 2 + 4x0 >= 2 + 2x0 = [[a!6220!6220isNat(_x0)]] 
  [[mark(s(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[s(mark(_x0))]] 
  [[mark(0)]] = 4 > 2 = [[0]] 
  [[a!6220!6220U11(_x0, _x1)]] = 3 + x0 + x1 > x0 + x1 = [[U11(_x0, _x1)]] 
  [[a!6220!6220U21(_x0, _x1, _x2)]] = x0 + x2 + 2x1 >= x0 + x2 + 2x1 = [[U21(_x0, _x1, _x2)]] 
  [[a!6220!6220plus(_x0, _x1)]] = 3 + 2x0 + 2x1 > x0 + x1 = [[plus(_x0, _x1)]] 
  [[a!6220!6220and(_x0, _x1)]] = 3 + x0 + 2x1 > x0 + x1 = [[and(_x0, _x1)]] 
  [[a!6220!6220isNat(_x0)]] = 2 + 2x0 > 1 + 2x0 = [[isNat(_x0)]] 

We can thus remove the following rules:

  mark(s(X)) => s(mark(X)) 
  mark(0) => 0 
  a!6220!6220U11(X, Y) => U11(X, Y) 
  a!6220!6220plus(X, Y) => plus(X, Y) 
  a!6220!6220and(X, Y) => and(X, Y) 
  a!6220!6220isNat(X) => isNat(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]):

  mark(U21(X, Y, Z)) >? a!6220!6220U21(mark(X), Y, Z) 
  mark(isNat(X)) >? a!6220!6220isNat(X) 
  a!6220!6220U21(X, Y, Z) >? U21(X, Y, Z) 

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

The following interpretation satisfies the requirements:

  U21 = \y0y1y2.y0 + y1 + y2 
  a!6220!6220U21 = \y0y1y2.y0 + y1 + y2 
  a!6220!6220isNat = \y0.y0 
  isNat = \y0.3 + y0 
  mark = \y0.y0 

Using this interpretation, the requirements translate to:

  [[mark(U21(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[a!6220!6220U21(mark(_x0), _x1, _x2)]] 
  [[mark(isNat(_x0))]] = 3 + x0 > x0 = [[a!6220!6220isNat(_x0)]] 
  [[a!6220!6220U21(_x0, _x1, _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U21(_x0, _x1, _x2)]] 

We can thus remove the following rules:

  mark(isNat(X)) => a!6220!6220isNat(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]):

  mark(U21(X, Y, Z)) >? a!6220!6220U21(mark(X), Y, Z) 
  a!6220!6220U21(X, Y, Z) >? U21(X, Y, Z) 

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

The following interpretation satisfies the requirements:

  U21 = \y0y1y2.2 + y0 + y2 + 2y1 
  a!6220!6220U21 = \y0y1y2.2 + y0 + y2 + 2y1 
  mark = \y0.2y0 

Using this interpretation, the requirements translate to:

  [[mark(U21(_x0, _x1, _x2))]] = 4 + 2x0 + 2x2 + 4x1 > 2 + x2 + 2x0 + 2x1 = [[a!6220!6220U21(mark(_x0), _x1, _x2)]] 
  [[a!6220!6220U21(_x0, _x1, _x2)]] = 2 + x0 + x2 + 2x1 >= 2 + x0 + x2 + 2x1 = [[U21(_x0, _x1, _x2)]] 

We can thus remove the following rules:

  mark(U21(X, Y, Z)) => a!6220!6220U21(mark(X), Y, Z) 

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

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

  a!6220!6220U21(X, Y, Z) >? U21(X, Y, Z) 

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

The following interpretation satisfies the requirements:

  U21 = \y0y1y2.y0 + y1 + y2 
  a!6220!6220U21 = \y0y1y2.3 + 3y0 + 3y1 + 3y2 

Using this interpretation, the requirements translate to:

  [[a!6220!6220U21(_x0, _x1, _x2)]] = 3 + 3x0 + 3x1 + 3x2 > x0 + x1 + x2 = [[U21(_x0, _x1, _x2)]] 

We can thus remove the following rules:

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