YES
O(n)
TRS:
 {g(a(), x) -> f(b(), x),
  f(a(), x) -> g(a(), x),
  f(a(), x) -> f(b(), x)}
 DUP: We consider a non-duplicating system.
  Trs:
   {g(a(), x) -> f(b(), x),
    f(a(), x) -> g(a(), x),
    f(a(), x) -> f(b(), x)}
  BOUND:
   Automaton:
    {
         b_2() -> 8,
         b_1() -> 7,
         b_0() -> 4,
     f_2(8, 4) -> 4,
     f_1(7, 4) -> 4,
     f_0(4, 4) -> 4,
         a_1() -> 5,
         a_0() -> 4,
     g_1(5, 4) -> 4,
     g_0(4, 4) -> 4
    }
   Strict:
    {}
   Qed