Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

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

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

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

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.

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

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.