Four-dimensional multi-inkdot finite automata
Yasuo Uchida, Takao Ito, Hidenobu Okabe, Makoto Sakamoto, Hiroshi Furutani, Michio Kono · 2008
Abstract: During the past about thirty-five years, many automata on a two- or three-dimensional input tape have been proposed and a lot of properties of such automata have been obtained. On the other hand, we think that recently, due to the advances in computer animation, motion image processing, and so forth, it is very useful for analyzing computational complexity of multi-dimensional information processing to explicate the properties of four-dimensional automata, i.e., three-dimensional automata with the time axis. In this paper, we propose a four-dimensional multi-inkdot finite automaton and mainly investigate its recognizability of four-dimensional connected pictures. Moreover, we briefly investigate some basic accepting powers of four-dimensional multi-inkdot finite automata.