A characterization of constant-time cellular automata computation

DOI10.1016/0167-2789(90)90198-XzbMath0719.68047OpenAlexW2075080321MaRDI QIDQ2640353

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 automatafinite state machinesconstant-time cellular automata languages

Mathematics Subject Classification ID

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

Related Items (5)

Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata ⋮ On time reduction and simulation in cellular spaces ⋮ Complexity-theoretic aspects of expanding cellular automata ⋮ Complexity-theoretic aspects of expanding cellular automata ⋮ Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata

Cites Work

• Fast parallel language recognition by cellular automata
• Parallel language recognition in constant time by cellular automata
• Characterizations of locally testable events
• Real-time language recognition by one-dimensional cellular automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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