Makoto Sakamoto and Yasuo Uchida and Makoto Nagatomo and Takao Ito and Tsunehiro Yoshinaga and Satoshi Ikeda and Masahiro Yokomichi and Hiroshi Furutani
Hierarchies Based On the Number of Cooperating Systems of Finite Automata on FourDimensional Input Tapes
1707 - 1712
2012
6
12
International Journal of Mathematical and Computational Sciences
https://publications.waset.org/pdf/6351
https://publications.waset.org/vol/72
World Academy of Science, Engineering and Technology
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 twodimensional automata as a computational model of twodimensional 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 threedimensional 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 fourdimensional automata as a computasional model of fourdimensional pattern processing has been meaningful 819,21. This paper introduces a cooperating system of fourdimensional finite automata as one model of fourdimensional automata. A cooperating system of fourdimensional finite automata consists of a finite number of fourdimensional finite automata and a fourdimensional 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 sevenway fourdimensional finite automata. The sevenway fourdimensional finite automaton is an eightway fourdimensional finite automaton whose input head can move east, west, south, north, up, down, or in the future, but not in the past on a fourdimensional input tape.
Open Science Index 72, 2012