YES(?,O(n^1))

Problem:
 a12(a12(a12(a12(x1)))) -> x1
 a13(a13(a13(a13(x1)))) -> x1
 a14(a14(a14(a14(x1)))) -> x1
 a15(a15(a15(a15(x1)))) -> x1
 a16(a16(a16(a16(x1)))) -> x1
 a23(a23(a23(a23(x1)))) -> x1
 a24(a24(a24(a24(x1)))) -> x1
 a25(a25(a25(a25(x1)))) -> x1
 a26(a26(a26(a26(x1)))) -> x1
 a34(a34(a34(a34(x1)))) -> x1
 a35(a35(a35(a35(x1)))) -> x1
 a36(a36(a36(a36(x1)))) -> x1
 a45(a45(a45(a45(x1)))) -> x1
 a46(a46(a46(a46(x1)))) -> x1
 a56(a56(a56(a56(x1)))) -> x1
 a13(a13(x1)) -> a12(a12(a23(a23(a12(a12(x1))))))
 a14(a14(x1)) -> a12(a12(a23(a23(a34(a34(a23(a23(a12(a12(x1))))))))))
 a15(a15(x1)) -> a12(a12(a23(a23(a34(a34(a45(a45(a34(a34(a23(a23(a12(a12(x1))))))))))))))
 a16(a16(x1)) ->
 a12(a12(a23(a23(a34(a34(a45(a45(a56(a56(a45(a45(a34(a34(a23(a23(a12(a12(x1))))))))))))))))))
 a24(a24(x1)) -> a23(a23(a34(a34(a23(a23(x1))))))
 a25(a25(x1)) -> a23(a23(a34(a34(a45(a45(a34(a34(a23(a23(x1))))))))))
 a26(a26(x1)) -> a23(a23(a34(a34(a45(a45(a56(a56(a45(a45(a34(a34(a23(a23(x1))))))))))))))
 a35(a35(x1)) -> a34(a34(a45(a45(a34(a34(x1))))))
 a36(a36(x1)) -> a34(a34(a45(a45(a56(a56(a45(a45(a34(a34(x1))))))))))
 a46(a46(x1)) -> a45(a45(a56(a56(a45(a45(x1))))))
 a12(a12(a23(a23(a12(a12(a23(a23(a12(a12(a23(a23(x1)))))))))))) -> x1
 a23(a23(a34(a34(a23(a23(a34(a34(a23(a23(a34(a34(x1)))))))))))) -> x1
 a34(a34(a45(a45(a34(a34(a45(a45(a34(a34(a45(a45(x1)))))))))))) -> x1
 a45(a45(a56(a56(a45(a45(a56(a56(a45(a45(a56(a56(x1)))))))))))) -> x1
 a12(a12(a34(a34(x1)))) -> a34(a34(a12(a12(x1))))
 a12(a12(a45(a45(x1)))) -> a45(a45(a12(a12(x1))))
 a12(a12(a56(a56(x1)))) -> a56(a56(a12(a12(x1))))
 a23(a23(a45(a45(x1)))) -> a45(a45(a23(a23(x1))))
 a23(a23(a56(a56(x1)))) -> a56(a56(a23(a23(x1))))
 a34(a34(a56(a56(x1)))) -> a56(a56(a34(a34(x1))))

Proof:
 Bounds Processor:
  bound: 0
  enrichment: match
  automaton:
   final states: {16,15,14,13,12,11,10,9,8,7,6,5,4,3,2}
   transitions:
    a120(1) -> 2*
    a130(1) -> 3*
    a140(1) -> 4*
    a150(1) -> 5*
    a160(1) -> 6*
    a230(1) -> 7*
    a240(1) -> 8*
    a250(1) -> 9*
    a260(1) -> 10*
    a340(1) -> 11*
    a350(1) -> 12*
    a360(1) -> 13*
    a450(1) -> 14*
    a460(1) -> 15*
    a560(1) -> 16*
    f300() -> 1*
  problem:
   
  Qed