YES(?,O(n^1))
TRS:
 {
          not false() -> true(),
           not true() -> false(),
      evenodd(x, 0()) -> not evenodd(x, s 0()),
  evenodd(s x, s 0()) -> evenodd(x, 0()),
  evenodd(0(), s 0()) -> false()
 }
 DUP: We consider a non-duplicating system.
  Trs:
   {
            not false() -> true(),
             not true() -> false(),
        evenodd(x, 0()) -> not evenodd(x, s 0()),
    evenodd(s x, s 0()) -> evenodd(x, 0()),
    evenodd(0(), s 0()) -> false()
   }
  BOUND:
   Bound: match(-raise)-bounded by 3
   Automaton:
    {
         0_2() -> 5*
         0_1() -> 2*
         0_0() -> 1*
        s_2(5) -> 6*
        s_1(2) -> 3*
        s_0(1) -> 1*
     evenodd_2(1, 6) -> 7*
     evenodd_1(1, 3) -> 4*
     evenodd_1(1, 2) -> 7 | 4 | 1
     evenodd_0(1, 1) -> 1*
         true_3() -> 7 | 4 | 1
         true_2() -> 7 | 4 | 1
         true_1() -> 1*
         true_0() -> 1*
        not_2(7) -> 7 | 4 | 1
        not_1(4) -> 1*
        not_0(1) -> 1*
         false_3() -> 7 | 4 | 1
         false_2() -> 1*
         false_1() -> 7 | 4 | 1
         false_0() -> 1*
    }
   Strict:
    {}
   Qed