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

  F : [] --> o 
  T : [] --> o 
  and : [o * o] --> o 
  equiv : [o * o] --> o 
  impl : [o * o] --> o 
  neg : [o] --> o 
  or : [o * o] --> o 
  xor : [o * o] --> o 

  xor(X, F) => X 
  xor(X, neg(X)) => F 
  and(X, T) => X 
  and(X, F) => F 
  and(X, X) => X 
  and(xor(X, Y), Z) => xor(and(X, Z), and(Y, Z)) 
  xor(X, X) => F 
  impl(X, Y) => xor(and(X, Y), xor(X, T)) 
  or(X, Y) => xor(and(X, Y), xor(X, Y)) 
  equiv(X, Y) => xor(X, xor(Y, T)) 
  neg(X) => xor(X, T) 

We use rule removal, following [Kop12, Theorem 2.23].

This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]):

  xor(X, F) >? X 
  xor(X, neg(X)) >? F 
  and(X, T) >? X 
  and(X, F) >? F 
  and(X, X) >? X 
  and(xor(X, Y), Z) >? xor(and(X, Z), and(Y, Z)) 
  xor(X, X) >? F 
  impl(X, Y) >? xor(and(X, Y), xor(X, T)) 
  or(X, Y) >? xor(and(X, Y), xor(X, Y)) 
  equiv(X, Y) >? xor(X, xor(Y, T)) 
  neg(X) >? xor(X, T) 

about to try horpo

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

Argument functions:

  [[T]] = _|_ 

We choose Lex = {} and Mul = {F, and, equiv, impl, neg, or, xor}, and the following precedence: equiv > impl > neg > or > and > xor > F

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

  xor(X, F) > X 
  xor(X, neg(X)) >= F 
  and(X, _|_) > X 
  and(X, F) >= F 
  and(X, X) >= X 
  and(xor(X, Y), Z) > xor(and(X, Z), and(Y, Z)) 
  xor(X, X) > F 
  impl(X, Y) > xor(and(X, Y), xor(X, _|_)) 
  or(X, Y) > xor(and(X, Y), xor(X, Y)) 
  equiv(X, Y) >= xor(X, xor(Y, _|_)) 
  neg(X) >= xor(X, _|_) 

With these choices, we have:

  1] xor(X, F) > X  because [2], by definition 
  2] xor*(X, F) >= X  because [3], by (Select) 
  3] X >= X  by (Meta) 

  4] xor(X, neg(X)) >= F  because [5], by (Star) 
  5] xor*(X, neg(X)) >= F  because xor > F, by (Copy) 

  6] and(X, _|_) > X  because [7], by definition 
  7] and*(X, _|_) >= X  because [3], by (Select) 

  8] and(X, F) >= F  because [9], by (Star) 
  9] and*(X, F) >= F  because and > F, by (Copy) 

  10] and(X, X) >= X  because [11], by (Star) 
  11] and*(X, X) >= X  because [3], by (Select) 

  12] and(xor(X, Y), Z) > xor(and(X, Z), and(Y, Z))  because [13], by definition 
  13] and*(xor(X, Y), Z) >= xor(and(X, Z), and(Y, Z))  because and > xor, [14] and [18], by (Copy) 
  14] and*(xor(X, Y), Z) >= and(X, Z)  because and in Mul, [15] and [17], by (Stat) 
  15] xor(X, Y) > X  because [16], by definition 
  16] xor*(X, Y) >= X  because [3], by (Select) 
  17] Z >= Z  by (Meta) 
  18] and*(xor(X, Y), Z) >= and(Y, Z)  because and in Mul, [19] and [17], by (Stat) 
  19] xor(X, Y) > Y  because [20], by definition 
  20] xor*(X, Y) >= Y  because [21], by (Select) 
  21] Y >= Y  by (Meta) 

  22] xor(X, X) > F  because [23], by definition 
  23] xor*(X, X) >= F  because xor > F, by (Copy) 

  24] impl(X, Y) > xor(and(X, Y), xor(X, _|_))  because [25], by definition 
  25] impl*(X, Y) >= xor(and(X, Y), xor(X, _|_))  because impl > xor, [26] and [29], by (Copy) 
  26] impl*(X, Y) >= and(X, Y)  because impl > and, [27] and [28], by (Copy) 
  27] impl*(X, Y) >= X  because [3], by (Select) 
  28] impl*(X, Y) >= Y  because [21], by (Select) 
  29] impl*(X, Y) >= xor(X, _|_)  because impl > xor, [27] and [30], by (Copy) 
  30] impl*(X, Y) >= _|_  by (Bot) 

  31] or(X, Y) > xor(and(X, Y), xor(X, Y))  because [32], by definition 
  32] or*(X, Y) >= xor(and(X, Y), xor(X, Y))  because or > xor, [33] and [36], by (Copy) 
  33] or*(X, Y) >= and(X, Y)  because or > and, [34] and [35], by (Copy) 
  34] or*(X, Y) >= X  because [3], by (Select) 
  35] or*(X, Y) >= Y  because [21], by (Select) 
  36] or*(X, Y) >= xor(X, Y)  because or > xor, [34] and [35], by (Copy) 

  37] equiv(X, Y) >= xor(X, xor(Y, _|_))  because [38], by (Star) 
  38] equiv*(X, Y) >= xor(X, xor(Y, _|_))  because equiv > xor, [39] and [40], by (Copy) 
  39] equiv*(X, Y) >= X  because [3], by (Select) 
  40] equiv*(X, Y) >= xor(Y, _|_)  because equiv > xor, [41] and [42], by (Copy) 
  41] equiv*(X, Y) >= Y  because [21], by (Select) 
  42] equiv*(X, Y) >= _|_  by (Bot) 

  43] neg(X) >= xor(X, _|_)  because [44], by (Star) 
  44] neg*(X) >= xor(X, _|_)  because neg > xor, [45] and [46], by (Copy) 
  45] neg*(X) >= X  because [3], by (Select) 
  46] neg*(X) >= _|_  by (Bot) 

We can thus remove the following rules:

  xor(X, F) => X 
  and(X, T) => X 
  and(xor(X, Y), Z) => xor(and(X, Z), and(Y, Z)) 
  xor(X, X) => F 
  impl(X, Y) => xor(and(X, Y), xor(X, T)) 
  or(X, Y) => xor(and(X, Y), xor(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]):

  xor(X, neg(X)) >? F 
  and(X, F) >? F 
  and(X, X) >? X 
  equiv(X, Y) >? xor(X, xor(Y, T)) 
  neg(X) >? xor(X, T) 

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

The following interpretation satisfies the requirements:

  F = 0 
  T = 0 
  and = \y0y1.3 + y0 + 3y1 
  equiv = \y0y1.3 + 3y0 + 3y1 
  neg = \y0.3 + 3y0 
  xor = \y0y1.y0 + y1 

Using this interpretation, the requirements translate to:

  [[xor(_x0, neg(_x0))]] = 3 + 4x0 > 0 = [[F]] 
  [[and(_x0, F)]] = 3 + x0 > 0 = [[F]] 
  [[and(_x0, _x0)]] = 3 + 4x0 > x0 = [[_x0]] 
  [[equiv(_x0, _x1)]] = 3 + 3x0 + 3x1 > x0 + x1 = [[xor(_x0, xor(_x1, T))]] 
  [[neg(_x0)]] = 3 + 3x0 > x0 = [[xor(_x0, T)]] 

We can thus remove the following rules:

  xor(X, neg(X)) => F 
  and(X, F) => F 
  and(X, X) => X 
  equiv(X, Y) => xor(X, xor(Y, T)) 
  neg(X) => xor(X, T) 

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.