Wyniki wyszukiwania - BazTech

1

How to Synchronize Cellular Automata – Recent Developments –.

Umeo Hiroshi

Fundamenta Informaticae

|

2020

|

Vol. 171, nr 1-4

393--419

EN

The synchronization in cellular automata has been known as the firing squad synchronization problem (FSSP) since its development, in which it was originally proposed by Myhill and reported by Moore in 1964 to synchronize all/some parts of self-reproducing cellular automata. The problem has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms has been proposed not only for one-dimensional (1D) arrays but also for multi-dimensional arrays. In the present paper, we construct a survey on the study of FSSP algorithms, focusing on recent developments.

2

A Small Five-State Non-Optimum-Time Solution to the Firing Squad Synchronization Problem - A Geometrical Approach -

Umeo H., Yanagihara T.

Fundamenta Informaticae

|

2009

|

Vol. 91, nr 1

161-178

EN

An existence or non-existence of five-state firing squad synchronization protocol has been a long-standing, famous open problem for a long time. In this paper, we answer partially to this problem by proposing a small five-state firing squad synchronization algorithm that can synchronize any one-dimensional cellular array of length n = 2^k in 3n - 3 steps for any positive integer k.

3

A New Time-Optimum Synchronization Algorithm for Rectangle Arrays

Umeo H., Uchino H.

Fundamenta Informaticae

|

2008

|

Vol. 87, nr 2

155-164

EN

The firing squad synchronization problem on cellular automata has been studied extensively for more than forty years, and a rich variety of synchronization algorithms have been proposed so far. In the present paper, we propose a new optimum-time algorithm for synchronizing two-dimensional cellular automata. The algorithm can synchronize any two-dimensional rectangle array of size m ×n in optimum m + n + max(m, n)- 3 steps. A partial implementation of the algorithm for small cellular arrays is also given.

4

State-efficient One-bit-communication Solutions for Some Classical Cellular Automata Problems

Umeo H., Michisaka K., Kamikawa N., Kanazawa M.

Fundamenta Informaticae

|

2007

|

Vol. 78, nr 3

449-465

EN

We present several state-efficient implementations on 1-bit inter-cell communication cellular automata for some classical cellular automata problems. The 1-bit inter-cell communication cellular automaton model (CA1-bit) studied in this paper is a subclass of cellular automata (CA) whose inter-cell communication at one step is restricted to 1-bit. We study an early bird problem, a firing squad synchronization problem and an integer sequence generation problem, all of which are known as the classical, fundamental problems in cellular automata. Firstly, it is shown that there exists a 37-state CA1-bit that solves the early bird problem in twice real-time. Then, we give a two-dimensional CA1-bit which can synchronize any n ×n (n ^(3) 2) square and m×n (m, n ^(3) 2) rectangular arrays in 2n - 1 and m+n+max(m, n) steps, respectively. In addition, we propose a generalized linear-time synchronization algorithm that operates in m+n+max(r+s,m+n-r-s+2)+O(1) steps on two-dimensional rectangular arrays of size m ×n with the general located at an arbitrary position (r, s) in the array, where m, n ^(3) 2, 1 ? r ? m and 1 ? s ? n. The time complexities for the first two algorithms developed are one to two steps larger than optimum ones proposed for O(1)-bit conventional communication model. In the last, it is shown that there exists a 1-state CA1-bit that can generate in real-time a context-sensitive integer sequence such that {2n | n = 1, 2, 3, ... }.

5

A State-Efficient Mapping Scheme for Designing Two-Dimensional Firing Squad Synchronization Algorithms

Umeo H., Maeda M., Hisaoka M., Teraoka M.

Fundamenta Informaticae

|

2006

|

Vol. 74, nr 4

603-623

EN

A simple and state-efficient mapping scheme is proposed for embedding any one-dimensional (1-D) firing squad synchronization algorithm onto two-dimensional (2-D) arrays, and some new 2-D synchronization algorithms based on the mapping scheme are presented. The proposed mapping scheme can be readily applied to the design of 2-D synchronization algorithms with fault tolerance, algorithms operating on multi-dimensional cellular arrays, and for the generalized case where the general is located at an arbitrary position on the 2-D array. First a six-state algorithm is developed that can synchronize any m ×n rectangular array in 2(m + n) - 4 steps. Then, a fourteen-state generalized algorithm is also developed that can synchronize any m×n rectangular array with the general at an arbitrary initial position (r, s) in m + n + max(r + s , m + n - r - s+ 2) - 4 steps. The latter algorithm is interesting in that it includes a new optimum-time synchronization algorithm as a special case where the general is located at one corner. We progressively reduce the number of internal states of each cellular automaton on rectangular arrays, achieving six states and fourteen states for a rectangular array in non-optimum and optimum-time complexities, respectively. These are the smallest number of states reported to date for synchronizing rectangular arrays.

6

Firing Squad Synchronization Problem in Number-Conserving Cellular Automata

Imai K., Morita K., Sako K.

Fundamenta Informaticae

|

2002

|

Vol. 52, nr 1-3

133-141

EN

We study the Firing Squad Synchronization Problem (FSSP) on a cellular automaton (CA) having number-conservation property. In a number-conserving CA, all states of cells are represented by (tuples of) non-negative integers and the total number of its configuration is conserved throughout its computing processes. But, if we use a usual framework of CA in which each state of a cell is represented by a single integer, it is not possible to make every cell to be in the same firing state, which should be different from the soldier state, under the usual FSSP condition without violating the number-conservativeness. So, we employ the framework of a partitioned cellular automaton, and define a number-conserving partitioned cellular automaton (NC-PCA). Its cell is divided into three parts, and hence each cell is represented by a triple of non-negative integers. In NC-PCA, only the constraint that the local transition function should satisfy a number-conserving condition is supposed. Thus, it makes relatively easy to construct an NC-PCA. Because each cell can hold three non-negative integers, it is possible to represent different states even if the sum of three numbers are equal. Using this technique, we show that Minsky's 3n time solution can be embedded into an NC-PCA, having an integer at most 9 in each part of a cell.