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

  app : [o * o] --> o 
  compose : [] --> o 
  cons : [] --> o 
  hd : [] --> o 
  init : [] --> o 
  last : [] --> o 
  nil : [] --> o 
  reverse : [] --> o 
  reverse2 : [] --> o 
  tl : [] --> o 

  app(app(app(compose, X), Y), Z) => app(Y, app(X, Z)) 
  app(reverse, X) => app(app(reverse2, X), nil) 
  app(app(reverse2, nil), X) => X 
  app(app(reverse2, app(app(cons, X), Y)), Z) => app(app(reverse2, Y), app(app(cons, X), Z)) 
  app(hd, app(app(cons, X), Y)) => X 
  app(tl, app(app(cons, X), Y)) => Y 
  last => app(app(compose, hd), reverse) 
  init => app(app(compose, reverse), app(app(compose, tl), reverse)) 

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

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

  app(app(app(compose, X), Y), Z) >? app(Y, app(X, Z)) 
  app(reverse, X) >? app(app(reverse2, X), nil) 
  app(app(reverse2, nil), X) >? X 
  app(app(reverse2, app(app(cons, X), Y)), Z) >? app(app(reverse2, Y), app(app(cons, X), Z)) 
  app(hd, app(app(cons, X), Y)) >? X 
  app(tl, app(app(cons, X), Y)) >? Y 
  last >? app(app(compose, hd), reverse) 
  init >? app(app(compose, reverse), app(app(compose, tl), reverse)) 

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

The following interpretation satisfies the requirements:

  app = \y0y1.y0 + y1 
  compose = 0 
  cons = 0 
  hd = 1 
  init = 3 
  last = 3 
  nil = 0 
  reverse = 0 
  reverse2 = 0 
  tl = 0 

Using this interpretation, the requirements translate to:

  [[app(app(app(compose, _x0), _x1), _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[app(_x1, app(_x0, _x2))]] 
  [[app(reverse, _x0)]] = x0 >= x0 = [[app(app(reverse2, _x0), nil)]] 
  [[app(app(reverse2, nil), _x0)]] = x0 >= x0 = [[_x0]] 
  [[app(app(reverse2, app(app(cons, _x0), _x1)), _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[app(app(reverse2, _x1), app(app(cons, _x0), _x2))]] 
  [[app(hd, app(app(cons, _x0), _x1))]] = 1 + x0 + x1 > x0 = [[_x0]] 
  [[app(tl, app(app(cons, _x0), _x1))]] = x0 + x1 >= x1 = [[_x1]] 
  [[last]] = 3 > 1 = [[app(app(compose, hd), reverse)]] 
  [[init]] = 3 > 0 = [[app(app(compose, reverse), app(app(compose, tl), reverse))]] 

We can thus remove the following rules:

  app(hd, app(app(cons, X), Y)) => X 
  last => app(app(compose, hd), reverse) 
  init => app(app(compose, reverse), app(app(compose, tl), reverse)) 

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

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

  app(app(app(compose, X), Y), Z) >? app(Y, app(X, Z)) 
  app(reverse, X) >? app(app(reverse2, X), nil) 
  app(app(reverse2, nil), X) >? X 
  app(app(reverse2, app(app(cons, X), Y)), Z) >? app(app(reverse2, Y), app(app(cons, X), Z)) 
  app(tl, app(app(cons, X), Y)) >? Y 

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

The following interpretation satisfies the requirements:

  app = \y0y1.y0 + y1 
  compose = 3 
  cons = 0 
  nil = 0 
  reverse = 3 
  reverse2 = 0 
  tl = 3 

Using this interpretation, the requirements translate to:

  [[app(app(app(compose, _x0), _x1), _x2)]] = 3 + x0 + x1 + x2 > x0 + x1 + x2 = [[app(_x1, app(_x0, _x2))]] 
  [[app(reverse, _x0)]] = 3 + x0 > x0 = [[app(app(reverse2, _x0), nil)]] 
  [[app(app(reverse2, nil), _x0)]] = x0 >= x0 = [[_x0]] 
  [[app(app(reverse2, app(app(cons, _x0), _x1)), _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[app(app(reverse2, _x1), app(app(cons, _x0), _x2))]] 
  [[app(tl, app(app(cons, _x0), _x1))]] = 3 + x0 + x1 > x1 = [[_x1]] 

We can thus remove the following rules:

  app(app(app(compose, X), Y), Z) => app(Y, app(X, Z)) 
  app(reverse, X) => app(app(reverse2, X), nil) 
  app(tl, app(app(cons, X), Y)) => 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]):

  app(app(reverse2, nil), X) >? X 
  app(app(reverse2, app(app(cons, X), Y)), Z) >? app(app(reverse2, Y), app(app(cons, X), Z)) 

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

The following interpretation satisfies the requirements:

  app = \y0y1.y0 + y1 
  cons = 0 
  nil = 3 
  reverse2 = 3 

Using this interpretation, the requirements translate to:

  [[app(app(reverse2, nil), _x0)]] = 6 + x0 > x0 = [[_x0]] 
  [[app(app(reverse2, app(app(cons, _x0), _x1)), _x2)]] = 3 + x0 + x1 + x2 >= 3 + x0 + x1 + x2 = [[app(app(reverse2, _x1), app(app(cons, _x0), _x2))]] 

We can thus remove the following rules:

  app(app(reverse2, nil), 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]):

  app(app(reverse2, app(app(cons, X), Y)), Z) >? app(app(reverse2, Y), app(app(cons, X), Z)) 

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

The following interpretation satisfies the requirements:

  app = \y0y1.1 + y1 + 2y0 
  cons = 0 
  reverse2 = 0 

Using this interpretation, the requirements translate to:

  [[app(app(reverse2, app(app(cons, _x0), _x1)), _x2)]] = 9 + x2 + 2x1 + 4x0 > 6 + x2 + 2x0 + 2x1 = [[app(app(reverse2, _x1), app(app(cons, _x0), _x2))]] 

We can thus remove the following rules:

  app(app(reverse2, app(app(cons, X), Y)), Z) => app(app(reverse2, Y), app(app(cons, X), 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.