Wyniki wyszukiwania - BazTech

1

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.

2

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.

3

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, ... }.

4

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.

5

Real-Time Generation of Primes by a 1-Bit-Communication Cellular Automaton

Umeo H., Kamikawa N.

Fundamenta Informaticae

|

2003

|

Vol. 58, nr 3,4

421--435

EN

It is shown that an infinite prime sequence can be generated in real-time by a cellular automaton having 1-bit inter-cell communications (CA1-bit). The algorithm presented is based on the classical sieve of Eratosthenes, and its implementation will be made on а СА1-bitusing 34 internal states and 71 transition rules.

6

A Design of Real-Time Non-Regular Sequence Generation Algorithms and Their Implementations on Cellular Automata with 1-Bit Inter-Cell Communications

Umeo H., Kamikawa N.

Fundamenta Informaticae

|

2002

|

Vol. 52, nr 1-3

255-275

EN

We introduce a special new class of cellular automata(CA) whose inter-cell communication is restricted to 1-bit. Several design examples for 1-bit inter-cell communication cellular algorithms are given. It is shown that infinite non-regular sequences such as {2n | n = 1, 2, 3,..}, { n2 | n = 1, 2, 3,..} and Fibonacci sequences can be generated in real-time by cellular automata with 1-bit inter-cell communications. In addition, twice real-time prime generation algorithm is also given.