/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 
  U11 : [o] --> o 
  U21 : [o * o] --> o 
  U22 : [o] --> o 
  U31 : [o] --> o 
  U41 : [o * o] --> o 
  U42 : [o] --> o 
  U51 : [o * o] --> o 
  U52 : [o] --> o 
  U61 : [o] --> o 
  U71 : [o * o] --> o 
  U72 : [o] --> o 
  U81 : [o] --> o 
  a : [] --> o 
  activate : [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!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 
  U11(tt) => tt 
  U21(tt, X) => U22(isList(activate(X))) 
  U22(tt) => tt 
  U31(tt) => tt 
  U41(tt, X) => U42(isNeList(activate(X))) 
  U42(tt) => tt 
  U51(tt, X) => U52(isList(activate(X))) 
  U52(tt) => tt 
  U61(tt) => tt 
  U71(tt, X) => U72(isPal(activate(X))) 
  U72(tt) => tt 
  U81(tt) => tt 
  isList(X) => U11(isNeList(activate(X))) 
  isList(n!6220!6220nil) => tt 
  isList(n!6220!6220!6220!6220(X, Y)) => U21(isList(activate(X)), activate(Y)) 
  isNeList(X) => U31(isQid(activate(X))) 
  isNeList(n!6220!6220!6220!6220(X, Y)) => U41(isList(activate(X)), activate(Y)) 
  isNeList(n!6220!6220!6220!6220(X, Y)) => U51(isNeList(activate(X)), activate(Y)) 
  isNePal(X) => U61(isQid(activate(X))) 
  isNePal(n!6220!6220!6220!6220(X, !6220!6220(Y, X))) => U71(isQid(activate(X)), activate(Y)) 
  isPal(X) => U81(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) 
  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!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 
  U11(tt) >? tt 
  U21(tt, X) >? U22(isList(activate(X))) 
  U22(tt) >? tt 
  U31(tt) >? tt 
  U41(tt, X) >? U42(isNeList(activate(X))) 
  U42(tt) >? tt 
  U51(tt, X) >? U52(isList(activate(X))) 
  U52(tt) >? tt 
  U61(tt) >? tt 
  U71(tt, X) >? U72(isPal(activate(X))) 
  U72(tt) >? tt 
  U81(tt) >? tt 
  isList(X) >? U11(isNeList(activate(X))) 
  isList(n!6220!6220nil) >? tt 
  isList(n!6220!6220!6220!6220(X, Y)) >? U21(isList(activate(X)), activate(Y)) 
  isNeList(X) >? U31(isQid(activate(X))) 
  isNeList(n!6220!6220!6220!6220(X, Y)) >? U41(isList(activate(X)), activate(Y)) 
  isNeList(n!6220!6220!6220!6220(X, Y)) >? U51(isNeList(activate(X)), activate(Y)) 
  isNePal(X) >? U61(isQid(activate(X))) 
  isNePal(n!6220!6220!6220!6220(X, !6220!6220(Y, X))) >? U71(isQid(activate(X)), activate(Y)) 
  isPal(X) >? U81(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) 
  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!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 
  U11 = \y0.y0 
  U21 = \y0y1.y0 + 2y1 
  U22 = \y0.y0 
  U31 = \y0.2y0 
  U41 = \y0y1.y0 + 2y1 
  U42 = \y0.y0 
  U51 = \y0y1.2y0 + 2y1 
  U52 = \y0.y0 
  U61 = \y0.y0 
  U71 = \y0y1.y0 + y1 
  U72 = \y0.y0 
  U81 = \y0.y0 
  a = 2 
  activate = \y0.y0 
  e = 0 
  i = 0 
  isList = \y0.2y0 
  isNeList = \y0.2y0 
  isNePal = \y0.y0 
  isPal = \y0.y0 
  isQid = \y0.y0 
  n!6220!6220!6220!6220 = \y0y1.y1 + 2y0 
  n!6220!6220a = 2 
  n!6220!6220e = 0 
  n!6220!6220i = 0 
  n!6220!6220nil = 1 
  n!6220!6220o = 2 
  n!6220!6220u = 0 
  nil = 1 
  o = 2 
  tt = 0 
  u = 0 

Using this interpretation, the requirements translate to:

  [[!6220!6220(!6220!6220(_x0, _x1), _x2)]] = x2 + 2x1 + 4x0 >= x2 + 2x0 + 2x1 = [[!6220!6220(_x0, !6220!6220(_x1, _x2))]] 
  [[!6220!6220(_x0, nil)]] = 1 + 2x0 > x0 = [[_x0]] 
  [[!6220!6220(nil, _x0)]] = 2 + x0 > x0 = [[_x0]] 
  [[U11(tt)]] = 0 >= 0 = [[tt]] 
  [[U21(tt, _x0)]] = 2x0 >= 2x0 = [[U22(isList(activate(_x0)))]] 
  [[U22(tt)]] = 0 >= 0 = [[tt]] 
  [[U31(tt)]] = 0 >= 0 = [[tt]] 
  [[U41(tt, _x0)]] = 2x0 >= 2x0 = [[U42(isNeList(activate(_x0)))]] 
  [[U42(tt)]] = 0 >= 0 = [[tt]] 
  [[U51(tt, _x0)]] = 2x0 >= 2x0 = [[U52(isList(activate(_x0)))]] 
  [[U52(tt)]] = 0 >= 0 = [[tt]] 
  [[U61(tt)]] = 0 >= 0 = [[tt]] 
  [[U71(tt, _x0)]] = x0 >= x0 = [[U72(isPal(activate(_x0)))]] 
  [[U72(tt)]] = 0 >= 0 = [[tt]] 
  [[U81(tt)]] = 0 >= 0 = [[tt]] 
  [[isList(_x0)]] = 2x0 >= 2x0 = [[U11(isNeList(activate(_x0)))]] 
  [[isList(n!6220!6220nil)]] = 2 > 0 = [[tt]] 
  [[isList(n!6220!6220!6220!6220(_x0, _x1))]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[U21(isList(activate(_x0)), activate(_x1))]] 
  [[isNeList(_x0)]] = 2x0 >= 2x0 = [[U31(isQid(activate(_x0)))]] 
  [[isNeList(n!6220!6220!6220!6220(_x0, _x1))]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[U41(isList(activate(_x0)), activate(_x1))]] 
  [[isNeList(n!6220!6220!6220!6220(_x0, _x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[U51(isNeList(activate(_x0)), activate(_x1))]] 
  [[isNePal(_x0)]] = x0 >= x0 = [[U61(isQid(activate(_x0)))]] 
  [[isNePal(n!6220!6220!6220!6220(_x0, !6220!6220(_x1, _x0)))]] = 2x1 + 3x0 >= x0 + x1 = [[U71(isQid(activate(_x0)), activate(_x1))]] 
  [[isPal(_x0)]] = x0 >= x0 = [[U81(isNePal(activate(_x0)))]] 
  [[isPal(n!6220!6220nil)]] = 1 > 0 = [[tt]] 
  [[isQid(n!6220!6220a)]] = 2 > 0 = [[tt]] 
  [[isQid(n!6220!6220e)]] = 0 >= 0 = [[tt]] 
  [[isQid(n!6220!6220i)]] = 0 >= 0 = [[tt]] 
  [[isQid(n!6220!6220o)]] = 2 > 0 = [[tt]] 
  [[isQid(n!6220!6220u)]] = 0 >= 0 = [[tt]] 
  [[nil]] = 1 >= 1 = [[n!6220!6220nil]] 
  [[!6220!6220(_x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[n!6220!6220!6220!6220(_x0, _x1)]] 
  [[a]] = 2 >= 2 = [[n!6220!6220a]] 
  [[e]] = 0 >= 0 = [[n!6220!6220e]] 
  [[i]] = 0 >= 0 = [[n!6220!6220i]] 
  [[o]] = 2 >= 2 = [[n!6220!6220o]] 
  [[u]] = 0 >= 0 = [[n!6220!6220u]] 
  [[activate(n!6220!6220nil)]] = 1 >= 1 = [[nil]] 
  [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] 
  [[activate(n!6220!6220a)]] = 2 >= 2 = [[a]] 
  [[activate(n!6220!6220e)]] = 0 >= 0 = [[e]] 
  [[activate(n!6220!6220i)]] = 0 >= 0 = [[i]] 
  [[activate(n!6220!6220o)]] = 2 >= 2 = [[o]] 
  [[activate(n!6220!6220u)]] = 0 >= 0 = [[u]] 
  [[activate(_x0)]] = x0 >= x0 = [[_x0]] 

We can thus remove the following rules:

  !6220!6220(X, nil) => X 
  !6220!6220(nil, X) => X 
  isList(n!6220!6220nil) => tt 
  isPal(n!6220!6220nil) => tt 
  isQid(n!6220!6220a) => tt 
  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]):

  !6220!6220(!6220!6220(X, Y), Z) >? !6220!6220(X, !6220!6220(Y, Z)) 
  U11(tt) >? tt 
  U21(tt, X) >? U22(isList(activate(X))) 
  U22(tt) >? tt 
  U31(tt) >? tt 
  U41(tt, X) >? U42(isNeList(activate(X))) 
  U42(tt) >? tt 
  U51(tt, X) >? U52(isList(activate(X))) 
  U52(tt) >? tt 
  U61(tt) >? tt 
  U71(tt, X) >? U72(isPal(activate(X))) 
  U72(tt) >? tt 
  U81(tt) >? tt 
  isList(X) >? U11(isNeList(activate(X))) 
  isList(n!6220!6220!6220!6220(X, Y)) >? U21(isList(activate(X)), activate(Y)) 
  isNeList(X) >? U31(isQid(activate(X))) 
  isNeList(n!6220!6220!6220!6220(X, Y)) >? U41(isList(activate(X)), activate(Y)) 
  isNeList(n!6220!6220!6220!6220(X, Y)) >? U51(isNeList(activate(X)), activate(Y)) 
  isNePal(X) >? U61(isQid(activate(X))) 
  isNePal(n!6220!6220!6220!6220(X, !6220!6220(Y, X))) >? U71(isQid(activate(X)), activate(Y)) 
  isPal(X) >? U81(isNePal(activate(X))) 
  isQid(n!6220!6220e) >? tt 
  isQid(n!6220!6220i) >? tt 
  isQid(n!6220!6220u) >? tt 
  nil >? n!6220!6220nil 
  !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) 
  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!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 
  U11 = \y0.y0 
  U21 = \y0y1.y0 + 2y1 
  U22 = \y0.y0 
  U31 = \y0.2y0 
  U41 = \y0y1.2 + 2y0 + 2y1 
  U42 = \y0.1 + y0 
  U51 = \y0y1.1 + 2y0 + 2y1 
  U52 = \y0.1 + y0 
  U61 = \y0.y0 
  U71 = \y0y1.1 + 2y0 + 2y1 
  U72 = \y0.y0 
  U81 = \y0.y0 
  a = 0 
  activate = \y0.y0 
  e = 0 
  i = 0 
  isList = \y0.2y0 
  isNeList = \y0.2y0 
  isNePal = \y0.y0 
  isPal = \y0.1 + 2y0 
  isQid = \y0.y0 
  n!6220!6220!6220!6220 = \y0y1.2 + y1 + 2y0 
  n!6220!6220a = 0 
  n!6220!6220e = 0 
  n!6220!6220i = 0 
  n!6220!6220nil = 0 
  n!6220!6220o = 0 
  n!6220!6220u = 2 
  nil = 0 
  o = 0 
  tt = 0 
  u = 2 

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))]] 
  [[U11(tt)]] = 0 >= 0 = [[tt]] 
  [[U21(tt, _x0)]] = 2x0 >= 2x0 = [[U22(isList(activate(_x0)))]] 
  [[U22(tt)]] = 0 >= 0 = [[tt]] 
  [[U31(tt)]] = 0 >= 0 = [[tt]] 
  [[U41(tt, _x0)]] = 2 + 2x0 > 1 + 2x0 = [[U42(isNeList(activate(_x0)))]] 
  [[U42(tt)]] = 1 > 0 = [[tt]] 
  [[U51(tt, _x0)]] = 1 + 2x0 >= 1 + 2x0 = [[U52(isList(activate(_x0)))]] 
  [[U52(tt)]] = 1 > 0 = [[tt]] 
  [[U61(tt)]] = 0 >= 0 = [[tt]] 
  [[U71(tt, _x0)]] = 1 + 2x0 >= 1 + 2x0 = [[U72(isPal(activate(_x0)))]] 
  [[U72(tt)]] = 0 >= 0 = [[tt]] 
  [[U81(tt)]] = 0 >= 0 = [[tt]] 
  [[isList(_x0)]] = 2x0 >= 2x0 = [[U11(isNeList(activate(_x0)))]] 
  [[isList(n!6220!6220!6220!6220(_x0, _x1))]] = 4 + 2x1 + 4x0 > 2x0 + 2x1 = [[U21(isList(activate(_x0)), activate(_x1))]] 
  [[isNeList(_x0)]] = 2x0 >= 2x0 = [[U31(isQid(activate(_x0)))]] 
  [[isNeList(n!6220!6220!6220!6220(_x0, _x1))]] = 4 + 2x1 + 4x0 > 2 + 2x1 + 4x0 = [[U41(isList(activate(_x0)), activate(_x1))]] 
  [[isNeList(n!6220!6220!6220!6220(_x0, _x1))]] = 4 + 2x1 + 4x0 > 1 + 2x1 + 4x0 = [[U51(isNeList(activate(_x0)), activate(_x1))]] 
  [[isNePal(_x0)]] = x0 >= x0 = [[U61(isQid(activate(_x0)))]] 
  [[isNePal(n!6220!6220!6220!6220(_x0, !6220!6220(_x1, _x0)))]] = 4 + 2x1 + 3x0 > 1 + 2x0 + 2x1 = [[U71(isQid(activate(_x0)), activate(_x1))]] 
  [[isPal(_x0)]] = 1 + 2x0 > x0 = [[U81(isNePal(activate(_x0)))]] 
  [[isQid(n!6220!6220e)]] = 0 >= 0 = [[tt]] 
  [[isQid(n!6220!6220i)]] = 0 >= 0 = [[tt]] 
  [[isQid(n!6220!6220u)]] = 2 > 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)]] 
  [[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]] = 2 >= 2 = [[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!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)]] = 2 >= 2 = [[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)) 
  U41(tt, X) => U42(isNeList(activate(X))) 
  U42(tt) => tt 
  U52(tt) => tt 
  isList(n!6220!6220!6220!6220(X, Y)) => U21(isList(activate(X)), activate(Y)) 
  isNeList(n!6220!6220!6220!6220(X, Y)) => U41(isList(activate(X)), activate(Y)) 
  isNeList(n!6220!6220!6220!6220(X, Y)) => U51(isNeList(activate(X)), activate(Y)) 
  isNePal(n!6220!6220!6220!6220(X, !6220!6220(Y, X))) => U71(isQid(activate(X)), activate(Y)) 
  isPal(X) => U81(isNePal(activate(X))) 
  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]):

  U11(tt) >? tt 
  U21(tt, X) >? U22(isList(activate(X))) 
  U22(tt) >? tt 
  U31(tt) >? tt 
  U51(tt, X) >? U52(isList(activate(X))) 
  U61(tt) >? tt 
  U71(tt, X) >? U72(isPal(activate(X))) 
  U72(tt) >? tt 
  U81(tt) >? tt 
  isList(X) >? U11(isNeList(activate(X))) 
  isNeList(X) >? U31(isQid(activate(X))) 
  isNePal(X) >? U61(isQid(activate(X))) 
  isQid(n!6220!6220e) >? tt 
  isQid(n!6220!6220i) >? tt 
  nil >? n!6220!6220nil 
  !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) 
  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!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 
  U11 = \y0.y0 
  U21 = \y0y1.3 + 3y0 + 3y1 
  U22 = \y0.y0 
  U31 = \y0.y0 
  U51 = \y0y1.3 + 3y0 + 3y1 
  U52 = \y0.y0 
  U61 = \y0.y0 
  U71 = \y0y1.3 + 3y0 + 3y1 
  U72 = \y0.2 + y0 
  U81 = \y0.3 + 3y0 
  a = 0 
  activate = \y0.y0 
  e = 0 
  i = 0 
  isList = \y0.y0 
  isNeList = \y0.y0 
  isNePal = \y0.3 + 3y0 
  isPal = \y0.y0 
  isQid = \y0.y0 
  n!6220!6220!6220!6220 = \y0y1.y0 + y1 
  n!6220!6220a = 0 
  n!6220!6220e = 0 
  n!6220!6220i = 0 
  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:

  [[U11(tt)]] = 0 >= 0 = [[tt]] 
  [[U21(tt, _x0)]] = 3 + 3x0 > x0 = [[U22(isList(activate(_x0)))]] 
  [[U22(tt)]] = 0 >= 0 = [[tt]] 
  [[U31(tt)]] = 0 >= 0 = [[tt]] 
  [[U51(tt, _x0)]] = 3 + 3x0 > x0 = [[U52(isList(activate(_x0)))]] 
  [[U61(tt)]] = 0 >= 0 = [[tt]] 
  [[U71(tt, _x0)]] = 3 + 3x0 > 2 + x0 = [[U72(isPal(activate(_x0)))]] 
  [[U72(tt)]] = 2 > 0 = [[tt]] 
  [[U81(tt)]] = 3 > 0 = [[tt]] 
  [[isList(_x0)]] = x0 >= x0 = [[U11(isNeList(activate(_x0)))]] 
  [[isNeList(_x0)]] = x0 >= x0 = [[U31(isQid(activate(_x0)))]] 
  [[isNePal(_x0)]] = 3 + 3x0 > x0 = [[U61(isQid(activate(_x0)))]] 
  [[isQid(n!6220!6220e)]] = 0 >= 0 = [[tt]] 
  [[isQid(n!6220!6220i)]] = 0 >= 0 = [[tt]] 
  [[nil]] = 0 >= 0 = [[n!6220!6220nil]] 
  [[!6220!6220(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] 
  [[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))]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] 
  [[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:

  U21(tt, X) => U22(isList(activate(X))) 
  U51(tt, X) => U52(isList(activate(X))) 
  U71(tt, X) => U72(isPal(activate(X))) 
  U72(tt) => tt 
  U81(tt) => tt 
  isNePal(X) => U61(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]):

  U11(tt) >? tt 
  U22(tt) >? tt 
  U31(tt) >? tt 
  U61(tt) >? tt 
  isList(X) >? U11(isNeList(activate(X))) 
  isNeList(X) >? U31(isQid(activate(X))) 
  isQid(n!6220!6220e) >? tt 
  isQid(n!6220!6220i) >? tt 
  nil >? n!6220!6220nil 
  !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) 
  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!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 
  U11 = \y0.y0 
  U22 = \y0.3 + 3y0 
  U31 = \y0.y0 
  U61 = \y0.3 + 3y0 
  a = 0 
  activate = \y0.y0 
  e = 0 
  i = 0 
  isList = \y0.3 + 3y0 
  isNeList = \y0.2y0 
  isQid = \y0.2y0 
  n!6220!6220!6220!6220 = \y0y1.y0 + y1 
  n!6220!6220a = 0 
  n!6220!6220e = 0 
  n!6220!6220i = 0 
  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:

  [[U11(tt)]] = 0 >= 0 = [[tt]] 
  [[U22(tt)]] = 3 > 0 = [[tt]] 
  [[U31(tt)]] = 0 >= 0 = [[tt]] 
  [[U61(tt)]] = 3 > 0 = [[tt]] 
  [[isList(_x0)]] = 3 + 3x0 > 2x0 = [[U11(isNeList(activate(_x0)))]] 
  [[isNeList(_x0)]] = 2x0 >= 2x0 = [[U31(isQid(activate(_x0)))]] 
  [[isQid(n!6220!6220e)]] = 0 >= 0 = [[tt]] 
  [[isQid(n!6220!6220i)]] = 0 >= 0 = [[tt]] 
  [[nil]] = 0 >= 0 = [[n!6220!6220nil]] 
  [[!6220!6220(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] 
  [[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!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:

  U22(tt) => tt 
  U61(tt) => tt 
  isList(X) => U11(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]):

  U11(tt) >? tt 
  U31(tt) >? tt 
  isNeList(X) >? U31(isQid(activate(X))) 
  isQid(n!6220!6220e) >? tt 
  isQid(n!6220!6220i) >? tt 
  nil >? n!6220!6220nil 
  !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) 
  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!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.3 + y0 + 2y1 
  U11 = \y0.3 + 3y0 
  U31 = \y0.y0 
  a = 3 
  activate = \y0.1 + 3y0 
  e = 2 
  i = 2 
  isNeList = \y0.3 + 3y0 
  isQid = \y0.y0 
  n!6220!6220!6220!6220 = \y0y1.2 + y0 + 2y1 
  n!6220!6220a = 3 
  n!6220!6220e = 1 
  n!6220!6220i = 1 
  n!6220!6220nil = 2 
  n!6220!6220o = 1 
  n!6220!6220u = 1 
  nil = 2 
  o = 2 
  tt = 0 
  u = 2 

Using this interpretation, the requirements translate to:

  [[U11(tt)]] = 3 > 0 = [[tt]] 
  [[U31(tt)]] = 0 >= 0 = [[tt]] 
  [[isNeList(_x0)]] = 3 + 3x0 > 1 + 3x0 = [[U31(isQid(activate(_x0)))]] 
  [[isQid(n!6220!6220e)]] = 1 > 0 = [[tt]] 
  [[isQid(n!6220!6220i)]] = 1 > 0 = [[tt]] 
  [[nil]] = 2 >= 2 = [[n!6220!6220nil]] 
  [[!6220!6220(_x0, _x1)]] = 3 + x0 + 2x1 > 2 + x0 + 2x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] 
  [[a]] = 3 >= 3 = [[n!6220!6220a]] 
  [[e]] = 2 > 1 = [[n!6220!6220e]] 
  [[i]] = 2 > 1 = [[n!6220!6220i]] 
  [[o]] = 2 > 1 = [[n!6220!6220o]] 
  [[u]] = 2 > 1 = [[n!6220!6220u]] 
  [[activate(n!6220!6220nil)]] = 7 > 2 = [[nil]] 
  [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = 7 + 3x0 + 6x1 > 3 + x0 + 2x1 = [[!6220!6220(_x0, _x1)]] 
  [[activate(n!6220!6220a)]] = 10 > 3 = [[a]] 
  [[activate(n!6220!6220e)]] = 4 > 2 = [[e]] 
  [[activate(n!6220!6220i)]] = 4 > 2 = [[i]] 
  [[activate(n!6220!6220o)]] = 4 > 2 = [[o]] 
  [[activate(n!6220!6220u)]] = 4 > 2 = [[u]] 
  [[activate(_x0)]] = 1 + 3x0 > x0 = [[_x0]] 

We can thus remove the following rules:

  U11(tt) => tt 
  isNeList(X) => U31(isQid(activate(X))) 
  isQid(n!6220!6220e) => tt 
  isQid(n!6220!6220i) => tt 
  !6220!6220(X, Y) => n!6220!6220!6220!6220(X, Y) 
  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!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]):

  U31(tt) >? tt 
  nil >? n!6220!6220nil 
  a >? n!6220!6220a 

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

The following interpretation satisfies the requirements:

  U31 = \y0.3 + 3y0 
  a = 3 
  n!6220!6220a = 0 
  n!6220!6220nil = 0 
  nil = 3 
  tt = 0 

Using this interpretation, the requirements translate to:

  [[U31(tt)]] = 3 > 0 = [[tt]] 
  [[nil]] = 3 > 0 = [[n!6220!6220nil]] 
  [[a]] = 3 > 0 = [[n!6220!6220a]] 

We can thus remove the following rules:

  U31(tt) => tt 
  nil => n!6220!6220nil 
  a => n!6220!6220a 

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.