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

  !870 : [o * o] --> o 
  false : [] --> o 
  mem : [o * o] --> o 
  nil : [] --> o 
  or : [o * o] --> o 
  set : [o] --> o 
  true : [] --> o 
  union : [o * o] --> o 

  or(true, X) => true 
  or(X, true) => true 
  or(false, false) => false 
  mem(X, nil) => false 
  mem(X, set(Y)) => !870(X, Y) 
  mem(X, union(Y, Z)) => or(mem(X, Y), mem(X, 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]):

  or(true, X) >? true 
  or(X, true) >? true 
  or(false, false) >? false 
  mem(X, nil) >? false 
  mem(X, set(Y)) >? !870(X, Y) 
  mem(X, union(Y, Z)) >? or(mem(X, Y), mem(X, Z)) 

about to try horpo

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

Argument functions:

  [[true]] = _|_ 

We choose Lex = {} and Mul = {!870, false, mem, nil, or, set, union}, and the following precedence: mem > or > false > nil > !870 > set > union

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

  or(_|_, X) >= _|_ 
  or(X, _|_) >= _|_ 
  or(false, false) > false 
  mem(X, nil) >= false 
  mem(X, set(Y)) >= !870(X, Y) 
  mem(X, union(Y, Z)) >= or(mem(X, Y), mem(X, Z)) 

With these choices, we have:

  1] or(_|_, X) >= _|_  by (Bot) 

  2] or(X, _|_) >= _|_  by (Bot) 

  3] or(false, false) > false  because [4], by definition 
  4] or*(false, false) >= false  because or > false, by (Copy) 

  5] mem(X, nil) >= false  because [6], by (Star) 
  6] mem*(X, nil) >= false  because mem > false, by (Copy) 

  7] mem(X, set(Y)) >= !870(X, Y)  because [8], by (Star) 
  8] mem*(X, set(Y)) >= !870(X, Y)  because mem > !870, [9] and [11], by (Copy) 
  9] mem*(X, set(Y)) >= X  because [10], by (Select) 
  10] X >= X  by (Meta) 
  11] mem*(X, set(Y)) >= Y  because [12], by (Select) 
  12] set(Y) >= Y  because [13], by (Star) 
  13] set*(Y) >= Y  because [14], by (Select) 
  14] Y >= Y  by (Meta) 

  15] mem(X, union(Y, Z)) >= or(mem(X, Y), mem(X, Z))  because [16], by (Star) 
  16] mem*(X, union(Y, Z)) >= or(mem(X, Y), mem(X, Z))  because mem > or, [17] and [21], by (Copy) 
  17] mem*(X, union(Y, Z)) >= mem(X, Y)  because mem in Mul, [18] and [19], by (Stat) 
  18] X >= X  by (Meta) 
  19] union(Y, Z) > Y  because [20], by definition 
  20] union*(Y, Z) >= Y  because [14], by (Select) 
  21] mem*(X, union(Y, Z)) >= mem(X, Z)  because mem in Mul, [18] and [22], by (Stat) 
  22] union(Y, Z) > Z  because [23], by definition 
  23] union*(Y, Z) >= Z  because [24], by (Select) 
  24] Z >= Z  by (Meta) 

We can thus remove the following rules:

  or(false, 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]):

  or(true, X) >? true 
  or(X, true) >? true 
  mem(X, nil) >? false 
  mem(X, set(Y)) >? !870(X, Y) 
  mem(X, union(Y, Z)) >? or(mem(X, Y), mem(X, Z)) 

about to try horpo

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

Argument functions:

  [[false]] = _|_ 
  [[set(x_1)]] = x_1 
  [[true]] = _|_ 

We choose Lex = {} and Mul = {!870, mem, nil, or, union}, and the following precedence: !870 = mem > or > nil > union

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

  or(_|_, X) > _|_ 
  or(X, _|_) >= _|_ 
  mem(X, nil) >= _|_ 
  mem(X, Y) >= !870(X, Y) 
  mem(X, union(Y, Z)) >= or(mem(X, Y), mem(X, Z)) 

With these choices, we have:

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

  3] or(X, _|_) >= _|_  by (Bot) 

  4] mem(X, nil) >= _|_  by (Bot) 

  5] mem(X, Y) >= !870(X, Y)  because mem = !870, mem in Mul, [6] and [7], by (Fun) 
  6] X >= X  by (Meta) 
  7] Y >= Y  by (Meta) 

  8] mem(X, union(Y, Z)) >= or(mem(X, Y), mem(X, Z))  because [9], by (Star) 
  9] mem*(X, union(Y, Z)) >= or(mem(X, Y), mem(X, Z))  because mem > or, [10] and [13], by (Copy) 
  10] mem*(X, union(Y, Z)) >= mem(X, Y)  because mem in Mul, [6] and [11], by (Stat) 
  11] union(Y, Z) > Y  because [12], by definition 
  12] union*(Y, Z) >= Y  because [7], by (Select) 
  13] mem*(X, union(Y, Z)) >= mem(X, Z)  because mem in Mul, [6] and [14], by (Stat) 
  14] union(Y, Z) > Z  because [15], by definition 
  15] union*(Y, Z) >= Z  because [16], by (Select) 
  16] Z >= Z  by (Meta) 

We can thus remove the following rules:

  or(true, X) => 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]):

  or(X, true) >? true 
  mem(X, nil) >? false 
  mem(X, set(Y)) >? !870(X, Y) 
  mem(X, union(Y, Z)) >? or(mem(X, Y), mem(X, Z)) 

about to try horpo

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

Argument functions:

  [[false]] = _|_ 
  [[true]] = _|_ 

We choose Lex = {} and Mul = {!870, mem, nil, or, set, union}, and the following precedence: union > nil > !870 = mem > set > or

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

  or(X, _|_) > _|_ 
  mem(X, nil) >= _|_ 
  mem(X, set(Y)) >= !870(X, Y) 
  mem(X, union(Y, Z)) >= or(mem(X, Y), mem(X, Z)) 

With these choices, we have:

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

  3] mem(X, nil) >= _|_  by (Bot) 

  4] mem(X, set(Y)) >= !870(X, Y)  because mem = !870, mem in Mul, [5] and [6], by (Fun) 
  5] X >= X  by (Meta) 
  6] set(Y) >= Y  because [7], by (Star) 
  7] set*(Y) >= Y  because [8], by (Select) 
  8] Y >= Y  by (Meta) 

  9] mem(X, union(Y, Z)) >= or(mem(X, Y), mem(X, Z))  because [10], by (Star) 
  10] mem*(X, union(Y, Z)) >= or(mem(X, Y), mem(X, Z))  because mem > or, [11] and [14], by (Copy) 
  11] mem*(X, union(Y, Z)) >= mem(X, Y)  because mem in Mul, [5] and [12], by (Stat) 
  12] union(Y, Z) > Y  because [13], by definition 
  13] union*(Y, Z) >= Y  because [8], by (Select) 
  14] mem*(X, union(Y, Z)) >= mem(X, Z)  because mem in Mul, [5] and [15], by (Stat) 
  15] union(Y, Z) > Z  because [16], by definition 
  16] union*(Y, Z) >= Z  because [17], by (Select) 
  17] Z >= Z  by (Meta) 

We can thus remove the following rules:

  or(X, 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]):

  mem(X, nil) >? false 
  mem(X, set(Y)) >? !870(X, Y) 
  mem(X, union(Y, Z)) >? or(mem(X, Y), mem(X, Z)) 

about to try horpo

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

Argument functions:

  [[false]] = _|_ 

We choose Lex = {} and Mul = {!870, mem, nil, or, set, union}, and the following precedence: mem > nil > or > union > !870 > set

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

  mem(X, nil) > _|_ 
  mem(X, set(Y)) >= !870(X, Y) 
  mem(X, union(Y, Z)) > or(mem(X, Y), mem(X, Z)) 

With these choices, we have:

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

  3] mem(X, set(Y)) >= !870(X, Y)  because [4], by (Star) 
  4] mem*(X, set(Y)) >= !870(X, Y)  because mem > !870, [5] and [7], by (Copy) 
  5] mem*(X, set(Y)) >= X  because [6], by (Select) 
  6] X >= X  by (Meta) 
  7] mem*(X, set(Y)) >= Y  because [8], by (Select) 
  8] set(Y) >= Y  because [9], by (Star) 
  9] set*(Y) >= Y  because [10], by (Select) 
  10] Y >= Y  by (Meta) 

  11] mem(X, union(Y, Z)) > or(mem(X, Y), mem(X, Z))  because [12], by definition 
  12] mem*(X, union(Y, Z)) >= or(mem(X, Y), mem(X, Z))  because mem > or, [13] and [17], by (Copy) 
  13] mem*(X, union(Y, Z)) >= mem(X, Y)  because mem in Mul, [14] and [15], by (Stat) 
  14] X >= X  by (Meta) 
  15] union(Y, Z) > Y  because [16], by definition 
  16] union*(Y, Z) >= Y  because [10], by (Select) 
  17] mem*(X, union(Y, Z)) >= mem(X, Z)  because mem in Mul, [14] and [18], by (Stat) 
  18] union(Y, Z) > Z  because [19], by definition 
  19] union*(Y, Z) >= Z  because [20], by (Select) 
  20] Z >= Z  by (Meta) 

We can thus remove the following rules:

  mem(X, nil) => false 
  mem(X, union(Y, Z)) => or(mem(X, Y), mem(X, 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]):

  mem(X, set(Y)) >? !870(X, Y) 

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

The following interpretation satisfies the requirements:

  !870 = \y0y1.y0 + y1 
  mem = \y0y1.3 + 3y0 + 3y1 
  set = \y0.3 + 3y0 

Using this interpretation, the requirements translate to:

  [[mem(_x0, set(_x1))]] = 12 + 3x0 + 9x1 > x0 + x1 = [[!870(_x0, _x1)]] 

We can thus remove the following rules:

  mem(X, set(Y)) => !870(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.