YES(?,O(n^1))
TRS:
 {
  a(f(), a(g(), a(f(), x))) -> a(f(), a(g(), a(g(), a(f(), x)))),
  a(g(), a(f(), a(g(), x))) -> a(g(), a(f(), a(f(), a(g(), x))))
 }
 DUP: We consider a non-duplicating system.
  Trs:
   {
    a(f(), a(g(), a(f(), x))) -> a(f(), a(g(), a(g(), a(f(), x)))),
    a(g(), a(f(), a(g(), x))) -> a(g(), a(f(), a(f(), a(g(), x))))
   }
  BOUND:
   Bound: match(-raise)-bounded by 4
   Automaton:
    {
     a_4(42, 44) -> 45*
     a_4(42, 43) -> 44*
     a_4(41, 45) -> 33*
     a_4(41, 36) -> 43*
     a_3(31, 40) -> 27 | 25
     a_3(31, 36) -> 37*
     a_3(31, 35) -> 36 | 33 | 25
     a_3(31, 33) -> 34*
     a_3(31, 32) -> 33*
     a_3(31, 29) -> 38*
     a_3(31, 25) -> 38*
     a_3(31, 23) -> 38*
     a_3(31, 20) -> 38*
     a_3(31, 16) -> 38*
     a_3(31, 15) -> 38*
     a_3(31, 13) -> 38*
      a_3(31, 7) -> 38*
      a_3(31, 5) -> 38*
     a_3(30, 39) -> 40*
     a_3(30, 38) -> 39 | 28 | 19
     a_3(30, 37) -> 39 | 32 | 28 | 24 | 22 | 19
     a_3(30, 34) -> 28 | 19
     a_3(30, 28) -> 35*
     a_3(30, 26) -> 32*
     a_3(30, 24) -> 35*
     a_3(30, 22) -> 35*
     a_3(30, 19) -> 35*
     a_3(30, 17) -> 32*
     a_3(30, 14) -> 32*
      a_3(30, 8) -> 35*
      a_3(30, 7) -> 32*
      a_3(30, 4) -> 32*
      a_3(30, 1) -> 32*
     a_2(11, 29) -> 33 | 27 | 25 | 7 | 5 | 1
     a_2(11, 25) -> 26*
     a_2(11, 24) -> 25*
     a_2(11, 23) -> 33 | 27 | 25 | 7 | 5 | 1
     a_2(11, 20) -> 33 | 27 | 25 | 13 | 7 | 5 | 1
     a_2(11, 16) -> 17*
     a_2(11, 15) -> 38 | 33 | 27 | 21 | 16 | 7 | 5 | 1
     a_2(11, 13) -> 14*
     a_2(11, 12) -> 13*
      a_2(11, 9) -> 21*
      a_2(11, 7) -> 26*
      a_2(11, 5) -> 18*
      a_2(11, 4) -> 27*
      a_2(11, 1) -> 25*
     a_2(10, 28) -> 29*
     a_2(10, 27) -> 28*
     a_2(10, 26) -> 39 | 32 | 28 | 24 | 22 | 19 | 8 | 4 | 1
     a_2(10, 25) -> 19*
     a_2(10, 24) -> 29*
     a_2(10, 22) -> 23*
     a_2(10, 21) -> 22*
     a_2(10, 19) -> 20*
     a_2(10, 18) -> 39 | 32 | 19
     a_2(10, 17) -> 32 | 24 | 22 | 8 | 4 | 1
     a_2(10, 14) -> 39 | 32 | 28 | 24 | 19 | 8 | 4 | 1
      a_2(10, 8) -> 15*
      a_2(10, 7) -> 24*
      a_2(10, 6) -> 12*
      a_2(10, 4) -> 24*
      a_2(10, 1) -> 24*
      a_1(3, 29) -> 7*
      a_1(3, 25) -> 7*
      a_1(3, 23) -> 7*
      a_1(3, 20) -> 7*
      a_1(3, 16) -> 7*
      a_1(3, 15) -> 7*
      a_1(3, 13) -> 7*
       a_1(3, 9) -> 7 | 1
       a_1(3, 7) -> 7*
       a_1(3, 5) -> 6*
       a_1(3, 4) -> 33 | 27 | 25 | 7 | 5 | 1
       a_1(3, 1) -> 7*
      a_1(2, 28) -> 20*
      a_1(2, 26) -> 20*
      a_1(2, 24) -> 20*
      a_1(2, 22) -> 20*
      a_1(2, 19) -> 20*
      a_1(2, 17) -> 9*
      a_1(2, 14) -> 20*
       a_1(2, 8) -> 9*
       a_1(2, 7) -> 32 | 24 | 8 | 4 | 1
       a_1(2, 6) -> 32 | 24 | 19 | 8 | 4 | 1
       a_1(2, 4) -> 9*
       a_1(2, 1) -> 4*
       a_0(1, 1) -> 1*
           g_4() -> 41*
           g_3() -> 31*
           g_2() -> 11*
           g_1() -> 3*
           g_0() -> 1*
           f_4() -> 42*
           f_3() -> 30*
           f_2() -> 10*
           f_1() -> 2*
           f_0() -> 1*
    }
   Strict:
    {}
   Qed