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

  !plus : [o * o] --> o 
  a : [] --> o 
  b : [] --> o 
  f : [o * o] --> o 

  !plus(a, b) => !plus(b, a) 
  !plus(a, !plus(b, X)) => !plus(b, !plus(a, X)) 
  !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, Z)) 
  f(a, X) => a 
  f(b, X) => b 
  f(!plus(X, Y), Z) => !plus(f(X, Z), f(Y, 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]):

  !plus(a, b) >? !plus(b, a) 
  !plus(a, !plus(b, X)) >? !plus(b, !plus(a, X)) 
  !plus(!plus(X, Y), Z) >? !plus(X, !plus(Y, Z)) 
  f(a, X) >? a 
  f(b, X) >? b 
  f(!plus(X, Y), Z) >? !plus(f(X, Z), f(Y, Z)) 

about to try horpo

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

We choose Lex = {!plus} and Mul = {a, b, f}, and the following precedence: f > !plus > a > b

With these choices, we have:

  1] !plus(a, b) >= !plus(b, a)  because [2], by (Star) 
  2] !plus*(a, b) >= !plus(b, a)  because [3], [5] and [6], by (Stat) 
  3] a > b  because [4], by definition 
  4] a* >= b  because a > b, by (Copy) 
  5] !plus*(a, b) >= b  because !plus > b, by (Copy) 
  6] !plus*(a, b) >= a  because !plus > a, by (Copy) 

  7] !plus(a, !plus(b, X)) > !plus(b, !plus(a, X))  because [8], by definition 
  8] !plus*(a, !plus(b, X)) >= !plus(b, !plus(a, X))  because [3], [9] and [10], by (Stat) 
  9] !plus*(a, !plus(b, X)) >= b  because !plus > b, by (Copy) 
  10] !plus*(a, !plus(b, X)) >= !plus(a, X)  because [11], [12], [15] and [16], by (Stat) 
  11] a >= a  by (Fun) 
  12] !plus(b, X) > X  because [13], by definition 
  13] !plus*(b, X) >= X  because [14], by (Select) 
  14] X >= X  by (Meta) 
  15] !plus*(a, !plus(b, X)) >= a  because !plus > a, by (Copy) 
  16] !plus*(a, !plus(b, X)) >= X  because [17], by (Select) 
  17] !plus(b, X) >= X  because [13], by (Star) 

  18] !plus(!plus(X, Y), Z) > !plus(X, !plus(Y, Z))  because [19], by definition 
  19] !plus*(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z))  because [20], [23] and [25], by (Stat) 
  20] !plus(X, Y) > X  because [21], by definition 
  21] !plus*(X, Y) >= X  because [22], by (Select) 
  22] X >= X  by (Meta) 
  23] !plus*(!plus(X, Y), Z) >= X  because [24], by (Select) 
  24] !plus(X, Y) >= X  because [21], by (Star) 
  25] !plus*(!plus(X, Y), Z) >= !plus(Y, Z)  because [26], [29] and [31], by (Stat) 
  26] !plus(X, Y) > Y  because [27], by definition 
  27] !plus*(X, Y) >= Y  because [28], by (Select) 
  28] Y >= Y  by (Meta) 
  29] !plus*(!plus(X, Y), Z) >= Y  because [30], by (Select) 
  30] !plus(X, Y) >= Y  because [27], by (Star) 
  31] !plus*(!plus(X, Y), Z) >= Z  because [14], by (Select) 

  32] f(a, X) >= a  because [33], by (Star) 
  33] f*(a, X) >= a  because f > a, by (Copy) 

  34] f(b, X) >= b  because [35], by (Star) 
  35] f*(b, X) >= b  because f > b, by (Copy) 

  36] f(!plus(X, Y), Z) >= !plus(f(X, Z), f(Y, Z))  because [37], by (Star) 
  37] f*(!plus(X, Y), Z) >= !plus(f(X, Z), f(Y, Z))  because f > !plus, [38] and [40], by (Copy) 
  38] f*(!plus(X, Y), Z) >= f(X, Z)  because f in Mul, [20] and [39], by (Stat) 
  39] Z >= Z  by (Meta) 
  40] f*(!plus(X, Y), Z) >= f(Y, Z)  because f in Mul, [26] and [39], by (Stat) 

We can thus remove the following rules:

  !plus(a, !plus(b, X)) => !plus(b, !plus(a, X)) 
  !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, 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]):

  !plus(a, b) >? !plus(b, a) 
  f(a, X) >? a 
  f(b, X) >? b 
  f(!plus(X, Y), Z) >? !plus(f(X, Z), f(Y, Z)) 

about to try horpo

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

We choose Lex = {} and Mul = {!plus, a, b, f}, and the following precedence: b > f > !plus > a

With these choices, we have:

  1] !plus(a, b) >= !plus(b, a)  because !plus in Mul, [2] and [3], by (Fun) 
  2] a >= a  by (Fun) 
  3] b >= b  by (Fun) 

  4] f(a, X) >= a  because [5], by (Star) 
  5] f*(a, X) >= a  because f > a, by (Copy) 

  6] f(b, X) >= b  because [7], by (Star) 
  7] f*(b, X) >= b  because [3], by (Select) 

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

We can thus remove the following rules:

  f(!plus(X, Y), Z) => !plus(f(X, Z), f(Y, 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]):

  !plus(a, b) >? !plus(b, a) 
  f(a, X) >? a 
  f(b, X) >? b 

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

The following interpretation satisfies the requirements:

  !plus = \y0y1.y1 + 2y0 
  a = 0 
  b = 0 
  f = \y0y1.3 + y1 + 3y0 

Using this interpretation, the requirements translate to:

  [[!plus(a, b)]] = 0 >= 0 = [[!plus(b, a)]] 
  [[f(a, _x0)]] = 3 + x0 > 0 = [[a]] 
  [[f(b, _x0)]] = 3 + x0 > 0 = [[b]] 

We can thus remove the following rules:

  f(a, X) => a 
  f(b, X) => b 

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(a, b) >? !plus(b, a) 

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

The following interpretation satisfies the requirements:

  !plus = \y0y1.y0 + 2y1 
  a = 0 
  b = 2 

Using this interpretation, the requirements translate to:

  [[!plus(a, b)]] = 4 > 2 = [[!plus(b, a)]] 

We can thus remove the following rules:

  !plus(a, b) => !plus(b, a) 

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.