A Linear Acceleration Theorem for 2D Cellular Automata on all Complete   Neighborhoods
  Linear acceleration theorems are known for most computational models. Although such results have been proved for two-dimensional cellular automata working on specific neighborhoods, no general construction was known. We present here a technique of linear acceleration for all two-dimensional languages recognized by cellular automata working on complete neighborhoods. 
Ana\"el Grandjean, Victor Poupet
cs.FL nlin.CG