On the reduction of computational complexity of cellular automata

MaRDI QIDQ2979827zbMATH OpenFDO

Authors M. Abramskiĭ

Publication date 26 April 2017

Full work available at URL http://bulletin.iis.nsk.su/files/article/abramskiy.pdf

zbMATH Keywords

cellular automata modelcomputational complexityWolfram behavior

Mathematics Subject Classification ID

Dynamical aspects of cellular automata (37B15) Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80)

Recommendations

• Computational complexity of finite asynchronous cellular automata
• Complexity of sequential realization of cellular automata maps
• scientific article; zbMATH DE number 17562
• On the computational complexity of finite cellular automata
• Computation theoretic aspects of cellular automata

Cited in

(9)

• Complexity of sequential realization of cellular automata maps
• Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
• Causal nets for geometrical Gandy-Păun-Rozenberg machines
• A Padding Technique on Cellular Automata to Transfer Inclusions of Complexity Classes
• On the computational power of totalistic cellular automata
• scientific article; zbMATH DE number 17562 (Why is no real title available?)
• On time reduction and simulation in cellular spaces
• Computational complexity of finite asynchronous cellular automata
• System Reduction: An Approach Based on Probabilistic Cellular Automata

This page was built for publication: On the reduction of computational complexity of cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2979827)