On One-way One-bit O (One)-message Cellular Automata

DOI10.1016/j.entcs.2009.09.015zbMath1338.68184OpenAlexW2085896607MaRDI QIDQ2811951

Martin Kutrib, Andreas Malcher

Publication date: 9 June 2016

Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.entcs.2009.09.015

zbMATH Keywords

cellular automatadecidabilityformal languageslimited communication

Mathematics Subject Classification ID

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

Related Items

IN MEMORIAM CHANDRA KINTALA ⋮ Hierarchies and undecidability results for iterative arrays with sparse communication ⋮ A computation model with automatic functions and relations as primitive operations ⋮ Hierarchies and undecidability results for iterative arrays with sparse communication ⋮ Iterative arrays with finite inter-cell communication ⋮ Iterative arrays with finite inter-cell communication ⋮ A new class of the smallest FSSP partial solutions for 1D rings of length \(n=2^k-1\)

Cites Work

• Some remarks about the efficiency of polyautomata
• Cellular Automata with Sparse Communication
• Fast Iterative Arrays with Restricted Inter-cell Communication: Constructions and Decidability
• Linear-time recognition of connectivity of binary images on 1-bit inter-cell communication cellular automaton
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item