Hierarchies Based On the Number of Cooperating Systems of Finite Automata on Four-Dimensional Input Tapes

Authors: Makoto Sakamoto, Yasuo Uchida, Makoto Nagatomo, Takao Ito, Tsunehiro Yoshinaga, Satoshi Ikeda, Masahiro Yokomichi, Hiroshi Furutani

Abstract:

In theoretical computer science, the Turing machine has played a number of important roles in understanding and exploiting basic concepts and mechanisms in computing and information processing [20]. It is a simple mathematical model of computers [9]. After that, M.Blum and C.Hewitt first proposed two-dimensional automata as a computational model of two-dimensional pattern processing, and investigated their pattern recognition abilities in 1967 [7]. Since then, a lot of researchers in this field have been investigating many properties about automata on a two- or three-dimensional tape. On the other hand, the question of whether processing fourdimensional digital patterns is much more difficult than two- or threedimensional ones is of great interest from the theoretical and practical standpoints. Thus, the study of four-dimensional automata as a computasional model of four-dimensional pattern processing has been meaningful [8]-[19],[21]. This paper introduces a cooperating system of four-dimensional finite automata as one model of four-dimensional automata. A cooperating system of four-dimensional finite automata consists of a finite number of four-dimensional finite automata and a four-dimensional input tape where these finite automata work independently (in parallel). Those finite automata whose input heads scan the same cell of the input tape can communicate with each other, that is, every finite automaton is allowed to know the internal states of other finite automata on the same cell it is scanning at the moment. In this paper, we mainly investigate some accepting powers of a cooperating system of eight- or seven-way four-dimensional finite automata. The seven-way four-dimensional finite automaton is an eight-way four-dimensional finite automaton whose input head can move east, west, south, north, up, down, or in the fu-ture, but not in the past on a four-dimensional input tape.

Keywords: computational complexity, cooperating system, finite automaton, four-dimension, hierarchy, multihead.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062752

References:

[1] M.Blum and C.Hewitt, Automata on a two-dimensional tape, in IEEE Symp.Switching Automata Theory, pp.155-160, 1967.
[2] M.Blum and W.J.Sakoda, On the capability of finite automata in 2 and 3 dimensional space, in Processings of the 18th Annual Simp. on Foundations of Computer Science pp.147-161, 1977.
[3] M.Blum and K.Kozen, On the power of the compass, in Processings of the 19th Annual Simp. on Foundations of Computer Science, 1987.
[4] A.Hemmerling, Normed two-plane trapes for finite system of cooperating compass automata, in EIK 23(8/9), pp.453-470, 1978.
[5] K.Inoue, I.Takanami, and H.Taniguchi, Three-way two-dimensional simple multihead finite automata - hierarchical properties (in Japanese), IECE Jan. Trans.(D), pp.65-72, 1979.
[6] K.Inoue, I.Takanami, and H.Taniguchi, Three-way two-dimensional simple multihead finite automata - closure properties (in Japanese),IECE Jan. Trans.(D), pp.273-280, 1979.
[7] K.Inoue and I.Takanami, A survey of two-dimensional automata theory, Information Science, Elsevier, Vo1.55, pp.99-121, 1991.
[8] T.Ito, M.Sakamoto, M.Saito, K.Iihoshi, H.Furutani, M.Kono, and K.Inoue, Three-dimensional synchronized alternating Tuning machines, Proceedings of the 11th International Symposium on Artificial Life alternating and Robotics, Oita, Japan, OS9-4, 2006.
[9] T.Ito and M.Sakamoto, Some accepting powers of three-dimensional synchronized alternating Turing machines, Journal of Engineering, Computing and Architecture,Scientific Journals International, Issue 1, Vol.1, pp.1-11, 2007.
[10] H.Okabe, S.Taniguchi, T.Makino, S.Nogami, Y.Nakama, M.Sakamoto, and K.Inoue, Computation for motion image processing by 4-dimensional alternating Turing machines, Proceedings of the 7th World Multiconference on SCI,Orlando,USA, pp241-246, 2003.
[11] M.Sakamoto, K.Inoue, and I.Takanami, A note on three-dimensional alternating Turing machines with space smaller than logm, Information Sciences, Elsevier, Vol.72, p.225-249, 1993.
[12] M.Sakamoto, K.Inoue, and I.Takanami, Three-dimensionally fully space constructible functions, IEICE Transactions on Information and Systems, Vol.E77-D, No.6, pp.723-725, 1994.
[13] M.Sakamoto, A.Ito, K.Inoue, and I.Takanami, Simulation of threedimensional one-marker automata by five-way Turing machines, Information Sciences, Elsevier, Vol.77, pp.77-99, 1994.
[14] M.Sakamoto and K.Inoue, Three-dimensional alternating Turing machines with only universal states, Information SciencesÔÇöInformation and Computer Sciences, Elsevier, Vol.95, pp.155-190, 1996.
[15] M.Sakamoto, T.Okazaki, and K.Inoue, Three-dimensional multicounter automata, Proceedings of the 6th International Workshop on Parallel Image Processing and AnalysisÔÇöTheory and Applications,Madras, India, pp.267-280,1999.
[16] M.Sakamoto, Three-dimensional alternating Turing machines, Ph.D.Thesis, Yamaguchi University, 1999.
[17] M.Sakamoto, H.Okabe, S.Nogami, S.Taniguchi, T.Makino, Y.Nakama, M.Saito, M.Kono, and K.Inoue, A note on four-dimensional finite automata, WSEAS TRANSACTIONS on COMPUTERS, Issue 5, Vol.3, pp.1651-1656, 2004.
[18] 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, Issue10, Vol.7, pp.1638-1647, 2008.
[19] M.Sakamoto, S.Okatani, K.Kajisa, M.Fukuda, T,Matsukawa, 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 AROB, Vol.4, No.3, pp.425-428, 2009.
[20] A.M.Turing, On computable number, with an application to the Entscheidungsproblem, Proceedings of the London Math. Soc., Vol.2, No.42, pp.230-265, 1936.
[21] Y.Uchida, T.Ito, H.Okabe, M.Sakamoto, H.Furutani, and M.Kono, Fourdimensional multi-inkdot finite automata, WSEAS TRANSACTIONS on COMPUTERS, Issue 9, Vol.7, pp.1437-1446, 2008.
[22] Y.Wang, K.Inoue, and I.Takanami, Some properties of cooperating systems of one-way finite automata (in Japanese), IECE Jan. Trans.(D-I) No.7, pp.391-399, 1992.