YES(?,O(n^1))

Problem:
 i(0()) -> 0()
 +(0(),y) -> y
 +(x,0()) -> x
 i(i(x)) -> x
 +(i(x),x) -> 0()
 +(x,i(x)) -> 0()
 i(+(x,y)) -> +(i(x),i(y))
 +(x,+(y,z)) -> +(+(x,y),z)
 +(+(x,i(y)),y) -> x
 +(+(x,y),i(y)) -> x

Proof:
 Bounds Processor:
  bound: 1
  enrichment: match
  automaton:
   final states: {4,3,2}
   transitions:
    01() -> 4*,3,1,2
    i0(4) -> 2*
    i0(1) -> 2*
    +0(4,4) -> 3*
    +0(1,4) -> 3*
    +0(4,1) -> 3*
    +0(1,1) -> 3*
    1 -> 3*
    4 -> 3*
  problem:
   
  Qed