/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 
  a!6220!6220eq : [o * o] --> o 
  a!6220!6220inf : [o] --> o 
  a!6220!6220length : [o] --> o 
  a!6220!6220take : [o * o] --> o 
  cons : [o * o] --> o 
  eq : [o * o] --> o 
  false : [] --> o 
  inf : [o] --> o 
  length : [o] --> o 
  mark : [o] --> o 
  nil : [] --> o 
  s : [o] --> o 
  take : [o * o] --> o 
  true : [] --> o 

  a!6220!6220eq(0, 0) => true 
  a!6220!6220eq(s(X), s(Y)) => a!6220!6220eq(X, Y) 
  a!6220!6220eq(X, Y) => false 
  a!6220!6220inf(X) => cons(X, inf(s(X))) 
  a!6220!6220take(0, X) => nil 
  a!6220!6220take(s(X), cons(Y, Z)) => cons(Y, take(X, Z)) 
  a!6220!6220length(nil) => 0 
  a!6220!6220length(cons(X, Y)) => s(length(Y)) 
  mark(eq(X, Y)) => a!6220!6220eq(X, Y) 
  mark(inf(X)) => a!6220!6220inf(mark(X)) 
  mark(take(X, Y)) => a!6220!6220take(mark(X), mark(Y)) 
  mark(length(X)) => a!6220!6220length(mark(X)) 
  mark(0) => 0 
  mark(true) => true 
  mark(s(X)) => s(X) 
  mark(false) => false 
  mark(cons(X, Y)) => cons(X, Y) 
  mark(nil) => nil 
  a!6220!6220eq(X, Y) => eq(X, Y) 
  a!6220!6220inf(X) => inf(X) 
  a!6220!6220take(X, Y) => take(X, Y) 
  a!6220!6220length(X) => length(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!6220eq(0, 0) >? true 
  a!6220!6220eq(s(X), s(Y)) >? a!6220!6220eq(X, Y) 
  a!6220!6220eq(X, Y) >? false 
  a!6220!6220inf(X) >? cons(X, inf(s(X))) 
  a!6220!6220take(0, X) >? nil 
  a!6220!6220take(s(X), cons(Y, Z)) >? cons(Y, take(X, Z)) 
  a!6220!6220length(nil) >? 0 
  a!6220!6220length(cons(X, Y)) >? s(length(Y)) 
  mark(eq(X, Y)) >? a!6220!6220eq(X, Y) 
  mark(inf(X)) >? a!6220!6220inf(mark(X)) 
  mark(take(X, Y)) >? a!6220!6220take(mark(X), mark(Y)) 
  mark(length(X)) >? a!6220!6220length(mark(X)) 
  mark(0) >? 0 
  mark(true) >? true 
  mark(s(X)) >? s(X) 
  mark(false) >? false 
  mark(cons(X, Y)) >? cons(X, Y) 
  mark(nil) >? nil 
  a!6220!6220eq(X, Y) >? eq(X, Y) 
  a!6220!6220inf(X) >? inf(X) 
  a!6220!6220take(X, Y) >? take(X, Y) 
  a!6220!6220length(X) >? length(X) 

about to try horpo

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

Argument functions:

  [[0]] = _|_ 
  [[a!6220!6220length(x_1)]] = x_1 
  [[false]] = _|_ 
  [[length(x_1)]] = x_1 
  [[nil]] = _|_ 
  [[true]] = _|_ 

We choose Lex = {} and Mul = {a!6220!6220eq, a!6220!6220inf, a!6220!6220take, cons, eq, inf, mark, s, take}, and the following precedence: mark > a!6220!6220inf > inf > a!6220!6220take = take > cons > a!6220!6220eq > eq > s

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

  a!6220!6220eq(_|_, _|_) >= _|_ 
  a!6220!6220eq(s(X), s(Y)) >= a!6220!6220eq(X, Y) 
  a!6220!6220eq(X, Y) >= _|_ 
  a!6220!6220inf(X) >= cons(X, inf(s(X))) 
  a!6220!6220take(_|_, X) >= _|_ 
  a!6220!6220take(s(X), cons(Y, Z)) > cons(Y, take(X, Z)) 
  _|_ >= _|_ 
  cons(X, Y) >= s(Y) 
  mark(eq(X, Y)) >= a!6220!6220eq(X, Y) 
  mark(inf(X)) > a!6220!6220inf(mark(X)) 
  mark(take(X, Y)) >= a!6220!6220take(mark(X), mark(Y)) 
  mark(X) >= mark(X) 
  mark(_|_) > _|_ 
  mark(_|_) > _|_ 
  mark(s(X)) >= s(X) 
  mark(_|_) >= _|_ 
  mark(cons(X, Y)) >= cons(X, Y) 
  mark(_|_) >= _|_ 
  a!6220!6220eq(X, Y) >= eq(X, Y) 
  a!6220!6220inf(X) >= inf(X) 
  a!6220!6220take(X, Y) >= take(X, Y) 
  X >= X 

With these choices, we have:

  1] a!6220!6220eq(_|_, _|_) >= _|_  by (Bot) 

  2] a!6220!6220eq(s(X), s(Y)) >= a!6220!6220eq(X, Y)  because [3], by (Star) 
  3] a!6220!6220eq*(s(X), s(Y)) >= a!6220!6220eq(X, Y)  because a!6220!6220eq in Mul, [4] and [7], by (Stat) 
  4] s(X) >= X  because [5], by (Star) 
  5] s*(X) >= X  because [6], by (Select) 
  6] X >= X  by (Meta) 
  7] s(Y) > Y  because [8], by definition 
  8] s*(Y) >= Y  because [9], by (Select) 
  9] Y >= Y  by (Meta) 

  10] a!6220!6220eq(X, Y) >= _|_  by (Bot) 

  11] a!6220!6220inf(X) >= cons(X, inf(s(X)))  because [12], by (Star) 
  12] a!6220!6220inf*(X) >= cons(X, inf(s(X)))  because a!6220!6220inf > cons, [13] and [14], by (Copy) 
  13] a!6220!6220inf*(X) >= X  because [6], by (Select) 
  14] a!6220!6220inf*(X) >= inf(s(X))  because a!6220!6220inf > inf and [15], by (Copy) 
  15] a!6220!6220inf*(X) >= s(X)  because a!6220!6220inf > s and [13], by (Copy) 

  16] a!6220!6220take(_|_, X) >= _|_  by (Bot) 

  17] a!6220!6220take(s(X), cons(Y, Z)) > cons(Y, take(X, Z))  because [18], by definition 
  18] a!6220!6220take*(s(X), cons(Y, Z)) >= cons(Y, take(X, Z))  because a!6220!6220take > cons, [19] and [22], by (Copy) 
  19] a!6220!6220take*(s(X), cons(Y, Z)) >= Y  because [20], by (Select) 
  20] cons(Y, Z) >= Y  because [21], by (Star) 
  21] cons*(Y, Z) >= Y  because [9], by (Select) 
  22] a!6220!6220take*(s(X), cons(Y, Z)) >= take(X, Z)  because a!6220!6220take = take, a!6220!6220take in Mul, [4] and [23], by (Stat) 
  23] cons(Y, Z) > Z  because [24], by definition 
  24] cons*(Y, Z) >= Z  because [25], by (Select) 
  25] Z >= Z  by (Meta) 

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

  27] cons(X, Y) >= s(Y)  because [28], by (Star) 
  28] cons*(X, Y) >= s(Y)  because cons > s and [29], by (Copy) 
  29] cons*(X, Y) >= Y  because [25], by (Select) 

  30] mark(eq(X, Y)) >= a!6220!6220eq(X, Y)  because [31], by (Star) 
  31] mark*(eq(X, Y)) >= a!6220!6220eq(X, Y)  because mark > a!6220!6220eq, [32] and [36], by (Copy) 
  32] mark*(eq(X, Y)) >= X  because [33], by (Select) 
  33] eq(X, Y) >= X  because [34], by (Star) 
  34] eq*(X, Y) >= X  because [35], by (Select) 
  35] X >= X  by (Meta) 
  36] mark*(eq(X, Y)) >= Y  because [37], by (Select) 
  37] eq(X, Y) >= Y  because [38], by (Star) 
  38] eq*(X, Y) >= Y  because [39], by (Select) 
  39] Y >= Y  by (Meta) 

  40] mark(inf(X)) > a!6220!6220inf(mark(X))  because [41], by definition 
  41] mark*(inf(X)) >= a!6220!6220inf(mark(X))  because mark > a!6220!6220inf and [42], by (Copy) 
  42] mark*(inf(X)) >= mark(X)  because mark in Mul and [43], by (Stat) 
  43] inf(X) > X  because [44], by definition 
  44] inf*(X) >= X  because [6], by (Select) 

  45] mark(take(X, Y)) >= a!6220!6220take(mark(X), mark(Y))  because [46], by (Star) 
  46] mark*(take(X, Y)) >= a!6220!6220take(mark(X), mark(Y))  because mark > a!6220!6220take, [47] and [50], by (Copy) 
  47] mark*(take(X, Y)) >= mark(X)  because mark in Mul and [48], by (Stat) 
  48] take(X, Y) > X  because [49], by definition 
  49] take*(X, Y) >= X  because [35], by (Select) 
  50] mark*(take(X, Y)) >= mark(Y)  because mark in Mul and [51], by (Stat) 
  51] take(X, Y) > Y  because [52], by definition 
  52] take*(X, Y) >= Y  because [39], by (Select) 

  53] mark(X) >= mark(X)  because mark in Mul and [54], by (Fun) 
  54] X >= X  by (Meta) 

  55] mark(_|_) > _|_  because [56], by definition 
  56] mark*(_|_) >= _|_  by (Bot) 

  57] mark(_|_) > _|_  because [58], by definition 
  58] mark*(_|_) >= _|_  by (Bot) 

  59] mark(s(X)) >= s(X)  because [60], by (Star) 
  60] mark*(s(X)) >= s(X)  because [61], by (Select) 
  61] s(X) >= s(X)  because s in Mul and [62], by (Fun) 
  62] X >= X  by (Meta) 

  63] mark(_|_) >= _|_  by (Bot) 

  64] mark(cons(X, Y)) >= cons(X, Y)  because [65], by (Star) 
  65] mark*(cons(X, Y)) >= cons(X, Y)  because mark > cons, [66] and [69], by (Copy) 
  66] mark*(cons(X, Y)) >= X  because [67], by (Select) 
  67] cons(X, Y) >= X  because [68], by (Star) 
  68] cons*(X, Y) >= X  because [35], by (Select) 
  69] mark*(cons(X, Y)) >= Y  because [70], by (Select) 
  70] cons(X, Y) >= Y  because [71], by (Star) 
  71] cons*(X, Y) >= Y  because [39], by (Select) 

  72] mark(_|_) >= _|_  by (Bot) 

  73] a!6220!6220eq(X, Y) >= eq(X, Y)  because [74], by (Star) 
  74] a!6220!6220eq*(X, Y) >= eq(X, Y)  because a!6220!6220eq > eq, [75] and [76], by (Copy) 
  75] a!6220!6220eq*(X, Y) >= X  because [35], by (Select) 
  76] a!6220!6220eq*(X, Y) >= Y  because [39], by (Select) 

  77] a!6220!6220inf(X) >= inf(X)  because [78], by (Star) 
  78] a!6220!6220inf*(X) >= inf(X)  because a!6220!6220inf > inf and [13], by (Copy) 

  79] a!6220!6220take(X, Y) >= take(X, Y)  because a!6220!6220take = take, a!6220!6220take in Mul, [80] and [81], by (Fun) 
  80] X >= X  by (Meta) 
  81] Y >= Y  by (Meta) 

  82] X >= X  by (Meta) 

We can thus remove the following rules:

  a!6220!6220take(s(X), cons(Y, Z)) => cons(Y, take(X, Z)) 
  mark(inf(X)) => a!6220!6220inf(mark(X)) 
  mark(0) => 0 
  mark(true) => true 

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!6220eq(0, 0) >? true 
  a!6220!6220eq(s(X), s(Y)) >? a!6220!6220eq(X, Y) 
  a!6220!6220eq(X, Y) >? false 
  a!6220!6220inf(X) >? cons(X, inf(s(X))) 
  a!6220!6220take(0, X) >? nil 
  a!6220!6220length(nil) >? 0 
  a!6220!6220length(cons(X, Y)) >? s(length(Y)) 
  mark(eq(X, Y)) >? a!6220!6220eq(X, Y) 
  mark(take(X, Y)) >? a!6220!6220take(mark(X), mark(Y)) 
  mark(length(X)) >? a!6220!6220length(mark(X)) 
  mark(s(X)) >? s(X) 
  mark(false) >? false 
  mark(cons(X, Y)) >? cons(X, Y) 
  mark(nil) >? nil 
  a!6220!6220eq(X, Y) >? eq(X, Y) 
  a!6220!6220inf(X) >? inf(X) 
  a!6220!6220take(X, Y) >? take(X, Y) 
  a!6220!6220length(X) >? length(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220eq = \y0y1.2 + y0 + 2y1 
  a!6220!6220inf = \y0.3 + 3y0 
  a!6220!6220length = \y0.y0 
  a!6220!6220take = \y0y1.2 + y0 + y1 
  cons = \y0y1.2 + y0 + y1 
  eq = \y0y1.1 + y0 + 2y1 
  false = 0 
  inf = \y0.y0 
  length = \y0.y0 
  mark = \y0.2y0 
  nil = 0 
  s = \y0.y0 
  take = \y0y1.1 + y0 + y1 
  true = 0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220eq(0, 0)]] = 2 > 0 = [[true]] 
  [[a!6220!6220eq(s(_x0), s(_x1))]] = 2 + x0 + 2x1 >= 2 + x0 + 2x1 = [[a!6220!6220eq(_x0, _x1)]] 
  [[a!6220!6220eq(_x0, _x1)]] = 2 + x0 + 2x1 > 0 = [[false]] 
  [[a!6220!6220inf(_x0)]] = 3 + 3x0 > 2 + 2x0 = [[cons(_x0, inf(s(_x0)))]] 
  [[a!6220!6220take(0, _x0)]] = 2 + x0 > 0 = [[nil]] 
  [[a!6220!6220length(nil)]] = 0 >= 0 = [[0]] 
  [[a!6220!6220length(cons(_x0, _x1))]] = 2 + x0 + x1 > x1 = [[s(length(_x1))]] 
  [[mark(eq(_x0, _x1))]] = 2 + 2x0 + 4x1 >= 2 + x0 + 2x1 = [[a!6220!6220eq(_x0, _x1)]] 
  [[mark(take(_x0, _x1))]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[a!6220!6220take(mark(_x0), mark(_x1))]] 
  [[mark(length(_x0))]] = 2x0 >= 2x0 = [[a!6220!6220length(mark(_x0))]] 
  [[mark(s(_x0))]] = 2x0 >= x0 = [[s(_x0)]] 
  [[mark(false)]] = 0 >= 0 = [[false]] 
  [[mark(cons(_x0, _x1))]] = 4 + 2x0 + 2x1 > 2 + x0 + x1 = [[cons(_x0, _x1)]] 
  [[mark(nil)]] = 0 >= 0 = [[nil]] 
  [[a!6220!6220eq(_x0, _x1)]] = 2 + x0 + 2x1 > 1 + x0 + 2x1 = [[eq(_x0, _x1)]] 
  [[a!6220!6220inf(_x0)]] = 3 + 3x0 > x0 = [[inf(_x0)]] 
  [[a!6220!6220take(_x0, _x1)]] = 2 + x0 + x1 > 1 + x0 + x1 = [[take(_x0, _x1)]] 
  [[a!6220!6220length(_x0)]] = x0 >= x0 = [[length(_x0)]] 

We can thus remove the following rules:

  a!6220!6220eq(0, 0) => true 
  a!6220!6220eq(X, Y) => false 
  a!6220!6220inf(X) => cons(X, inf(s(X))) 
  a!6220!6220take(0, X) => nil 
  a!6220!6220length(cons(X, Y)) => s(length(Y)) 
  mark(cons(X, Y)) => cons(X, Y) 
  a!6220!6220eq(X, Y) => eq(X, Y) 
  a!6220!6220inf(X) => inf(X) 
  a!6220!6220take(X, Y) => take(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]):

  a!6220!6220eq(s(X), s(Y)) >? a!6220!6220eq(X, Y) 
  a!6220!6220length(nil) >? 0 
  mark(eq(X, Y)) >? a!6220!6220eq(X, Y) 
  mark(take(X, Y)) >? a!6220!6220take(mark(X), mark(Y)) 
  mark(length(X)) >? a!6220!6220length(mark(X)) 
  mark(s(X)) >? s(X) 
  mark(false) >? false 
  mark(nil) >? nil 
  a!6220!6220length(X) >? length(X) 

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

The following interpretation satisfies the requirements:

  0 = 0 
  a!6220!6220eq = \y0y1.y1 + 2y0 
  a!6220!6220length = \y0.1 + 2y0 
  a!6220!6220take = \y0y1.y0 + y1 
  eq = \y0y1.3 + 3y0 + 3y1 
  false = 1 
  length = \y0.1 + 2y0 
  mark = \y0.2y0 
  nil = 0 
  s = \y0.y0 
  take = \y0y1.3 + 3y0 + 3y1 

Using this interpretation, the requirements translate to:

  [[a!6220!6220eq(s(_x0), s(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[a!6220!6220eq(_x0, _x1)]] 
  [[a!6220!6220length(nil)]] = 1 > 0 = [[0]] 
  [[mark(eq(_x0, _x1))]] = 6 + 6x0 + 6x1 > x1 + 2x0 = [[a!6220!6220eq(_x0, _x1)]] 
  [[mark(take(_x0, _x1))]] = 6 + 6x0 + 6x1 > 2x0 + 2x1 = [[a!6220!6220take(mark(_x0), mark(_x1))]] 
  [[mark(length(_x0))]] = 2 + 4x0 > 1 + 4x0 = [[a!6220!6220length(mark(_x0))]] 
  [[mark(s(_x0))]] = 2x0 >= x0 = [[s(_x0)]] 
  [[mark(false)]] = 2 > 1 = [[false]] 
  [[mark(nil)]] = 0 >= 0 = [[nil]] 
  [[a!6220!6220length(_x0)]] = 1 + 2x0 >= 1 + 2x0 = [[length(_x0)]] 

We can thus remove the following rules:

  a!6220!6220length(nil) => 0 
  mark(eq(X, Y)) => a!6220!6220eq(X, Y) 
  mark(take(X, Y)) => a!6220!6220take(mark(X), mark(Y)) 
  mark(length(X)) => a!6220!6220length(mark(X)) 
  mark(false) => false 

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!6220eq(s(X), s(Y)) >? a!6220!6220eq(X, Y) 
  mark(s(X)) >? s(X) 
  mark(nil) >? nil 
  a!6220!6220length(X) >? length(X) 

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

The following interpretation satisfies the requirements:

  a!6220!6220eq = \y0y1.y0 + y1 
  a!6220!6220length = \y0.3 + 3y0 
  length = \y0.y0 
  mark = \y0.3 + 3y0 
  nil = 0 
  s = \y0.3y0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220eq(s(_x0), s(_x1))]] = 3x0 + 3x1 >= x0 + x1 = [[a!6220!6220eq(_x0, _x1)]] 
  [[mark(s(_x0))]] = 3 + 9x0 > 3x0 = [[s(_x0)]] 
  [[mark(nil)]] = 3 > 0 = [[nil]] 
  [[a!6220!6220length(_x0)]] = 3 + 3x0 > x0 = [[length(_x0)]] 

We can thus remove the following rules:

  mark(s(X)) => s(X) 
  mark(nil) => nil 
  a!6220!6220length(X) => length(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!6220eq(s(X), s(Y)) >? a!6220!6220eq(X, Y) 

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

The following interpretation satisfies the requirements:

  a!6220!6220eq = \y0y1.y0 + y1 
  s = \y0.3 + 3y0 

Using this interpretation, the requirements translate to:

  [[a!6220!6220eq(s(_x0), s(_x1))]] = 6 + 3x0 + 3x1 > x0 + x1 = [[a!6220!6220eq(_x0, _x1)]] 

We can thus remove the following rules:

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