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

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.

• Makoto Sakamoto
• Yasuo Uchida
• Makoto Nagatomo
• Takao Ito
• Tsunehiro Yoshinaga
• Satoshi Ikeda
• Masahiro Yokomichi
• Hiroshi Furutani

• computational complexity
• cooperating system
• finite automaton
• four-dimension
• hierarchy
• multihead.

[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.