A characterization of constant-time cellular automata computation

DOI10.1016/0167-2789(90)90198-XMaRDI QIDQ2640353zbMATH OpenOpenAlexFDO

Authors Robert McCloskey, Sam M. Kim

Publication date 1990

Published in Physica D (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-2789(90)90198-x

zbMATH Keywords

cellular automataconstant-time cellular automata languagesfinite state machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80)

Recommendations

• A Time Hierarchy Theorem for Nondeterministic Cellular Automata
• scientific article; zbMATH DE number 3872685
• On the computational complexity of finite cellular automata
• On time computability of functions in one-way cellular automata
• Computation theoretic aspects of cellular automata
• scientific article; zbMATH DE number 2113944
• scientific article; zbMATH DE number 1834667
• Universal Construction on Self-Timed Cellular Automata
• Computational complexity of finite asynchronous cellular automata
• scientific article; zbMATH DE number 17562

Cites work

• Characterizations of locally testable events
• Fast parallel language recognition by cellular automata
• scientific article; zbMATH DE number 4215382 (Why is no real title available?)
• scientific article; zbMATH DE number 4064440 (Why is no real title available?)
• scientific article; zbMATH DE number 3738961 (Why is no real title available?)
• scientific article; zbMATH DE number 140486 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Parallel language recognition in constant time by cellular automata
• Real-time language recognition by one-dimensional cellular automata

Cited in

(11)

• Fast language acceptance by shrinking cellular automata
• On time computability of functions in one-way cellular automata
• Complexity-theoretic aspects of expanding cellular automata
• Some results on time-varying and relativised cellular automata^*
• On time reduction and simulation in cellular spaces
• Sublinear-time language recognition and decision by one-dimensional cellular automata
• Definability by Horn formulas and linear time on cellular automata
• Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
• Complexity-theoretic aspects of expanding cellular automata
• Descriptive complexity for minimal time of cellular automata
• Pseudorandom generators for sliding-window algorithms

This page was built for publication: A characterization of constant-time cellular automata computation

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