A note on three-dimensional finite automata |
| |
Authors: | Hiroshi Taniguchi Katsushi Inoue Itsuo Takanami |
| |
Affiliation: | Department of Electronics, Faculty of Engineering, Yamaguchi University, Ube, 755 Japan |
| |
Abstract: | This paper investigates the relationships between the accepting powers of three-dimensional six-way finite automata (3-FA's) and three-dimensional five-way Turing machines (5WTM's), where the input tapes of these automata are restricted to cubic ones. A 3-FA (5WTM) can be considered as a natural extension of the two-dimensional four-way finite automaton (two-dimensional three-way Turing machine) to three dimensions. The main results are: (1) n2logn (n3) space is necessary and sufficient for deterministic 5WTM's to simulate deterministic (nondeterministic) 3-FA's; (2) n2 (n2) space is necessary and sufficient for nondeterministic 5WTM's to simulate deterministic (nondeterministic) 3-FA's. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |