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

  0 : [] --> o 
  add : [o * o] --> o 
  cons : [o] --> o 
  from : [o] --> o 
  fst : [o * o] --> o 
  len : [o] --> o 
  nil : [] --> o 
  s : [] --> o 

  fst(0, X) => nil 
  fst(s, cons(X)) => cons(X) 
  from(X) => cons(X) 
  add(0, X) => X 
  add(s, X) => s 
  len(nil) => 0 
  len(cons(X)) => s 

As the system is orthogonal, it is terminating if it is innermost terminating by [Gra95].  Then, by [FuhGieParSchSwi11], it suffices to prove (innermost) termination of the typed system, with sort annotations chosen to respect the rules, as follows:

  0 : [] --> za 
  add : [za * za] --> za 
  cons : [za] --> ya 
  from : [za] --> ya 
  fst : [za * ya] --> ya 
  len : [ya] --> za 
  nil : [] --> ya 
  s : [] --> za 

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

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

  fst(0, X) >? nil 
  fst(s, cons(X)) >? cons(X) 
  from(X) >? cons(X) 
  add(0, X) >? X 
  add(s, X) >? s 
  len(nil) >? 0 
  len(cons(X)) >? s 

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

The following interpretation satisfies the requirements:

  0 = 0 
  add = \y0y1.3 + y1 + 3y0 
  cons = \y0.y0 
  from = \y0.3 + 3y0 
  fst = \y0y1.3 + 3y0 + 3y1 
  len = \y0.3 + 3y0 
  nil = 0 
  s = 0 

Using this interpretation, the requirements translate to:

  [[fst(0, _x0)]] = 3 + 3x0 > 0 = [[nil]] 
  [[fst(s, cons(_x0))]] = 3 + 3x0 > x0 = [[cons(_x0)]] 
  [[from(_x0)]] = 3 + 3x0 > x0 = [[cons(_x0)]] 
  [[add(0, _x0)]] = 3 + x0 > x0 = [[_x0]] 
  [[add(s, _x0)]] = 3 + x0 > 0 = [[s]] 
  [[len(nil)]] = 3 > 0 = [[0]] 
  [[len(cons(_x0))]] = 3 + 3x0 > 0 = [[s]] 

We can thus remove the following rules:

  fst(0, X) => nil 
  fst(s, cons(X)) => cons(X) 
  from(X) => cons(X) 
  add(0, X) => X 
  add(s, X) => s 
  len(nil) => 0 
  len(cons(X)) => s 

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 +++

[FuhGieParSchSwi11]  C. Fuhs, J. Giesl, M. Parting, P. Schneider-Kamp, and S. Swiderski.  Proving Termination by Dependency Pairs and Inductive Theorem Proving.  In volume 47(2) of Journal of Automated Reasoning.  133--160, 2011.
[Gra95]  B. Gramlich.  Abstract Relations Between Restricted Termination and Confluence Properties of Rewrite Systems.  In volume 24(1-2) of Fundamentae Informaticae.  3--23, 1995.
[Kop12]  C. Kop.  Higher Order Termination.  PhD Thesis, 2012.