Path-bounded three-dimensional finite automata

被引：1

作者：

Sakamoto, Makoto ^{[1
]}

Fukuda, Masatsugu ^{[1
]}

Okatani, Satoshi ^{[1
]}

Ito, Takao ^{[2
]}

Furutani, Hiroshi ^{[1
]}

Kono, Michio ^{[1
]}

机构：

[1] Univ Miyazaki, Dept Comp Sci & Syst Engn, Miyazaki 8892192, Japan

[2] Ube Natl Coll Technol, Dept Business Adm, Ube, Yamaguchi, Japan

来源：

ARTIFICIAL LIFE AND ROBOTICS | 2008年 / 13卷 / 01期

关键词：

Computational complexity; Finite automaton; Multihead; Path-bounded; Three-dimension;

D O I：

10.1007/s10015-008-0521-9

中图分类号：

TP24 [机器人技术];

学科分类号：

080202 ; 1405 ;

摘要：

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.

引用

页码：54 / 57

页数：4

共 10 条

[1] CLASSES OF BOUNDED NONDETERMINISM [J].

DIAZ, J ;

TORAN, J .

MATHEMATICAL SYSTEMS THEORY, 1990, 23 (01) :21-32

[2] A separation of determinism, Las Vegas and nondeterminism for picture recognition [J].

Duris, P ;

Hromkovic, J ;

Inoue, K .

15TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2000, :214-228

[3]

Hromkovic J., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P551, DOI 10.1145/237814.238003

[4]

Hromkovic J, 2000, TR00076 ECCC

[5]

Inoue K, 1979, T IECE 79 2, V62, P65

[6]

Inoue S, 2003, 2006 CHUG SECT JOINT, P262

[7]

Inoue S, 2003, STUDY PATH BOUNDED M

[8]

Sakamoto M., 2007, TECHN M INF SYST IEE, P11

[9] A NOTE ON 3-DIMENSIONAL FINITE AUTOMATA [J].

TANIGUCHI, H ;

INOUE, K ;

TAKANAMI, I .

INFORMATION SCIENCES, 1982, 26 (01) :65-85

[10] K+1 HEADS ARE BETTER THAN K [J].

YAO, AC ;

RIVEST, RL .

JOURNAL OF THE ACM, 1978, 25 (02) :337-340

← 1 →