Consideration on the Recognizability of Three-Dimensional Patterns

Due to the advances in computer vision, robotics, and so forth, it has become increasingly apparent that the study of three-dimensional pattern processing should be very important. Thus, the study of three-dimensional automata as the computational model of three-dimensional information processing has been significant. During the past about thirty years, automata on a three-dimensional tape have been obtained. On the other hand, it is well-known that whether or not the pattern on a two-or three-dimensional rectangular tape is connected can be decided by a deterministic one-marker finite automata. As far as we know, however, it is unknown whether a similar result holds for recognition of the connectedness of patterns on three-dimensional arbitrarily shaped tape. In this paper, we deal with the recognizability of three-dimensional patterns, and consider the recognizability of three-dimensional connected tapes by alternating Turing machines and arbitrarily shaped tapes by k marker finite automata.