YES(?,O(n^1))

Problem:
 p(f(f(x))) -> q(f(g(x)))
 p(g(g(x))) -> q(g(f(x)))
 q(f(f(x))) -> p(f(g(x)))
 q(g(g(x))) -> p(g(f(x)))

Proof:
 Bounds Processor:
  bound: 1
  enrichment: match
  automaton:
   final states: {5}
   transitions:
    p1(21) -> 22*
    g1(15) -> 16*
    g1(10) -> 11*
    f1(14) -> 15*
    f1(11) -> 12*
    q1(12) -> 13*
    p0(5) -> 5*
    f0(5) -> 5*
    q0(5) -> 5*
    g0(5) -> 5*
    5 -> 14,10
    12 -> 21*
    13 -> 5*
    16 -> 12*
    22 -> 5*
  problem:
   
  Qed