/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 
  false : [] --> o 
  implies : [o * o] --> o 
  not : [o] --> o 
  or : [o * o] --> o 
  true : [] --> o 
  xor : [o * o] --> o 

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

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

about to try horpo

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

Argument functions:

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

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

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

  not(X) >= xor(X, _|_) 
  or(X, Y) >= xor(and(X, Y), xor(X, Y)) 
  implies(X, Y) >= xor(and(X, Y), xor(X, _|_)) 
  and(X, _|_) >= X 
  and(X, _|_) >= _|_ 
  and(X, X) > X 
  xor(X, _|_) > X 
  xor(X, X) >= _|_ 
  and(xor(X, Y), Z) >= xor(and(X, Z), and(Y, Z)) 

With these choices, we have:

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

  6] or(X, Y) >= xor(and(X, Y), xor(X, Y))  because [7], by (Star) 
  7] or*(X, Y) >= xor(and(X, Y), xor(X, Y))  because or > xor, [8] and [12], by (Copy) 
  8] or*(X, Y) >= and(X, Y)  because or > and, [9] and [10], by (Copy) 
  9] or*(X, Y) >= X  because [4], by (Select) 
  10] or*(X, Y) >= Y  because [11], by (Select) 
  11] Y >= Y  by (Meta) 
  12] or*(X, Y) >= xor(X, Y)  because or > xor, [9] and [10], by (Copy) 

  13] implies(X, Y) >= xor(and(X, Y), xor(X, _|_))  because [14], by (Star) 
  14] implies*(X, Y) >= xor(and(X, Y), xor(X, _|_))  because implies > xor, [15] and [18], by (Copy) 
  15] implies*(X, Y) >= and(X, Y)  because implies > and, [16] and [17], by (Copy) 
  16] implies*(X, Y) >= X  because [4], by (Select) 
  17] implies*(X, Y) >= Y  because [11], by (Select) 
  18] implies*(X, Y) >= xor(X, _|_)  because implies > xor, [16] and [19], by (Copy) 
  19] implies*(X, Y) >= _|_  by (Bot) 

  20] and(X, _|_) >= X  because [21], by (Star) 
  21] and*(X, _|_) >= X  because [4], by (Select) 

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

  23] and(X, X) > X  because [24], by definition 
  24] and*(X, X) >= X  because [4], by (Select) 

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

  27] xor(X, X) >= _|_  by (Bot) 

  28] and(xor(X, Y), Z) >= xor(and(X, Z), and(Y, Z))  because [29], by (Star) 
  29] and*(xor(X, Y), Z) >= xor(and(X, Z), and(Y, Z))  because and > xor, [30] and [34], by (Copy) 
  30] and*(xor(X, Y), Z) >= and(X, Z)  because and in Mul, [31] and [33], by (Stat) 
  31] xor(X, Y) > X  because [32], by definition 
  32] xor*(X, Y) >= X  because [4], by (Select) 
  33] Z >= Z  by (Meta) 
  34] and*(xor(X, Y), Z) >= and(Y, Z)  because and in Mul, [35] and [33], by (Stat) 
  35] xor(X, Y) > Y  because [36], by definition 
  36] xor*(X, Y) >= Y  because [11], by (Select) 

We can thus remove the following rules:

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

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

about to try horpo

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

Argument functions:

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

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

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

  not(X) >= xor(X, _|_) 
  or(X, Y) >= xor(and(X, Y), xor(X, Y)) 
  implies(X, Y) >= xor(and(X, Y), xor(X, _|_)) 
  and(X, _|_) >= X 
  and(X, _|_) >= _|_ 
  xor(X, X) > _|_ 
  and(xor(X, Y), Z) >= xor(and(X, Z), and(Y, Z)) 

With these choices, we have:

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

  6] or(X, Y) >= xor(and(X, Y), xor(X, Y))  because [7], by (Star) 
  7] or*(X, Y) >= xor(and(X, Y), xor(X, Y))  because or > xor, [8] and [12], by (Copy) 
  8] or*(X, Y) >= and(X, Y)  because or > and, [9] and [10], by (Copy) 
  9] or*(X, Y) >= X  because [4], by (Select) 
  10] or*(X, Y) >= Y  because [11], by (Select) 
  11] Y >= Y  by (Meta) 
  12] or*(X, Y) >= xor(X, Y)  because or > xor, [9] and [10], by (Copy) 

  13] implies(X, Y) >= xor(and(X, Y), xor(X, _|_))  because [14], by (Star) 
  14] implies*(X, Y) >= xor(and(X, Y), xor(X, _|_))  because implies > xor, [15] and [18], by (Copy) 
  15] implies*(X, Y) >= and(X, Y)  because implies > and, [16] and [17], by (Copy) 
  16] implies*(X, Y) >= X  because [4], by (Select) 
  17] implies*(X, Y) >= Y  because [11], by (Select) 
  18] implies*(X, Y) >= xor(X, _|_)  because implies > xor, [16] and [19], by (Copy) 
  19] implies*(X, Y) >= _|_  by (Bot) 

  20] and(X, _|_) >= X  because [21], by (Star) 
  21] and*(X, _|_) >= X  because [4], by (Select) 

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

  23] xor(X, X) > _|_  because [24], by definition 
  24] xor*(X, X) >= _|_  by (Bot) 

  25] and(xor(X, Y), Z) >= xor(and(X, Z), and(Y, Z))  because [26], by (Star) 
  26] and*(xor(X, Y), Z) >= xor(and(X, Z), and(Y, Z))  because and > xor, [27] and [31], by (Copy) 
  27] and*(xor(X, Y), Z) >= and(X, Z)  because and in Mul, [28] and [30], by (Stat) 
  28] xor(X, Y) > X  because [29], by definition 
  29] xor*(X, Y) >= X  because [4], by (Select) 
  30] Z >= Z  by (Meta) 
  31] and*(xor(X, Y), Z) >= and(Y, Z)  because and in Mul, [32] and [30], by (Stat) 
  32] xor(X, Y) > Y  because [33], by definition 
  33] xor*(X, Y) >= Y  because [11], by (Select) 

We can thus remove the following rules:

  xor(X, 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]):

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

about to try horpo

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

Argument functions:

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

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

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

  not(X) >= xor(X, _|_) 
  or(X, Y) >= xor(and(X, Y), xor(X, Y)) 
  implies(X, Y) >= xor(and(X, Y), xor(X, _|_)) 
  and(X, _|_) >= X 
  and(X, _|_) > _|_ 
  and(xor(X, Y), Z) >= xor(and(X, Z), and(Y, Z)) 

With these choices, we have:

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

  6] or(X, Y) >= xor(and(X, Y), xor(X, Y))  because [7], by (Star) 
  7] or*(X, Y) >= xor(and(X, Y), xor(X, Y))  because or > xor, [8] and [12], by (Copy) 
  8] or*(X, Y) >= and(X, Y)  because or > and, [9] and [10], by (Copy) 
  9] or*(X, Y) >= X  because [4], by (Select) 
  10] or*(X, Y) >= Y  because [11], by (Select) 
  11] Y >= Y  by (Meta) 
  12] or*(X, Y) >= xor(X, Y)  because or > xor, [9] and [10], by (Copy) 

  13] implies(X, Y) >= xor(and(X, Y), xor(X, _|_))  because [14], by (Star) 
  14] implies*(X, Y) >= xor(and(X, Y), xor(X, _|_))  because implies > xor, [15] and [18], by (Copy) 
  15] implies*(X, Y) >= and(X, Y)  because implies > and, [16] and [17], by (Copy) 
  16] implies*(X, Y) >= X  because [4], by (Select) 
  17] implies*(X, Y) >= Y  because [11], by (Select) 
  18] implies*(X, Y) >= xor(X, _|_)  because implies > xor, [16] and [19], by (Copy) 
  19] implies*(X, Y) >= _|_  by (Bot) 

  20] and(X, _|_) >= X  because [21], by (Star) 
  21] and*(X, _|_) >= X  because [4], by (Select) 

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

  24] and(xor(X, Y), Z) >= xor(and(X, Z), and(Y, Z))  because [25], by (Star) 
  25] and*(xor(X, Y), Z) >= xor(and(X, Z), and(Y, Z))  because and > xor, [26] and [30], by (Copy) 
  26] and*(xor(X, Y), Z) >= and(X, Z)  because and in Mul, [27] and [29], by (Stat) 
  27] xor(X, Y) > X  because [28], by definition 
  28] xor*(X, Y) >= X  because [4], by (Select) 
  29] Z >= Z  by (Meta) 
  30] and*(xor(X, Y), Z) >= and(Y, Z)  because and in Mul, [31] and [29], by (Stat) 
  31] xor(X, Y) > Y  because [32], by definition 
  32] xor*(X, Y) >= Y  because [11], by (Select) 

We can thus remove the following rules:

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

  not(X) >? xor(X, true) 
  or(X, Y) >? xor(and(X, Y), xor(X, Y)) 
  implies(X, Y) >? xor(and(X, Y), xor(X, true)) 
  and(X, true) >? X 
  and(xor(X, Y), Z) >? xor(and(X, Z), and(Y, Z)) 

about to try horpo

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

Argument functions:

  [[true]] = _|_ 

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

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

  not(X) > xor(X, _|_) 
  or(X, Y) >= xor(and(X, Y), xor(X, Y)) 
  implies(X, Y) >= xor(and(X, Y), xor(X, _|_)) 
  and(X, _|_) >= X 
  and(xor(X, Y), Z) >= xor(and(X, Z), and(Y, Z)) 

With these choices, we have:

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

  6] or(X, Y) >= xor(and(X, Y), xor(X, Y))  because [7], by (Star) 
  7] or*(X, Y) >= xor(and(X, Y), xor(X, Y))  because or > xor, [8] and [12], by (Copy) 
  8] or*(X, Y) >= and(X, Y)  because or > and, [9] and [10], by (Copy) 
  9] or*(X, Y) >= X  because [4], by (Select) 
  10] or*(X, Y) >= Y  because [11], by (Select) 
  11] Y >= Y  by (Meta) 
  12] or*(X, Y) >= xor(X, Y)  because or > xor, [9] and [10], by (Copy) 

  13] implies(X, Y) >= xor(and(X, Y), xor(X, _|_))  because [14], by (Star) 
  14] implies*(X, Y) >= xor(and(X, Y), xor(X, _|_))  because implies > xor, [15] and [18], by (Copy) 
  15] implies*(X, Y) >= and(X, Y)  because implies > and, [16] and [17], by (Copy) 
  16] implies*(X, Y) >= X  because [4], by (Select) 
  17] implies*(X, Y) >= Y  because [11], by (Select) 
  18] implies*(X, Y) >= xor(X, _|_)  because implies > xor, [16] and [19], by (Copy) 
  19] implies*(X, Y) >= _|_  by (Bot) 

  20] and(X, _|_) >= X  because [21], by (Star) 
  21] and*(X, _|_) >= X  because [4], by (Select) 

  22] and(xor(X, Y), Z) >= xor(and(X, Z), and(Y, Z))  because [23], by (Star) 
  23] and*(xor(X, Y), Z) >= xor(and(X, Z), and(Y, Z))  because and > xor, [24] and [28], by (Copy) 
  24] and*(xor(X, Y), Z) >= and(X, Z)  because and in Mul, [25] and [27], by (Stat) 
  25] xor(X, Y) > X  because [26], by definition 
  26] xor*(X, Y) >= X  because [4], by (Select) 
  27] Z >= Z  by (Meta) 
  28] and*(xor(X, Y), Z) >= and(Y, Z)  because and in Mul, [29] and [27], by (Stat) 
  29] xor(X, Y) > Y  because [30], by definition 
  30] xor*(X, Y) >= Y  because [11], by (Select) 

We can thus remove the following rules:

  not(X) => xor(X, true) 

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

about to try horpo

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

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

With these choices, we have:

  1] or(X, Y) >= xor(and(X, Y), xor(X, Y))  because [2], by (Star) 
  2] or*(X, Y) >= xor(and(X, Y), xor(X, Y))  because or > xor, [3] and [8], by (Copy) 
  3] or*(X, Y) >= and(X, Y)  because or > and, [4] and [6], by (Copy) 
  4] or*(X, Y) >= X  because [5], by (Select) 
  5] X >= X  by (Meta) 
  6] or*(X, Y) >= Y  because [7], by (Select) 
  7] Y >= Y  by (Meta) 
  8] or*(X, Y) >= xor(X, Y)  because or > xor, [4] and [6], by (Copy) 

  9] implies(X, Y) > xor(and(X, Y), xor(X, true))  because [10], by definition 
  10] implies*(X, Y) >= xor(and(X, Y), xor(X, true))  because implies > xor, [11] and [14], by (Copy) 
  11] implies*(X, Y) >= and(X, Y)  because implies > and, [12] and [13], by (Copy) 
  12] implies*(X, Y) >= X  because [5], by (Select) 
  13] implies*(X, Y) >= Y  because [7], by (Select) 
  14] implies*(X, Y) >= xor(X, true)  because implies > xor, [12] and [15], by (Copy) 
  15] implies*(X, Y) >= true  because implies > true, by (Copy) 

  16] and(X, true) >= X  because [17], by (Star) 
  17] and*(X, true) >= X  because [5], by (Select) 

  18] and(xor(X, Y), Z) >= xor(and(X, Z), and(Y, Z))  because [19], by (Star) 
  19] and*(xor(X, Y), Z) >= xor(and(X, Z), and(Y, Z))  because and > xor, [20] and [24], by (Copy) 
  20] and*(xor(X, Y), Z) >= and(X, Z)  because and in Mul, [21] and [23], by (Stat) 
  21] xor(X, Y) > X  because [22], by definition 
  22] xor*(X, Y) >= X  because [5], by (Select) 
  23] Z >= Z  by (Meta) 
  24] and*(xor(X, Y), Z) >= and(Y, Z)  because and in Mul, [25] and [23], by (Stat) 
  25] xor(X, Y) > Y  because [26], by definition 
  26] xor*(X, Y) >= Y  because [7], by (Select) 

We can thus remove the following rules:

  implies(X, Y) => xor(and(X, Y), xor(X, true)) 

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

about to try horpo

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

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

With these choices, we have:

  1] or(X, Y) > xor(and(X, Y), xor(X, Y))  because [2], by definition 
  2] or*(X, Y) >= xor(and(X, Y), xor(X, Y))  because or > xor, [3] and [8], by (Copy) 
  3] or*(X, Y) >= and(X, Y)  because or > and, [4] and [6], by (Copy) 
  4] or*(X, Y) >= X  because [5], by (Select) 
  5] X >= X  by (Meta) 
  6] or*(X, Y) >= Y  because [7], by (Select) 
  7] Y >= Y  by (Meta) 
  8] or*(X, Y) >= xor(X, Y)  because or > xor, [4] and [6], by (Copy) 

  9] and(X, true) > X  because [10], by definition 
  10] and*(X, true) >= X  because [5], by (Select) 

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

We can thus remove the following rules:

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

  and(xor(X, Y), Z) >? xor(and(X, Z), and(Y, Z)) 

about to try horpo

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

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

With these choices, we have:

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

We can thus remove the following rules:

  and(xor(X, Y), Z) => xor(and(X, Z), and(Y, Z)) 

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.