YES(?,O(n^1))

Problem:
 b(c(a(x1))) -> a(b(a(b(c(x1)))))
 b(x1) -> c(c(x1))
 c(d(x1)) -> a(b(c(a(x1))))
 a(a(x1)) -> a(c(b(a(x1))))

Proof:
 Bounds Processor:
  bound: 3
  enrichment: match
  automaton:
   final states: {4,3,2}
   transitions:
    a1(14) -> 15*
    a1(11) -> 12*
    b1(13) -> 14*
    c1(12) -> 13*
    c1(9) -> 10*
    c1(8) -> 9*
    c2(27) -> 28*
    c2(34) -> 35*
    c2(56) -> 57*
    c2(33) -> 34*
    a2(57) -> 58*
    a2(29) -> 30*
    a2(31) -> 32*
    b0(1) -> 2*
    b2(55) -> 56*
    b2(30) -> 31*
    b2(28) -> 29*
    c0(1) -> 3*
    c3(60) -> 61*
    c3(40) -> 41*
    c3(59) -> 60*
    c3(49) -> 50*
    c3(39) -> 40*
    c3(48) -> 49*
    a0(1) -> 4*
    d0(1) -> 1*
    1 -> 11,8
    10 -> 2*
    11 -> 27*
    13 -> 33*
    15 -> 28,9,3
    28 -> 39*
    30 -> 48*
    32 -> 55,14
    35 -> 14*
    41 -> 29*
    50 -> 31*
    55 -> 59*
    58 -> 15,3,9
    61 -> 56*
  problem:
   
  Qed