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

• Autorzy: Umeo H. , Kamikawa N.
• Języki publikacji: EN

Abstrakty

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 (CA_1-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.

Słowa kluczowe

EN

cellular automata; 1-bit inter-cell communication; real-time prime generation algorithm; sieve of Eratosthenes

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 58, nr 3,4
• Strony: 421--435
• Opis fizyczny: Bibliogr. 17 poz., wykr.

Twórcy

autor

Umeo H.

• Faculty of Information Science and Technology, Osaka Electro-Communication University, Neyagawa-shi, Hatsu-cho, 18-8, Osaka, 572-8530, Japan

autor

Kamikawa N.

• Noritsu Koki Co., Ltd. Wakayama-shi, Umehara, 579-1, Wakayama, 640-8550, Japan

Bibliografia

• [1] M. Arisawa: On the generation of integer series by the one-dimensional iterative arrays of finite state machines (in Japanese). The Trans. Of lECE, 71/8 Vol.54-C, No.8, pp.759-766, (1971).
• [2] C. R. Dyer: One-way bounded cellular automata. Information and Control, Vol.44, pp.261-281, (1980).
• [3] P. C. Fischer: Generation of primes by a one-dimensional real-time iterative array. J. of ACM, Vol. 12, No.3, pp.388-394, (1965).
• [4] I. Korec: Real-time generation of primes by a one-dimensional cellular automaton with 11 states. Proc. of 22nd Intent. Symp. on MFCS '97, Lecture Notes in Computer Science, 1295, pp.358-367, (1997).
• [5] J. Mazoyer: A minimal time solution to the firing squad synchronization problem with only one bit of information exchanged. Technical report of Ecole Normale Superieure de Lyon, No.89-03, pp.51, April, (1989).
• [6] J. Mazoyer: On optimal solutions to the firing squad synchronization problem. Theoretical Computer Science, 168, pp. 367-404, (1996).
• 17] J. Mazoyer and V. Terrier: Signals in one-dimensional cellular automata. Theoretical Computer Science, 217, pp.53-80, (1999).
• [8] A. R. Smith: Real-time language recognition by one-dimensional cellular automata. J. of Computer and System Sciences, 6, pp.233-253, (1972).
• [9] V. Terrier: On real-time one-way cellular array. Theoretical Computer Science, 141, pp.331-335, (1995).
• [10] V. Terrier: Language not recognizable in real lime by one-way cellular automata. Theoretical Computer Science, 156, pp.281-287, (1996).
• [11] S. L. Torre, M. Napoli and D. Párente: Synchronization of a line of identical processors at a given time. Fundamenta Informaticae 34(1-2), pp. 103-128.(1998).
• [12] H. Umeo: Cellular algorithms with 1-bit inter-cell communications. Proc. of MFCS'98 Satellite Workshop on Cellular Automata (Eds. T. Worsch and R. Vollmar), Interner Bericht 19/98, University of Karlsruhe, pp.93-104, (1998).
• [13] H. Umeo and M. Inada: A design of cellular algorithms for 1 -bit inter-cell communications. Proc. of the Fifth International Workshop on Parallel Image Analysis, IWPIA '97, pp.51-62, (1997).
• [14] H. Umeo: Linear-time recognition of connectivity of binary images on 1 -bit inter-cell communication cellular automaton. Parallel Computing, 21, pp.587-599, (2001).
• [15] H. Umeo and N. Kamikawa: A design of real-time non-regular sequence generation algorithms and their implementations on cellular automata with 1-bit inter-cell communications. Fundamenta Informaticae, 52. No. 1-3, pp.255-273, (2002).
• [16] H. Umeo and N. Kamikawa: An infinite prime sequence can be generated in real-time by a 1-bit inter-cell communication cellular automaton. Proc. of The Sixth Internal Conference on Developments in Language Theory, (Eds. M. Ito and M. Toyama), LNCS 2450, pp.339-348, (2002).
• [17] T. Worsch: Linear time language recognition on cellular automata with restricted communication, Proc. of LATIN2000¡Theoretical Informatics (Eds. G. H. Gonnet, D. Panario and A. Viola), LNCS 1776, pp.417-426, (2000).