Efficient 1-Bit-Communication Cellular Algorithms

Hiroshi Umeo (), Koshi Michisaka (), Naoki Kamikawa () and Yuichi Kinugasa
Additional contact information
Hiroshi Umeo: Univ. of Osaka Eletcro-Communication
Koshi Michisaka: Internet Initiative Japan
Naoki Kamikawa: Noristu Koki
Yuichi Kinugasa: Univ. of Osaka Eletcro-Communication

A chapter in Modeling, Simulation and Optimization of Complex Processes, 2005, pp 509-522 from Springer

Abstract: Summary We propose several efficient algorithms for a large scale of cellular automata having 1-bit inter-cell communications (CA1-bit). A 1-bit inter-cell communication model studied in this paper is a new class of cellular automata (CA) whose inter-cell communication is restricted to 1-bit. We call the model 1-bit CA in short. The number of internal states of the 1-bit CA is assumed to be finite in a usual way. The next state of each cell is determined by the present state of itself and two binary 1-bit inputs from its left and right neighbor cells. Thus the 1-bit CA can be thought to be one of the most powerless and simplest models in a variety of CAs. We study a sequence generation problem, a firing squad synchronization problem and an early bird problem, all of which are known as the classical and fundamental problems in cellular automata. First we consider the sequence generation problem. It is shown that there exists a 1-state CA1-bit that can generate in real-time a context-sensitive sequence such that {2n|n = 1, 2, 3, …}. Prime sequence can also be generated in real-time by CA1-bit with 34 states. Secondary, we study the firing squad synchronization problem on two-dimensional CA1-bit. We give a two-dimensional CA1-bit which can synchronize any n × n square and m × n rectangular arrays in 2n − 1 and m + n + max(m, n) steps, respectively. In addition, we propose a generalized synchronization algorithm that operates in linear steps on two-dimensional rectangular arrays with the general located at an arbitrary position of the array. The time complexities for the first two algorithms developed are one to two steps larger than optimum ones proposed for O(1)-bit communication model. In the last, we give a 1-bit implementation for an early bird problem. It is shown that there exists a 12-state CA1-bit that solves the early bird problem in linear time.

Date: 2005
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-27170-3_38

Ordering information: This item can be ordered from
http://www.springer.com/9783540271703

DOI: 10.1007/3-540-27170-8_38

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().