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

  and : [o * o] --> o 
  false : [] --> o 
  or : [o * o] --> o 
  true : [] --> o 

  and(X, or(Y, Z)) => or(and(X, Y), and(X, Z)) 
  and(X, and(Y, Y)) => and(X, Y) 
  or(or(X, Y), and(Y, Z)) => or(X, Y) 
  or(X, and(X, Y)) => X 
  or(true, X) => true 
  or(X, false) => X 
  or(X, X) => X 
  or(X, or(Y, Y)) => or(X, Y) 
  and(X, true) => X 
  and(false, X) => false 
  and(X, X) => X 

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

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

  and(X, or(Y, Z)) >? or(and(X, Y), and(X, Z)) 
  and(X, and(Y, Y)) >? and(X, Y) 
  or(or(X, Y), and(Y, Z)) >? or(X, Y) 
  or(X, and(X, Y)) >? X 
  or(true, X) >? true 
  or(X, false) >? X 
  or(X, X) >? X 
  or(X, or(Y, Y)) >? or(X, Y) 
  and(X, true) >? X 
  and(false, X) >? false 
  and(X, X) >? X 

about to try horpo

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

Argument functions:

  [[false]] = _|_ 

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

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

  and(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) 
  and(X, and(Y, Y)) >= and(X, Y) 
  or(or(X, Y), and(Y, Z)) >= or(X, Y) 
  or(X, and(X, Y)) > X 
  or(true, X) > true 
  or(X, _|_) > X 
  or(X, X) >= X 
  or(X, or(Y, Y)) >= or(X, Y) 
  and(X, true) >= X 
  and(_|_, X) >= _|_ 
  and(X, X) > X 

With these choices, we have:

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

  12] and(X, and(Y, Y)) >= and(X, Y)  because [13], by (Star) 
  13] and*(X, and(Y, Y)) >= and(X, Y)  because and in Mul, [4] and [14], by (Stat) 
  14] and(Y, Y) > Y  because [15], by definition 
  15] and*(Y, Y) >= Y  because [7], by (Select) 

  16] or(or(X, Y), and(Y, Z)) >= or(X, Y)  because or in Mul, [17] and [19], by (Fun) 
  17] or(X, Y) >= X  because [18], by (Star) 
  18] or*(X, Y) >= X  because [4], by (Select) 
  19] and(Y, Z) >= Y  because [20], by (Star) 
  20] and*(Y, Z) >= Y  because [7], by (Select) 

  21] or(X, and(X, Y)) > X  because [22], by definition 
  22] or*(X, and(X, Y)) >= X  because [4], by (Select) 

  23] or(true, X) > true  because [24], by definition 
  24] or*(true, X) >= true  because or = true and or in Mul, by (Stat) 

  25] or(X, _|_) > X  because [26], by definition 
  26] or*(X, _|_) >= X  because [4], by (Select) 

  27] or(X, X) >= X  because [28], by (Star) 
  28] or*(X, X) >= X  because [4], by (Select) 

  29] or(X, or(Y, Y)) >= or(X, Y)  because or in Mul, [4] and [30], by (Fun) 
  30] or(Y, Y) >= Y  because [31], by (Star) 
  31] or*(Y, Y) >= Y  because [7], by (Select) 

  32] and(X, true) >= X  because [33], by (Star) 
  33] and*(X, true) >= X  because [4], by (Select) 

  34] and(_|_, X) >= _|_  by (Bot) 

  35] and(X, X) > X  because [36], by definition 
  36] and*(X, X) >= X  because [4], by (Select) 

We can thus remove the following rules:

  or(X, and(X, Y)) => X 
  or(true, X) => true 
  or(X, false) => X 
  and(X, X) => X 

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

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

  and(X, or(Y, Z)) >? or(and(X, Y), and(X, Z)) 
  and(X, and(Y, Y)) >? and(X, Y) 
  or(or(X, Y), and(Y, Z)) >? or(X, Y) 
  or(X, X) >? X 
  or(X, or(Y, Y)) >? or(X, Y) 
  and(X, true) >? X 
  and(false, X) >? false 

about to try horpo

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

Argument functions:

  [[false]] = _|_ 

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

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

  and(X, or(Y, Z)) >= or(and(X, Y), and(X, Z)) 
  and(X, and(Y, Y)) >= and(X, Y) 
  or(or(X, Y), and(Y, Z)) >= or(X, Y) 
  or(X, X) >= X 
  or(X, or(Y, Y)) >= or(X, Y) 
  and(X, true) >= X 
  and(_|_, X) > _|_ 

With these choices, we have:

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

  12] and(X, and(Y, Y)) >= and(X, Y)  because [13], by (Star) 
  13] and*(X, and(Y, Y)) >= and(X, Y)  because and in Mul, [4] and [14], by (Stat) 
  14] and(Y, Y) > Y  because [15], by definition 
  15] and*(Y, Y) >= Y  because [7], by (Select) 

  16] or(or(X, Y), and(Y, Z)) >= or(X, Y)  because [17], by (Star) 
  17] or*(or(X, Y), and(Y, Z)) >= or(X, Y)  because or in Mul, [18] and [20], by (Stat) 
  18] or(X, Y) > X  because [19], by definition 
  19] or*(X, Y) >= X  because [4], by (Select) 
  20] or(X, Y) > Y  because [21], by definition 
  21] or*(X, Y) >= Y  because [7], by (Select) 

  22] or(X, X) >= X  because [23], by (Star) 
  23] or*(X, X) >= X  because [4], by (Select) 

  24] or(X, or(Y, Y)) >= or(X, Y)  because or in Mul, [4] and [25], by (Fun) 
  25] or(Y, Y) >= Y  because [26], by (Star) 
  26] or*(Y, Y) >= Y  because [7], by (Select) 

  27] and(X, true) >= X  because [28], by (Star) 
  28] and*(X, true) >= X  because [4], by (Select) 

  29] and(_|_, X) > _|_  because [30], by definition 
  30] and*(_|_, X) >= _|_  by (Bot) 

We can thus remove the following rules:

  and(false, X) => 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]):

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

about to try horpo

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

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

With these choices, we have:

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

  12] and(X, and(Y, Y)) >= and(X, Y)  because [13], by (Star) 
  13] and*(X, and(Y, Y)) >= and(X, Y)  because and in Mul, [4] and [14], by (Stat) 
  14] and(Y, Y) > Y  because [15], by definition 
  15] and*(Y, Y) >= Y  because [7], by (Select) 

  16] or(or(X, Y), and(Y, Z)) >= or(X, Y)  because [17], by (Star) 
  17] or*(or(X, Y), and(Y, Z)) >= or(X, Y)  because [18], by (Select) 
  18] or(X, Y) >= or(X, Y)  because or in Mul, [4] and [19], by (Fun) 
  19] Y >= Y  by (Meta) 

  20] or(X, X) > X  because [21], by definition 
  21] or*(X, X) >= X  because [4], by (Select) 

  22] or(X, or(Y, Y)) >= or(X, Y)  because [23], by (Star) 
  23] or*(X, or(Y, Y)) >= or(X, Y)  because or in Mul, [4] and [24], by (Stat) 
  24] or(Y, Y) > Y  because [25], by definition 
  25] or*(Y, Y) >= Y  because [19], by (Select) 

  26] and(X, true) >= X  because [27], by (Star) 
  27] and*(X, true) >= X  because [4], by (Select) 

We can thus remove the following rules:

  or(X, X) => X 

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

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

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

about to try horpo

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

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

With these choices, we have:

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

  12] and(X, and(Y, Y)) > and(X, Y)  because [13], by definition 
  13] and*(X, and(Y, Y)) >= and(X, Y)  because and in Mul, [4] and [14], by (Stat) 
  14] and(Y, Y) > Y  because [15], by definition 
  15] and*(Y, Y) >= Y  because [7], by (Select) 

  16] or(or(X, Y), and(Y, Z)) >= or(X, Y)  because or in Mul, [17] and [19], by (Fun) 
  17] or(X, Y) >= X  because [18], by (Star) 
  18] or*(X, Y) >= X  because [4], by (Select) 
  19] and(Y, Z) >= Y  because [20], by (Star) 
  20] and*(Y, Z) >= Y  because [7], by (Select) 

  21] or(X, or(Y, Y)) > or(X, Y)  because [22], by definition 
  22] or*(X, or(Y, Y)) >= or(X, Y)  because or in Mul, [4] and [23], by (Stat) 
  23] or(Y, Y) > Y  because [24], by definition 
  24] or*(Y, Y) >= Y  because [7], by (Select) 

  25] and(X, true) > X  because [26], by definition 
  26] and*(X, true) >= X  because [4], by (Select) 

We can thus remove the following rules:

  and(X, or(Y, Z)) => or(and(X, Y), and(X, Z)) 
  and(X, and(Y, Y)) => and(X, Y) 
  or(X, or(Y, Y)) => or(X, Y) 
  and(X, true) => X 

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(or(X, Y), and(Y, Z)) >? or(X, Y) 

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

The following interpretation satisfies the requirements:

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

Using this interpretation, the requirements translate to:

  [[or(or(_x0, _x1), and(_x1, _x2))]] = 12 + 2x2 + 4x0 + 5x1 > 3 + x1 + 2x0 = [[or(_x0, _x1)]] 

We can thus remove the following rules:

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