Cellular automata with sparse communication
From MaRDI portal
Publication:1959660
DOI10.1016/j.tcs.2010.05.024zbMath1207.68214MaRDI 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/
cellular automata; parallel computing; formal languages; computational capacity; restricted communication; decidability questions
68Q80: Cellular automata (computational aspects)
Related Items
Freezing, Bounded-Change and Convergent Cellular Automata, Cold dynamics in cellular automata: a tutorial, Counter machines and distributed automata -- a story about exchanging space and time, Hierarchies and undecidability results for iterative arrays with sparse 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, On the impact of treewidth in the computational complexity of freezing dynamics, Emptiness problems for distributed automata, Iterative arrays with finite inter-cell communication, IN MEMORIAM CHANDRA KINTALA
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item