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: {7,6,3,2}
   transitions:
    i0(7) -> 2*
    i0(6) -> 2*
    i0(1) -> 2*
    00() -> 6*,3,1
    +0(6,6) -> 3*
    +0(1,6) -> 3*
    +0(7,1) -> 3*
    +0(7,7) -> 3*
    +0(6,1) -> 3*
    +0(1,1) -> 3*
    +0(6,7) -> 3*
    +0(1,7) -> 3*
    +0(7,6) -> 3*
    01() -> 6,7*,3,1,2
    1 -> 3*
    6 -> 3*
    7 -> 3*
  problem:
   
  Qed