A Padding Technique on Cellular Automata to Transfer Inclusions of Complexity Classes

DOI10.1007/978-3-540-74510-5_34zbMATH Open1188.68201OpenAlexW1492014486MaRDI QIDQ3499783FDOQ3499783

Authors: Victor Poupet 

Publication date: 3 June 2008

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74510-5_34

Recommendations

• scientific article; zbMATH DE number 1738667
• Complexity classes on spatially periodic cellular automata
• Complexity-theoretic aspects of expanding cellular automata
• scientific article; zbMATH DE number 6149843
• On the computational complexity of finite cellular automata
• On the classifiability of cellular automata
• Kolmogorov complexity and cellular automata classification
• On the reduction of computational complexity of cellular automata
• The complexity of permutive cellular automata
• On expansivity and pseudo-orbit tracing property for cellular automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Cellular automata (computational aspects) (68Q80)

Cited In (1)

• Lower bounds and hardness magnification for sublinear-time shrinking cellular automata

This page was built for publication: A Padding Technique on Cellular Automata to Transfer Inclusions of Complexity Classes

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