Cellular automata with sparse communication

DOI10.1016/j.tcs.2010.05.024zbMath1207.68214OpenAlexW2129693101MaRDI QIDQ1959660

Andreas Malcher, Martin Kutrib

Publication date: 7 October 2010

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

Full work available at URL: http://geb.uni-giessen.de/geb/volltexte/2012/9081/

zbMATH Keywords

cellular automataparallel computingformal languagescomputational capacityrestricted communicationdecidability questions

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Related Items (12)

IN MEMORIAM CHANDRA KINTALA ⋮ Counter machines and distributed automata -- a story about exchanging space and time ⋮ Hierarchies and undecidability results for iterative arrays with sparse communication ⋮ Emptiness problems for distributed automata ⋮ Cold dynamics in cellular automata: a tutorial ⋮ 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\) ⋮ The mirage of universality in cellular automata ⋮ Freezing, Bounded-Change and Convergent Cellular Automata ⋮ On the impact of treewidth in the computational complexity of freezing dynamics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some remarks about the efficiency of polyautomata
• On real-time cellular automata and trellis automata
• Iterative tree automata
• Fast reversible language recognition using cellular automata
• On time computability of functions in one-way cellular automata
• Signals in one-dimensional cellular automata
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• 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

This page was built for publication: Cellular automata with sparse communication