/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 
  activate : [o] --> o 
  add : [o * o] --> o 
  cons : [o * o] --> o 
  dbl : [o] --> o 
  first : [o * o] --> o 
  half : [o] --> o 
  n!6220!6220first : [o * o] --> o 
  n!6220!6220terms : [o] --> o 
  nil : [] --> o 
  recip : [o] --> o 
  s : [o] --> o 
  sqr : [o] --> o 
  terms : [o] --> o 

  terms(X) => cons(recip(sqr(X)), n!6220!6220terms(s(X))) 
  sqr(0) => 0 
  sqr(s(X)) => s(add(sqr(X), dbl(X))) 
  dbl(0) => 0 
  dbl(s(X)) => s(s(dbl(X))) 
  add(0, X) => X 
  add(s(X), Y) => s(add(X, Y)) 
  first(0, X) => nil 
  first(s(X), cons(Y, Z)) => cons(Y, n!6220!6220first(X, activate(Z))) 
  half(0) => 0 
  half(s(0)) => 0 
  half(s(s(X))) => s(half(X)) 
  half(dbl(X)) => X 
  terms(X) => n!6220!6220terms(X) 
  first(X, Y) => n!6220!6220first(X, Y) 
  activate(n!6220!6220terms(X)) => terms(X) 
  activate(n!6220!6220first(X, Y)) => first(X, Y) 
  activate(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]):

  terms(X) >? cons(recip(sqr(X)), n!6220!6220terms(s(X))) 
  sqr(0) >? 0 
  sqr(s(X)) >? s(add(sqr(X), dbl(X))) 
  dbl(0) >? 0 
  dbl(s(X)) >? s(s(dbl(X))) 
  add(0, X) >? X 
  add(s(X), Y) >? s(add(X, Y)) 
  first(0, X) >? nil 
  first(s(X), cons(Y, Z)) >? cons(Y, n!6220!6220first(X, activate(Z))) 
  half(0) >? 0 
  half(s(0)) >? 0 
  half(s(s(X))) >? s(half(X)) 
  half(dbl(X)) >? X 
  terms(X) >? n!6220!6220terms(X) 
  first(X, Y) >? n!6220!6220first(X, Y) 
  activate(n!6220!6220terms(X)) >? terms(X) 
  activate(n!6220!6220first(X, Y)) >? first(X, Y) 
  activate(X) >? X 

about to try horpo

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

Argument functions:

  [[0]] = _|_ 
  [[n!6220!6220terms(x_1)]] = x_1 
  [[nil]] = _|_ 

We choose Lex = {} and Mul = {activate, add, cons, dbl, first, half, n!6220!6220first, recip, s, sqr, terms}, and the following precedence: activate = first > n!6220!6220first > terms > cons > recip > dbl = sqr > add > half = s

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

  terms(X) >= cons(recip(sqr(X)), s(X)) 
  sqr(_|_) >= _|_ 
  sqr(s(X)) > s(add(sqr(X), dbl(X))) 
  dbl(_|_) >= _|_ 
  dbl(s(X)) >= s(s(dbl(X))) 
  add(_|_, X) > X 
  add(s(X), Y) > s(add(X, Y)) 
  first(_|_, X) >= _|_ 
  first(s(X), cons(Y, Z)) >= cons(Y, n!6220!6220first(X, activate(Z))) 
  half(_|_) >= _|_ 
  half(s(_|_)) >= _|_ 
  half(s(s(X))) >= s(half(X)) 
  half(dbl(X)) > X 
  terms(X) >= X 
  first(X, Y) >= n!6220!6220first(X, Y) 
  activate(X) > terms(X) 
  activate(n!6220!6220first(X, Y)) >= first(X, Y) 
  activate(X) >= X 

With these choices, we have:

  1] terms(X) >= cons(recip(sqr(X)), s(X))  because [2], by (Star) 
  2] terms*(X) >= cons(recip(sqr(X)), s(X))  because terms > cons, [3] and [7], by (Copy) 
  3] terms*(X) >= recip(sqr(X))  because terms > recip and [4], by (Copy) 
  4] terms*(X) >= sqr(X)  because terms > sqr and [5], by (Copy) 
  5] terms*(X) >= X  because [6], by (Select) 
  6] X >= X  by (Meta) 
  7] terms*(X) >= s(X)  because terms > s and [5], by (Copy) 

  8] sqr(_|_) >= _|_  by (Bot) 

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

  17] dbl(_|_) >= _|_  by (Bot) 

  18] dbl(s(X)) >= s(s(dbl(X)))  because [19], by (Star) 
  19] dbl*(s(X)) >= s(s(dbl(X)))  because dbl > s and [20], by (Copy) 
  20] dbl*(s(X)) >= s(dbl(X))  because dbl > s and [21], by (Copy) 
  21] dbl*(s(X)) >= dbl(X)  because dbl in Mul and [13], by (Stat) 

  22] add(_|_, X) > X  because [23], by definition 
  23] add*(_|_, X) >= X  because [15], by (Select) 

  24] add(s(X), Y) > s(add(X, Y))  because [25], by definition 
  25] add*(s(X), Y) >= s(add(X, Y))  because add > s and [26], by (Copy) 
  26] add*(s(X), Y) >= add(X, Y)  because add in Mul, [13] and [27], by (Stat) 
  27] Y >= Y  by (Meta) 

  28] first(_|_, X) >= _|_  by (Bot) 

  29] first(s(X), cons(Y, Z)) >= cons(Y, n!6220!6220first(X, activate(Z)))  because [30], by (Star) 
  30] first*(s(X), cons(Y, Z)) >= cons(Y, n!6220!6220first(X, activate(Z)))  because first > cons, [31] and [34], by (Copy) 
  31] first*(s(X), cons(Y, Z)) >= Y  because [32], by (Select) 
  32] cons(Y, Z) >= Y  because [33], by (Star) 
  33] cons*(Y, Z) >= Y  because [27], by (Select) 
  34] first*(s(X), cons(Y, Z)) >= n!6220!6220first(X, activate(Z))  because first > n!6220!6220first, [35] and [37], by (Copy) 
  35] first*(s(X), cons(Y, Z)) >= X  because [36], by (Select) 
  36] s(X) >= X  because [14], by (Star) 
  37] first*(s(X), cons(Y, Z)) >= activate(Z)  because first = activate, first in Mul and [38], by (Stat) 
  38] cons(Y, Z) >= Z  because [39], by (Star) 
  39] cons*(Y, Z) >= Z  because [40], by (Select) 
  40] Z >= Z  by (Meta) 

  41] half(_|_) >= _|_  by (Bot) 

  42] half(s(_|_)) >= _|_  by (Bot) 

  43] half(s(s(X))) >= s(half(X))  because half = s, half in Mul and [44], by (Fun) 
  44] s(s(X)) >= half(X)  because s = half, s in Mul and [45], by (Fun) 
  45] s(X) >= X  because [14], by (Star) 

  46] half(dbl(X)) > X  because [47], by definition 
  47] half*(dbl(X)) >= X  because [48], by (Select) 
  48] dbl(X) >= X  because [49], by (Star) 
  49] dbl*(X) >= X  because [15], by (Select) 

  50] terms(X) >= X  because [51], by (Star) 
  51] terms*(X) >= X  because [15], by (Select) 

  52] first(X, Y) >= n!6220!6220first(X, Y)  because [53], by (Star) 
  53] first*(X, Y) >= n!6220!6220first(X, Y)  because first > n!6220!6220first, [54] and [56], by (Copy) 
  54] first*(X, Y) >= X  because [55], by (Select) 
  55] X >= X  by (Meta) 
  56] first*(X, Y) >= Y  because [57], by (Select) 
  57] Y >= Y  by (Meta) 

  58] activate(X) > terms(X)  because [59], by definition 
  59] activate*(X) >= terms(X)  because activate > terms and [60], by (Copy) 
  60] activate*(X) >= X  because [61], by (Select) 
  61] X >= X  by (Meta) 

  62] activate(n!6220!6220first(X, Y)) >= first(X, Y)  because [63], by (Star) 
  63] activate*(n!6220!6220first(X, Y)) >= first(X, Y)  because activate = first, activate in Mul, [64] and [66], by (Stat) 
  64] n!6220!6220first(X, Y) > X  because [65], by definition 
  65] n!6220!6220first*(X, Y) >= X  because [55], by (Select) 
  66] n!6220!6220first(X, Y) > Y  because [67], by definition 
  67] n!6220!6220first*(X, Y) >= Y  because [57], by (Select) 

  68] activate(X) >= X  because [69], by (Star) 
  69] activate*(X) >= X  because [61], by (Select) 

We can thus remove the following rules:

  sqr(s(X)) => s(add(sqr(X), dbl(X))) 
  add(0, X) => X 
  add(s(X), Y) => s(add(X, Y)) 
  half(dbl(X)) => X 
  activate(n!6220!6220terms(X)) => terms(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]):

  terms(X) >? cons(recip(sqr(X)), n!6220!6220terms(s(X))) 
  sqr(0) >? 0 
  dbl(0) >? 0 
  dbl(s(X)) >? s(s(dbl(X))) 
  first(0, X) >? nil 
  first(s(X), cons(Y, Z)) >? cons(Y, n!6220!6220first(X, activate(Z))) 
  half(0) >? 0 
  half(s(0)) >? 0 
  half(s(s(X))) >? s(half(X)) 
  terms(X) >? n!6220!6220terms(X) 
  first(X, Y) >? n!6220!6220first(X, Y) 
  activate(n!6220!6220first(X, Y)) >? first(X, Y) 
  activate(X) >? X 

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

The following interpretation satisfies the requirements:

  0 = 0 
  activate = \y0.y0 
  cons = \y0y1.y0 + y1 
  dbl = \y0.2y0 
  first = \y0y1.y0 + y1 
  half = \y0.2y0 
  n!6220!6220first = \y0y1.y0 + y1 
  n!6220!6220terms = \y0.y0 
  nil = 0 
  recip = \y0.y0 
  s = \y0.y0 
  sqr = \y0.y0 
  terms = \y0.3 + 3y0 

Using this interpretation, the requirements translate to:

  [[terms(_x0)]] = 3 + 3x0 > 2x0 = [[cons(recip(sqr(_x0)), n!6220!6220terms(s(_x0)))]] 
  [[sqr(0)]] = 0 >= 0 = [[0]] 
  [[dbl(0)]] = 0 >= 0 = [[0]] 
  [[dbl(s(_x0))]] = 2x0 >= 2x0 = [[s(s(dbl(_x0)))]] 
  [[first(0, _x0)]] = x0 >= 0 = [[nil]] 
  [[first(s(_x0), cons(_x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[cons(_x1, n!6220!6220first(_x0, activate(_x2)))]] 
  [[half(0)]] = 0 >= 0 = [[0]] 
  [[half(s(0))]] = 0 >= 0 = [[0]] 
  [[half(s(s(_x0)))]] = 2x0 >= 2x0 = [[s(half(_x0))]] 
  [[terms(_x0)]] = 3 + 3x0 > x0 = [[n!6220!6220terms(_x0)]] 
  [[first(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220first(_x0, _x1)]] 
  [[activate(n!6220!6220first(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[first(_x0, _x1)]] 
  [[activate(_x0)]] = x0 >= x0 = [[_x0]] 

We can thus remove the following rules:

  terms(X) => cons(recip(sqr(X)), n!6220!6220terms(s(X))) 
  terms(X) => n!6220!6220terms(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]):

  sqr(0) >? 0 
  dbl(0) >? 0 
  dbl(s(X)) >? s(s(dbl(X))) 
  first(0, X) >? nil 
  first(s(X), cons(Y, Z)) >? cons(Y, n!6220!6220first(X, activate(Z))) 
  half(0) >? 0 
  half(s(0)) >? 0 
  half(s(s(X))) >? s(half(X)) 
  first(X, Y) >? n!6220!6220first(X, Y) 
  activate(n!6220!6220first(X, Y)) >? first(X, Y) 
  activate(X) >? X 

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

The following interpretation satisfies the requirements:

  0 = 0 
  activate = \y0.2y0 
  cons = \y0y1.y0 + 2y1 
  dbl = \y0.y0 
  first = \y0y1.2y0 + 2y1 
  half = \y0.1 + 2y0 
  n!6220!6220first = \y0y1.y0 + y1 
  nil = 0 
  s = \y0.y0 
  sqr = \y0.3 + 3y0 

Using this interpretation, the requirements translate to:

  [[sqr(0)]] = 3 > 0 = [[0]] 
  [[dbl(0)]] = 0 >= 0 = [[0]] 
  [[dbl(s(_x0))]] = x0 >= x0 = [[s(s(dbl(_x0)))]] 
  [[first(0, _x0)]] = 2x0 >= 0 = [[nil]] 
  [[first(s(_x0), cons(_x1, _x2))]] = 2x0 + 2x1 + 4x2 >= x1 + 2x0 + 4x2 = [[cons(_x1, n!6220!6220first(_x0, activate(_x2)))]] 
  [[half(0)]] = 1 > 0 = [[0]] 
  [[half(s(0))]] = 1 > 0 = [[0]] 
  [[half(s(s(_x0)))]] = 1 + 2x0 >= 1 + 2x0 = [[s(half(_x0))]] 
  [[first(_x0, _x1)]] = 2x0 + 2x1 >= x0 + x1 = [[n!6220!6220first(_x0, _x1)]] 
  [[activate(n!6220!6220first(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[first(_x0, _x1)]] 
  [[activate(_x0)]] = 2x0 >= x0 = [[_x0]] 

We can thus remove the following rules:

  sqr(0) => 0 
  half(0) => 0 
  half(s(0)) => 0 

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

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

  dbl(0) >? 0 
  dbl(s(X)) >? s(s(dbl(X))) 
  first(0, X) >? nil 
  first(s(X), cons(Y, Z)) >? cons(Y, n!6220!6220first(X, activate(Z))) 
  half(s(s(X))) >? s(half(X)) 
  first(X, Y) >? n!6220!6220first(X, Y) 
  activate(n!6220!6220first(X, Y)) >? first(X, Y) 
  activate(X) >? X 

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

The following interpretation satisfies the requirements:

  0 = 0 
  activate = \y0.y0 
  cons = \y0y1.3 + y0 + y1 
  dbl = \y0.y0 
  first = \y0y1.2 + y0 + 2y1 
  half = \y0.2y0 
  n!6220!6220first = \y0y1.2 + y0 + 2y1 
  nil = 0 
  s = \y0.y0 

Using this interpretation, the requirements translate to:

  [[dbl(0)]] = 0 >= 0 = [[0]] 
  [[dbl(s(_x0))]] = x0 >= x0 = [[s(s(dbl(_x0)))]] 
  [[first(0, _x0)]] = 2 + 2x0 > 0 = [[nil]] 
  [[first(s(_x0), cons(_x1, _x2))]] = 8 + x0 + 2x1 + 2x2 > 5 + x0 + x1 + 2x2 = [[cons(_x1, n!6220!6220first(_x0, activate(_x2)))]] 
  [[half(s(s(_x0)))]] = 2x0 >= 2x0 = [[s(half(_x0))]] 
  [[first(_x0, _x1)]] = 2 + x0 + 2x1 >= 2 + x0 + 2x1 = [[n!6220!6220first(_x0, _x1)]] 
  [[activate(n!6220!6220first(_x0, _x1))]] = 2 + x0 + 2x1 >= 2 + x0 + 2x1 = [[first(_x0, _x1)]] 
  [[activate(_x0)]] = x0 >= x0 = [[_x0]] 

We can thus remove the following rules:

  first(0, X) => nil 
  first(s(X), cons(Y, Z)) => cons(Y, n!6220!6220first(X, activate(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]):

  dbl(0) >? 0 
  dbl(s(X)) >? s(s(dbl(X))) 
  half(s(s(X))) >? s(half(X)) 
  first(X, Y) >? n!6220!6220first(X, Y) 
  activate(n!6220!6220first(X, Y)) >? first(X, Y) 
  activate(X) >? X 

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

The following interpretation satisfies the requirements:

  0 = 0 
  activate = \y0.3 + 3y0 
  dbl = \y0.y0 
  first = \y0y1.3 + y0 + 2y1 
  half = \y0.2y0 
  n!6220!6220first = \y0y1.y0 + y1 
  s = \y0.y0 

Using this interpretation, the requirements translate to:

  [[dbl(0)]] = 0 >= 0 = [[0]] 
  [[dbl(s(_x0))]] = x0 >= x0 = [[s(s(dbl(_x0)))]] 
  [[half(s(s(_x0)))]] = 2x0 >= 2x0 = [[s(half(_x0))]] 
  [[first(_x0, _x1)]] = 3 + x0 + 2x1 > x0 + x1 = [[n!6220!6220first(_x0, _x1)]] 
  [[activate(n!6220!6220first(_x0, _x1))]] = 3 + 3x0 + 3x1 >= 3 + x0 + 2x1 = [[first(_x0, _x1)]] 
  [[activate(_x0)]] = 3 + 3x0 > x0 = [[_x0]] 

We can thus remove the following rules:

  first(X, Y) => n!6220!6220first(X, Y) 
  activate(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]):

  dbl(0) >? 0 
  dbl(s(X)) >? s(s(dbl(X))) 
  half(s(s(X))) >? s(half(X)) 
  activate(n!6220!6220first(X, Y)) >? first(X, Y) 

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

The following interpretation satisfies the requirements:

  0 = 1 
  activate = \y0.3 + 2y0 
  dbl = \y0.y0 
  first = \y0y1.y0 + y1 
  half = \y0.y0 
  n!6220!6220first = \y0y1.3 + y0 + y1 
  s = \y0.y0 

Using this interpretation, the requirements translate to:

  [[dbl(0)]] = 1 >= 1 = [[0]] 
  [[dbl(s(_x0))]] = x0 >= x0 = [[s(s(dbl(_x0)))]] 
  [[half(s(s(_x0)))]] = x0 >= x0 = [[s(half(_x0))]] 
  [[activate(n!6220!6220first(_x0, _x1))]] = 9 + 2x0 + 2x1 > x0 + x1 = [[first(_x0, _x1)]] 

We can thus remove the following rules:

  activate(n!6220!6220first(X, Y)) => first(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]):

  dbl(0) >? 0 
  dbl(s(X)) >? s(s(dbl(X))) 
  half(s(s(X))) >? s(half(X)) 

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

The following interpretation satisfies the requirements:

  0 = 2 
  dbl = \y0.2 + y0 
  half = \y0.2y0 
  s = \y0.y0 

Using this interpretation, the requirements translate to:

  [[dbl(0)]] = 4 > 2 = [[0]] 
  [[dbl(s(_x0))]] = 2 + x0 >= 2 + x0 = [[s(s(dbl(_x0)))]] 
  [[half(s(s(_x0)))]] = 2x0 >= 2x0 = [[s(half(_x0))]] 

We can thus remove the following rules:

  dbl(0) => 0 

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

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

  dbl(s(X)) >? s(s(dbl(X))) 
  half(s(s(X))) >? s(half(X)) 

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

The following interpretation satisfies the requirements:

  dbl = \y0.3y0 
  half = \y0.y0 
  s = \y0.1 + y0 

Using this interpretation, the requirements translate to:

  [[dbl(s(_x0))]] = 3 + 3x0 > 2 + 3x0 = [[s(s(dbl(_x0)))]] 
  [[half(s(s(_x0)))]] = 2 + x0 > 1 + x0 = [[s(half(_x0))]] 

We can thus remove the following rules:

  dbl(s(X)) => s(s(dbl(X))) 
  half(s(s(X))) => s(half(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.