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

  !6220!6220 : [o * o] --> o 
  a : [] --> o 
  activate : [o] --> o 
  and : [o * o] --> o 
  e : [] --> o 
  i : [] --> o 
  isList : [o] --> o 
  isNeList : [o] --> o 
  isNePal : [o] --> o 
  isPal : [o] --> o 
  isQid : [o] --> o 
  n!6220!6220!6220!6220 : [o * o] --> o 
  n!6220!6220a : [] --> o 
  n!6220!6220e : [] --> o 
  n!6220!6220i : [] --> o 
  n!6220!6220isList : [o] --> o 
  n!6220!6220isNeList : [o] --> o 
  n!6220!6220isPal : [o] --> o 
  n!6220!6220nil : [] --> o 
  n!6220!6220o : [] --> o 
  n!6220!6220u : [] --> o 
  nil : [] --> o 
  o : [] --> o 
  tt : [] --> o 
  u : [] --> o 

  !6220!6220(!6220!6220(X, Y), Z) => !6220!6220(X, !6220!6220(Y, Z)) 
  !6220!6220(X, nil) => X 
  !6220!6220(nil, X) => X 
  and(tt, X) => activate(X) 
  isList(X) => isNeList(activate(X)) 
  isList(n!6220!6220nil) => tt 
  isList(n!6220!6220!6220!6220(X, Y)) => and(isList(activate(X)), n!6220!6220isList(activate(Y))) 
  isNeList(X) => isQid(activate(X)) 
  isNeList(n!6220!6220!6220!6220(X, Y)) => and(isList(activate(X)), n!6220!6220isNeList(activate(Y))) 
  isNeList(n!6220!6220!6220!6220(X, Y)) => and(isNeList(activate(X)), n!6220!6220isList(activate(Y))) 
  isNePal(X) => isQid(activate(X)) 
  isNePal(n!6220!6220!6220!6220(X, !6220!6220(Y, X))) => and(isQid(activate(X)), n!6220!6220isPal(activate(Y))) 
  isPal(X) => isNePal(activate(X)) 
  isPal(n!6220!6220nil) => tt 
  isQid(n!6220!6220a) => tt 
  isQid(n!6220!6220e) => tt 
  isQid(n!6220!6220i) => tt 
  isQid(n!6220!6220o) => tt 
  isQid(n!6220!6220u) => tt 
  nil => n!6220!6220nil 
  !6220!6220(X, Y) => n!6220!6220!6220!6220(X, Y) 
  isList(X) => n!6220!6220isList(X) 
  isNeList(X) => n!6220!6220isNeList(X) 
  isPal(X) => n!6220!6220isPal(X) 
  a => n!6220!6220a 
  e => n!6220!6220e 
  i => n!6220!6220i 
  o => n!6220!6220o 
  u => n!6220!6220u 
  activate(n!6220!6220nil) => nil 
  activate(n!6220!6220!6220!6220(X, Y)) => !6220!6220(X, Y) 
  activate(n!6220!6220isList(X)) => isList(X) 
  activate(n!6220!6220isNeList(X)) => isNeList(X) 
  activate(n!6220!6220isPal(X)) => isPal(X) 
  activate(n!6220!6220a) => a 
  activate(n!6220!6220e) => e 
  activate(n!6220!6220i) => i 
  activate(n!6220!6220o) => o 
  activate(n!6220!6220u) => u 
  activate(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]):

  !6220!6220(!6220!6220(X, Y), Z) >? !6220!6220(X, !6220!6220(Y, Z)) 
  !6220!6220(X, nil) >? X 
  !6220!6220(nil, X) >? X 
  and(tt, X) >? activate(X) 
  isList(X) >? isNeList(activate(X)) 
  isList(n!6220!6220nil) >? tt 
  isList(n!6220!6220!6220!6220(X, Y)) >? and(isList(activate(X)), n!6220!6220isList(activate(Y))) 
  isNeList(X) >? isQid(activate(X)) 
  isNeList(n!6220!6220!6220!6220(X, Y)) >? and(isList(activate(X)), n!6220!6220isNeList(activate(Y))) 
  isNeList(n!6220!6220!6220!6220(X, Y)) >? and(isNeList(activate(X)), n!6220!6220isList(activate(Y))) 
  isNePal(X) >? isQid(activate(X)) 
  isNePal(n!6220!6220!6220!6220(X, !6220!6220(Y, X))) >? and(isQid(activate(X)), n!6220!6220isPal(activate(Y))) 
  isPal(X) >? isNePal(activate(X)) 
  isPal(n!6220!6220nil) >? tt 
  isQid(n!6220!6220a) >? tt 
  isQid(n!6220!6220e) >? tt 
  isQid(n!6220!6220i) >? tt 
  isQid(n!6220!6220o) >? tt 
  isQid(n!6220!6220u) >? tt 
  nil >? n!6220!6220nil 
  !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) 
  isList(X) >? n!6220!6220isList(X) 
  isNeList(X) >? n!6220!6220isNeList(X) 
  isPal(X) >? n!6220!6220isPal(X) 
  a >? n!6220!6220a 
  e >? n!6220!6220e 
  i >? n!6220!6220i 
  o >? n!6220!6220o 
  u >? n!6220!6220u 
  activate(n!6220!6220nil) >? nil 
  activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(X, Y) 
  activate(n!6220!6220isList(X)) >? isList(X) 
  activate(n!6220!6220isNeList(X)) >? isNeList(X) 
  activate(n!6220!6220isPal(X)) >? isPal(X) 
  activate(n!6220!6220a) >? a 
  activate(n!6220!6220e) >? e 
  activate(n!6220!6220i) >? i 
  activate(n!6220!6220o) >? o 
  activate(n!6220!6220u) >? u 
  activate(X) >? X 

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

The following interpretation satisfies the requirements:

  !6220!6220 = \y0y1.y0 + y1 
  a = 0 
  activate = \y0.y0 
  and = \y0y1.y0 + y1 
  e = 2 
  i = 0 
  isList = \y0.y0 
  isNeList = \y0.y0 
  isNePal = \y0.y0 
  isPal = \y0.y0 
  isQid = \y0.y0 
  n!6220!6220!6220!6220 = \y0y1.y0 + y1 
  n!6220!6220a = 0 
  n!6220!6220e = 2 
  n!6220!6220i = 0 
  n!6220!6220isList = \y0.y0 
  n!6220!6220isNeList = \y0.y0 
  n!6220!6220isPal = \y0.y0 
  n!6220!6220nil = 0 
  n!6220!6220o = 0 
  n!6220!6220u = 0 
  nil = 0 
  o = 0 
  tt = 0 
  u = 0 

Using this interpretation, the requirements translate to:

  [[!6220!6220(!6220!6220(_x0, _x1), _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[!6220!6220(_x0, !6220!6220(_x1, _x2))]] 
  [[!6220!6220(_x0, nil)]] = x0 >= x0 = [[_x0]] 
  [[!6220!6220(nil, _x0)]] = x0 >= x0 = [[_x0]] 
  [[and(tt, _x0)]] = x0 >= x0 = [[activate(_x0)]] 
  [[isList(_x0)]] = x0 >= x0 = [[isNeList(activate(_x0))]] 
  [[isList(n!6220!6220nil)]] = 0 >= 0 = [[tt]] 
  [[isList(n!6220!6220!6220!6220(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[and(isList(activate(_x0)), n!6220!6220isList(activate(_x1)))]] 
  [[isNeList(_x0)]] = x0 >= x0 = [[isQid(activate(_x0))]] 
  [[isNeList(n!6220!6220!6220!6220(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[and(isList(activate(_x0)), n!6220!6220isNeList(activate(_x1)))]] 
  [[isNeList(n!6220!6220!6220!6220(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[and(isNeList(activate(_x0)), n!6220!6220isList(activate(_x1)))]] 
  [[isNePal(_x0)]] = x0 >= x0 = [[isQid(activate(_x0))]] 
  [[isNePal(n!6220!6220!6220!6220(_x0, !6220!6220(_x1, _x0)))]] = x1 + 2x0 >= x0 + x1 = [[and(isQid(activate(_x0)), n!6220!6220isPal(activate(_x1)))]] 
  [[isPal(_x0)]] = x0 >= x0 = [[isNePal(activate(_x0))]] 
  [[isPal(n!6220!6220nil)]] = 0 >= 0 = [[tt]] 
  [[isQid(n!6220!6220a)]] = 0 >= 0 = [[tt]] 
  [[isQid(n!6220!6220e)]] = 2 > 0 = [[tt]] 
  [[isQid(n!6220!6220i)]] = 0 >= 0 = [[tt]] 
  [[isQid(n!6220!6220o)]] = 0 >= 0 = [[tt]] 
  [[isQid(n!6220!6220u)]] = 0 >= 0 = [[tt]] 
  [[nil]] = 0 >= 0 = [[n!6220!6220nil]] 
  [[!6220!6220(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] 
  [[isList(_x0)]] = x0 >= x0 = [[n!6220!6220isList(_x0)]] 
  [[isNeList(_x0)]] = x0 >= x0 = [[n!6220!6220isNeList(_x0)]] 
  [[isPal(_x0)]] = x0 >= x0 = [[n!6220!6220isPal(_x0)]] 
  [[a]] = 0 >= 0 = [[n!6220!6220a]] 
  [[e]] = 2 >= 2 = [[n!6220!6220e]] 
  [[i]] = 0 >= 0 = [[n!6220!6220i]] 
  [[o]] = 0 >= 0 = [[n!6220!6220o]] 
  [[u]] = 0 >= 0 = [[n!6220!6220u]] 
  [[activate(n!6220!6220nil)]] = 0 >= 0 = [[nil]] 
  [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] 
  [[activate(n!6220!6220isList(_x0))]] = x0 >= x0 = [[isList(_x0)]] 
  [[activate(n!6220!6220isNeList(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] 
  [[activate(n!6220!6220isPal(_x0))]] = x0 >= x0 = [[isPal(_x0)]] 
  [[activate(n!6220!6220a)]] = 0 >= 0 = [[a]] 
  [[activate(n!6220!6220e)]] = 2 >= 2 = [[e]] 
  [[activate(n!6220!6220i)]] = 0 >= 0 = [[i]] 
  [[activate(n!6220!6220o)]] = 0 >= 0 = [[o]] 
  [[activate(n!6220!6220u)]] = 0 >= 0 = [[u]] 
  [[activate(_x0)]] = x0 >= x0 = [[_x0]] 

We can thus remove the following rules:

  isQid(n!6220!6220e) => tt 

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

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

  !6220!6220(!6220!6220(X, Y), Z) >? !6220!6220(X, !6220!6220(Y, Z)) 
  !6220!6220(X, nil) >? X 
  !6220!6220(nil, X) >? X 
  and(tt, X) >? activate(X) 
  isList(X) >? isNeList(activate(X)) 
  isList(n!6220!6220nil) >? tt 
  isList(n!6220!6220!6220!6220(X, Y)) >? and(isList(activate(X)), n!6220!6220isList(activate(Y))) 
  isNeList(X) >? isQid(activate(X)) 
  isNeList(n!6220!6220!6220!6220(X, Y)) >? and(isList(activate(X)), n!6220!6220isNeList(activate(Y))) 
  isNeList(n!6220!6220!6220!6220(X, Y)) >? and(isNeList(activate(X)), n!6220!6220isList(activate(Y))) 
  isNePal(X) >? isQid(activate(X)) 
  isNePal(n!6220!6220!6220!6220(X, !6220!6220(Y, X))) >? and(isQid(activate(X)), n!6220!6220isPal(activate(Y))) 
  isPal(X) >? isNePal(activate(X)) 
  isPal(n!6220!6220nil) >? tt 
  isQid(n!6220!6220a) >? tt 
  isQid(n!6220!6220i) >? tt 
  isQid(n!6220!6220o) >? tt 
  isQid(n!6220!6220u) >? tt 
  nil >? n!6220!6220nil 
  !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) 
  isList(X) >? n!6220!6220isList(X) 
  isNeList(X) >? n!6220!6220isNeList(X) 
  isPal(X) >? n!6220!6220isPal(X) 
  a >? n!6220!6220a 
  e >? n!6220!6220e 
  i >? n!6220!6220i 
  o >? n!6220!6220o 
  u >? n!6220!6220u 
  activate(n!6220!6220nil) >? nil 
  activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(X, Y) 
  activate(n!6220!6220isList(X)) >? isList(X) 
  activate(n!6220!6220isNeList(X)) >? isNeList(X) 
  activate(n!6220!6220isPal(X)) >? isPal(X) 
  activate(n!6220!6220a) >? a 
  activate(n!6220!6220e) >? e 
  activate(n!6220!6220i) >? i 
  activate(n!6220!6220o) >? o 
  activate(n!6220!6220u) >? u 
  activate(X) >? X 

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

The following interpretation satisfies the requirements:

  !6220!6220 = \y0y1.2 + y1 + 2y0 
  a = 1 
  activate = \y0.y0 
  and = \y0y1.y1 + 2y0 
  e = 0 
  i = 1 
  isList = \y0.2y0 
  isNeList = \y0.2y0 
  isNePal = \y0.y0 
  isPal = \y0.2y0 
  isQid = \y0.y0 
  n!6220!6220!6220!6220 = \y0y1.2 + y1 + 2y0 
  n!6220!6220a = 1 
  n!6220!6220e = 0 
  n!6220!6220i = 1 
  n!6220!6220isList = \y0.2y0 
  n!6220!6220isNeList = \y0.2y0 
  n!6220!6220isPal = \y0.2y0 
  n!6220!6220nil = 0 
  n!6220!6220o = 0 
  n!6220!6220u = 0 
  nil = 0 
  o = 0 
  tt = 0 
  u = 0 

Using this interpretation, the requirements translate to:

  [[!6220!6220(!6220!6220(_x0, _x1), _x2)]] = 6 + x2 + 2x1 + 4x0 > 4 + x2 + 2x0 + 2x1 = [[!6220!6220(_x0, !6220!6220(_x1, _x2))]] 
  [[!6220!6220(_x0, nil)]] = 2 + 2x0 > x0 = [[_x0]] 
  [[!6220!6220(nil, _x0)]] = 2 + x0 > x0 = [[_x0]] 
  [[and(tt, _x0)]] = x0 >= x0 = [[activate(_x0)]] 
  [[isList(_x0)]] = 2x0 >= 2x0 = [[isNeList(activate(_x0))]] 
  [[isList(n!6220!6220nil)]] = 0 >= 0 = [[tt]] 
  [[isList(n!6220!6220!6220!6220(_x0, _x1))]] = 4 + 2x1 + 4x0 > 2x1 + 4x0 = [[and(isList(activate(_x0)), n!6220!6220isList(activate(_x1)))]] 
  [[isNeList(_x0)]] = 2x0 >= x0 = [[isQid(activate(_x0))]] 
  [[isNeList(n!6220!6220!6220!6220(_x0, _x1))]] = 4 + 2x1 + 4x0 > 2x1 + 4x0 = [[and(isList(activate(_x0)), n!6220!6220isNeList(activate(_x1)))]] 
  [[isNeList(n!6220!6220!6220!6220(_x0, _x1))]] = 4 + 2x1 + 4x0 > 2x1 + 4x0 = [[and(isNeList(activate(_x0)), n!6220!6220isList(activate(_x1)))]] 
  [[isNePal(_x0)]] = x0 >= x0 = [[isQid(activate(_x0))]] 
  [[isNePal(n!6220!6220!6220!6220(_x0, !6220!6220(_x1, _x0)))]] = 4 + 2x1 + 3x0 > 2x0 + 2x1 = [[and(isQid(activate(_x0)), n!6220!6220isPal(activate(_x1)))]] 
  [[isPal(_x0)]] = 2x0 >= x0 = [[isNePal(activate(_x0))]] 
  [[isPal(n!6220!6220nil)]] = 0 >= 0 = [[tt]] 
  [[isQid(n!6220!6220a)]] = 1 > 0 = [[tt]] 
  [[isQid(n!6220!6220i)]] = 1 > 0 = [[tt]] 
  [[isQid(n!6220!6220o)]] = 0 >= 0 = [[tt]] 
  [[isQid(n!6220!6220u)]] = 0 >= 0 = [[tt]] 
  [[nil]] = 0 >= 0 = [[n!6220!6220nil]] 
  [[!6220!6220(_x0, _x1)]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[n!6220!6220!6220!6220(_x0, _x1)]] 
  [[isList(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220isList(_x0)]] 
  [[isNeList(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220isNeList(_x0)]] 
  [[isPal(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220isPal(_x0)]] 
  [[a]] = 1 >= 1 = [[n!6220!6220a]] 
  [[e]] = 0 >= 0 = [[n!6220!6220e]] 
  [[i]] = 1 >= 1 = [[n!6220!6220i]] 
  [[o]] = 0 >= 0 = [[n!6220!6220o]] 
  [[u]] = 0 >= 0 = [[n!6220!6220u]] 
  [[activate(n!6220!6220nil)]] = 0 >= 0 = [[nil]] 
  [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[!6220!6220(_x0, _x1)]] 
  [[activate(n!6220!6220isList(_x0))]] = 2x0 >= 2x0 = [[isList(_x0)]] 
  [[activate(n!6220!6220isNeList(_x0))]] = 2x0 >= 2x0 = [[isNeList(_x0)]] 
  [[activate(n!6220!6220isPal(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] 
  [[activate(n!6220!6220a)]] = 1 >= 1 = [[a]] 
  [[activate(n!6220!6220e)]] = 0 >= 0 = [[e]] 
  [[activate(n!6220!6220i)]] = 1 >= 1 = [[i]] 
  [[activate(n!6220!6220o)]] = 0 >= 0 = [[o]] 
  [[activate(n!6220!6220u)]] = 0 >= 0 = [[u]] 
  [[activate(_x0)]] = x0 >= x0 = [[_x0]] 

We can thus remove the following rules:

  !6220!6220(!6220!6220(X, Y), Z) => !6220!6220(X, !6220!6220(Y, Z)) 
  !6220!6220(X, nil) => X 
  !6220!6220(nil, X) => X 
  isList(n!6220!6220!6220!6220(X, Y)) => and(isList(activate(X)), n!6220!6220isList(activate(Y))) 
  isNeList(n!6220!6220!6220!6220(X, Y)) => and(isList(activate(X)), n!6220!6220isNeList(activate(Y))) 
  isNeList(n!6220!6220!6220!6220(X, Y)) => and(isNeList(activate(X)), n!6220!6220isList(activate(Y))) 
  isNePal(n!6220!6220!6220!6220(X, !6220!6220(Y, X))) => and(isQid(activate(X)), n!6220!6220isPal(activate(Y))) 
  isQid(n!6220!6220a) => tt 
  isQid(n!6220!6220i) => tt 

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(tt, X) >? activate(X) 
  isList(X) >? isNeList(activate(X)) 
  isList(n!6220!6220nil) >? tt 
  isNeList(X) >? isQid(activate(X)) 
  isNePal(X) >? isQid(activate(X)) 
  isPal(X) >? isNePal(activate(X)) 
  isPal(n!6220!6220nil) >? tt 
  isQid(n!6220!6220o) >? tt 
  isQid(n!6220!6220u) >? tt 
  nil >? n!6220!6220nil 
  !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) 
  isList(X) >? n!6220!6220isList(X) 
  isNeList(X) >? n!6220!6220isNeList(X) 
  isPal(X) >? n!6220!6220isPal(X) 
  a >? n!6220!6220a 
  e >? n!6220!6220e 
  i >? n!6220!6220i 
  o >? n!6220!6220o 
  u >? n!6220!6220u 
  activate(n!6220!6220nil) >? nil 
  activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(X, Y) 
  activate(n!6220!6220isList(X)) >? isList(X) 
  activate(n!6220!6220isNeList(X)) >? isNeList(X) 
  activate(n!6220!6220isPal(X)) >? isPal(X) 
  activate(n!6220!6220a) >? a 
  activate(n!6220!6220e) >? e 
  activate(n!6220!6220i) >? i 
  activate(n!6220!6220o) >? o 
  activate(n!6220!6220u) >? u 
  activate(X) >? X 

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

The following interpretation satisfies the requirements:

  !6220!6220 = \y0y1.y0 + 2y1 
  a = 0 
  activate = \y0.y0 
  and = \y0y1.3 + 3y0 + 3y1 
  e = 0 
  i = 0 
  isList = \y0.y0 
  isNeList = \y0.y0 
  isNePal = \y0.y0 
  isPal = \y0.y0 
  isQid = \y0.y0 
  n!6220!6220!6220!6220 = \y0y1.y0 + 2y1 
  n!6220!6220a = 0 
  n!6220!6220e = 0 
  n!6220!6220i = 0 
  n!6220!6220isList = \y0.y0 
  n!6220!6220isNeList = \y0.y0 
  n!6220!6220isPal = \y0.y0 
  n!6220!6220nil = 2 
  n!6220!6220o = 1 
  n!6220!6220u = 2 
  nil = 2 
  o = 1 
  tt = 1 
  u = 2 

Using this interpretation, the requirements translate to:

  [[and(tt, _x0)]] = 6 + 3x0 > x0 = [[activate(_x0)]] 
  [[isList(_x0)]] = x0 >= x0 = [[isNeList(activate(_x0))]] 
  [[isList(n!6220!6220nil)]] = 2 > 1 = [[tt]] 
  [[isNeList(_x0)]] = x0 >= x0 = [[isQid(activate(_x0))]] 
  [[isNePal(_x0)]] = x0 >= x0 = [[isQid(activate(_x0))]] 
  [[isPal(_x0)]] = x0 >= x0 = [[isNePal(activate(_x0))]] 
  [[isPal(n!6220!6220nil)]] = 2 > 1 = [[tt]] 
  [[isQid(n!6220!6220o)]] = 1 >= 1 = [[tt]] 
  [[isQid(n!6220!6220u)]] = 2 > 1 = [[tt]] 
  [[nil]] = 2 >= 2 = [[n!6220!6220nil]] 
  [[!6220!6220(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] 
  [[isList(_x0)]] = x0 >= x0 = [[n!6220!6220isList(_x0)]] 
  [[isNeList(_x0)]] = x0 >= x0 = [[n!6220!6220isNeList(_x0)]] 
  [[isPal(_x0)]] = x0 >= x0 = [[n!6220!6220isPal(_x0)]] 
  [[a]] = 0 >= 0 = [[n!6220!6220a]] 
  [[e]] = 0 >= 0 = [[n!6220!6220e]] 
  [[i]] = 0 >= 0 = [[n!6220!6220i]] 
  [[o]] = 1 >= 1 = [[n!6220!6220o]] 
  [[u]] = 2 >= 2 = [[n!6220!6220u]] 
  [[activate(n!6220!6220nil)]] = 2 >= 2 = [[nil]] 
  [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[!6220!6220(_x0, _x1)]] 
  [[activate(n!6220!6220isList(_x0))]] = x0 >= x0 = [[isList(_x0)]] 
  [[activate(n!6220!6220isNeList(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] 
  [[activate(n!6220!6220isPal(_x0))]] = x0 >= x0 = [[isPal(_x0)]] 
  [[activate(n!6220!6220a)]] = 0 >= 0 = [[a]] 
  [[activate(n!6220!6220e)]] = 0 >= 0 = [[e]] 
  [[activate(n!6220!6220i)]] = 0 >= 0 = [[i]] 
  [[activate(n!6220!6220o)]] = 1 >= 1 = [[o]] 
  [[activate(n!6220!6220u)]] = 2 >= 2 = [[u]] 
  [[activate(_x0)]] = x0 >= x0 = [[_x0]] 

We can thus remove the following rules:

  and(tt, X) => activate(X) 
  isList(n!6220!6220nil) => tt 
  isPal(n!6220!6220nil) => tt 
  isQid(n!6220!6220u) => tt 

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

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

  isList(X) >? isNeList(activate(X)) 
  isNeList(X) >? isQid(activate(X)) 
  isNePal(X) >? isQid(activate(X)) 
  isPal(X) >? isNePal(activate(X)) 
  isQid(n!6220!6220o) >? tt 
  nil >? n!6220!6220nil 
  !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) 
  isList(X) >? n!6220!6220isList(X) 
  isNeList(X) >? n!6220!6220isNeList(X) 
  isPal(X) >? n!6220!6220isPal(X) 
  a >? n!6220!6220a 
  e >? n!6220!6220e 
  i >? n!6220!6220i 
  o >? n!6220!6220o 
  u >? n!6220!6220u 
  activate(n!6220!6220nil) >? nil 
  activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(X, Y) 
  activate(n!6220!6220isList(X)) >? isList(X) 
  activate(n!6220!6220isNeList(X)) >? isNeList(X) 
  activate(n!6220!6220isPal(X)) >? isPal(X) 
  activate(n!6220!6220a) >? a 
  activate(n!6220!6220e) >? e 
  activate(n!6220!6220i) >? i 
  activate(n!6220!6220o) >? o 
  activate(n!6220!6220u) >? u 
  activate(X) >? X 

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

The following interpretation satisfies the requirements:

  !6220!6220 = \y0y1.y0 + 2y1 
  a = 1 
  activate = \y0.y0 
  e = 1 
  i = 0 
  isList = \y0.2y0 
  isNeList = \y0.2y0 
  isNePal = \y0.1 + y0 
  isPal = \y0.1 + y0 
  isQid = \y0.y0 
  n!6220!6220!6220!6220 = \y0y1.y0 + 2y1 
  n!6220!6220a = 1 
  n!6220!6220e = 1 
  n!6220!6220i = 0 
  n!6220!6220isList = \y0.2y0 
  n!6220!6220isNeList = \y0.2y0 
  n!6220!6220isPal = \y0.1 + y0 
  n!6220!6220nil = 0 
  n!6220!6220o = 0 
  n!6220!6220u = 0 
  nil = 0 
  o = 0 
  tt = 0 
  u = 0 

Using this interpretation, the requirements translate to:

  [[isList(_x0)]] = 2x0 >= 2x0 = [[isNeList(activate(_x0))]] 
  [[isNeList(_x0)]] = 2x0 >= x0 = [[isQid(activate(_x0))]] 
  [[isNePal(_x0)]] = 1 + x0 > x0 = [[isQid(activate(_x0))]] 
  [[isPal(_x0)]] = 1 + x0 >= 1 + x0 = [[isNePal(activate(_x0))]] 
  [[isQid(n!6220!6220o)]] = 0 >= 0 = [[tt]] 
  [[nil]] = 0 >= 0 = [[n!6220!6220nil]] 
  [[!6220!6220(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] 
  [[isList(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220isList(_x0)]] 
  [[isNeList(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220isNeList(_x0)]] 
  [[isPal(_x0)]] = 1 + x0 >= 1 + x0 = [[n!6220!6220isPal(_x0)]] 
  [[a]] = 1 >= 1 = [[n!6220!6220a]] 
  [[e]] = 1 >= 1 = [[n!6220!6220e]] 
  [[i]] = 0 >= 0 = [[n!6220!6220i]] 
  [[o]] = 0 >= 0 = [[n!6220!6220o]] 
  [[u]] = 0 >= 0 = [[n!6220!6220u]] 
  [[activate(n!6220!6220nil)]] = 0 >= 0 = [[nil]] 
  [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[!6220!6220(_x0, _x1)]] 
  [[activate(n!6220!6220isList(_x0))]] = 2x0 >= 2x0 = [[isList(_x0)]] 
  [[activate(n!6220!6220isNeList(_x0))]] = 2x0 >= 2x0 = [[isNeList(_x0)]] 
  [[activate(n!6220!6220isPal(_x0))]] = 1 + x0 >= 1 + x0 = [[isPal(_x0)]] 
  [[activate(n!6220!6220a)]] = 1 >= 1 = [[a]] 
  [[activate(n!6220!6220e)]] = 1 >= 1 = [[e]] 
  [[activate(n!6220!6220i)]] = 0 >= 0 = [[i]] 
  [[activate(n!6220!6220o)]] = 0 >= 0 = [[o]] 
  [[activate(n!6220!6220u)]] = 0 >= 0 = [[u]] 
  [[activate(_x0)]] = x0 >= x0 = [[_x0]] 

We can thus remove the following rules:

  isNePal(X) => isQid(activate(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]):

  isList(X) >? isNeList(activate(X)) 
  isNeList(X) >? isQid(activate(X)) 
  isPal(X) >? isNePal(activate(X)) 
  isQid(n!6220!6220o) >? tt 
  nil >? n!6220!6220nil 
  !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) 
  isList(X) >? n!6220!6220isList(X) 
  isNeList(X) >? n!6220!6220isNeList(X) 
  isPal(X) >? n!6220!6220isPal(X) 
  a >? n!6220!6220a 
  e >? n!6220!6220e 
  i >? n!6220!6220i 
  o >? n!6220!6220o 
  u >? n!6220!6220u 
  activate(n!6220!6220nil) >? nil 
  activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(X, Y) 
  activate(n!6220!6220isList(X)) >? isList(X) 
  activate(n!6220!6220isNeList(X)) >? isNeList(X) 
  activate(n!6220!6220isPal(X)) >? isPal(X) 
  activate(n!6220!6220a) >? a 
  activate(n!6220!6220e) >? e 
  activate(n!6220!6220i) >? i 
  activate(n!6220!6220o) >? o 
  activate(n!6220!6220u) >? u 
  activate(X) >? X 

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

The following interpretation satisfies the requirements:

  !6220!6220 = \y0y1.y1 + 2y0 
  a = 0 
  activate = \y0.y0 
  e = 0 
  i = 0 
  isList = \y0.1 + 2y0 
  isNeList = \y0.1 + 2y0 
  isNePal = \y0.y0 
  isPal = \y0.2y0 
  isQid = \y0.1 + y0 
  n!6220!6220!6220!6220 = \y0y1.y1 + 2y0 
  n!6220!6220a = 0 
  n!6220!6220e = 0 
  n!6220!6220i = 0 
  n!6220!6220isList = \y0.1 + 2y0 
  n!6220!6220isNeList = \y0.1 + 2y0 
  n!6220!6220isPal = \y0.2y0 
  n!6220!6220nil = 0 
  n!6220!6220o = 1 
  n!6220!6220u = 0 
  nil = 0 
  o = 1 
  tt = 0 
  u = 0 

Using this interpretation, the requirements translate to:

  [[isList(_x0)]] = 1 + 2x0 >= 1 + 2x0 = [[isNeList(activate(_x0))]] 
  [[isNeList(_x0)]] = 1 + 2x0 >= 1 + x0 = [[isQid(activate(_x0))]] 
  [[isPal(_x0)]] = 2x0 >= x0 = [[isNePal(activate(_x0))]] 
  [[isQid(n!6220!6220o)]] = 2 > 0 = [[tt]] 
  [[nil]] = 0 >= 0 = [[n!6220!6220nil]] 
  [[!6220!6220(_x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[n!6220!6220!6220!6220(_x0, _x1)]] 
  [[isList(_x0)]] = 1 + 2x0 >= 1 + 2x0 = [[n!6220!6220isList(_x0)]] 
  [[isNeList(_x0)]] = 1 + 2x0 >= 1 + 2x0 = [[n!6220!6220isNeList(_x0)]] 
  [[isPal(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220isPal(_x0)]] 
  [[a]] = 0 >= 0 = [[n!6220!6220a]] 
  [[e]] = 0 >= 0 = [[n!6220!6220e]] 
  [[i]] = 0 >= 0 = [[n!6220!6220i]] 
  [[o]] = 1 >= 1 = [[n!6220!6220o]] 
  [[u]] = 0 >= 0 = [[n!6220!6220u]] 
  [[activate(n!6220!6220nil)]] = 0 >= 0 = [[nil]] 
  [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] 
  [[activate(n!6220!6220isList(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[isList(_x0)]] 
  [[activate(n!6220!6220isNeList(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[isNeList(_x0)]] 
  [[activate(n!6220!6220isPal(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] 
  [[activate(n!6220!6220a)]] = 0 >= 0 = [[a]] 
  [[activate(n!6220!6220e)]] = 0 >= 0 = [[e]] 
  [[activate(n!6220!6220i)]] = 0 >= 0 = [[i]] 
  [[activate(n!6220!6220o)]] = 1 >= 1 = [[o]] 
  [[activate(n!6220!6220u)]] = 0 >= 0 = [[u]] 
  [[activate(_x0)]] = x0 >= x0 = [[_x0]] 

We can thus remove the following rules:

  isQid(n!6220!6220o) => tt 

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

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

  isList(X) >? isNeList(activate(X)) 
  isNeList(X) >? isQid(activate(X)) 
  isPal(X) >? isNePal(activate(X)) 
  nil >? n!6220!6220nil 
  !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) 
  isList(X) >? n!6220!6220isList(X) 
  isNeList(X) >? n!6220!6220isNeList(X) 
  isPal(X) >? n!6220!6220isPal(X) 
  a >? n!6220!6220a 
  e >? n!6220!6220e 
  i >? n!6220!6220i 
  o >? n!6220!6220o 
  u >? n!6220!6220u 
  activate(n!6220!6220nil) >? nil 
  activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(X, Y) 
  activate(n!6220!6220isList(X)) >? isList(X) 
  activate(n!6220!6220isNeList(X)) >? isNeList(X) 
  activate(n!6220!6220isPal(X)) >? isPal(X) 
  activate(n!6220!6220a) >? a 
  activate(n!6220!6220e) >? e 
  activate(n!6220!6220i) >? i 
  activate(n!6220!6220o) >? o 
  activate(n!6220!6220u) >? u 
  activate(X) >? X 

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

The following interpretation satisfies the requirements:

  !6220!6220 = \y0y1.2y0 + 2y1 
  a = 0 
  activate = \y0.y0 
  e = 0 
  i = 0 
  isList = \y0.2y0 
  isNeList = \y0.2y0 
  isNePal = \y0.y0 
  isPal = \y0.2 + y0 
  isQid = \y0.y0 
  n!6220!6220!6220!6220 = \y0y1.2y0 + 2y1 
  n!6220!6220a = 0 
  n!6220!6220e = 0 
  n!6220!6220i = 0 
  n!6220!6220isList = \y0.2y0 
  n!6220!6220isNeList = \y0.2y0 
  n!6220!6220isPal = \y0.2 + y0 
  n!6220!6220nil = 0 
  n!6220!6220o = 0 
  n!6220!6220u = 0 
  nil = 0 
  o = 0 
  u = 0 

Using this interpretation, the requirements translate to:

  [[isList(_x0)]] = 2x0 >= 2x0 = [[isNeList(activate(_x0))]] 
  [[isNeList(_x0)]] = 2x0 >= x0 = [[isQid(activate(_x0))]] 
  [[isPal(_x0)]] = 2 + x0 > x0 = [[isNePal(activate(_x0))]] 
  [[nil]] = 0 >= 0 = [[n!6220!6220nil]] 
  [[!6220!6220(_x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] 
  [[isList(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220isList(_x0)]] 
  [[isNeList(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220isNeList(_x0)]] 
  [[isPal(_x0)]] = 2 + x0 >= 2 + x0 = [[n!6220!6220isPal(_x0)]] 
  [[a]] = 0 >= 0 = [[n!6220!6220a]] 
  [[e]] = 0 >= 0 = [[n!6220!6220e]] 
  [[i]] = 0 >= 0 = [[n!6220!6220i]] 
  [[o]] = 0 >= 0 = [[n!6220!6220o]] 
  [[u]] = 0 >= 0 = [[n!6220!6220u]] 
  [[activate(n!6220!6220nil)]] = 0 >= 0 = [[nil]] 
  [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[!6220!6220(_x0, _x1)]] 
  [[activate(n!6220!6220isList(_x0))]] = 2x0 >= 2x0 = [[isList(_x0)]] 
  [[activate(n!6220!6220isNeList(_x0))]] = 2x0 >= 2x0 = [[isNeList(_x0)]] 
  [[activate(n!6220!6220isPal(_x0))]] = 2 + x0 >= 2 + x0 = [[isPal(_x0)]] 
  [[activate(n!6220!6220a)]] = 0 >= 0 = [[a]] 
  [[activate(n!6220!6220e)]] = 0 >= 0 = [[e]] 
  [[activate(n!6220!6220i)]] = 0 >= 0 = [[i]] 
  [[activate(n!6220!6220o)]] = 0 >= 0 = [[o]] 
  [[activate(n!6220!6220u)]] = 0 >= 0 = [[u]] 
  [[activate(_x0)]] = x0 >= x0 = [[_x0]] 

We can thus remove the following rules:

  isPal(X) => isNePal(activate(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]):

  isList(X) >? isNeList(activate(X)) 
  isNeList(X) >? isQid(activate(X)) 
  nil >? n!6220!6220nil 
  !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) 
  isList(X) >? n!6220!6220isList(X) 
  isNeList(X) >? n!6220!6220isNeList(X) 
  isPal(X) >? n!6220!6220isPal(X) 
  a >? n!6220!6220a 
  e >? n!6220!6220e 
  i >? n!6220!6220i 
  o >? n!6220!6220o 
  u >? n!6220!6220u 
  activate(n!6220!6220nil) >? nil 
  activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(X, Y) 
  activate(n!6220!6220isList(X)) >? isList(X) 
  activate(n!6220!6220isNeList(X)) >? isNeList(X) 
  activate(n!6220!6220isPal(X)) >? isPal(X) 
  activate(n!6220!6220a) >? a 
  activate(n!6220!6220e) >? e 
  activate(n!6220!6220i) >? i 
  activate(n!6220!6220o) >? o 
  activate(n!6220!6220u) >? u 
  activate(X) >? X 

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

The following interpretation satisfies the requirements:

  !6220!6220 = \y0y1.y1 + 2y0 
  a = 0 
  activate = \y0.y0 
  e = 0 
  i = 0 
  isList = \y0.1 + 2y0 
  isNeList = \y0.1 + 2y0 
  isPal = \y0.y0 
  isQid = \y0.y0 
  n!6220!6220!6220!6220 = \y0y1.y1 + 2y0 
  n!6220!6220a = 0 
  n!6220!6220e = 0 
  n!6220!6220i = 0 
  n!6220!6220isList = \y0.1 + 2y0 
  n!6220!6220isNeList = \y0.1 + 2y0 
  n!6220!6220isPal = \y0.y0 
  n!6220!6220nil = 0 
  n!6220!6220o = 0 
  n!6220!6220u = 0 
  nil = 0 
  o = 0 
  u = 0 

Using this interpretation, the requirements translate to:

  [[isList(_x0)]] = 1 + 2x0 >= 1 + 2x0 = [[isNeList(activate(_x0))]] 
  [[isNeList(_x0)]] = 1 + 2x0 > x0 = [[isQid(activate(_x0))]] 
  [[nil]] = 0 >= 0 = [[n!6220!6220nil]] 
  [[!6220!6220(_x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[n!6220!6220!6220!6220(_x0, _x1)]] 
  [[isList(_x0)]] = 1 + 2x0 >= 1 + 2x0 = [[n!6220!6220isList(_x0)]] 
  [[isNeList(_x0)]] = 1 + 2x0 >= 1 + 2x0 = [[n!6220!6220isNeList(_x0)]] 
  [[isPal(_x0)]] = x0 >= x0 = [[n!6220!6220isPal(_x0)]] 
  [[a]] = 0 >= 0 = [[n!6220!6220a]] 
  [[e]] = 0 >= 0 = [[n!6220!6220e]] 
  [[i]] = 0 >= 0 = [[n!6220!6220i]] 
  [[o]] = 0 >= 0 = [[n!6220!6220o]] 
  [[u]] = 0 >= 0 = [[n!6220!6220u]] 
  [[activate(n!6220!6220nil)]] = 0 >= 0 = [[nil]] 
  [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] 
  [[activate(n!6220!6220isList(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[isList(_x0)]] 
  [[activate(n!6220!6220isNeList(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[isNeList(_x0)]] 
  [[activate(n!6220!6220isPal(_x0))]] = x0 >= x0 = [[isPal(_x0)]] 
  [[activate(n!6220!6220a)]] = 0 >= 0 = [[a]] 
  [[activate(n!6220!6220e)]] = 0 >= 0 = [[e]] 
  [[activate(n!6220!6220i)]] = 0 >= 0 = [[i]] 
  [[activate(n!6220!6220o)]] = 0 >= 0 = [[o]] 
  [[activate(n!6220!6220u)]] = 0 >= 0 = [[u]] 
  [[activate(_x0)]] = x0 >= x0 = [[_x0]] 

We can thus remove the following rules:

  isNeList(X) => isQid(activate(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]):

  isList(X) >? isNeList(activate(X)) 
  nil >? n!6220!6220nil 
  !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) 
  isList(X) >? n!6220!6220isList(X) 
  isNeList(X) >? n!6220!6220isNeList(X) 
  isPal(X) >? n!6220!6220isPal(X) 
  a >? n!6220!6220a 
  e >? n!6220!6220e 
  i >? n!6220!6220i 
  o >? n!6220!6220o 
  u >? n!6220!6220u 
  activate(n!6220!6220nil) >? nil 
  activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(X, Y) 
  activate(n!6220!6220isList(X)) >? isList(X) 
  activate(n!6220!6220isNeList(X)) >? isNeList(X) 
  activate(n!6220!6220isPal(X)) >? isPal(X) 
  activate(n!6220!6220a) >? a 
  activate(n!6220!6220e) >? e 
  activate(n!6220!6220i) >? i 
  activate(n!6220!6220o) >? o 
  activate(n!6220!6220u) >? u 
  activate(X) >? X 

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

The following interpretation satisfies the requirements:

  !6220!6220 = \y0y1.y0 + y1 
  a = 0 
  activate = \y0.y0 
  e = 0 
  i = 0 
  isList = \y0.1 + 2y0 
  isNeList = \y0.2y0 
  isPal = \y0.y0 
  n!6220!6220!6220!6220 = \y0y1.y0 + y1 
  n!6220!6220a = 0 
  n!6220!6220e = 0 
  n!6220!6220i = 0 
  n!6220!6220isList = \y0.1 + 2y0 
  n!6220!6220isNeList = \y0.2y0 
  n!6220!6220isPal = \y0.y0 
  n!6220!6220nil = 0 
  n!6220!6220o = 0 
  n!6220!6220u = 0 
  nil = 0 
  o = 0 
  u = 0 

Using this interpretation, the requirements translate to:

  [[isList(_x0)]] = 1 + 2x0 > 2x0 = [[isNeList(activate(_x0))]] 
  [[nil]] = 0 >= 0 = [[n!6220!6220nil]] 
  [[!6220!6220(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] 
  [[isList(_x0)]] = 1 + 2x0 >= 1 + 2x0 = [[n!6220!6220isList(_x0)]] 
  [[isNeList(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220isNeList(_x0)]] 
  [[isPal(_x0)]] = x0 >= x0 = [[n!6220!6220isPal(_x0)]] 
  [[a]] = 0 >= 0 = [[n!6220!6220a]] 
  [[e]] = 0 >= 0 = [[n!6220!6220e]] 
  [[i]] = 0 >= 0 = [[n!6220!6220i]] 
  [[o]] = 0 >= 0 = [[n!6220!6220o]] 
  [[u]] = 0 >= 0 = [[n!6220!6220u]] 
  [[activate(n!6220!6220nil)]] = 0 >= 0 = [[nil]] 
  [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] 
  [[activate(n!6220!6220isList(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[isList(_x0)]] 
  [[activate(n!6220!6220isNeList(_x0))]] = 2x0 >= 2x0 = [[isNeList(_x0)]] 
  [[activate(n!6220!6220isPal(_x0))]] = x0 >= x0 = [[isPal(_x0)]] 
  [[activate(n!6220!6220a)]] = 0 >= 0 = [[a]] 
  [[activate(n!6220!6220e)]] = 0 >= 0 = [[e]] 
  [[activate(n!6220!6220i)]] = 0 >= 0 = [[i]] 
  [[activate(n!6220!6220o)]] = 0 >= 0 = [[o]] 
  [[activate(n!6220!6220u)]] = 0 >= 0 = [[u]] 
  [[activate(_x0)]] = x0 >= x0 = [[_x0]] 

We can thus remove the following rules:

  isList(X) => isNeList(activate(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]):

  nil >? n!6220!6220nil 
  !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) 
  isList(X) >? n!6220!6220isList(X) 
  isNeList(X) >? n!6220!6220isNeList(X) 
  isPal(X) >? n!6220!6220isPal(X) 
  a >? n!6220!6220a 
  e >? n!6220!6220e 
  i >? n!6220!6220i 
  o >? n!6220!6220o 
  u >? n!6220!6220u 
  activate(n!6220!6220nil) >? nil 
  activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(X, Y) 
  activate(n!6220!6220isList(X)) >? isList(X) 
  activate(n!6220!6220isNeList(X)) >? isNeList(X) 
  activate(n!6220!6220isPal(X)) >? isPal(X) 
  activate(n!6220!6220a) >? a 
  activate(n!6220!6220e) >? e 
  activate(n!6220!6220i) >? i 
  activate(n!6220!6220o) >? o 
  activate(n!6220!6220u) >? u 
  activate(X) >? X 

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

The following interpretation satisfies the requirements:

  !6220!6220 = \y0y1.y0 + y1 
  a = 2 
  activate = \y0.3 + 3y0 
  e = 0 
  i = 0 
  isList = \y0.1 + 2y0 
  isNeList = \y0.y0 
  isPal = \y0.2 + y0 
  n!6220!6220!6220!6220 = \y0y1.y0 + y1 
  n!6220!6220a = 1 
  n!6220!6220e = 0 
  n!6220!6220i = 0 
  n!6220!6220isList = \y0.2y0 
  n!6220!6220isNeList = \y0.y0 
  n!6220!6220isPal = \y0.1 + y0 
  n!6220!6220nil = 0 
  n!6220!6220o = 1 
  n!6220!6220u = 0 
  nil = 1 
  o = 2 
  u = 2 

Using this interpretation, the requirements translate to:

  [[nil]] = 1 > 0 = [[n!6220!6220nil]] 
  [[!6220!6220(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] 
  [[isList(_x0)]] = 1 + 2x0 > 2x0 = [[n!6220!6220isList(_x0)]] 
  [[isNeList(_x0)]] = x0 >= x0 = [[n!6220!6220isNeList(_x0)]] 
  [[isPal(_x0)]] = 2 + x0 > 1 + x0 = [[n!6220!6220isPal(_x0)]] 
  [[a]] = 2 > 1 = [[n!6220!6220a]] 
  [[e]] = 0 >= 0 = [[n!6220!6220e]] 
  [[i]] = 0 >= 0 = [[n!6220!6220i]] 
  [[o]] = 2 > 1 = [[n!6220!6220o]] 
  [[u]] = 2 > 0 = [[n!6220!6220u]] 
  [[activate(n!6220!6220nil)]] = 3 > 1 = [[nil]] 
  [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = 3 + 3x0 + 3x1 > x0 + x1 = [[!6220!6220(_x0, _x1)]] 
  [[activate(n!6220!6220isList(_x0))]] = 3 + 6x0 > 1 + 2x0 = [[isList(_x0)]] 
  [[activate(n!6220!6220isNeList(_x0))]] = 3 + 3x0 > x0 = [[isNeList(_x0)]] 
  [[activate(n!6220!6220isPal(_x0))]] = 6 + 3x0 > 2 + x0 = [[isPal(_x0)]] 
  [[activate(n!6220!6220a)]] = 6 > 2 = [[a]] 
  [[activate(n!6220!6220e)]] = 3 > 0 = [[e]] 
  [[activate(n!6220!6220i)]] = 3 > 0 = [[i]] 
  [[activate(n!6220!6220o)]] = 6 > 2 = [[o]] 
  [[activate(n!6220!6220u)]] = 3 > 2 = [[u]] 
  [[activate(_x0)]] = 3 + 3x0 > x0 = [[_x0]] 

We can thus remove the following rules:

  nil => n!6220!6220nil 
  isList(X) => n!6220!6220isList(X) 
  isPal(X) => n!6220!6220isPal(X) 
  a => n!6220!6220a 
  o => n!6220!6220o 
  u => n!6220!6220u 
  activate(n!6220!6220nil) => nil 
  activate(n!6220!6220!6220!6220(X, Y)) => !6220!6220(X, Y) 
  activate(n!6220!6220isList(X)) => isList(X) 
  activate(n!6220!6220isNeList(X)) => isNeList(X) 
  activate(n!6220!6220isPal(X)) => isPal(X) 
  activate(n!6220!6220a) => a 
  activate(n!6220!6220e) => e 
  activate(n!6220!6220i) => i 
  activate(n!6220!6220o) => o 
  activate(n!6220!6220u) => u 
  activate(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]):

  !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) 
  isNeList(X) >? n!6220!6220isNeList(X) 
  e >? n!6220!6220e 
  i >? n!6220!6220i 

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

The following interpretation satisfies the requirements:

  !6220!6220 = \y0y1.3 + y0 + y1 
  e = 3 
  i = 3 
  isNeList = \y0.3 + y0 
  n!6220!6220!6220!6220 = \y0y1.y0 + y1 
  n!6220!6220e = 0 
  n!6220!6220i = 0 
  n!6220!6220isNeList = \y0.y0 

Using this interpretation, the requirements translate to:

  [[!6220!6220(_x0, _x1)]] = 3 + x0 + x1 > x0 + x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] 
  [[isNeList(_x0)]] = 3 + x0 > x0 = [[n!6220!6220isNeList(_x0)]] 
  [[e]] = 3 > 0 = [[n!6220!6220e]] 
  [[i]] = 3 > 0 = [[n!6220!6220i]] 

We can thus remove the following rules:

  !6220!6220(X, Y) => n!6220!6220!6220!6220(X, Y) 
  isNeList(X) => n!6220!6220isNeList(X) 
  e => n!6220!6220e 
  i => n!6220!6220i 

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.