YES
O(n)
TRS:
 {
  q(f(f(x))) -> p(f(g(x))),
  q(g(g(x))) -> p(g(f(x))),
  p(f(f(x))) -> q(f(g(x))),
  p(g(g(x))) -> q(g(f(x)))
 }
 DUP: We consider a non-duplicating system.
  Trs:
   {
    q(f(f(x))) -> p(f(g(x))),
    q(g(g(x))) -> p(g(f(x))),
    p(f(f(x))) -> q(f(g(x))),
    p(g(g(x))) -> q(g(f(x)))
   }
  BOUND:
   Automaton:
    {
     p_1(18) -> 19,
      p_0(4) -> 4,
     g_1(14) -> 15,
      g_1(5) -> 6,
      g_0(4) -> 4,
     f_1(13) -> 14,
      f_1(6) -> 7,
      f_0(4) -> 4,
      q_1(7) -> 8,
      q_0(4) -> 4,
          19 -> 4,
          15 -> 7,
           8 -> 4,
           7 -> 18,
           4 -> 13 | 5
    }
   Strict:
    {}
   Qed