A Linear Acceleration Theorem for 2D Cellular Automata on all Complete Neighborhoods
classification
💻 cs.FL
nlin.CG
keywords
accelerationautomatacellularlinearneighborhoodscompleteknowntwo-dimensional
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.