Some results about hierarchy and recognizability of four-dimensional synchronized alternating turing machines
Makoto Sakamoto, Ryoju Katamune, Tomoya Matsukawa, Hiroshi Furutani, Michio Kono, Satoshi Ikeda, Takao Ito, Yasuo Uchida, Tsunehiro Yoshinaga · AMERICAN-MATH'10 Proceedings of the 2010 American conference on Applied mathematics · 2010
The recent advances in computer animation, motion image processing, robotics and so on prompted us to analyze computational complexity of four-dimensional pattern processing. Thus, the research of four-dimensional automata as a computational model of four-dimensional pattern processing has also been meaningful. From this viewpoint, we introduced a four-dimensional alternating Turing machine (4-ATM) operating in parallel. In this paper, we continue the investigations about 4-ATM's, deal with a four-dimensional synchronized alternating Turing machine (4-SATM), and investigate some properties of 4-SATM's which each sidelength of each input tape is equivalent. The main topics of this paper are: (1) hierarchies based on the number of processes of 4-SATM's, and (2) recognizability of connected pictures by 4-SATM's.