Some properties of three-dimensional synchronized alternating turing machines
Takao Ito, Makoto Sakamoto, Naoko Tomozoe, Kouichi Iihoshi, Hiroshi Furutani, Michio Kono, Tatsuhiro Tamaki, Katsushi Inoue · Annual Conference on Computers · 2006
The recent advances in motion image processing, robotics and so on prompted us to analyze computational complexity of three-dimensional pattern processing. Thus, the research of three-dimensional automata as a computational model of three-dimensional pattern processing has also been meaningful. From this viewpoint, we introduced a three-dimensional alternating Turing machine (3-ATM) operating in parallel. In this paper, we continue the investigations about 3-ATM's, introduce a three-dimensional synchronized alternating Turing machine (3-SATM), and investigate some properties of 3-SATM's whose input tapes are restricted to cubic ones. The main topics of this paper are: (1) hierarchies based on the number of processes of 3-SATM's, and (2) recognizability of connected pictures by 3-SATM's.