Four-Dimensional Homogeneous Systolic Pyramid Automata

Authors

  • Makoto Nagatomo Faculty of Engineering, University of Miyazaki, Miyazaki 889-2192, Japan.
  • Makoto Sakamoto Faculty of Engineering, University of Miyazaki, Miyazaki 889-2192, Japan.
  • Chongyang Sun Faculty of Engineering, University of Miyazaki, Miyazaki 889-2192, Japan.
  • Shinnosuke Yano Faculty of Engineering, University of Miyazaki, Miyazaki 889-2192, Japan.
  • Satoshi Ikeda Faculty of Engineering, University of Miyazaki, Miyazaki 889-2192, Japan.
  • Takao Ito Institute of Engineering, Hiroshima University, Higashi-Hiroshima, Hiroshima 739-8527, Japan.
  • Tsutomu Ito Institute of Engineering, Hiroshima University, Higashi-Hiroshima, Hiroshima 739-8527, Japan.
  • Yasuo Uchida Department of Business Administration, Ube National College of Technology, Ube, Yamaguchi 755-8555, Japan.
  • Tsunehiro Yoshinaga Department of Computer Science and Electronic Engineering, Tokuyama college of Technology, Shunan, Yamaguchi 745-8585, Japan.

Keywords:

Cellular Automaton, Diameter, Finite Automaton, Four-Dimension, Parallelism, Pattern Recognition, Real Time,

Abstract

Cellular automaton is famous as a kind of the parallel automaton. Cellular automata were investigated not only in the viewpoint of formal language theory, but also in the viewpoint of pattern recognition. Cellular automata can be classified into some types. A systolic pyramid automata is also one parallel model of various cellular automata. A homogeneous systolic pyramid automaton with four-dimensional layers (4-HSPA) is a pyramid stack of four-dimensional arrays of cells in which the bottom four-dimensional layer (level 0) has size an (a≥1), the next lowest 4(a-1), and so forth, the (a-1)st fourdimensional layer (level (a-1)) consisting of a single cell, called the root. Each cell means an identical finite-state machine. The input is accepted if and only if the root cell ever enters an accepting state. A 4-HSPA is said to be a real-time 4-HSPA if for every four-dimensional tape of size 4a (a≥1), it accepts the fourdimensional tape in time a-1. Moreover, a 1- way fourdimensional cellular automaton (1-4CA) can be considered as a natural extension of the 1-way two-dimensional cellular automaton to four-dimension. The initial configuration is accepted if the last special cell reaches a final state. A 1-4CA is said to be a real- time 1-4CA if when started with fourdimensional array of cells in nonquiescent state, the special cell reaches a final state. In this paper, we proposed a homogeneous systolic automaton with four-dimensional layers (4-HSPA), and investigated some properties of real-time 4-HSPA. Specifically, we first investigated the relationship between the accepting powers of real-time 4-HSPA’s and real-time 1-4CA’s. We next showed the recognizability of four-dimensional connected tapes by real-time 4-HSPA’s.

References

K.Culik II, J.Gruska and Salomaa, Sytolic trellis automata, Part I, International Journal of Computer Mathmatics, (1991), 55:pp.99-121.

C. Iwamoto, K.Inoue, and I.Takanami, Some Properties of Homogeneous Pyramid Automata, The IEICE Transactions on Information and Systems (Japanese Edition), (1990), J73-D-I(9) : 778-780.

C. Iwamoto, K. Inoue, and I. Takanami, Some Properties of Homogeneous Pyramid Automata, The IEICE Transactions on Information and Systems (Japanese Edition), (1990), J73-D-I(9) : 778-780.

K. Krithivasan and M. Mahajan, Systolic pyramid automata, cellular automata and array languages, International Journal of Pattern Recognition and Artificial Intelligence, (1989), 3(3 4):405-433.

M.Sakamoto, Three-Dimensional Alternating Turing Machines, Ph.D. Thesis, Yamaguchi University, (1999).

M.Sakamoto, H.Okabe, and K.Inoue, Some properties of fourdimansional finite automata, in 2002 Chugoku − Section Joint Convention Record of Insistes of Electrical and Information Engineerings, Japan, (2002), p.351.

M.Sakamoto, S.Nagami, K.Kono, A relationship between the accepting powers of three- dimentional layers, Trans. of SCI(Japan), Vol.17, No.10, (2004), pp.451-458.

M.Sakamoto, H.Okabe, S.Nagami, S.Taniguchi, T.Maki, Y.Nakama, M.Saito, M.Kono, and K.Inoue, A note on four-dimensional finite automata, WSEAS Transactions on Computers, Issue 5,Vol.3, (2004), pp.1651-1656.

M.Sakamoto, T.Ito, N.Tomozoe, and H.Furutani, Asurvey of threedimensional automata, The papers of Technical Meeting n Information Systems, IEE, Japan, IS-07-12, (2007), pp.11-17.

M.Sakamoto, T.Ito, H.Furutani, and M.Kono, Some accepting powers of three-dimensional parallel Turning machines, in 1st European Workshop on Artificial Life and Robotics, V ienna, Austria, (2007), pp.73-79.

M.Sakamoto, N.Tomozoe, H.Furutani, M.Kono, T.Ito, Y.Uchida, and H.Okabe, A survey of automata on three-dimensional input tapes, WSEAS Transactions on Computers, Issue 10,Vol.7, (2008), pp.1638-1647.

M.Sakamoto, T.Ito, H.Furutani, and M.Kono, Some accepting powers of three-dimensional parallel Turning machines, International Journal of Artificial Life and Robotics, Springer, Vol.13,No.1, (2008), pp.27-30.

M.Sakamoto, M.Fukuda, S.Okatani, T.Ito, H.Furutani, and M.Kono, Path-bouded Three- dimensional finite automata, International Journal of Artificial life and Robotics, Springer,Vol.13,No.1, (2008), pp.54-57.

M.Sakamoto, S.Okatani, M.Fukuda, T.Ito, and H.Furutani, and M.Kono, A relationship between Turning machines and finite automata on four-dimensional input tapes, International Journal of Artificial life and Robotics, Springer, Vol.13,No.1, (2008), pp.58-60.

M.Sakamoto, S.Okatani, K.Kajisa, M.Fukuda, T.Matsuawa, A.Taniue, T.Ito, H.Furutani, and M.Kono, Hierarchies based on the number of cooperating systems of three-dimensional finite automata,International Journal of Artificial Life and Robotics, Springer, Vo.4,No.3, (2009), pp.425-428.

M.Sakamoto, T.Matsukawa, R.Katamune, H.Furutani, M.Kono, S.Ikeda, T.Ito, Y.Uchida, and T.Yoshinaga, Four-dimensional synchronized alternating Turning machines, Proceedings of the 10th American Conference on Applied Mathmatics, Harvard University, Cambridge, USA, (2010), pp.195-200 (CD-ROM).

M.Sakamoto, R.Katamune, T.Matsukawa, H.Furutani, M.Kono, S.Ikeda, T.Ito, Y.Uchida, and T.Yoshinaga, Some result about hierarchy and recognizability of four-dimensional sychronized alternating Turning machines, Proceedings of the 10th American Conference on Applied Mathmatics, Harvard University, Cambridge, USA, (2010), pp.201-205(CD-ROM).

M.Sakamoto, T.Matsukawa, R.Katamune, H.Furutani, M.Kono, S.Ikeda, T.Ito, Y.Uchida, and T.Yoshinaga, Synchronized Alternating Turning Machines on Four-Dimensional In- put Tapes, WSES TRANSACTIONS on COMPUTERS,Issue 4,Vol.9, (2010), pp.319-328.

M.Sakamoto, R.Katamune, T.Matsukawa, H.Furutani, M.Kono, S.Ikeda, T.Ito, Y.Uchida, and T.Yoshinaga, Hardware Hierarchies and Recognizabilities of Four-Dimensional Synchronized Alternating Turning Machines, WSEAS TRANSACTIONS on COMPUTERS,Issue 4, (2010), pp.329-338.

M.Sakamoto, T.Ito, X.Qingquan, Y.Uchida, T.Yochinaga, M.Yokomichi, S.Ikeda, and H.Furutani, A Note on Three-dimensional probabilistic Finite Automata, The Seventeenth International Symposium on Artificial Life and Robotics 2012, Oita, Japan, (2012), pp.492- 495 (CD-ROM).

M.Sakamoto, Y.Uchida, T.Hamada, T.Ito, T.Yoshinaga, M.Yokomichi, S.Ikeda, and H.Furutani, A Relationship between the Accept- ing Powers of Nondeterministic Finite Automata and Probabilistic Finite Automata on Three-Dimensional Input Tapes, in the 2012 IEICE General Conference, Okayama University, (2012), p.4 (CD-ROM).

T. Toffoli and N. Margolus, Cellullar automaton machines − new environment for modeling, MIT Press, (1987).

J. Wiedermann, Parallel Turing machines, Technical Report RUU-CS-84-11, Department of Computer Science, University of Utrecht, the Netherlands, (1984).

Downloads

Published

2017-06-01

How to Cite

Nagatomo, M., Sakamoto, M., Sun, C., Yano, S., Ikeda, S., Ito, T., Ito, T., Uchida, Y., & Yoshinaga, T. (2017). Four-Dimensional Homogeneous Systolic Pyramid Automata. Journal of Telecommunication, Electronic and Computer Engineering (JTEC), 9(2-5), 75–77. Retrieved from https://jtec.utem.edu.my/jtec/article/view/2397

Issue

Vol. 9 No. 2-5: Circuit and System Advancement in Modern World IV

Section

Articles

License

TRANSFER OF COPYRIGHT AGREEMENT

The manuscript is herewith submitted for publication in the Journal of Telecommunication, Electronic and Computer Engineering (JTEC). It has not been published before, and it is not under consideration for publication in any other journals. It contains no material that is scandalous, obscene, libelous or otherwise contrary to law. When the manuscript is accepted for publication, I, as the author, hereby agree to transfer to JTEC, all rights including those pertaining to electronic forms and transmissions, under existing copyright laws, except for the following, which the author(s) specifically retain(s):

  1. All proprietary right other than copyright, such as patent rights
  2. The right to make further copies of all or part of the published article for my use in classroom teaching
  3. The right to reuse all or part of this manuscript in a compilation of my own works or in a textbook of which I am the author; and
  4. The right to make copies of the published work for internal distribution within the institution that employs me

I agree that copies made under these circumstances will continue to carry the copyright notice that appears in the original published work. I agree to inform my co-authors, if any, of the above terms. I certify that I have obtained written permission for the use of text, tables, and/or illustrations from any copyrighted source(s), and I agree to supply such written permission(s) to JTEC upon request.