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

  terms(X) => cons(recip(sqr(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)) => cons(Y) 
  half(0) => 0 
  half(s(0)) => 0 
  half(s(s(X))) => s(half(X)) 
  half(dbl(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))) 
  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)) >? cons(Y) 
  half(0) >? 0 
  half(s(0)) >? 0 
  half(s(s(X))) >? s(half(X)) 
  half(dbl(X)) >? X 

about to try horpo

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

Argument functions:

  [[0]] = _|_ 
  [[cons(x_1)]] = x_1 
  [[nil]] = _|_ 

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

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

  terms(X) > recip(sqr(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), Y) > Y 
  half(_|_) >= _|_ 
  half(s(_|_)) >= _|_ 
  half(s(s(X))) > s(half(X)) 
  half(dbl(X)) > X 

With these choices, we have:

  1] terms(X) > recip(sqr(X))  because [2], by definition 
  2] terms*(X) >= recip(sqr(X))  because terms > recip and [3], by (Copy) 
  3] terms*(X) >= sqr(X)  because terms > sqr and [4], by (Copy) 
  4] terms*(X) >= X  because [5], by (Select) 
  5] X >= X  by (Meta) 

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

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

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

  16] dbl(s(X)) >= s(s(dbl(X)))  because [17], by (Star) 
  17] dbl*(s(X)) >= s(s(dbl(X)))  because dbl > s and [18], by (Copy) 
  18] dbl*(s(X)) >= s(dbl(X))  because dbl > s and [19], by (Copy) 
  19] dbl*(s(X)) >= dbl(X)  because dbl in Mul and [11], by (Stat) 

  20] add(_|_, X) > X  because [21], by definition 
  21] add*(_|_, X) >= X  because [13], by (Select) 

  22] add(s(X), Y) > s(add(X, Y))  because [23], by definition 
  23] add*(s(X), Y) >= s(add(X, Y))  because add > s and [24], by (Copy) 
  24] add*(s(X), Y) >= add(X, Y)  because add in Mul, [11] and [25], by (Stat) 
  25] Y >= Y  by (Meta) 

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

  27] first(s(X), Y) > Y  because [28], by definition 
  28] first*(s(X), Y) >= Y  because [29], by (Select) 
  29] Y >= Y  by (Meta) 

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

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

  32] half(s(s(X))) > s(half(X))  because [33], by definition 
  33] half*(s(s(X))) >= s(half(X))  because half > s and [34], by (Copy) 
  34] half*(s(s(X))) >= half(X)  because half in Mul and [35], by (Stat) 
  35] s(s(X)) > X  because [36], by definition 
  36] s*(s(X)) >= X  because [37], by (Select) 
  37] s(X) >= X  because [12], by (Star) 

  38] half(dbl(X)) > X  because [39], by definition 
  39] half*(dbl(X)) >= X  because [40], by (Select) 
  40] dbl(X) >= X  because [41], by (Star) 
  41] dbl*(X) >= X  because [13], by (Select) 

We can thus remove the following rules:

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

  sqr(0) >? 0 
  sqr(s(X)) >? s(add(sqr(X), dbl(X))) 
  dbl(0) >? 0 
  dbl(s(X)) >? s(s(dbl(X))) 
  first(0, X) >? nil 
  half(0) >? 0 
  half(s(0)) >? 0 

about to try horpo

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

Argument functions:

  [[0]] = _|_ 
  [[half(x_1)]] = x_1 
  [[nil]] = _|_ 

We choose Lex = {} and Mul = {add, dbl, first, s, sqr}, and the following precedence: first > dbl = sqr > s > add

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

  sqr(_|_) >= _|_ 
  sqr(s(X)) >= s(add(sqr(X), dbl(X))) 
  dbl(_|_) >= _|_ 
  dbl(s(X)) > s(s(dbl(X))) 
  first(_|_, X) >= _|_ 
  _|_ >= _|_ 
  s(_|_) >= _|_ 

With these choices, we have:

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

  2] sqr(s(X)) >= s(add(sqr(X), dbl(X)))  because [3], by (Star) 
  3] sqr*(s(X)) >= s(add(sqr(X), dbl(X)))  because sqr > s and [4], by (Copy) 
  4] sqr*(s(X)) >= add(sqr(X), dbl(X))  because sqr > add, [5] and [9], by (Copy) 
  5] sqr*(s(X)) >= sqr(X)  because sqr in Mul and [6], by (Stat) 
  6] s(X) > X  because [7], by definition 
  7] s*(X) >= X  because [8], by (Select) 
  8] X >= X  by (Meta) 
  9] sqr*(s(X)) >= dbl(X)  because sqr = dbl, sqr in Mul and [6], by (Stat) 

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

  11] dbl(s(X)) > s(s(dbl(X)))  because [12], by definition 
  12] dbl*(s(X)) >= s(s(dbl(X)))  because dbl > s and [13], by (Copy) 
  13] dbl*(s(X)) >= s(dbl(X))  because dbl > s and [14], by (Copy) 
  14] dbl*(s(X)) >= dbl(X)  because dbl in Mul and [6], by (Stat) 

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

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

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

We can thus remove the following rules:

  dbl(s(X)) => s(s(dbl(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 
  sqr(s(X)) >? s(add(sqr(X), dbl(X))) 
  dbl(0) >? 0 
  first(0, X) >? nil 
  half(0) >? 0 
  half(s(0)) >? 0 

about to try horpo

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

Argument functions:

  [[0]] = _|_ 
  [[half(x_1)]] = x_1 
  [[nil]] = _|_ 

We choose Lex = {} and Mul = {add, dbl, first, s, sqr}, and the following precedence: first > dbl = sqr > s > add

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

  sqr(_|_) >= _|_ 
  sqr(s(X)) >= s(add(sqr(X), dbl(X))) 
  dbl(_|_) >= _|_ 
  first(_|_, X) > _|_ 
  _|_ >= _|_ 
  s(_|_) >= _|_ 

With these choices, we have:

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

  2] sqr(s(X)) >= s(add(sqr(X), dbl(X)))  because [3], by (Star) 
  3] sqr*(s(X)) >= s(add(sqr(X), dbl(X)))  because sqr > s and [4], by (Copy) 
  4] sqr*(s(X)) >= add(sqr(X), dbl(X))  because sqr > add, [5] and [9], by (Copy) 
  5] sqr*(s(X)) >= sqr(X)  because sqr in Mul and [6], by (Stat) 
  6] s(X) > X  because [7], by definition 
  7] s*(X) >= X  because [8], by (Select) 
  8] X >= X  by (Meta) 
  9] sqr*(s(X)) >= dbl(X)  because sqr = dbl, sqr in Mul and [6], by (Stat) 

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

  11] first(_|_, X) > _|_  because [12], by definition 
  12] first*(_|_, X) >= _|_  by (Bot) 

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

  14] s(_|_) >= _|_  by (Bot) 

We can thus remove the following rules:

  first(0, X) => nil 

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 
  sqr(s(X)) >? s(add(sqr(X), dbl(X))) 
  dbl(0) >? 0 
  half(0) >? 0 
  half(s(0)) >? 0 

about to try horpo

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

Argument functions:

  [[0]] = _|_ 

We choose Lex = {} and Mul = {add, dbl, half, s, sqr}, and the following precedence: half > dbl = sqr > s > add

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

  sqr(_|_) > _|_ 
  sqr(s(X)) >= s(add(sqr(X), dbl(X))) 
  dbl(_|_) >= _|_ 
  half(_|_) >= _|_ 
  half(s(_|_)) >= _|_ 

With these choices, we have:

  1] sqr(_|_) > _|_  because [2], by definition 
  2] sqr*(_|_) >= _|_  by (Bot) 

  3] sqr(s(X)) >= s(add(sqr(X), dbl(X)))  because [4], by (Star) 
  4] sqr*(s(X)) >= s(add(sqr(X), dbl(X)))  because sqr > s and [5], by (Copy) 
  5] sqr*(s(X)) >= add(sqr(X), dbl(X))  because sqr > add, [6] and [10], by (Copy) 
  6] sqr*(s(X)) >= sqr(X)  because sqr in Mul and [7], by (Stat) 
  7] s(X) > X  because [8], by definition 
  8] s*(X) >= X  because [9], by (Select) 
  9] X >= X  by (Meta) 
  10] sqr*(s(X)) >= dbl(X)  because sqr = dbl, sqr in Mul and [7], by (Stat) 

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

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

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

We can thus remove the following rules:

  sqr(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]):

  sqr(s(X)) >? s(add(sqr(X), dbl(X))) 
  dbl(0) >? 0 
  half(0) >? 0 
  half(s(0)) >? 0 

about to try horpo

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

Argument functions:

  [[0]] = _|_ 
  [[half(x_1)]] = x_1 

We choose Lex = {} and Mul = {add, dbl, s, sqr}, and the following precedence: dbl = sqr > s > add

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

  sqr(s(X)) >= s(add(sqr(X), dbl(X))) 
  dbl(_|_) >= _|_ 
  _|_ >= _|_ 
  s(_|_) > _|_ 

With these choices, we have:

  1] sqr(s(X)) >= s(add(sqr(X), dbl(X)))  because [2], by (Star) 
  2] sqr*(s(X)) >= s(add(sqr(X), dbl(X)))  because sqr > s and [3], by (Copy) 
  3] sqr*(s(X)) >= add(sqr(X), dbl(X))  because sqr > add, [4] and [8], by (Copy) 
  4] sqr*(s(X)) >= sqr(X)  because sqr in Mul and [5], by (Stat) 
  5] s(X) > X  because [6], by definition 
  6] s*(X) >= X  because [7], by (Select) 
  7] X >= X  by (Meta) 
  8] sqr*(s(X)) >= dbl(X)  because sqr = dbl, sqr in Mul and [5], by (Stat) 

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

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

  11] s(_|_) > _|_  because [12], by definition 
  12] s*(_|_) >= _|_  by (Bot) 

We can thus remove the following rules:

  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]):

  sqr(s(X)) >? s(add(sqr(X), dbl(X))) 
  dbl(0) >? 0 
  half(0) >? 0 

about to try horpo

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

Argument functions:

  [[0]] = _|_ 

We choose Lex = {} and Mul = {add, dbl, half, s, sqr}, and the following precedence: sqr > dbl = s > add > half

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

  sqr(s(X)) >= s(add(sqr(X), dbl(X))) 
  dbl(_|_) >= _|_ 
  half(_|_) > _|_ 

With these choices, we have:

  1] sqr(s(X)) >= s(add(sqr(X), dbl(X)))  because [2], by (Star) 
  2] sqr*(s(X)) >= s(add(sqr(X), dbl(X)))  because sqr > s and [3], by (Copy) 
  3] sqr*(s(X)) >= add(sqr(X), dbl(X))  because sqr > add, [4] and [8], by (Copy) 
  4] sqr*(s(X)) >= sqr(X)  because sqr in Mul and [5], by (Stat) 
  5] s(X) > X  because [6], by definition 
  6] s*(X) >= X  because [7], by (Select) 
  7] X >= X  by (Meta) 
  8] sqr*(s(X)) >= dbl(X)  because [9], by (Select) 
  9] s(X) >= dbl(X)  because s = dbl, s in Mul and [10], by (Fun) 
  10] X >= X  by (Meta) 

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

  12] half(_|_) > _|_  because [13], by definition 
  13] half*(_|_) >= _|_  by (Bot) 

We can thus remove the following rules:

  half(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]):

  sqr(s(X)) >? s(add(sqr(X), dbl(X))) 
  dbl(0) >? 0 

about to try horpo

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

Argument functions:

  [[0]] = _|_ 

We choose Lex = {} and Mul = {add, dbl, s, sqr}, and the following precedence: dbl = sqr > s > add

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

  sqr(s(X)) >= s(add(sqr(X), dbl(X))) 
  dbl(_|_) > _|_ 

With these choices, we have:

  1] sqr(s(X)) >= s(add(sqr(X), dbl(X)))  because [2], by (Star) 
  2] sqr*(s(X)) >= s(add(sqr(X), dbl(X)))  because sqr > s and [3], by (Copy) 
  3] sqr*(s(X)) >= add(sqr(X), dbl(X))  because sqr > add, [4] and [8], by (Copy) 
  4] sqr*(s(X)) >= sqr(X)  because sqr in Mul and [5], by (Stat) 
  5] s(X) > X  because [6], by definition 
  6] s*(X) >= X  because [7], by (Select) 
  7] X >= X  by (Meta) 
  8] sqr*(s(X)) >= dbl(X)  because sqr = dbl, sqr in Mul and [5], by (Stat) 

  9] dbl(_|_) > _|_  because [10], by definition 
  10] dbl*(_|_) >= _|_  by (Bot) 

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]):

  sqr(s(X)) >? s(add(sqr(X), dbl(X))) 

about to try horpo

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

We choose Lex = {} and Mul = {add, dbl, s, sqr}, and the following precedence: sqr > add > s > dbl

With these choices, we have:

  1] sqr(s(X)) > s(add(sqr(X), dbl(X)))  because [2], by definition 
  2] sqr*(s(X)) >= s(add(sqr(X), dbl(X)))  because sqr > s and [3], by (Copy) 
  3] sqr*(s(X)) >= add(sqr(X), dbl(X))  because sqr > add, [4] and [8], by (Copy) 
  4] sqr*(s(X)) >= sqr(X)  because sqr in Mul and [5], by (Stat) 
  5] s(X) > X  because [6], by definition 
  6] s*(X) >= X  because [7], by (Select) 
  7] X >= X  by (Meta) 
  8] sqr*(s(X)) >= dbl(X)  because [9], by (Select) 
  9] s(X) >= dbl(X)  because [10], by (Star) 
  10] s*(X) >= dbl(X)  because s > dbl and [6], by (Copy) 

We can thus remove the following rules:

  sqr(s(X)) => s(add(sqr(X), dbl(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.