A Linear Acceleration Theorem for 2D Cellular Automata on all Complete Neighborhoods

Anaël Grandjean, Victor Poupet

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.

Knowledge Graph



Sign up or login to leave a comment