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

  and : [o * o] --> o 
  not : [o] --> o 
  or : [o * o] --> o 

  not(and(X, Y)) => or(not(X), not(Y)) 
  not(or(X, Y)) => and(not(X), not(Y)) 
  and(X, or(Y, Z)) => or(and(X, Y), and(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]):

  not(and(X, Y)) >? or(not(X), not(Y)) 
  not(or(X, Y)) >? and(not(X), not(Y)) 
  and(X, or(Y, Z)) >? or(and(X, Y), and(X, Z)) 

about to try horpo

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

We choose Lex = {} and Mul = {and, not, or}, and the following precedence: not > and > or

With these choices, we have:

  1] not(and(X, Y)) >= or(not(X), not(Y))  because [2], by (Star) 
  2] not*(and(X, Y)) >= or(not(X), not(Y))  because not > or, [3] and [7], by (Copy) 
  3] not*(and(X, Y)) >= not(X)  because not in Mul and [4], by (Stat) 
  4] and(X, Y) > X  because [5], by definition 
  5] and*(X, Y) >= X  because [6], by (Select) 
  6] X >= X  by (Meta) 
  7] not*(and(X, Y)) >= not(Y)  because not in Mul and [8], by (Stat) 
  8] and(X, Y) > Y  because [9], by definition 
  9] and*(X, Y) >= Y  because [10], by (Select) 
  10] Y >= Y  by (Meta) 

  11] not(or(X, Y)) > and(not(X), not(Y))  because [12], by definition 
  12] not*(or(X, Y)) >= and(not(X), not(Y))  because not > and, [13] and [16], by (Copy) 
  13] not*(or(X, Y)) >= not(X)  because not in Mul and [14], by (Stat) 
  14] or(X, Y) > X  because [15], by definition 
  15] or*(X, Y) >= X  because [6], by (Select) 
  16] not*(or(X, Y)) >= not(Y)  because not in Mul and [17], by (Stat) 
  17] or(X, Y) > Y  because [18], by definition 
  18] or*(X, Y) >= Y  because [10], by (Select) 

  19] and(X, or(Y, Z)) > or(and(X, Y), and(X, Z))  because [20], by definition 
  20] and*(X, or(Y, Z)) >= or(and(X, Y), and(X, Z))  because and > or, [21] and [25], by (Copy) 
  21] and*(X, or(Y, Z)) >= and(X, Y)  because and in Mul, [22] and [23], by (Stat) 
  22] X >= X  by (Meta) 
  23] or(Y, Z) > Y  because [24], by definition 
  24] or*(Y, Z) >= Y  because [10], by (Select) 
  25] and*(X, or(Y, Z)) >= and(X, Z)  because and in Mul, [22] and [26], by (Stat) 
  26] or(Y, Z) > Z  because [27], by definition 
  27] or*(Y, Z) >= Z  because [28], by (Select) 
  28] Z >= Z  by (Meta) 

We can thus remove the following rules:

  not(or(X, Y)) => and(not(X), not(Y)) 
  and(X, or(Y, Z)) => or(and(X, Y), and(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]):

  not(and(X, Y)) >? or(not(X), not(Y)) 

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

The following interpretation satisfies the requirements:

  and = \y0y1.3 + 3y0 + 3y1 
  not = \y0.3y0 
  or = \y0y1.y0 + y1 

Using this interpretation, the requirements translate to:

  [[not(and(_x0, _x1))]] = 9 + 9x0 + 9x1 > 3x0 + 3x1 = [[or(not(_x0), not(_x1))]] 

We can thus remove the following rules:

  not(and(X, Y)) => or(not(X), not(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.