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

  !870 : [o * o] --> o 
  !plus!plus : [o * o] --> o 
  f : [o * o] --> o 
  false : [] --> o 
  g : [o * o] --> o 
  max : [o] --> o 
  max!450 : [o * o] --> o 
  mem : [o * o] --> o 
  nil : [] --> o 
  not : [o] --> o 
  null : [o] --> o 
  or : [o * o] --> o 
  true : [] --> o 
  u : [] --> o 

  f(X, nil) => g(nil, X) 
  f(X, g(Y, Z)) => g(f(X, Y), Z) 
  !plus!plus(X, nil) => X 
  !plus!plus(X, g(Y, Z)) => g(!plus!plus(X, Y), Z) 
  null(nil) => true 
  null(g(X, Y)) => false 
  mem(nil, X) => false 
  mem(g(X, Y), Z) => or(!870(Y, Z), mem(X, Z)) 
  mem(X, max(X)) => not(null(X)) 
  max(g(g(nil, X), Y)) => max!450(X, Y) 
  max(g(g(g(X, Y), Z), u)) => max!450(max(g(g(X, Y), Z)), u) 

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(X, nil) >? g(nil, X) 
  f(X, g(Y, Z)) >? g(f(X, Y), Z) 
  !plus!plus(X, nil) >? X 
  !plus!plus(X, g(Y, Z)) >? g(!plus!plus(X, Y), Z) 
  null(nil) >? true 
  null(g(X, Y)) >? false 
  mem(nil, X) >? false 
  mem(g(X, Y), Z) >? or(!870(Y, Z), mem(X, Z)) 
  mem(X, max(X)) >? not(null(X)) 
  max(g(g(nil, X), Y)) >? max!450(X, Y) 
  max(g(g(g(X, Y), Z), u)) >? max!450(max(g(g(X, Y), Z)), u) 

about to try horpo

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

Argument functions:

  [[false]] = _|_ 
  [[nil]] = _|_ 
  [[true]] = _|_ 
  [[u]] = _|_ 

We choose Lex = {} and Mul = {!870, !plus!plus, f, g, max, max!450, mem, not, null, or}, and the following precedence: mem > f > or > not > !plus!plus > !870 > null > max > max!450 > g

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

  f(X, _|_) >= g(_|_, X) 
  f(X, g(Y, Z)) > g(f(X, Y), Z) 
  !plus!plus(X, _|_) >= X 
  !plus!plus(X, g(Y, Z)) >= g(!plus!plus(X, Y), Z) 
  null(_|_) >= _|_ 
  null(g(X, Y)) >= _|_ 
  mem(_|_, X) >= _|_ 
  mem(g(X, Y), Z) >= or(!870(Y, Z), mem(X, Z)) 
  mem(X, max(X)) > not(null(X)) 
  max(g(g(_|_, X), Y)) >= max!450(X, Y) 
  max(g(g(g(X, Y), Z), _|_)) > max!450(max(g(g(X, Y), Z)), _|_) 

With these choices, we have:

  1] f(X, _|_) >= g(_|_, X)  because [2], by (Star) 
  2] f*(X, _|_) >= g(_|_, X)  because f > g, [3] and [4], by (Copy) 
  3] f*(X, _|_) >= _|_  by (Bot) 
  4] f*(X, _|_) >= X  because [5], by (Select) 
  5] X >= X  by (Meta) 

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

  17] !plus!plus(X, _|_) >= X  because [18], by (Star) 
  18] !plus!plus*(X, _|_) >= X  because [9], by (Select) 

  19] !plus!plus(X, g(Y, Z)) >= g(!plus!plus(X, Y), Z)  because [20], by (Star) 
  20] !plus!plus*(X, g(Y, Z)) >= g(!plus!plus(X, Y), Z)  because !plus!plus > g, [21] and [22], by (Copy) 
  21] !plus!plus*(X, g(Y, Z)) >= !plus!plus(X, Y)  because !plus!plus in Mul, [9] and [10], by (Stat) 
  22] !plus!plus*(X, g(Y, Z)) >= Z  because [14], by (Select) 

  23] null(_|_) >= _|_  by (Bot) 

  24] null(g(X, Y)) >= _|_  by (Bot) 

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

  26] mem(g(X, Y), Z) >= or(!870(Y, Z), mem(X, Z))  because [27], by (Star) 
  27] mem*(g(X, Y), Z) >= or(!870(Y, Z), mem(X, Z))  because mem > or, [28] and [33], by (Copy) 
  28] mem*(g(X, Y), Z) >= !870(Y, Z)  because mem > !870, [29] and [32], by (Copy) 
  29] mem*(g(X, Y), Z) >= Y  because [30], by (Select) 
  30] g(X, Y) >= Y  because [31], by (Star) 
  31] g*(X, Y) >= Y  because [12], by (Select) 
  32] mem*(g(X, Y), Z) >= Z  because [16], by (Select) 
  33] mem*(g(X, Y), Z) >= mem(X, Z)  because mem in Mul, [34] and [36], by (Stat) 
  34] g(X, Y) > X  because [35], by definition 
  35] g*(X, Y) >= X  because [9], by (Select) 
  36] Z >= Z  by (Meta) 

  37] mem(X, max(X)) > not(null(X))  because [38], by definition 
  38] mem*(X, max(X)) >= not(null(X))  because mem > not and [39], by (Copy) 
  39] mem*(X, max(X)) >= null(X)  because mem > null and [40], by (Copy) 
  40] mem*(X, max(X)) >= X  because [9], by (Select) 

  41] max(g(g(_|_, X), Y)) >= max!450(X, Y)  because [42], by (Star) 
  42] max*(g(g(_|_, X), Y)) >= max!450(X, Y)  because max > max!450, [43] and [48], by (Copy) 
  43] max*(g(g(_|_, X), Y)) >= X  because [44], by (Select) 
  44] g(g(_|_, X), Y) >= X  because [45], by (Star) 
  45] g*(g(_|_, X), Y) >= X  because [46], by (Select) 
  46] g(_|_, X) >= X  because [47], by (Star) 
  47] g*(_|_, X) >= X  because [9], by (Select) 
  48] max*(g(g(_|_, X), Y)) >= Y  because [49], by (Select) 
  49] g(g(_|_, X), Y) >= Y  because [50], by (Star) 
  50] g*(g(_|_, X), Y) >= Y  because [12], by (Select) 

  51] max(g(g(g(X, Y), Z), _|_)) > max!450(max(g(g(X, Y), Z)), _|_)  because [52], by definition 
  52] max*(g(g(g(X, Y), Z), _|_)) >= max!450(max(g(g(X, Y), Z)), _|_)  because max > max!450, [53] and [59], by (Copy) 
  53] max*(g(g(g(X, Y), Z), _|_)) >= max(g(g(X, Y), Z))  because max in Mul and [54], by (Stat) 
  54] g(g(g(X, Y), Z), _|_) > g(g(X, Y), Z)  because [55], by definition 
  55] g*(g(g(X, Y), Z), _|_) >= g(g(X, Y), Z)  because [56], by (Select) 
  56] g(g(X, Y), Z) >= g(g(X, Y), Z)  because g in Mul, [57] and [36], by (Fun) 
  57] g(X, Y) >= g(X, Y)  because g in Mul, [9] and [58], by (Fun) 
  58] Y >= Y  by (Meta) 
  59] max*(g(g(g(X, Y), Z), _|_)) >= _|_  by (Bot) 

We can thus remove the following rules:

  f(X, g(Y, Z)) => g(f(X, Y), Z) 
  mem(X, max(X)) => not(null(X)) 
  max(g(g(g(X, Y), Z), u)) => max!450(max(g(g(X, Y), Z)), u) 

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(X, nil) >? g(nil, X) 
  !plus!plus(X, nil) >? X 
  !plus!plus(X, g(Y, Z)) >? g(!plus!plus(X, Y), Z) 
  null(nil) >? true 
  null(g(X, Y)) >? false 
  mem(nil, X) >? false 
  mem(g(X, Y), Z) >? or(!870(Y, Z), mem(X, Z)) 
  max(g(g(nil, X), Y)) >? max!450(X, Y) 

about to try horpo

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

Argument functions:

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

We choose Lex = {} and Mul = {!870, !plus!plus, f, g, max, max!450, mem, null, or}, and the following precedence: mem > !870 > f > null > max > or > !plus!plus > max!450 > g

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

  f(X, _|_) > g(_|_, X) 
  !plus!plus(X, _|_) >= X 
  !plus!plus(X, g(Y, Z)) >= g(!plus!plus(X, Y), Z) 
  null(_|_) >= _|_ 
  null(g(X, Y)) >= _|_ 
  mem(_|_, X) >= _|_ 
  mem(g(X, Y), Z) > or(!870(Y, Z), mem(X, Z)) 
  max(g(g(_|_, X), Y)) > max!450(X, Y) 

With these choices, we have:

  1] f(X, _|_) > g(_|_, X)  because [2], by definition 
  2] f*(X, _|_) >= g(_|_, X)  because f > g, [3] and [4], by (Copy) 
  3] f*(X, _|_) >= _|_  by (Bot) 
  4] f*(X, _|_) >= X  because [5], by (Select) 
  5] X >= X  by (Meta) 

  6] !plus!plus(X, _|_) >= X  because [7], by (Star) 
  7] !plus!plus*(X, _|_) >= X  because [5], by (Select) 

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

  19] null(_|_) >= _|_  by (Bot) 

  20] null(g(X, Y)) >= _|_  by (Bot) 

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

  22] mem(g(X, Y), Z) > or(!870(Y, Z), mem(X, Z))  because [23], by definition 
  23] mem*(g(X, Y), Z) >= or(!870(Y, Z), mem(X, Z))  because mem > or, [24] and [29], by (Copy) 
  24] mem*(g(X, Y), Z) >= !870(Y, Z)  because mem > !870, [25] and [28], by (Copy) 
  25] mem*(g(X, Y), Z) >= Y  because [26], by (Select) 
  26] g(X, Y) >= Y  because [27], by (Star) 
  27] g*(X, Y) >= Y  because [14], by (Select) 
  28] mem*(g(X, Y), Z) >= Z  because [18], by (Select) 
  29] mem*(g(X, Y), Z) >= mem(X, Z)  because mem in Mul, [30] and [32], by (Stat) 
  30] g(X, Y) > X  because [31], by definition 
  31] g*(X, Y) >= X  because [11], by (Select) 
  32] Z >= Z  by (Meta) 

  33] max(g(g(_|_, X), Y)) > max!450(X, Y)  because [34], by definition 
  34] max*(g(g(_|_, X), Y)) >= max!450(X, Y)  because max > max!450, [35] and [40], by (Copy) 
  35] max*(g(g(_|_, X), Y)) >= X  because [36], by (Select) 
  36] g(g(_|_, X), Y) >= X  because [37], by (Star) 
  37] g*(g(_|_, X), Y) >= X  because [38], by (Select) 
  38] g(_|_, X) >= X  because [39], by (Star) 
  39] g*(_|_, X) >= X  because [11], by (Select) 
  40] max*(g(g(_|_, X), Y)) >= Y  because [41], by (Select) 
  41] g(g(_|_, X), Y) >= Y  because [42], by (Star) 
  42] g*(g(_|_, X), Y) >= Y  because [14], by (Select) 

We can thus remove the following rules:

  f(X, nil) => g(nil, X) 
  mem(g(X, Y), Z) => or(!870(Y, Z), mem(X, Z)) 
  max(g(g(nil, X), Y)) => max!450(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]):

  !plus!plus(X, nil) >? X 
  !plus!plus(X, g(Y, Z)) >? g(!plus!plus(X, Y), Z) 
  null(nil) >? true 
  null(g(X, Y)) >? false 
  mem(nil, X) >? false 

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

The following interpretation satisfies the requirements:

  !plus!plus = \y0y1.3 + y0 + 3y1 
  false = 0 
  g = \y0y1.3 + y0 + y1 
  mem = \y0y1.3 + y1 + 3y0 
  nil = 3 
  null = \y0.3 + 3y0 
  true = 0 

Using this interpretation, the requirements translate to:

  [[!plus!plus(_x0, nil)]] = 12 + x0 > x0 = [[_x0]] 
  [[!plus!plus(_x0, g(_x1, _x2))]] = 12 + x0 + 3x1 + 3x2 > 6 + x0 + x2 + 3x1 = [[g(!plus!plus(_x0, _x1), _x2)]] 
  [[null(nil)]] = 12 > 0 = [[true]] 
  [[null(g(_x0, _x1))]] = 12 + 3x0 + 3x1 > 0 = [[false]] 
  [[mem(nil, _x0)]] = 12 + x0 > 0 = [[false]] 

We can thus remove the following rules:

  !plus!plus(X, nil) => X 
  !plus!plus(X, g(Y, Z)) => g(!plus!plus(X, Y), Z) 
  null(nil) => true 
  null(g(X, Y)) => false 
  mem(nil, X) => false 

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.