Path-bounded three-dimensional finite automata |
| |
Authors: | Makoto Sakamoto Masatsugu Fukuda Satoshi Okatani Takao Ito Hiroshi Furutani Michio Kono |
| |
Affiliation: | (1) Department of Computer Science and Systems Engineering, University of Miyazaki, Miyazaki 889-2192, Japan;(2) Department of Business Administration, Ube National College of Technology, Ube, Japan |
| |
Abstract: | The comparative study of the computational powers of deterministic and nondeterministic computations is one of the central tasks in complexity theory. This paper investigates the computational power of nondeterministic computing devices with restricted nondeterminism. There are only few results measuring the computational power of restricted nondeterminism. In general, there are three possibilities to measure the amount of nondeterminism in computation. In this paper, we consider the possibility to count the number of different nondeterministic computation paths on any input. In particular, we deal with five-way three-dimensional finite automata with multiple input heads operating on three-dimensional input tapes. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008 |
| |
Keywords: | Computational complexity Finite automaton Multihead Path-bounded Three-dimension |
本文献已被 SpringerLink 等数据库收录! |
|