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

  !plus : [o * o] --> o 
  0 : [] --> o 
  f : [o] --> o 
  g : [o] --> o 
  h : [o] --> o 
  p : [o] --> o 
  pair : [o * o] --> o 
  q : [o] --> o 
  s : [o] --> o 

  f(0) => 0 
  f(s(0)) => s(0) 
  f(s(s(X))) => p(h(g(X))) 
  g(0) => pair(s(0), s(0)) 
  g(s(X)) => h(g(X)) 
  h(X) => pair(!plus(p(X), q(X)), p(X)) 
  p(pair(X, Y)) => X 
  q(pair(X, Y)) => Y 
  !plus(X, 0) => X 
  !plus(X, s(Y)) => s(!plus(X, Y)) 
  f(s(s(X))) => !plus(p(g(X)), q(g(X))) 
  g(s(X)) => pair(!plus(p(g(X)), q(g(X))), p(g(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]):

  f(0) >? 0 
  f(s(0)) >? s(0) 
  f(s(s(X))) >? p(h(g(X))) 
  g(0) >? pair(s(0), s(0)) 
  g(s(X)) >? h(g(X)) 
  h(X) >? pair(!plus(p(X), q(X)), p(X)) 
  p(pair(X, Y)) >? X 
  q(pair(X, Y)) >? Y 
  !plus(X, 0) >? X 
  !plus(X, s(Y)) >? s(!plus(X, Y)) 
  f(s(s(X))) >? !plus(p(g(X)), q(g(X))) 
  g(s(X)) >? pair(!plus(p(g(X)), q(g(X))), p(g(X))) 

about to try horpo

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

Argument functions:

  [[!plus(x_1, x_2)]] = !plus(x_2, x_1) 

We choose Lex = {!plus} and Mul = {0, f, g, h, p, pair, q, s}, and the following precedence: f > g > 0 > h > p > pair > !plus > q > s

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

  f(0) >= 0 
  f(s(0)) >= s(0) 
  f(s(s(X))) >= p(h(g(X))) 
  g(0) >= pair(s(0), s(0)) 
  g(s(X)) > h(g(X)) 
  h(X) > pair(!plus(p(X), q(X)), p(X)) 
  p(pair(X, Y)) > X 
  q(pair(X, Y)) > Y 
  !plus(X, 0) >= X 
  !plus(X, s(Y)) >= s(!plus(X, Y)) 
  f(s(s(X))) >= !plus(p(g(X)), q(g(X))) 
  g(s(X)) > pair(!plus(p(g(X)), q(g(X))), p(g(X))) 

With these choices, we have:

  1] f(0) >= 0  because [2], by (Star) 
  2] f*(0) >= 0  because f > 0, by (Copy) 

  3] f(s(0)) >= s(0)  because [4], by (Star) 
  4] f*(s(0)) >= s(0)  because [5], by (Select) 
  5] s(0) >= s(0)  because s in Mul and [6], by (Fun) 
  6] 0 >= 0  by (Fun) 

  7] f(s(s(X))) >= p(h(g(X)))  because [8], by (Star) 
  8] f*(s(s(X))) >= p(h(g(X)))  because f > p and [9], by (Copy) 
  9] f*(s(s(X))) >= h(g(X))  because f > h and [10], by (Copy) 
  10] f*(s(s(X))) >= g(X)  because f > g and [11], by (Copy) 
  11] f*(s(s(X))) >= X  because [12], by (Select) 
  12] s(s(X)) >= X  because [13], by (Star) 
  13] s*(s(X)) >= X  because [14], by (Select) 
  14] s(X) >= X  because [15], by (Star) 
  15] s*(X) >= X  because [16], by (Select) 
  16] X >= X  by (Meta) 

  17] g(0) >= pair(s(0), s(0))  because [18], by (Star) 
  18] g*(0) >= pair(s(0), s(0))  because g > pair, [19] and [19], by (Copy) 
  19] g*(0) >= s(0)  because g > s and [20], by (Copy) 
  20] g*(0) >= 0  because g > 0, by (Copy) 

  21] g(s(X)) > h(g(X))  because [22], by definition 
  22] g*(s(X)) >= h(g(X))  because g > h and [23], by (Copy) 
  23] g*(s(X)) >= g(X)  because g in Mul and [24], by (Stat) 
  24] s(X) > X  because [25], by definition 
  25] s*(X) >= X  because [16], by (Select) 

  26] h(X) > pair(!plus(p(X), q(X)), p(X))  because [27], by definition 
  27] h*(X) >= pair(!plus(p(X), q(X)), p(X))  because h > pair, [28] and [29], by (Copy) 
  28] h*(X) >= !plus(p(X), q(X))  because h > !plus, [29] and [31], by (Copy) 
  29] h*(X) >= p(X)  because h > p and [30], by (Copy) 
  30] h*(X) >= X  because [16], by (Select) 
  31] h*(X) >= q(X)  because h > q and [30], by (Copy) 

  32] p(pair(X, Y)) > X  because [33], by definition 
  33] p*(pair(X, Y)) >= X  because [34], by (Select) 
  34] pair(X, Y) >= X  because [35], by (Star) 
  35] pair*(X, Y) >= X  because [16], by (Select) 

  36] q(pair(X, Y)) > Y  because [37], by definition 
  37] q*(pair(X, Y)) >= Y  because [38], by (Select) 
  38] pair(X, Y) >= Y  because [39], by (Star) 
  39] pair*(X, Y) >= Y  because [40], by (Select) 
  40] Y >= Y  by (Meta) 

  41] !plus(X, 0) >= X  because [42], by (Star) 
  42] !plus*(X, 0) >= X  because [16], by (Select) 

  43] !plus(X, s(Y)) >= s(!plus(X, Y))  because [44], by (Star) 
  44] !plus*(X, s(Y)) >= s(!plus(X, Y))  because !plus > s and [45], by (Copy) 
  45] !plus*(X, s(Y)) >= !plus(X, Y)  because [46], [48] and [49], by (Stat) 
  46] s(Y) > Y  because [47], by definition 
  47] s*(Y) >= Y  because [40], by (Select) 
  48] !plus*(X, s(Y)) >= X  because [16], by (Select) 
  49] !plus*(X, s(Y)) >= Y  because [50], by (Select) 
  50] s(Y) >= Y  because [47], by (Star) 

  51] f(s(s(X))) >= !plus(p(g(X)), q(g(X)))  because [52], by (Star) 
  52] f*(s(s(X))) >= !plus(p(g(X)), q(g(X)))  because f > !plus, [53] and [54], by (Copy) 
  53] f*(s(s(X))) >= p(g(X))  because f > p and [10], by (Copy) 
  54] f*(s(s(X))) >= q(g(X))  because f > q and [10], by (Copy) 

  55] g(s(X)) > pair(!plus(p(g(X)), q(g(X))), p(g(X)))  because [56], by definition 
  56] g*(s(X)) >= pair(!plus(p(g(X)), q(g(X))), p(g(X)))  because g > pair, [57] and [58], by (Copy) 
  57] g*(s(X)) >= !plus(p(g(X)), q(g(X)))  because g > !plus, [58] and [59], by (Copy) 
  58] g*(s(X)) >= p(g(X))  because g > p and [23], by (Copy) 
  59] g*(s(X)) >= q(g(X))  because g > q and [23], by (Copy) 

We can thus remove the following rules:

  g(s(X)) => h(g(X)) 
  h(X) => pair(!plus(p(X), q(X)), p(X)) 
  p(pair(X, Y)) => X 
  q(pair(X, Y)) => Y 
  g(s(X)) => pair(!plus(p(g(X)), q(g(X))), p(g(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]):

  f(0) >? 0 
  f(s(0)) >? s(0) 
  f(s(s(X))) >? p(h(g(X))) 
  g(0) >? pair(s(0), s(0)) 
  !plus(X, 0) >? X 
  !plus(X, s(Y)) >? s(!plus(X, Y)) 
  f(s(s(X))) >? !plus(p(g(X)), q(g(X))) 

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

The following interpretation satisfies the requirements:

  !plus = \y0y1.y0 + 2y1 
  0 = 0 
  f = \y0.3 + 3y0 
  g = \y0.1 + y0 
  h = \y0.y0 
  p = \y0.y0 
  pair = \y0y1.y0 + y1 
  q = \y0.y0 
  s = \y0.y0 

Using this interpretation, the requirements translate to:

  [[f(0)]] = 3 > 0 = [[0]] 
  [[f(s(0))]] = 3 > 0 = [[s(0)]] 
  [[f(s(s(_x0)))]] = 3 + 3x0 > 1 + x0 = [[p(h(g(_x0)))]] 
  [[g(0)]] = 1 > 0 = [[pair(s(0), s(0))]] 
  [[!plus(_x0, 0)]] = x0 >= x0 = [[_x0]] 
  [[!plus(_x0, s(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[s(!plus(_x0, _x1))]] 
  [[f(s(s(_x0)))]] = 3 + 3x0 >= 3 + 3x0 = [[!plus(p(g(_x0)), q(g(_x0)))]] 

We can thus remove the following rules:

  f(0) => 0 
  f(s(0)) => s(0) 
  f(s(s(X))) => p(h(g(X))) 
  g(0) => pair(s(0), s(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]):

  !plus(X, 0) >? X 
  !plus(X, s(Y)) >? s(!plus(X, Y)) 
  f(s(s(X))) >? !plus(p(g(X)), q(g(X))) 

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

The following interpretation satisfies the requirements:

  !plus = \y0y1.y0 + 2y1 
  0 = 3 
  f = \y0.3 + 3y0 
  g = \y0.y0 
  p = \y0.y0 
  q = \y0.y0 
  s = \y0.y0 

Using this interpretation, the requirements translate to:

  [[!plus(_x0, 0)]] = 6 + x0 > x0 = [[_x0]] 
  [[!plus(_x0, s(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[s(!plus(_x0, _x1))]] 
  [[f(s(s(_x0)))]] = 3 + 3x0 > 3x0 = [[!plus(p(g(_x0)), q(g(_x0)))]] 

We can thus remove the following rules:

  !plus(X, 0) => X 
  f(s(s(X))) => !plus(p(g(X)), q(g(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]):

  !plus(X, s(Y)) >? s(!plus(X, Y)) 

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

The following interpretation satisfies the requirements:

  !plus = \y0y1.y0 + 3y1 
  s = \y0.1 + y0 

Using this interpretation, the requirements translate to:

  [[!plus(_x0, s(_x1))]] = 3 + x0 + 3x1 > 1 + x0 + 3x1 = [[s(!plus(_x0, _x1))]] 

We can thus remove the following rules:

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

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.