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

• Autorzy: Umeo H. , Michisaka K. , Kamikawa N. , Kanazawa M.
• Języki publikacji: EN

Abstrakty

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

Słowa kluczowe

EN

cellular automata; one-bit inter-cell communication model; early bird problem; firing squad synchronization problem; integer sequence generation problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 78, nr 3
• Strony: 449--465
• Opis fizyczny: bibliogr. 27 poz., tab., wykr.

Twórcy

autor

Umeo H.

autor

Michisaka K.

autor

Kamikawa N.

autor

Kanazawa M.

• Faculty of Information Science and Technology, Osaka Electro-Communication University, Neyagawa-shi, Hatsu-cho, 18-8, Osaka, 572-8530, 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 IECE 71/8, Vol.54-C, No.8, pp. 759-766, (1971).
• [2] R. Balzer: An 8-state minimal time solution to the firing squad synchronization problem. Information and Control, vol. 10, pp. 22-42, (1967).
• [3] W. T. Beyer: Recognition of topological invariants by iterative arrays. Ph.D. Thesis, MIT, pp. 144, (1969).
• [4] H. Kleine-Büning: The early bird problem is unsolvable in a one-dimensional cellular space with 4 states. Acta Cybernetica, vol.6, pp.23-31, (1983).
• [5] B. Fay and M. Kutrib: The fault-tolerant early bird problem. IEICE Trans. on Information and Systems, vol.E87-D, No.3, pp.687-693, (2004).
• [6] 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).
• [7] E. Goto: A minimal time solution of the firing squad problem. Dittoed course notes for AppliedMathematics 298, Harvard University, pp. 52-59, (1962).
• [8] I. Korec: Real-time generation of primes by a one-dimensional cellular automaton with 11 states. Proc. Of 22nd Intern. Symp. on MFCS '97, Lecture Notes in Computer Science, 1295, pp. 358-367, (1997).
• [9] T. Legendi and E. Katona: A 5-state solution of the early bird problem in a one-dimensional cellular space. Acta Cybernetica, Vol.5, No.2, pp. 173-179, (1981).
• [10] T. Legendi and E. Katona: A solution of the early bird problem in an n-dimensional cellular space. Acta Cybernetica, Vol.7, No.1, pp. 81-87, (1985).
• [11] J. Mazoyer: A six-state minimal time solution to the firing squad synchronization problem. Theoretical Computer Science, vol. 50, pp.183-238, (1987).
• [12] J.Mazoyer: On optimal solutions to the firing squad synchronization problem. Theoretical Computer Science, vol. 168, pp. 367-404, (1996).
• [13] E. F. Moore: The firing squad synchronization problem. in Sequential Machines, Selected Papers (E. F. Moore ed.), Addison-Wesley, Reading MA., pp. 213-214, (1964).
• [14] J. Nishimura, T. Sogabe, and H. Umeo: A design of optimum-time firing squad synchronization algorithm on 1-bit cellular automaton. Proc. of The 8th International Symposium on Artificial Life and Robotics, pp.381-386, (2003).
• [15] P. Rosenstiehl, J. R. Fiksel, and A. Holliger: Intelligent graphs: Networks of finite automata capable of solving graph problems. In: Graph Theory and Computing (R. C. Reed Ed.), Academic Press, New York, pp.219-265, (1973).
• [16] I. Shinahr: Two- and three-dimensional firing squad synchronization problems. Information and Control, vol. 24, pp. 163-180, (1974).
• [17] H. Szwerinski: Time-optimum solution of the firing-squad-synchronization-problem for n-dimensional rectangles with the general at an arbitrary position. Theoretical Computer Science, vol.19, pp. 305-320, (1982).
• [18] S. L. Torre,M. Napoli, and M. Parente: A compositional approach to synchronize two dimensional networks of processors. Theoretical Informatics and Applications, 34 pp. 549-564, (2000).
• [19] H. Umeo: Linear-time recognition of connectivity of binary images on 1-bit inter-cell communication cellular automaton. Parallel Computing, 27, pp. 587-599, (2001).
• [20] H. Umeo,M. Hisaoka, K. Michisaka, K. Nishioka, and Masashi Maeda: Some new generalized synchronization algorithms and their implementations for large scale cellular automata. Proc. of The Third International Conference on UnconventionalModels of Computation(C. S. Calude, M. J. Dinneen and F. Pepper Eds.), pp. 276-286, (2002).
• [21] 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, 255-275, (2002).
• [22] H. Umeo and N. Kamikawa: Real-time generation of primes by a 1-bit-communication cellular automaton. Fundamenta Informaticae, 58(3, 4)421-435, (2003).
• [23] H. Umeo,M.Maeda, and N. Fujiwara: An efficient mapping scheme for embedding any one-dimensional firing squad synchronization algorithm onto two-dimensional arrays. Proc. of the 5th International Conference on Cellular Automata for Research and Industry, LNCS 2493, Springer-Verlag, pp. 69-81, (2000).
• [24] H. Umeo, M. Maeda, M. Hisaoka and M. Teraoka: A state-efficient mapping scheme for designing twodimensional firing squad synchronization algorithms. Fundamenta Informaticae, 74(4) 603-623, (2006).
• [25] R. Vollmar: On two modified problems of synchronization in cellular automata. Acta Cybernetica, Vol.3, No.4, pp. 293-300, (1978).
• [26] R. Vollmar: Algorithmen in Zellularautomaten. Teubner, pp. 192, Stuttgart, (1979).
• [27] A. Waksman: An optimum solution to the firing squad synchronization problem. Information and Control, vol. 9, pp. 66-78, (1966).