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

DOI10.1007/978-3-540-74510-5_34MaRDI QIDQ3499783zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

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)