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

  !770 : [o * o] --> o 
  !dot : [o * o] --> o 
  !plus!plus : [o * o] --> o 
  false : [] --> o 
  if : [o * o * o] --> o 
  merge : [o * o] --> o 
  nil : [] --> o 
  true : [] --> o 

  merge(nil, X) => X 
  merge(X, nil) => X 
  merge(!dot(X, Y), !dot(Z, U)) => if(!770(X, Z), !dot(X, merge(Y, !dot(Z, U))), !dot(Z, merge(!dot(X, Y), U))) 
  !plus!plus(nil, X) => X 
  !plus!plus(!dot(X, Y), Z) => !dot(X, !plus!plus(Y, Z)) 
  if(true, X, Y) => X 
  if(false, X, Y) => 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]):

  merge(nil, X) >? X 
  merge(X, nil) >? X 
  merge(!dot(X, Y), !dot(Z, U)) >? if(!770(X, Z), !dot(X, merge(Y, !dot(Z, U))), !dot(Z, merge(!dot(X, Y), U))) 
  !plus!plus(nil, X) >? X 
  !plus!plus(!dot(X, Y), Z) >? !dot(X, !plus!plus(Y, Z)) 
  if(true, X, Y) >? X 
  if(false, X, Y) >? X 

about to try horpo

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

We choose Lex = {} and Mul = {!770, !dot, !plus!plus, false, if, merge, nil, true}, and the following precedence: !plus!plus > !770 = merge > !dot > nil > true > false > if

With these choices, we have:

  1] merge(nil, X) >= X  because [2], by (Star) 
  2] merge*(nil, X) >= X  because [3], by (Select) 
  3] X >= X  by (Meta) 

  4] merge(X, nil) > X  because [5], by definition 
  5] merge*(X, nil) >= X  because [6], by (Select) 
  6] X >= X  by (Meta) 

  7] merge(!dot(X, Y), !dot(Z, U)) >= if(!770(X, Z), !dot(X, merge(Y, !dot(Z, U))), !dot(Z, merge(!dot(X, Y), U)))  because [8], by (Star) 
  8] merge*(!dot(X, Y), !dot(Z, U)) >= if(!770(X, Z), !dot(X, merge(Y, !dot(Z, U))), !dot(Z, merge(!dot(X, Y), U)))  because merge > if, [9], [15] and [23], by (Copy) 
  9] merge*(!dot(X, Y), !dot(Z, U)) >= !770(X, Z)  because merge = !770, merge in Mul, [10] and [12], by (Stat) 
  10] !dot(X, Y) >= X  because [11], by (Star) 
  11] !dot*(X, Y) >= X  because [6], by (Select) 
  12] !dot(Z, U) > Z  because [13], by definition 
  13] !dot*(Z, U) >= Z  because [14], by (Select) 
  14] Z >= Z  by (Meta) 
  15] merge*(!dot(X, Y), !dot(Z, U)) >= !dot(X, merge(Y, !dot(Z, U)))  because merge > !dot, [16] and [17], by (Copy) 
  16] merge*(!dot(X, Y), !dot(Z, U)) >= X  because [10], by (Select) 
  17] merge*(!dot(X, Y), !dot(Z, U)) >= merge(Y, !dot(Z, U))  because merge in Mul, [18] and [20], by (Stat) 
  18] !dot(X, Y) > Y  because [19], by definition 
  19] !dot*(X, Y) >= Y  because [3], by (Select) 
  20] !dot(Z, U) >= !dot(Z, U)  because !dot in Mul, [21] and [22], by (Fun) 
  21] Z >= Z  by (Meta) 
  22] U >= U  by (Meta) 
  23] merge*(!dot(X, Y), !dot(Z, U)) >= !dot(Z, merge(!dot(X, Y), U))  because merge > !dot, [24] and [26], by (Copy) 
  24] merge*(!dot(X, Y), !dot(Z, U)) >= Z  because [25], by (Select) 
  25] !dot(Z, U) >= Z  because [13], by (Star) 
  26] merge*(!dot(X, Y), !dot(Z, U)) >= merge(!dot(X, Y), U)  because merge in Mul, [27] and [30], by (Stat) 
  27] !dot(X, Y) >= !dot(X, Y)  because !dot in Mul, [28] and [29], by (Fun) 
  28] X >= X  by (Meta) 
  29] Y >= Y  by (Meta) 
  30] !dot(Z, U) > U  because [31], by definition 
  31] !dot*(Z, U) >= U  because [22], by (Select) 

  32] !plus!plus(nil, X) >= X  because [33], by (Star) 
  33] !plus!plus*(nil, X) >= X  because [29], by (Select) 

  34] !plus!plus(!dot(X, Y), Z) > !dot(X, !plus!plus(Y, Z))  because [35], by definition 
  35] !plus!plus*(!dot(X, Y), Z) >= !dot(X, !plus!plus(Y, Z))  because !plus!plus > !dot, [36] and [37], by (Copy) 
  36] !plus!plus*(!dot(X, Y), Z) >= X  because [10], by (Select) 
  37] !plus!plus*(!dot(X, Y), Z) >= !plus!plus(Y, Z)  because !plus!plus in Mul, [18] and [38], by (Stat) 
  38] Z >= Z  by (Meta) 

  39] if(true, X, Y) >= X  because [40], by (Star) 
  40] if*(true, X, Y) >= X  because [28], by (Select) 

  41] if(false, X, Y) >= X  because [42], by (Star) 
  42] if*(false, X, Y) >= X  because [28], by (Select) 

We can thus remove the following rules:

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

  merge(nil, X) >? X 
  merge(!dot(X, Y), !dot(Z, U)) >? if(!770(X, Z), !dot(X, merge(Y, !dot(Z, U))), !dot(Z, merge(!dot(X, Y), U))) 
  !plus!plus(nil, X) >? X 
  if(true, X, Y) >? X 
  if(false, X, Y) >? X 

about to try horpo

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

We choose Lex = {} and Mul = {!770, !dot, !plus!plus, false, if, merge, nil, true}, and the following precedence: true > !770 = merge > nil > false > !plus!plus > if > !dot

With these choices, we have:

  1] merge(nil, X) >= X  because [2], by (Star) 
  2] merge*(nil, X) >= X  because [3], by (Select) 
  3] X >= X  by (Meta) 

  4] merge(!dot(X, Y), !dot(Z, U)) > if(!770(X, Z), !dot(X, merge(Y, !dot(Z, U))), !dot(Z, merge(!dot(X, Y), U)))  because [5], by definition 
  5] merge*(!dot(X, Y), !dot(Z, U)) >= if(!770(X, Z), !dot(X, merge(Y, !dot(Z, U))), !dot(Z, merge(!dot(X, Y), U)))  because merge > if, [6], [13] and [21], by (Copy) 
  6] merge*(!dot(X, Y), !dot(Z, U)) >= !770(X, Z)  because merge = !770, merge in Mul, [7] and [10], by (Stat) 
  7] !dot(X, Y) >= X  because [8], by (Star) 
  8] !dot*(X, Y) >= X  because [9], by (Select) 
  9] X >= X  by (Meta) 
  10] !dot(Z, U) > Z  because [11], by definition 
  11] !dot*(Z, U) >= Z  because [12], by (Select) 
  12] Z >= Z  by (Meta) 
  13] merge*(!dot(X, Y), !dot(Z, U)) >= !dot(X, merge(Y, !dot(Z, U)))  because merge > !dot, [14] and [15], by (Copy) 
  14] merge*(!dot(X, Y), !dot(Z, U)) >= X  because [7], by (Select) 
  15] merge*(!dot(X, Y), !dot(Z, U)) >= merge(Y, !dot(Z, U))  because merge in Mul, [16] and [18], by (Stat) 
  16] !dot(X, Y) > Y  because [17], by definition 
  17] !dot*(X, Y) >= Y  because [3], by (Select) 
  18] !dot(Z, U) >= !dot(Z, U)  because !dot in Mul, [19] and [20], by (Fun) 
  19] Z >= Z  by (Meta) 
  20] U >= U  by (Meta) 
  21] merge*(!dot(X, Y), !dot(Z, U)) >= !dot(Z, merge(!dot(X, Y), U))  because merge > !dot, [22] and [24], by (Copy) 
  22] merge*(!dot(X, Y), !dot(Z, U)) >= Z  because [23], by (Select) 
  23] !dot(Z, U) >= Z  because [11], by (Star) 
  24] merge*(!dot(X, Y), !dot(Z, U)) >= merge(!dot(X, Y), U)  because merge in Mul, [25] and [28], by (Stat) 
  25] !dot(X, Y) >= !dot(X, Y)  because !dot in Mul, [26] and [27], by (Fun) 
  26] X >= X  by (Meta) 
  27] Y >= Y  by (Meta) 
  28] !dot(Z, U) > U  because [29], by definition 
  29] !dot*(Z, U) >= U  because [20], by (Select) 

  30] !plus!plus(nil, X) >= X  because [31], by (Star) 
  31] !plus!plus*(nil, X) >= X  because [27], by (Select) 

  32] if(true, X, Y) > X  because [33], by definition 
  33] if*(true, X, Y) >= X  because [26], by (Select) 

  34] if(false, X, Y) >= X  because [35], by (Star) 
  35] if*(false, X, Y) >= X  because [26], by (Select) 

We can thus remove the following rules:

  merge(!dot(X, Y), !dot(Z, U)) => if(!770(X, Z), !dot(X, merge(Y, !dot(Z, U))), !dot(Z, merge(!dot(X, Y), U))) 
  if(true, X, Y) => 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]):

  merge(nil, X) >? X 
  !plus!plus(nil, X) >? X 
  if(false, X, Y) >? X 

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

The following interpretation satisfies the requirements:

  !plus!plus = \y0y1.3 + y0 + y1 
  false = 3 
  if = \y0y1y2.3 + y0 + y1 + y2 
  merge = \y0y1.3 + y0 + y1 
  nil = 3 

Using this interpretation, the requirements translate to:

  [[merge(nil, _x0)]] = 6 + x0 > x0 = [[_x0]] 
  [[!plus!plus(nil, _x0)]] = 6 + x0 > x0 = [[_x0]] 
  [[if(false, _x0, _x1)]] = 6 + x0 + x1 > x0 = [[_x0]] 

We can thus remove the following rules:

  merge(nil, X) => X 
  !plus!plus(nil, X) => X 
  if(false, X, Y) => X 

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.